///////////////////////////////////////////////////////////////////////////// // Name: hashmap.h // Purpose: interface of wxHashMap // Author: wxWidgets team // Licence: wxWindows licence ///////////////////////////////////////////////////////////////////////////// /** @class wxHashMap This is a simple, type-safe, and reasonably efficient hash map class, whose interface is a subset of the interface of STL containers. In particular, the interface is modelled after std::map, and the various, non-standard, std::hash_map (http://www.cppreference.com/wiki/stl/map/start). Example: @code class MyClass { ... }; // declare a hash map with string keys and int values WX_DECLARE_STRING_HASH_MAP( int, MyHash5 ); // same, with int keys and MyClass* values WX_DECLARE_HASH_MAP( int, MyClass*, wxIntegerHash, wxIntegerEqual, MyHash1 ); // same, with wxString keys and int values WX_DECLARE_STRING_HASH_MAP( int, MyHash3 ); // same, with wxString keys and values WX_DECLARE_STRING_HASH_MAP( wxString, MyHash2 ); MyHash1 h1; MyHash2 h2; // store and retrieve values h1[1] = new MyClass( 1 ); h1[10000000] = NULL; h1[50000] = new MyClass( 2 ); h2["Bill"] = "ABC"; wxString tmp = h2["Bill"]; // since element with key "Joe" is not present, this will return // the default value, which is an empty string in the case of wxString MyClass tmp2 = h2["Joe"]; // iterate over all the elements in the class MyHash2::iterator it; for( it = h2.begin(); it != h2.end(); ++it ) { wxString key = it->first, value = it->second; // do something useful with key and value } @endcode @section hashmap_declaringnew Declaring new hash table types @code WX_DECLARE_STRING_HASH_MAP( VALUE_T, // type of the values CLASSNAME ); // name of the class @endcode Declares a hash map class named CLASSNAME, with wxString keys and VALUE_T values. @code WX_DECLARE_VOIDPTR_HASH_MAP( VALUE_T, // type of the values CLASSNAME ); // name of the class @endcode Declares a hash map class named CLASSNAME, with void* keys and VALUE_T values. @code WX_DECLARE_HASH_MAP( KEY_T, // type of the keys VALUE_T, // type of the values 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: @c wxIntegerHash for integer types ( int, long, short, and their unsigned counterparts ), @c wxStringHash for strings ( wxString, wxChar*, char* ), and @c wxPointerHash for any kind of pointer. Similarly three equality predicates: @c wxIntegerEqual, @c wxStringEqual, @c wxPointerEqual are provided. Using this you could declare a hash map mapping int values to wxString like this: @code WX_DECLARE_HASH_MAP( int, wxString, wxIntegerHash, wxIntegerEqual, MyHash ); // 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_MAP( MyKey, // type of the keys SOME_TYPE, // any type you like MyKeyHash, // hasher MyKeyEqual, // key equality predicate CLASSNAME); // name of the class @endcode @section hashmap_types Types In the documentation below you should replace wxHashMap with the name you used in the class declaration. - wxHashMap::key_type: Type of the hash keys. - wxHashMap::mapped_type: Type of the values stored in the hash map. - wxHashMap::value_type: Equivalent to struct { key_type first; mapped_type second }. - wxHashMap::iterator: Used to enumerate all the elements in a hash map; it is similar to a value_type*. - wxHashMap::const_iterator: Used to enumerate all the elements in a constant hash map; it is similar to a const value_type*. - wxHashMap::size_type: Used for sizes. - wxHashMap::Insert_Result: The return value for insert(). @section hashmap_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->first ( it->second ) to access the key ( value ) of the element pointed to. Hash maps provide forward only iterators, this means that you can't use --it, it + 3, it1 - it2. @section hashmap_predef Predefined hashmap types wxWidgets defines the following hashmap types: - wxLongToLongHashMap (uses long both for keys and values) - wxStringToStringHashMap (uses wxString both for keys and values) @library{wxbase} @category{containers} */ class wxHashMap { public: /** The size parameter is just a hint, the table will resize automatically to preserve performance. */ wxHashMap(size_type size = 10); /** Copy constructor. */ wxHashMap(const wxHashMap& map); //@{ /** Returns an iterator pointing at the first element of the hash map. Please remember that hash maps do not guarantee ordering. */ const_iterator begin() const; iterator begin(); //@} /** Removes all elements from the hash map. */ void clear(); /** Counts the number of elements with the given key present in the map. This function returns only 0 or 1. */ size_type count(const key_type& key) const; /** Returns @true if the hash map does not contain any elements, @false otherwise. */ bool empty() const; //@{ /** Returns an iterator pointing at the one-after-the-last element of the hash map. Please remember that hash maps 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. @code hashmap.find( non_existent_key ) == hashmap.end() @endcode */ iterator find(const key_type& key) const; const_iterator find(const key_type& key) const; //@} /** Inserts the given value in the hash map. 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); /** Use the key as an array subscript. The only difference is that if the given key is not present in the hash map, an element with the default @c value_type() is inserted in the table. */ mapped_type operator[](const key_type& key); /** Returns the number of elements in the map. */ size_type size() const; };