wxHashSet

This is a simple, type-safe, and reasonably efficient hash set class, whose interface is a subset of the interface of STL containers. In particular, the interface is modeled after std::set, and the various, non standard, std::hash_map.

Example

    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
    }

Declaring new hash set types

    WX_DECLARE_HASH_SET( KEY_T,      // type of the keys
                         HASH_T,     // hasher
                         KEY_EQ_T,   // key equality predicate
                         CLASSNAME); // name of the class

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:

    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

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()

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.

Include files

<wx/hashset.h>



wxHashSet::wxHashSet



wxHashSet(size_type size = 10)

The size parameter is just a hint, the table will resize automatically to preserve performance.



wxHashSet(const wxHashSet& set)

Copy constructor.



wxHashSet::begin

const_iterator begin() const



iterator begin()

Returns an iterator pointing at the first element of the hash set. Please remember that hash sets do not guarantee ordering.



wxHashSet::clear



void clear()

Removes all elements from the hash set.



wxHashSet::count

size_type count(const key_type& key) const

Counts the number of elements with the given key present in the set. This function returns only 0 or 1.



wxHashSet::empty

bool empty() const

Returns true if the hash set does not contain any elements, false otherwise.



wxHashSet::end

const_iterator end() const



iterator end()

Returns an iterator pointing at the one-after-the-last element of the hash set. Please remember that hash sets do not guarantee ordering.



wxHashSet::erase



size_type erase(const key_type& key)

Erases the element with the given key, and returns the number of elements erased (either 0 or 1).



void erase(iterator it)



void erase(const_iterator it)

Erases the element pointed to by the iterator. After the deletion the iterator is no longer valid and must not be used.



wxHashSet::find



iterator find(const key_type& key)

const_iterator find(const key_type& key) const

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. hashset.find( non_existent_key ) == hashset.end()).



wxHashSet::insert



Insert_Result insert(const value_type& v)

Inserts the given value in the hash set. The return value is equivalent to a std::pair<wxHashMap::iterator, bool>; the iterator points to the inserted element, the boolean value is true if v was actually inserted.



wxHashSet::size

size_type size() const

Returns the number of elements in the set.

ymasuda 平成17年11月19日