-#ifndef STLPLUS_HASH\r
-#define STLPLUS_HASH\r
-////////////////////////////////////////////////////////////////////////////////\r
-\r
-// Author: Andy Rushton\r
-// Copyright: (c) Southampton University 1999-2004\r
-// (c) Andy Rushton 2004-2009\r
-// License: BSD License, see ../docs/license.html\r
-\r
-// A chained hash table using STL semantics\r
-\r
-////////////////////////////////////////////////////////////////////////////////\r
-#include "containers_fixes.hpp"\r
-#include "exceptions.hpp"\r
-#include "safe_iterator.hpp"\r
-#include <map>\r
-#include <iostream>\r
-\r
-namespace stlplus\r
-{\r
-\r
- ////////////////////////////////////////////////////////////////////////////////\r
- // internals\r
-\r
- template<typename K, typename T, class H, class E> class hash;\r
- template<typename K, typename T, class H, class E> class hash_element;\r
-\r
- ////////////////////////////////////////////////////////////////////////////////\r
- // iterator class\r
-\r
- template<typename K, typename T, class H, class E, typename V>\r
- class hash_iterator : public safe_iterator<hash<K,T,H,E>,hash_element<K,T,H,E> >\r
- {\r
- public:\r
- friend class hash<K,T,H,E>;\r
-\r
- // local type definitions\r
- // an iterator points to a value whilst a const_iterator points to a const value\r
- typedef V value_type;\r
- typedef hash_iterator<K,T,H,E,std::pair<const K,T> > iterator;\r
- typedef hash_iterator<K,T,H,E,const std::pair<const K,T> > const_iterator;\r
- typedef hash_iterator<K,T,H,E,V> this_iterator;\r
- typedef V& reference;\r
- typedef V* pointer;\r
-\r
- // constructor to create a null iterator - you must assign a valid value to this iterator before using it\r
- // any attempt to dereference or use a null iterator is an error\r
- // the only valid thing you can do is assign an iterator to it\r
- hash_iterator(void);\r
- ~hash_iterator(void);\r
-\r
- // Type conversion methods allow const_iterator and iterator to be converted\r
- // convert an iterator/const_iterator to a const_iterator\r
- const_iterator constify(void) const;\r
- // convert an iterator/const_iterator to an iterator\r
- iterator deconstify(void) const;\r
-\r
- // increment operators used to step through the set of all values in a hash\r
- // it is only legal to increment a valid iterator\r
- // there's no decrement - I've only implemented this as a unidirectional iterator\r
- // pre-increment\r
- this_iterator& operator ++ (void)\r
- throw(null_dereference,end_dereference);\r
- // post-increment\r
- this_iterator operator ++ (int)\r
- throw(null_dereference,end_dereference);\r
-\r
- // test useful for testing whether iteration has completed\r
- bool operator == (const this_iterator& r) const;\r
- bool operator != (const this_iterator& r) const;\r
- bool operator < (const this_iterator& r) const;\r
-\r
- // access the value - a const_iterator gives you a const value, an iterator a non-const value\r
- // it is illegal to dereference an invalid (i.e. null or end) iterator\r
- reference operator*(void) const\r
- throw(null_dereference,end_dereference);\r
- pointer operator->(void) const\r
- throw(null_dereference,end_dereference);\r
-\r
- private:\r
- friend class hash_element<K,T,H,E>;\r
-\r
- // constructor used by hash to create a non-null iterator\r
- // you cannot create a valid iterator except by calling a hash method that returns one\r
- explicit hash_iterator(hash_element<K,T,H,E>* element);\r
- // constructor used to create an end iterator\r
- explicit hash_iterator(const hash<K,T,H,E>* owner);\r
- // used to create an alias of an iterator\r
- explicit hash_iterator(const safe_iterator<hash<K,T,H,E>, hash_element<K,T,H,E> >& iterator);\r
- };\r
-\r
- ////////////////////////////////////////////////////////////////////////////////\r
- // Hash class\r
- // K = key type\r
- // T = value type\r
- // H = hash function object with the profile 'unsigned H(const K&)'\r
- // E = equal function object with profile 'bool E(const K&, const K&)' defaults to equal_to which in turn calls '=='\r
-\r
- template<typename K, typename T, class H, class E = std::equal_to<K> >\r
- class hash\r
- {\r
- public:\r
- typedef unsigned size_type;\r
- typedef K key_type;\r
- typedef T data_type;\r
- typedef T mapped_type;\r
- typedef std::pair<const K, T> value_type;\r
- typedef hash_iterator<K,T,H,E,value_type> iterator;\r
- typedef hash_iterator<K,T,H,E,const value_type> const_iterator;\r
-\r
- // construct a hash table with specified number of bins\r
- // the default 0 bins means leave it to the table to decide\r
- // specifying 0 bins also enables auto-rehashing, otherwise auto-rehashing defaults off\r
- hash(unsigned bins = 0);\r
- ~hash(void);\r
-\r
- // copy and equality copy the data elements but not the size of the copied table\r
- hash(const hash&);\r
- hash& operator = (const hash&);\r
-\r
- // test for an empty table and for the size of a table\r
- // efficient because the size is stored separately from the table contents\r
- bool empty(void) const;\r
- unsigned size(void) const;\r
-\r
- // test for equality - two hashes are equal if they contain equal values\r
- bool operator == (const hash&) const;\r
- bool operator != (const hash&) const;\r
-\r
- // switch auto-rehash on\r
- void auto_rehash(void);\r
- // switch auto-rehash off\r
- void manual_rehash(void);\r
- // force a rehash now\r
- // default of 0 means implement built-in size calculation for rehashing (recommended - it doubles the number of bins)\r
- void rehash(unsigned bins = 0);\r
- // test the loading ratio, which is the size divided by the number of bins\r
- // use this if you are doing your own rehashing\r
- // the recommendation is to double the bins when the loading exceeds 0.5 which is what auto-rehashing does\r
- float loading(void) const;\r
-\r
- // test for the presence of a key\r
- bool present(const K& key) const;\r
- // provide map equivalent key count function (0 or 1, as not a multimap)\r
- size_type count(const K& key) const;\r
-\r
- // insert a new key/data pair - replaces any previous value for this key\r
- iterator insert(const K& key, const T& data);\r
- // insert a copy of the pair into the table (std::map compatible)\r
- std::pair<iterator, bool> insert(const value_type& value);\r
- // insert a new key and return the iterator so that the data can be filled in\r
- iterator insert(const K& key);\r
-\r
- // remove a key/data pair from the hash table\r
- // as in map, this returns the number of elements erased\r
- size_type erase(const K& key);\r
- // remove an element from the hash table using an iterator\r
- // as in map, returns an iterator to the next element\r
- iterator erase(iterator it);\r
- // remove all elements from the hash table\r
- void erase(void);\r
- // map equivalent of above\r
- void clear(void);\r
-\r
- // find a key and return an iterator to it\r
- // The iterator is like a pointer to a pair<const K,T>\r
- // end() is returned if the find fails\r
- const_iterator find(const K& key) const;\r
- iterator find(const K& key);\r
-\r
- // returns the data corresponding to the key\r
- // const version is used for const hashes and cannot change the hash, so failure causes an exception\r
- // non-const version is for non-const hashes and is like map - it creates a new key/data pair if find fails\r
- const T& operator[] (const K& key) const throw(std::out_of_range);\r
- T& operator[] (const K& key);\r
-\r
- // iterators allow the hash table to be traversed\r
- // iterators remain valid unless an item is removed or unless a rehash happens\r
- const_iterator begin(void) const;\r
- iterator begin(void);\r
- const_iterator end(void) const;\r
- iterator end(void);\r
-\r
- // diagnostic report shows the number of items in each bin so can be used\r
- // to diagnose effectiveness of hash functions\r
- void debug_report(std::ostream&) const;\r
-\r
- // internals\r
- private:\r
- friend class hash_element<K,T,H,E>;\r
- friend class hash_iterator<K,T,H,E,std::pair<const K,T> >;\r
- friend class hash_iterator<K,T,H,E,const std::pair<const K,T> >;\r
-\r
- unsigned m_rehash;\r
- unsigned m_bins;\r
- unsigned m_size;\r
- hash_element<K,T,H,E>** m_values;\r
- };\r
-\r
- ////////////////////////////////////////////////////////////////////////////////\r
-\r
-} // end namespace stlplus\r
-\r
-#include "hash.tpp"\r
-#endif\r
+#ifndef STLPLUS_HASH
+#define STLPLUS_HASH
+////////////////////////////////////////////////////////////////////////////////
+
+// Author: Andy Rushton
+// Copyright: (c) Southampton University 1999-2004
+// (c) Andy Rushton 2004-2009
+// License: BSD License, see ../docs/license.html
+
+// A chained hash table using STL semantics
+
+////////////////////////////////////////////////////////////////////////////////
+#include "containers_fixes.hpp"
+#include "exceptions.hpp"
+#include "safe_iterator.hpp"
+#include <map>
+#include <iostream>
+
+namespace stlplus
+{
+
+ ////////////////////////////////////////////////////////////////////////////////
+ // internals
+
+ template<typename K, typename T, class H, class E> class hash;
+ template<typename K, typename T, class H, class E> class hash_element;
+
+ ////////////////////////////////////////////////////////////////////////////////
+ // iterator class
+
+ template<typename K, typename T, class H, class E, typename V>
+ class hash_iterator : public safe_iterator<hash<K,T,H,E>,hash_element<K,T,H,E> >
+ {
+ public:
+ friend class hash<K,T,H,E>;
+
+ // local type definitions
+ // an iterator points to a value whilst a const_iterator points to a const value
+ typedef V value_type;
+ typedef hash_iterator<K,T,H,E,std::pair<const K,T> > iterator;
+ typedef hash_iterator<K,T,H,E,const std::pair<const K,T> > const_iterator;
+ typedef hash_iterator<K,T,H,E,V> this_iterator;
+ typedef V& reference;
+ typedef V* pointer;
+
+ // constructor to create a null iterator - you must assign a valid value to this iterator before using it
+ // any attempt to dereference or use a null iterator is an error
+ // the only valid thing you can do is assign an iterator to it
+ hash_iterator(void);
+ ~hash_iterator(void);
+
+ // Type conversion methods allow const_iterator and iterator to be converted
+ // convert an iterator/const_iterator to a const_iterator
+ const_iterator constify(void) const;
+ // convert an iterator/const_iterator to an iterator
+ iterator deconstify(void) const;
+
+ // increment operators used to step through the set of all values in a hash
+ // it is only legal to increment a valid iterator
+ // there's no decrement - I've only implemented this as a unidirectional iterator
+ // pre-increment
+ this_iterator& operator ++ (void)
+ throw(null_dereference,end_dereference);
+ // post-increment
+ this_iterator operator ++ (int)
+ throw(null_dereference,end_dereference);
+
+ // test useful for testing whether iteration has completed
+ bool operator == (const this_iterator& r) const;
+ bool operator != (const this_iterator& r) const;
+ bool operator < (const this_iterator& r) const;
+
+ // access the value - a const_iterator gives you a const value, an iterator a non-const value
+ // it is illegal to dereference an invalid (i.e. null or end) iterator
+ reference operator*(void) const
+ throw(null_dereference,end_dereference);
+ pointer operator->(void) const
+ throw(null_dereference,end_dereference);
+
+ private:
+ friend class hash_element<K,T,H,E>;
+
+ // constructor used by hash to create a non-null iterator
+ // you cannot create a valid iterator except by calling a hash method that returns one
+ explicit hash_iterator(hash_element<K,T,H,E>* element);
+ // constructor used to create an end iterator
+ explicit hash_iterator(const hash<K,T,H,E>* owner);
+ // used to create an alias of an iterator
+ explicit hash_iterator(const safe_iterator<hash<K,T,H,E>, hash_element<K,T,H,E> >& iterator);
+ };
+
+ ////////////////////////////////////////////////////////////////////////////////
+ // Hash class
+ // K = key type
+ // T = value type
+ // H = hash function object with the profile 'unsigned H(const K&)'
+ // E = equal function object with profile 'bool E(const K&, const K&)' defaults to equal_to which in turn calls '=='
+
+ template<typename K, typename T, class H, class E = std::equal_to<K> >
+ class hash
+ {
+ public:
+ typedef unsigned size_type;
+ typedef K key_type;
+ typedef T data_type;
+ typedef T mapped_type;
+ typedef std::pair<const K, T> value_type;
+ typedef hash_iterator<K,T,H,E,value_type> iterator;
+ typedef hash_iterator<K,T,H,E,const value_type> const_iterator;
+
+ // construct a hash table with specified number of bins
+ // the default 0 bins means leave it to the table to decide
+ // specifying 0 bins also enables auto-rehashing, otherwise auto-rehashing defaults off
+ hash(unsigned bins = 0);
+ ~hash(void);
+
+ // copy and equality copy the data elements but not the size of the copied table
+ hash(const hash&);
+ hash& operator = (const hash&);
+
+ // test for an empty table and for the size of a table
+ // efficient because the size is stored separately from the table contents
+ bool empty(void) const;
+ unsigned size(void) const;
+
+ // test for equality - two hashes are equal if they contain equal values
+ bool operator == (const hash&) const;
+ bool operator != (const hash&) const;
+
+ // switch auto-rehash on
+ void auto_rehash(void);
+ // switch auto-rehash off
+ void manual_rehash(void);
+ // force a rehash now
+ // default of 0 means implement built-in size calculation for rehashing (recommended - it doubles the number of bins)
+ void rehash(unsigned bins = 0);
+ // test the loading ratio, which is the size divided by the number of bins
+ // use this if you are doing your own rehashing
+ // the recommendation is to double the bins when the loading exceeds 0.5 which is what auto-rehashing does
+ float loading(void) const;
+
+ // test for the presence of a key
+ bool present(const K& key) const;
+ // provide map equivalent key count function (0 or 1, as not a multimap)
+ size_type count(const K& key) const;
+
+ // insert a new key/data pair - replaces any previous value for this key
+ iterator insert(const K& key, const T& data);
+ // insert a copy of the pair into the table (std::map compatible)
+ std::pair<iterator, bool> insert(const value_type& value);
+ // insert a new key and return the iterator so that the data can be filled in
+ iterator insert(const K& key);
+
+ // remove a key/data pair from the hash table
+ // as in map, this returns the number of elements erased
+ size_type erase(const K& key);
+ // remove an element from the hash table using an iterator
+ // as in map, returns an iterator to the next element
+ iterator erase(iterator it);
+ // remove all elements from the hash table
+ void erase(void);
+ // map equivalent of above
+ void clear(void);
+
+ // find a key and return an iterator to it
+ // The iterator is like a pointer to a pair<const K,T>
+ // end() is returned if the find fails
+ const_iterator find(const K& key) const;
+ iterator find(const K& key);
+
+ // returns the data corresponding to the key
+ // const version is used for const hashes and cannot change the hash, so failure causes an exception
+ // non-const version is for non-const hashes and is like map - it creates a new key/data pair if find fails
+ const T& operator[] (const K& key) const throw(std::out_of_range);
+ T& operator[] (const K& key);
+
+ // iterators allow the hash table to be traversed
+ // iterators remain valid unless an item is removed or unless a rehash happens
+ const_iterator begin(void) const;
+ iterator begin(void);
+ const_iterator end(void) const;
+ iterator end(void);
+
+ // diagnostic report shows the number of items in each bin so can be used
+ // to diagnose effectiveness of hash functions
+ void debug_report(std::ostream&) const;
+
+ // internals
+ private:
+ friend class hash_element<K,T,H,E>;
+ friend class hash_iterator<K,T,H,E,std::pair<const K,T> >;
+ friend class hash_iterator<K,T,H,E,const std::pair<const K,T> >;
+
+ unsigned m_rehash;
+ unsigned m_bins;
+ unsigned m_size;
+ hash_element<K,T,H,E>** m_values;
+ };
+
+ ////////////////////////////////////////////////////////////////////////////////
+
+} // end namespace stlplus
+
+#include "hash.tpp"
+#endif
projects / chaz / yoink / blobdiff