docs/latex/wx/hashmap.tex

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