]>
Dogcows Code - chaz/yoink/blob - hash.hpp
13e9541f81d0cc2ff31320b60ae0f592eef590d6
3 ////////////////////////////////////////////////////////////////////////////////
5 // Author: Andy Rushton
6 // Copyright: (c) Southampton University 1999-2004
7 // (c) Andy Rushton 2004-2009
8 // License: BSD License, see ../docs/license.html
10 // A chained hash table using STL semantics
12 ////////////////////////////////////////////////////////////////////////////////
13 #include "containers_fixes.hpp"
14 #include "exceptions.hpp"
15 #include "safe_iterator.hpp"
22 ////////////////////////////////////////////////////////////////////////////////
25 template<typename K
, typename T
, class H
, class E
> class hash
;
26 template<typename K
, typename T
, class H
, class E
> class hash_element
;
28 ////////////////////////////////////////////////////////////////////////////////
31 template<typename K
, typename T
, class H
, class E
, typename V
>
32 class hash_iterator
: public safe_iterator
<hash
<K
,T
,H
,E
>,hash_element
<K
,T
,H
,E
> >
35 friend class hash
<K
,T
,H
,E
>;
37 // local type definitions
38 // an iterator points to a value whilst a const_iterator points to a const value
40 typedef hash_iterator
<K
,T
,H
,E
,std::pair
<const K
,T
> > iterator
;
41 typedef hash_iterator
<K
,T
,H
,E
,const std::pair
<const K
,T
> > const_iterator
;
42 typedef hash_iterator
<K
,T
,H
,E
,V
> this_iterator
;
46 // constructor to create a null iterator - you must assign a valid value to this iterator before using it
47 // any attempt to dereference or use a null iterator is an error
48 // the only valid thing you can do is assign an iterator to it
52 // Type conversion methods allow const_iterator and iterator to be converted
53 // convert an iterator/const_iterator to a const_iterator
54 const_iterator
constify(void) const;
55 // convert an iterator/const_iterator to an iterator
56 iterator
deconstify(void) const;
58 // increment operators used to step through the set of all values in a hash
59 // it is only legal to increment a valid iterator
60 // there's no decrement - I've only implemented this as a unidirectional iterator
62 this_iterator
& operator ++ (void)
63 throw(null_dereference
,end_dereference
);
65 this_iterator
operator ++ (int)
66 throw(null_dereference
,end_dereference
);
68 // test useful for testing whether iteration has completed
69 bool operator == (const this_iterator
& r
) const;
70 bool operator != (const this_iterator
& r
) const;
71 bool operator < (const this_iterator
& r
) const;
73 // access the value - a const_iterator gives you a const value, an iterator a non-const value
74 // it is illegal to dereference an invalid (i.e. null or end) iterator
75 reference
operator*(void) const
76 throw(null_dereference
,end_dereference
);
77 pointer
operator->(void) const
78 throw(null_dereference
,end_dereference
);
81 friend class hash_element
<K
,T
,H
,E
>;
83 // constructor used by hash to create a non-null iterator
84 // you cannot create a valid iterator except by calling a hash method that returns one
85 explicit hash_iterator(hash_element
<K
,T
,H
,E
>* element
);
86 // constructor used to create an end iterator
87 explicit hash_iterator(const hash
<K
,T
,H
,E
>* owner
);
88 // used to create an alias of an iterator
89 explicit hash_iterator(const safe_iterator
<hash
<K
,T
,H
,E
>, hash_element
<K
,T
,H
,E
> >& iterator
);
92 ////////////////////////////////////////////////////////////////////////////////
96 // H = hash function object with the profile 'unsigned H(const K&)'
97 // E = equal function object with profile 'bool E(const K&, const K&)' defaults to equal_to which in turn calls '=='
99 template<typename K
, typename T
, class H
, class E
= std::equal_to
<K
> >
103 typedef unsigned size_type
;
106 typedef T mapped_type
;
107 typedef std::pair
<const K
, T
> value_type
;
108 typedef hash_iterator
<K
,T
,H
,E
,value_type
> iterator
;
109 typedef hash_iterator
<K
,T
,H
,E
,const value_type
> const_iterator
;
111 // construct a hash table with specified number of bins
112 // the default 0 bins means leave it to the table to decide
113 // specifying 0 bins also enables auto-rehashing, otherwise auto-rehashing defaults off
114 hash(unsigned bins
= 0);
117 // copy and equality copy the data elements but not the size of the copied table
119 hash
& operator = (const hash
&);
121 // test for an empty table and for the size of a table
122 // efficient because the size is stored separately from the table contents
123 bool empty(void) const;
124 unsigned size(void) const;
126 // test for equality - two hashes are equal if they contain equal values
127 bool operator == (const hash
&) const;
128 bool operator != (const hash
&) const;
130 // switch auto-rehash on
131 void auto_rehash(void);
132 // switch auto-rehash off
133 void manual_rehash(void);
134 // force a rehash now
135 // default of 0 means implement built-in size calculation for rehashing (recommended - it doubles the number of bins)
136 void rehash(unsigned bins
= 0);
137 // test the loading ratio, which is the size divided by the number of bins
138 // use this if you are doing your own rehashing
139 // the recommendation is to double the bins when the loading exceeds 0.5 which is what auto-rehashing does
140 float loading(void) const;
142 // test for the presence of a key
143 bool present(const K
& key
) const;
144 // provide map equivalent key count function (0 or 1, as not a multimap)
145 size_type
count(const K
& key
) const;
147 // insert a new key/data pair - replaces any previous value for this key
148 iterator
insert(const K
& key
, const T
& data
);
149 // insert a copy of the pair into the table (std::map compatible)
150 std::pair
<iterator
, bool> insert(const value_type
& value
);
151 // insert a new key and return the iterator so that the data can be filled in
152 iterator
insert(const K
& key
);
154 // remove a key/data pair from the hash table
155 // as in map, this returns the number of elements erased
156 size_type
erase(const K
& key
);
157 // remove an element from the hash table using an iterator
158 // as in map, returns an iterator to the next element
159 iterator
erase(iterator it
);
160 // remove all elements from the hash table
162 // map equivalent of above
165 // find a key and return an iterator to it
166 // The iterator is like a pointer to a pair<const K,T>
167 // end() is returned if the find fails
168 const_iterator
find(const K
& key
) const;
169 iterator
find(const K
& key
);
171 // returns the data corresponding to the key
172 // const version is used for const hashes and cannot change the hash, so failure causes an exception
173 // non-const version is for non-const hashes and is like map - it creates a new key/data pair if find fails
174 const T
& operator[] (const K
& key
) const throw(std::out_of_range
);
175 T
& operator[] (const K
& key
);
177 // iterators allow the hash table to be traversed
178 // iterators remain valid unless an item is removed or unless a rehash happens
179 const_iterator
begin(void) const;
180 iterator
begin(void);
181 const_iterator
end(void) const;
184 // diagnostic report shows the number of items in each bin so can be used
185 // to diagnose effectiveness of hash functions
186 void debug_report(std::ostream
&) const;
190 friend class hash_element
<K
,T
,H
,E
>;
191 friend class hash_iterator
<K
,T
,H
,E
,std::pair
<const K
,T
> >;
192 friend class hash_iterator
<K
,T
,H
,E
,const std::pair
<const K
,T
> >;
197 hash_element
<K
,T
,H
,E
>** m_values
;
200 ////////////////////////////////////////////////////////////////////////////////
202 } // end namespace stlplus
This page took 0.046073 seconds and 3 git commands to generate.