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