interface/wx/hashmap.h

   1 /////////////////////////////////////////////////////////////////////////////
   2 // Name:        hashmap.h
   3 // Purpose:     interface of wxHashMap
   4 // Author:      wxWidgets team
   5 // RCS-ID:      $Id$
   6 // Licence:     wxWindows license
   7 /////////////////////////////////////////////////////////////////////////////
   8
   9 /**
  10     @class wxHashMap
  11
  12     This is a simple, type-safe, and reasonably efficient hash map class,
  13     whose interface is a subset of the interface of STL containers.
  14     In particular, the interface is modeled after std::map, and the various,
  15     non-standard, std::hash_map (http://www.cppreference.com/wiki/stl/map/start).
  16
  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:
  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
  78     any kind of pointer.
  79     Similarly three equality predicates: @c wxIntegerEqual, @c wxStringEqual,
  80     @c wxPointerEqual are provided.
  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,
  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             {
 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
 122                          MyKeyHash,  // hasher
 123                          MyKeyEqual, // key equality predicate
 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
 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
 161     @library{wxbase}
 162     @category{containers}
 163 */
 164 class wxHashMap
 165 {
 166 public:
 167     /**
 168         The size parameter is just a hint, the table will resize automatically
 169         to preserve performance.
 170     */
 171     wxHashMap(size_type size = 10);
 172
 173     /**
 174         Copy constructor.
 175     */
 176     wxHashMap(const wxHashMap& map);
 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     */
 183     const_iterator begin() const;
 184     iterator begin();
 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     */
 196     size_type count(const key_type& key) const;
 197
 198     /**
 199         Returns @true if the hash map does not contain any elements, @false otherwise.
 200     */
 201     bool empty() const;
 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     */
 208     const_iterator end() const;
 209     iterator end();
 210     //@}
 211
 212     //@{
 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
 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     */
 223     void erase(iterator it);
 224     void erase(const_iterator it);
 225     //@}
 226
 227     //@{
 228     /**
 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
 231         returned.
 232
 233         @code
 234             hashmap.find( non_existent_key ) == hashmap.end()
 235         @endcode
 236     */
 237     iterator find(const key_type& key) const;
 238     const_iterator find(const key_type& key) const;
 239     //@}
 240
 241     /**
 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.
 247     */
 248     Insert_Result insert(const value_type& v);
 249
 250     /**
 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.
 254     */
 255     mapped_type operator[](const key_type& key);
 256
 257     /**
 258         Returns the number of elements in the map.
 259     */
 260     size_type size() const;
 261 };
 262