]>
Commit | Line | Data |
---|---|---|
23324ae1 FM |
1 | ///////////////////////////////////////////////////////////////////////////// |
2 | // Name: hashmap.h | |
e54c96f1 | 3 | // Purpose: interface of wxHashMap |
23324ae1 FM |
4 | // Author: wxWidgets team |
5 | // RCS-ID: $Id$ | |
526954c5 | 6 | // Licence: wxWindows licence |
23324ae1 FM |
7 | ///////////////////////////////////////////////////////////////////////////// |
8 | ||
9 | /** | |
10 | @class wxHashMap | |
7c913512 | 11 | |
23324ae1 | 12 | This is a simple, type-safe, and reasonably efficient hash map class, |
9cc56d1f | 13 | whose interface is a subset of the interface of STL containers. |
8cddee2d | 14 | In particular, the interface is modelled after std::map, and the various, |
730b772b | 15 | non-standard, std::hash_map (http://www.cppreference.com/wiki/stl/map/start). |
7c913512 | 16 | |
9cc56d1f FM |
17 | Example: |
18 | @code | |
19 | class MyClass { ... }; | |
20 | ||
21 | // declare a hash map with string keys and int values | |
22 | WX_DECLARE_STRING_HASH_MAP( int, MyHash5 ); | |
23 | // same, with int keys and MyClass* values | |
24 | WX_DECLARE_HASH_MAP( int, MyClass*, wxIntegerHash, wxIntegerEqual, MyHash1 ); | |
25 | // same, with wxString keys and int values | |
26 | WX_DECLARE_STRING_HASH_MAP( int, MyHash3 ); | |
27 | // same, with wxString keys and values | |
28 | WX_DECLARE_STRING_HASH_MAP( wxString, MyHash2 ); | |
29 | ||
30 | MyHash1 h1; | |
31 | MyHash2 h2; | |
32 | ||
33 | // store and retrieve values | |
34 | h1[1] = new MyClass( 1 ); | |
35 | h1[10000000] = NULL; | |
36 | h1[50000] = new MyClass( 2 ); | |
37 | h2["Bill"] = "ABC"; | |
38 | wxString tmp = h2["Bill"]; | |
39 | // since element with key "Joe" is not present, this will return | |
40 | // the default value, which is an empty string in the case of wxString | |
41 | MyClass tmp2 = h2["Joe"]; | |
42 | ||
43 | // iterate over all the elements in the class | |
44 | MyHash2::iterator it; | |
45 | for( it = h2.begin(); it != h2.end(); ++it ) | |
46 | { | |
47 | wxString key = it->first, value = it->second; | |
48 | // do something useful with key and value | |
49 | } | |
50 | @endcode | |
51 | ||
52 | ||
53 | @section hashmap_declaringnew Declaring new hash table types | |
54 | ||
55 | @code | |
56 | WX_DECLARE_STRING_HASH_MAP( VALUE_T, // type of the values | |
57 | CLASSNAME ); // name of the class | |
58 | @endcode | |
59 | Declares a hash map class named CLASSNAME, with wxString keys and VALUE_T values. | |
60 | ||
61 | @code | |
62 | WX_DECLARE_VOIDPTR_HASH_MAP( VALUE_T, // type of the values | |
63 | CLASSNAME ); // name of the class | |
64 | @endcode | |
65 | Declares a hash map class named CLASSNAME, with void* keys and VALUE_T values. | |
66 | ||
67 | @code | |
68 | WX_DECLARE_HASH_MAP( KEY_T, // type of the keys | |
69 | VALUE_T, // type of the values | |
70 | HASH_T, // hasher | |
71 | KEY_EQ_T, // key equality predicate | |
72 | CLASSNAME); // name of the class | |
73 | @endcode | |
74 | The HASH_T and KEY_EQ_T are the types used for the hashing function and | |
75 | key comparison. wxWidgets provides three predefined hashing functions: | |
730b772b FM |
76 | @c wxIntegerHash for integer types ( int, long, short, and their unsigned counterparts ), |
77 | @c wxStringHash for strings ( wxString, wxChar*, char* ), and @c wxPointerHash for | |
9cc56d1f | 78 | any kind of pointer. |
730b772b FM |
79 | Similarly three equality predicates: @c wxIntegerEqual, @c wxStringEqual, |
80 | @c wxPointerEqual are provided. | |
9cc56d1f FM |
81 | Using this you could declare a hash map mapping int values to wxString like this: |
82 | ||
83 | @code | |
84 | WX_DECLARE_HASH_MAP( int, | |
85 | wxString, | |
7a7fa93b VZ |
86 | wxIntegerHash, |
87 | wxIntegerEqual, | |
9cc56d1f FM |
88 | MyHash ); |
89 | ||
90 | // using an user-defined class for keys | |
91 | class MyKey { ... }; | |
92 | ||
93 | // hashing function | |
94 | class MyKeyHash | |
95 | { | |
96 | public: | |
97 | MyKeyHash() { } | |
98 | ||
99 | unsigned long operator()( const MyKey& k ) const | |
100 | { | |
101 | // compute the hash | |
102 | } | |
103 | ||
104 | MyKeyHash& operator=(const MyKeyHash&) { return *this; } | |
105 | }; | |
106 | ||
107 | // comparison operator | |
108 | class MyKeyEqual | |
109 | { | |
110 | public: | |
111 | MyKeyEqual() { } | |
112 | bool operator()( const MyKey& a, const MyKey& b ) const | |
113 | { | |
114 | // compare for equality | |
115 | } | |
116 | ||
117 | MyKeyEqual& operator=(const MyKeyEqual&) { return *this; } | |
118 | }; | |
119 | ||
120 | WX_DECLARE_HASH_MAP( MyKey, // type of the keys | |
121 | SOME_TYPE, // any type you like | |
7a7fa93b VZ |
122 | MyKeyHash, // hasher |
123 | MyKeyEqual, // key equality predicate | |
9cc56d1f FM |
124 | CLASSNAME); // name of the class |
125 | @endcode | |
126 | ||
127 | ||
128 | @section hashmap_types Types | |
129 | ||
130 | In the documentation below you should replace wxHashMap with the name you used | |
131 | in the class declaration. | |
132 | ||
133 | - wxHashMap::key_type: Type of the hash keys. | |
134 | - wxHashMap::mapped_type: Type of the values stored in the hash map. | |
135 | - wxHashMap::value_type: Equivalent to struct { key_type first; mapped_type second }. | |
136 | - wxHashMap::iterator: Used to enumerate all the elements in a hash map; | |
137 | it is similar to a value_type*. | |
138 | - wxHashMap::const_iterator: Used to enumerate all the elements in a constant | |
139 | hash map; it is similar to a const value_type*. | |
140 | - wxHashMap::size_type: Used for sizes. | |
141 | - wxHashMap::Insert_Result: The return value for insert(). | |
142 | ||
143 | ||
144 | @section hashmap_iter Iterators | |
145 | ||
146 | An iterator is similar to a pointer, and so you can use the usual pointer operations: | |
147 | ++it ( and it++ ) to move to the next element, *it to access the element pointed to, | |
148 | it->first ( it->second ) to access the key ( value ) of the element pointed to. | |
149 | ||
150 | Hash maps provide forward only iterators, this means that you can't use --it, | |
151 | it + 3, it1 - it2. | |
152 | ||
153 | ||
730b772b FM |
154 | @section hashmap_predef Predefined hashmap types |
155 | ||
156 | wxWidgets defines the following hashmap types: | |
157 | - wxLongToLongHashMap (uses long both for keys and values) | |
158 | - wxStringToStringHashMap (uses wxString both for keys and values) | |
159 | ||
160 | ||
23324ae1 | 161 | @library{wxbase} |
9cc56d1f | 162 | @category{containers} |
23324ae1 | 163 | */ |
7c913512 | 164 | class wxHashMap |
23324ae1 FM |
165 | { |
166 | public: | |
23324ae1 | 167 | /** |
9cc56d1f FM |
168 | The size parameter is just a hint, the table will resize automatically |
169 | to preserve performance. | |
23324ae1 FM |
170 | */ |
171 | wxHashMap(size_type size = 10); | |
9cc56d1f FM |
172 | |
173 | /** | |
174 | Copy constructor. | |
175 | */ | |
7c913512 | 176 | wxHashMap(const wxHashMap& map); |
23324ae1 FM |
177 | |
178 | //@{ | |
179 | /** | |
180 | Returns an iterator pointing at the first element of the hash map. | |
181 | Please remember that hash maps do not guarantee ordering. | |
182 | */ | |
9cc56d1f FM |
183 | const_iterator begin() const; |
184 | iterator begin(); | |
23324ae1 FM |
185 | //@} |
186 | ||
187 | /** | |
188 | Removes all elements from the hash map. | |
189 | */ | |
190 | void clear(); | |
191 | ||
192 | /** | |
193 | Counts the number of elements with the given key present in the map. | |
194 | This function returns only 0 or 1. | |
195 | */ | |
328f5751 | 196 | size_type count(const key_type& key) const; |
23324ae1 FM |
197 | |
198 | /** | |
199 | Returns @true if the hash map does not contain any elements, @false otherwise. | |
200 | */ | |
328f5751 | 201 | bool empty() const; |
23324ae1 FM |
202 | |
203 | //@{ | |
204 | /** | |
205 | Returns an iterator pointing at the one-after-the-last element of the hash map. | |
206 | Please remember that hash maps do not guarantee ordering. | |
207 | */ | |
9cc56d1f FM |
208 | const_iterator end() const; |
209 | iterator end(); | |
23324ae1 FM |
210 | //@} |
211 | ||
212 | //@{ | |
9cc56d1f FM |
213 | /** |
214 | Erases the element with the given key, and returns the number of elements | |
215 | erased (either 0 or 1). | |
216 | */ | |
217 | size_type erase(const key_type& key); | |
218 | ||
23324ae1 FM |
219 | /** |
220 | Erases the element pointed to by the iterator. After the deletion | |
221 | the iterator is no longer valid and must not be used. | |
222 | */ | |
7c913512 FM |
223 | void erase(iterator it); |
224 | void erase(const_iterator it); | |
23324ae1 FM |
225 | //@} |
226 | ||
227 | //@{ | |
228 | /** | |
9cc56d1f FM |
229 | If an element with the given key is present, the functions returns an |
230 | iterator pointing at that element, otherwise an invalid iterator is | |
9e89b438 BP |
231 | returned. |
232 | ||
9cc56d1f FM |
233 | @code |
234 | hashmap.find( non_existent_key ) == hashmap.end() | |
235 | @endcode | |
23324ae1 | 236 | */ |
328f5751 FM |
237 | iterator find(const key_type& key) const; |
238 | const_iterator find(const key_type& key) const; | |
23324ae1 FM |
239 | //@} |
240 | ||
241 | /** | |
9cc56d1f FM |
242 | Inserts the given value in the hash map. |
243 | The return value is equivalent to a | |
244 | @code std::pair<wxHashMap::iterator, bool> @endcode | |
245 | The iterator points to the inserted element, the boolean value is @true | |
246 | if @a v was actually inserted. | |
23324ae1 FM |
247 | */ |
248 | Insert_Result insert(const value_type& v); | |
249 | ||
250 | /** | |
9cc56d1f FM |
251 | Use the key as an array subscript. |
252 | The only difference is that if the given key is not present in the hash map, | |
253 | an element with the default @c value_type() is inserted in the table. | |
23324ae1 FM |
254 | */ |
255 | mapped_type operator[](const key_type& key); | |
256 | ||
257 | /** | |
258 | Returns the number of elements in the map. | |
259 | */ | |
328f5751 | 260 | size_type size() const; |
23324ae1 | 261 | }; |
e54c96f1 | 262 |