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 modeled 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 a 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 a 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 a 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 a 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 \twocolitem{wxHashMap::Insert\_Result}{The return value for
 139 \helpref{insert()}{wxhashmapinsert}}
 140 \end{twocollist}
 141
 142 \wxheading{Iterators}
 143
 144 An iterator is similar to a pointer, and so you can use the usual pointer
 145 operations: {\tt ++it} ( and {\tt it++} ) to move to the next element,
 146 {\tt *it} to access the element pointed to, {\tt it->first}
 147 ( {\tt it->second} ) to access the key ( value )
 148 of the element pointed to. Hash maps provide forward only iterators, this
 149 means that you can't use {\tt --it}, {\tt it + 3}, {\tt it1 - it2}.
 150
 151 \wxheading{Include files}
 152
 153 <wx/hashmap.h>
 154
 155 \latexignore{\rtfignore{\wxheading{Members}}}
 156
 157 \membersection{wxHashMap::wxHashMap}\label{wxhashmapctor}
 158
 159 \func{}{wxHashMap}{\param{size\_type}{ size = 10}}
 160
 161 The size parameter is just a hint, the table will resize automatically
 162 to preserve performance.
 163
 164 \func{}{wxHashMap}{\param{const wxHashMap\&}{ map}}
 165
 166 Copy constructor.
 167
 168 \membersection{wxHashMap::begin}\label{wxhashmapbegin}
 169
 170 \constfunc{const\_iterator}{begin}{}
 171
 172 \func{iterator}{begin}{}
 173
 174 Returns an iterator pointing at the first element of the hash map.
 175 Please remember that hash maps do not guarantee ordering.
 176
 177 \membersection{wxHashMap::clear}\label{wxhashmapclear}
 178
 179 \func{void}{clear}{}
 180
 181 Removes all elements from the hash map.
 182
 183 \membersection{wxHashMap::count}\label{wxhashmapcount}
 184
 185 \constfunc{size\_type}{count}{\param{const key\_type\&}{ key}}
 186
 187 Counts the number of elements with the given key present in the map.
 188 This function returns only 0 or 1.
 189
 190 \membersection{wxHashMap::empty}\label{wxhashmapempty}
 191
 192 \constfunc{bool}{empty}{}
 193
 194 Returns true if the hash map does not contain any elements, false otherwise.
 195
 196 \membersection{wxHashMap::end}\label{wxhashmapend}
 197
 198 \constfunc{const\_iterator}{end}{}
 199
 200 \func{iterator}{end}{}
 201
 202 Returns an iterator pointing at the one-after-the-last element of the hash map.
 203 Please remember that hash maps do not guarantee ordering.
 204
 205 \membersection{wxHashMap::erase}\label{wxhashmaperase}
 206
 207 \func{size\_type}{erase}{\param{const key\_type\&}{ key}}
 208
 209 Erases the element with the given key, and returns the number of elements
 210 erased (either 0 or 1).
 211
 212 \func{void}{erase}{\param{iterator}{ it}}
 213
 214 \func{void}{erase}{\param{const\_iterator}{ it}}
 215
 216 Erases the element pointed to by the iterator. After the deletion
 217 the iterator is no longer valid and must not be used.
 218
 219 \membersection{wxHashMap::find}\label{wxhashmapfind}
 220
 221 \func{iterator}{find}{\param{const key\_type\&}{ key}}
 222
 223 \constfunc{const\_iterator}{find}{\param{const key\_type\&}{ key}}
 224
 225 If an element with the given key is present, the functions returns
 226 an iterator pointing at that element, otherwise an invalid iterator
 227 is returned (i.e. hashmap.find( non\_existent\_key ) == hashmap.end()).
 228
 229 \membersection{wxHashMap::insert}\label{wxhashmapinsert}
 230
 231 \func{Insert\_Result}{insert}{\param{const value\_type\&}{ v}}
 232
 233 Inserts the given value in the hash map. The return value is
 234 equivalent to a \texttt{std::pair<wxHashMap::iterator, bool>};
 235 the iterator points to the inserted element, the boolean value
 236 is \texttt{true} if \texttt{v} was actually inserted.
 237
 238 \membersection{wxHashMap::operator[]}\label{wxhashmapbracket}
 239
 240 \func{mapped\_type\&}{operator[]}{\param{const key\_type\&}{ key}}
 241
 242 Use the key as an array subscript. The only difference is that if the
 243 given key is not present in the hash map, an element with the
 244 default {\tt value\_type()} is inserted in the table.
 245
 246 \membersection{wxHashMap::size}\label{wxhashmapsize}
 247
 248 \constfunc{size\_type}{size}{}
 249
 250 Returns the number of elements in the map.
 251