interface/wx/hashset.h

   1 /////////////////////////////////////////////////////////////////////////////
   2 // Name:        hashset.h
   3 // Purpose:     interface of wxHashSet
   4 // Author:      wxWidgets team
   5 // RCS-ID:      $Id$
   6 // Licence:     wxWindows license
   7 /////////////////////////////////////////////////////////////////////////////
   8
   9 /**
  10     @class wxHashSet
  11
  12     This is a simple, type-safe, and reasonably efficient hash set class,
  13     whose interface is a subset of the interface of STL containers.
  14     In particular, the interface is modeled after std::set, and the various,
  15     non-standard, std::hash_map.
  16
  17     Example:
  18     @code
  19         class MyClass { ... };
  20
  21         // same, with MyClass* keys (only uses pointer equality!)
  22         WX_DECLARE_HASH_SET( MyClass*, wxPointerHash, wxPointerEqual, MySet1 );
  23         // same, with int keys
  24         WX_DECLARE_HASH_SET( int, wxIntegerHash, wxIntegerEqual, MySet2 );
  25         // declare a hash set with string keys
  26         WX_DECLARE_HASH_SET( wxString, wxStringHash, wxStringEqual, MySet3 );
  27
  28         MySet1 h1;
  29         MySet2 h1;
  30         MySet3 h3;
  31
  32         // store and retrieve values
  33         h1.insert( new MyClass( 1 ) );
  34
  35         h3.insert( "foo" );
  36         h3.insert( "bar" );
  37         h3.insert( "baz" );
  38
  39         int size = h3.size(); // now is three
  40         bool has_foo = h3.find( "foo" ) != h3.end();
  41
  42         h3.insert( "bar" ); // still has size three
  43
  44         // iterate over all the elements in the class
  45         MySet3::iterator it;
  46         for( it = h3.begin(); it != h3.end(); ++it )
  47         {
  48             wxString key = *it;
  49             // do something useful with key
  50         }
  51     @endcode
  52
  53
  54     @section hashset_declaringnew Declaring new hash set types
  55
  56     @code
  57     WX_DECLARE_HASH_SET( KEY_T,      // type of the keys
  58                          HASH_T,     // hasher
  59                          KEY_EQ_T,   // key equality predicate
  60                          CLASSNAME); // name of the class
  61     @endcode
  62     The HASH_T and KEY_EQ_T are the types used for the hashing function and key
  63     comparison. wxWidgets provides three predefined hashing functions:
  64     wxIntegerHash for integer types ( int, long, short, and their unsigned counterparts ),
  65     wxStringHash for strings ( wxString, wxChar*, char* ), and wxPointerHash for
  66     any kind of pointer.
  67     Similarly three equality predicates: wxIntegerEqual, wxStringEqual, wxPointerEqual
  68     are provided. Using this you could declare a hash set using int values like this:
  69
  70     @code
  71         WX_DECLARE_HASH_SET( int,
  72                             wxIntegerHash,
  73                             wxIntegerEqual,
  74                             MySet );
  75
  76         // using an user-defined class for keys
  77         class MyKey { ... };
  78
  79         // hashing function
  80         class MyKeyHash
  81         {
  82         public:
  83             MyKeyHash() { }
  84
  85             unsigned long operator()( const MyKey& k ) const
  86                 {
  87                     // compute the hash
  88                 }
  89
  90             MyKeyHash& operator=(const MyKeyHash&) { return *this; }
  91         };
  92
  93         // comparison operator
  94         class MyKeyEqual
  95         {
  96         public:
  97             MyKeyEqual() { }
  98             bool operator()( const MyKey& a, const MyKey& b ) const
  99                 {
 100                     // compare for equality
 101                 }
 102
 103             MyKeyEqual& operator=(const MyKeyEqual&) { return *this; }
 104         };
 105
 106         WX_DECLARE_HASH_SET( MyKey,      // type of the keys
 107                             MyKeyHash,  // hasher
 108                             MyKeyEqual, // key equality predicate
 109                             CLASSNAME); // name of the class
 110     @endcode
 111
 112
 113     @section hashset_types Types
 114
 115     In the documentation below you should replace wxHashSet with the name you
 116     used in the class declaration.
 117
 118     - wxHashSet::key_type: Type of the hash keys
 119     - wxHashSet::mapped_type: Type of hash keys
 120     - wxHashSet::value_type: Type of hash keys
 121     - wxHashSet::iterator: Used to enumerate all the elements in a hash set;
 122                            it is similar to a value_type*
 123     - wxHashSet::const_iterator: Used to enumerate all the elements in a constant
 124                                  hash set; it is similar to a const value_type*
 125     - wxHashSet::size_type: Used for sizes
 126     - wxHashSet::Insert_Result: The return value for insert()
 127
 128
 129     @section hashset_iter Iterators
 130
 131     An iterator is similar to a pointer, and so you can use the usual pointer
 132     operations: ++it ( and it++ ) to move to the next element, *it to access the
 133     element pointed to, *it to access the value of the element pointed to.
 134     Hash sets provide forward only iterators, this means that you can't use --it,
 135     it + 3, it1 - it2.
 136
 137     @library{wxbase}
 138     @category{containers}
 139 */
 140 class wxHashSet
 141 {
 142 public:
 143     /**
 144         The size parameter is just a hint, the table will resize automatically
 145         to preserve performance.
 146     */
 147     wxHashSet(size_type size = 10);
 148
 149     /**
 150         Copy constructor.
 151     */
 152     wxHashSet(const wxHashSet& set);
 153
 154     //@{
 155     /**
 156         Returns an iterator pointing at the first element of the hash set.
 157         Please remember that hash sets do not guarantee ordering.
 158     */
 159     const_iterator begin() const;
 160     iterator begin();
 161     //@}
 162
 163     /**
 164         Removes all elements from the hash set.
 165     */
 166     void clear();
 167
 168     /**
 169         Counts the number of elements with the given key present in the set.
 170         This function returns only 0 or 1.
 171     */
 172     size_type count(const key_type& key) const;
 173
 174     /**
 175         Returns @true if the hash set does not contain any elements, @false otherwise.
 176     */
 177     bool empty() const;
 178
 179     //@{
 180     /**
 181         Returns an iterator pointing at the one-after-the-last element of the hash set.
 182         Please remember that hash sets do not guarantee ordering.
 183     */
 184     const_iterator end() const;
 185     iterator end();
 186     //@}
 187
 188     /**
 189         Erases the element with the given key, and returns the number of elements
 190         erased (either 0 or 1).
 191     */
 192     size_type erase(const key_type& key);
 193
 194     //@{
 195     /**
 196         Erases the element pointed to by the iterator. After the deletion
 197         the iterator is no longer valid and must not be used.
 198     */
 199     void erase(iterator it);
 200     void erase(const_iterator it);
 201     //@}
 202
 203     //@{
 204     /**
 205         If an element with the given key is present, the functions returns
 206         an iterator pointing at that element, otherwise an invalid iterator
 207         is returned; i.e.
 208         @code
 209             hashset.find( non_existent_key ) == hashset.end()
 210         @endcode
 211     */
 212     iterator find(const key_type& key) const;
 213     const_iterator find(const key_type& key) const;
 214     //@}
 215
 216     /**
 217         Inserts the given value in the hash set.
 218         The return value is equivalent to a
 219         @code std::pair<wxHashMap::iterator, bool> @endcode
 220         The iterator points to the inserted element, the boolean value is @true
 221         if @a v was actually inserted.
 222     */
 223     Insert_Result insert(const value_type& v);
 224
 225     /**
 226         Returns the number of elements in the set.
 227     */
 228     size_type size() const;
 229 };
 230