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.
  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     wxIntegerHash for integer types ( int, long, short, and their unsigned counterparts ),
  77     wxStringHash for strings ( wxString, wxChar*, char* ), and wxPointerHash for
  78     any kind of pointer.
  79     Similarly three equality predicates: wxIntegerEqual, wxStringEqual,
  80     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     @library{wxbase}
 155     @category{containers}
 156 */
 157 class wxHashMap
 158 {
 159 public:
 160     /**
 161         The size parameter is just a hint, the table will resize automatically
 162         to preserve performance.
 163     */
 164     wxHashMap(size_type size = 10);
 165
 166     /**
 167         Copy constructor.
 168     */
 169     wxHashMap(const wxHashMap& map);
 170
 171     //@{
 172     /**
 173         Returns an iterator pointing at the first element of the hash map.
 174         Please remember that hash maps do not guarantee ordering.
 175     */
 176     const_iterator begin() const;
 177     iterator begin();
 178     //@}
 179
 180     /**
 181         Removes all elements from the hash map.
 182     */
 183     void clear();
 184
 185     /**
 186         Counts the number of elements with the given key present in the map.
 187         This function returns only 0 or 1.
 188     */
 189     size_type count(const key_type& key) const;
 190
 191     /**
 192         Returns @true if the hash map does not contain any elements, @false otherwise.
 193     */
 194     bool empty() const;
 195
 196     //@{
 197     /**
 198         Returns an iterator pointing at the one-after-the-last element of the hash map.
 199         Please remember that hash maps do not guarantee ordering.
 200     */
 201     const_iterator end() const;
 202     iterator end();
 203     //@}
 204
 205     //@{
 206     /**
 207         Erases the element with the given key, and returns the number of elements
 208         erased (either 0 or 1).
 209     */
 210     size_type erase(const key_type& key);
 211
 212     /**
 213         Erases the element pointed to by the iterator. After the deletion
 214         the iterator is no longer valid and must not be used.
 215     */
 216     void erase(iterator it);
 217     void erase(const_iterator it);
 218     //@}
 219
 220     //@{
 221     /**
 222         If an element with the given key is present, the functions returns an
 223         iterator pointing at that element, otherwise an invalid iterator is
 224         returned; i.e.
 225         @code
 226             hashmap.find( non_existent_key ) == hashmap.end()
 227         @endcode
 228     */
 229     iterator find(const key_type& key) const;
 230     const_iterator find(const key_type& key) const;
 231     //@}
 232
 233     /**
 234         Inserts the given value in the hash map.
 235         The return value is equivalent to a
 236         @code std::pair<wxHashMap::iterator, bool> @endcode
 237         The iterator points to the inserted element, the boolean value is @true
 238         if @a v was actually inserted.
 239     */
 240     Insert_Result insert(const value_type& v);
 241
 242     /**
 243         Use the key as an array subscript.
 244         The only difference is that if the given key is not present in the hash map,
 245         an element with the default @c value_type() is inserted in the table.
 246     */
 247     mapped_type operator[](const key_type& key);
 248
 249     /**
 250         Returns the number of elements in the map.
 251     */
 252     size_type size() const;
 253 };
 254