containers/hash.hpp
1: #ifndef STLPLUS_HASH
2: #define STLPLUS_HASH
3: ////////////////////////////////////////////////////////////////////////////////
4:
5: // Author: Andy Rushton
6: // Copyright: (c) Southampton University 1999-2004
7: // (c) Andy Rushton 2004 onwards
8: // License: BSD License, see ../docs/license.html
9:
10: // A chained hash table using STL semantics
11:
12: ////////////////////////////////////////////////////////////////////////////////
13: #include "containers_fixes.hpp"
14: #include "exceptions.hpp"
15: #include "safe_iterator.hpp"
16: #include <map>
17: #include <iostream>
18:
19: namespace stlplus
20: {
21:
22: ////////////////////////////////////////////////////////////////////////////////
23: // internals
24:
25: template<typename K, typename T, class H, class E> class hash;
26: template<typename K, typename T, class H, class E> class hash_element;
27:
28: ////////////////////////////////////////////////////////////////////////////////
29: // iterator class
30:
31: template<typename K, typename T, class H, class E, typename V>
32: class hash_iterator : public safe_iterator<hash<K,T,H,E>,hash_element<K,T,H,E> >
33: {
34: public:
35: friend class hash<K,T,H,E>;
36:
37: // local type definitions
38: // an iterator points to a value whilst a const_iterator points to a const value
39: typedef V value_type;
40: typedef hash_iterator<K,T,H,E,std::pair<const K,T> > iterator;
41: typedef hash_iterator<K,T,H,E,const std::pair<const K,T> > const_iterator;
42: typedef hash_iterator<K,T,H,E,V> this_iterator;
43: typedef V& reference;
44: typedef V* pointer;
45:
46: // constructor to create a null iterator - you must assign a valid value to this iterator before using it
47: // any attempt to dereference or use a null iterator is an error
48: // the only valid thing you can do is assign an iterator to it
49: hash_iterator(void);
50: ~hash_iterator(void);
51:
52: // Type conversion methods allow const_iterator and iterator to be converted
53: // convert an iterator/const_iterator to a const_iterator
54: const_iterator constify(void) const;
55: // convert an iterator/const_iterator to an iterator
56: iterator deconstify(void) const;
57:
58: // increment operators used to step through the set of all values in a hash
59: // it is only legal to increment a valid iterator
60: // there's no decrement - I've only implemented this as a unidirectional iterator
61: // pre-increment
62: this_iterator& operator ++ (void)
63: throw(null_dereference,end_dereference);
64: // post-increment
65: this_iterator operator ++ (int)
66: throw(null_dereference,end_dereference);
67:
68: // test useful for testing whether iteration has completed
69: bool operator == (const this_iterator& r) const;
70: bool operator != (const this_iterator& r) const;
71: bool operator < (const this_iterator& r) const;
72:
73: // access the value - a const_iterator gives you a const value, an iterator a non-const value
74: // it is illegal to dereference an invalid (i.e. null or end) iterator
75: reference operator*(void) const
76: throw(null_dereference,end_dereference);
77: pointer operator->(void) const
78: throw(null_dereference,end_dereference);
79:
80: private:
81: friend class hash_element<K,T,H,E>;
82:
83: // constructor used by hash to create a non-null iterator
84: // you cannot create a valid iterator except by calling a hash method that returns one
85: explicit hash_iterator(hash_element<K,T,H,E>* element);
86: // constructor used to create an end iterator
87: explicit hash_iterator(const hash<K,T,H,E>* owner);
88: // used to create an alias of an iterator
89: explicit hash_iterator(const safe_iterator<hash<K,T,H,E>, hash_element<K,T,H,E> >& iterator);
90: };
91:
92: ////////////////////////////////////////////////////////////////////////////////
93: // Hash class
94: // K = key type
95: // T = value type
96: // H = hash function object with the profile 'unsigned H(const K&)'
97: // E = equal function object with profile 'bool E(const K&, const K&)' defaults to equal_to which in turn calls '=='
98:
99: template<typename K, typename T, class H, class E = std::equal_to<K> >
100: class hash
101: {
102: public:
103: typedef unsigned size_type;
104: typedef K key_type;
105: typedef T data_type;
106: typedef T mapped_type;
107: typedef std::pair<const K, T> value_type;
108: typedef hash_iterator<K,T,H,E,value_type> iterator;
109: typedef hash_iterator<K,T,H,E,const value_type> const_iterator;
110:
111: // construct a hash table with specified number of bins
112: // the default 0 bins means leave it to the table to decide
113: // specifying 0 bins also enables auto-rehashing, otherwise auto-rehashing defaults off
114: hash(unsigned bins = 0);
115: ~hash(void);
116:
117: // copy and equality copy the data elements but not the size of the copied table
118: hash(const hash&);
119: hash& operator = (const hash&);
120:
121: // test for an empty table and for the size of a table
122: // efficient because the size is stored separately from the table contents
123: bool empty(void) const;
124: unsigned size(void) const;
125:
126: // test for equality - two hashes are equal if they contain equal values
127: bool operator == (const hash&) const;
128: bool operator != (const hash&) const;
129:
130: // switch auto-rehash on
131: void auto_rehash(void);
132: // switch auto-rehash off
133: void manual_rehash(void);
134: // force a rehash now
135: // default of 0 means implement built-in size calculation for rehashing (recommended - it doubles the number of bins)
136: void rehash(unsigned bins = 0);
137: // test the loading ratio, which is the size divided by the number of bins
138: // use this if you are doing your own rehashing
139: // the recommendation is to double the bins when the loading exceeds 0.5 which is what auto-rehashing does
140: float loading(void) const;
141:
142: // test for the presence of a key
143: bool present(const K& key) const;
144: // provide map equivalent key count function (0 or 1, as not a multimap)
145: size_type count(const K& key) const;
146:
147: // insert a new key/data pair - replaces any previous value for this key
148: iterator insert(const K& key, const T& data);
149: // insert a copy of the pair into the table (std::map compatible)
150: std::pair<iterator, bool> insert(const value_type& value);
151: // insert a new key and return the iterator so that the data can be filled in
152: iterator insert(const K& key);
153:
154: // remove a key/data pair from the hash table
155: // as in map, this returns the number of elements erased
156: size_type erase(const K& key);
157: // remove an element from the hash table using an iterator
158: // as in map, returns an iterator to the next element
159: iterator erase(iterator it);
160: // remove all elements from the hash table
161: void erase(void);
162: // map equivalent of above
163: void clear(void);
164:
165: // find a key and return an iterator to it
166: // The iterator is like a pointer to a pair<const K,T>
167: // end() is returned if the find fails
168: const_iterator find(const K& key) const;
169: iterator find(const K& key);
170:
171: // returns the data corresponding to the key
172: // const version is used for const hashes and cannot change the hash, so failure causes an exception
173: // non-const version is for non-const hashes and is like map - it creates a new key/data pair if find fails
174: const T& operator[] (const K& key) const throw(std::out_of_range);
175: T& operator[] (const K& key);
176:
177: // iterators allow the hash table to be traversed
178: // iterators remain valid unless an item is removed or unless a rehash happens
179: const_iterator begin(void) const;
180: iterator begin(void);
181: const_iterator end(void) const;
182: iterator end(void);
183:
184: // diagnostic report shows the number of items in each bin so can be used
185: // to diagnose effectiveness of hash functions
186: void debug_report(std::ostream&) const;
187:
188: // internals
189: private:
190: friend class hash_element<K,T,H,E>;
191: friend class hash_iterator<K,T,H,E,std::pair<const K,T> >;
192: friend class hash_iterator<K,T,H,E,const std::pair<const K,T> >;
193:
194: unsigned m_rehash;
195: unsigned m_bins;
196: unsigned m_size;
197: hash_element<K,T,H,E>** m_values;
198: };
199:
200: ////////////////////////////////////////////////////////////////////////////////
201:
202: } // end namespace stlplus
203:
204: #include "hash.tpp"
205: #endif