docs/latex/wx/hashset.tex

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