X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/12f5e1e78fe906050ff2fee9529476db332633f0..92c0fc34c104c8d7c12d6a3b78ea232690fc23f4:/interface/wx/hashset.h?ds=sidebyside diff --git a/interface/wx/hashset.h b/interface/wx/hashset.h index 8ca4fc1535..dc5220347a 100644 --- a/interface/wx/hashset.h +++ b/interface/wx/hashset.h @@ -2,39 +2,162 @@ // Name: hashset.h // Purpose: interface of wxHashSet // Author: wxWidgets team -// RCS-ID: $Id$ -// Licence: wxWindows license +// 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. In - particular, the interface is modeled after std::set, and the various, - non-standard, std::hash_map. + 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{FIXME} + @category{containers} */ class wxHashSet { public: - //@{ /** - Copy constructor. + 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(); + const_iterator begin() const; + iterator begin(); //@} /** @@ -58,16 +181,21 @@ public: 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(); + 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. */ - size_type erase(const key_type& key); void erase(iterator it); void erase(const_iterator it); //@} @@ -76,17 +204,21 @@ public: /** 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()). + 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 @c std::pairwxHashMap::iterator, bool; - the iterator points to the inserted element, the boolean value - is @true if @c v was actually inserted. + Inserts the given value in the hash set. + The return value is equivalent to a + @code std::pair @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);