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