File: hashset.h

package info (click to toggle)
wxwidgets3.0 3.0.2%2Bdfsg-4
  • links: PTS, VCS
  • area: main
  • in suites: stretch
  • size: 120,808 kB
  • ctags: 118,010
  • sloc: cpp: 889,420; makefile: 52,980; ansic: 21,933; sh: 5,603; python: 2,935; xml: 1,534; perl: 281
file content (231 lines) | stat: -rw-r--r-- 7,169 bytes parent folder | download | duplicates (10)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
/////////////////////////////////////////////////////////////////////////////
// Name:        hashset.h
// Purpose:     interface of wxHashSet
// Author:      wxWidgets team
// Licence:     wxWindows licence
/////////////////////////////////////////////////////////////////////////////

/**
    @class wxHashSet

    This is a simple, type-safe, and reasonably efficient hash set class,
    whose interface is a subset of the interface of STL containers.

    The interface is similar to std::tr1::hash_set or std::set classes but
    notice that, unlike std::set, the contents of a hash set is not sorted.

    Example:
    @code
        class MyClass { ... };

        // same, with MyClass* keys (only uses pointer equality!)
        WX_DECLARE_HASH_SET( MyClass*, wxPointerHash, wxPointerEqual, MySet1 );
        // same, with int keys
        WX_DECLARE_HASH_SET( int, wxIntegerHash, wxIntegerEqual, MySet2 );
        // declare a hash set with string keys
        WX_DECLARE_HASH_SET( wxString, wxStringHash, wxStringEqual, MySet3 );

        MySet1 h1;
        MySet2 h1;
        MySet3 h3;

        // store and retrieve values
        h1.insert( new MyClass( 1 ) );

        h3.insert( "foo" );
        h3.insert( "bar" );
        h3.insert( "baz" );

        int size = h3.size(); // now is three
        bool has_foo = h3.find( "foo" ) != h3.end();

        h3.insert( "bar" ); // still has size three

        // iterate over all the elements in the class
        MySet3::iterator it;
        for( it = h3.begin(); it != h3.end(); ++it )
        {
            wxString key = *it;
            // do something useful with key
        }
    @endcode


    @section hashset_declaringnew Declaring new hash set types

    @code
    WX_DECLARE_HASH_SET( KEY_T,      // type of the keys
                         HASH_T,     // hasher
                         KEY_EQ_T,   // key equality predicate
                         CLASSNAME); // name of the class
    @endcode
    The HASH_T and KEY_EQ_T are the types used for the hashing function and key
    comparison. wxWidgets provides three predefined hashing functions:
    wxIntegerHash for integer types ( int, long, short, and their unsigned counterparts ),
    wxStringHash for strings ( wxString, wxChar*, char* ), and wxPointerHash for
    any kind of pointer.
    Similarly three equality predicates: wxIntegerEqual, wxStringEqual, wxPointerEqual
    are provided. Using this you could declare a hash set using int values like this:

    @code
        WX_DECLARE_HASH_SET( int,
                            wxIntegerHash,
                            wxIntegerEqual,
                            MySet );

        // using an user-defined class for keys
        class MyKey { ... };

        // hashing function
        class MyKeyHash
        {
        public:
            MyKeyHash() { }

            unsigned long operator()( const MyKey& k ) const
                {
                    // compute the hash
                }

            MyKeyHash& operator=(const MyKeyHash&) { return *this; }
        };

        // comparison operator
        class MyKeyEqual
        {
        public:
            MyKeyEqual() { }
            bool operator()( const MyKey& a, const MyKey& b ) const
                {
                    // compare for equality
                }

            MyKeyEqual& operator=(const MyKeyEqual&) { return *this; }
        };

        WX_DECLARE_HASH_SET( MyKey,      // type of the keys
                            MyKeyHash,  // hasher
                            MyKeyEqual, // key equality predicate
                            CLASSNAME); // name of the class
    @endcode


    @section hashset_types Types

    In the documentation below you should replace wxHashSet with the name you
    used in the class declaration.

    - wxHashSet::key_type: Type of the hash keys
    - wxHashSet::mapped_type: Type of hash keys
    - wxHashSet::value_type: Type of hash keys
    - wxHashSet::iterator: Used to enumerate all the elements in a hash set;
                           it is similar to a value_type*
    - wxHashSet::const_iterator: Used to enumerate all the elements in a constant
                                 hash set; it is similar to a const value_type*
    - wxHashSet::size_type: Used for sizes
    - wxHashSet::Insert_Result: The return value for insert()


    @section hashset_iter Iterators

    An iterator is similar to a pointer, and so you can use the usual pointer
    operations: ++it ( and it++ ) to move to the next element, *it to access the
    element pointed to, *it to access the value of the element pointed to.
    Hash sets provide forward only iterators, this means that you can't use --it,
    it + 3, it1 - it2.

    @library{wxbase}
    @category{containers}
*/
class wxHashSet
{
public:
    /**
        The size parameter is just a hint, the table will resize automatically
        to preserve performance.
    */
    wxHashSet(size_type size = 10);

    /**
        Copy constructor.
    */
    wxHashSet(const wxHashSet& set);

    //@{
    /**
        Returns an iterator pointing at the first element of the hash set.
        Please remember that hash sets do not guarantee ordering.
    */
    const_iterator begin() const;
    iterator begin();
    //@}

    /**
        Removes all elements from the hash set.
    */
    void clear();

    /**
        Counts the number of elements with the given key present in the set.
        This function returns only 0 or 1.
    */
    size_type count(const key_type& key) const;

    /**
        Returns @true if the hash set does not contain any elements, @false otherwise.
    */
    bool empty() const;

    //@{
    /**
        Returns an iterator pointing at the one-after-the-last element of the hash set.
        Please remember that hash sets do not guarantee ordering.
    */
    const_iterator end() const;
    iterator end();
    //@}

    /**
        Erases the element with the given key, and returns the number of elements
        erased (either 0 or 1).
    */
    size_type erase(const key_type& key);

    //@{
    /**
        Erases the element pointed to by the iterator. After the deletion
        the iterator is no longer valid and must not be used.
    */
    void erase(iterator it);
    void erase(const_iterator it);
    //@}

    //@{
    /**
        If an element with the given key is present, the functions returns
        an iterator pointing at that element, otherwise an invalid iterator
        is returned.
        i.e.
        @code
            hashset.find( non_existent_key ) == hashset.end()
        @endcode
    */
    iterator find(const key_type& key) const;
    const_iterator find(const key_type& key) const;
    //@}

    /**
        Inserts the given value in the hash set.
        The return value is equivalent to a
        @code std::pair<wxHashMap::iterator, bool> @endcode
        The iterator points to the inserted element, the boolean value is @true
        if @a v was actually inserted.
    */
    Insert_Result insert(const value_type& v);

    /**
        Returns the number of elements in the set.
    */
    size_type size() const;
};