interface/wx/hashmap.h

   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