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