CVC3  2.4.1
hash_set.h
Go to the documentation of this file.
1 /*****************************************************************************/
2 /*!
3  *\file hash_set.h
4  *\brief hash map implementation
5  *
6  * Author: Alexander Fuchs
7  *
8  * Created: Thu Oct 19 11:04:00 2006
9  *
10  * <hr>
11  *
12  * License to use, copy, modify, sell and/or distribute this software
13  * and its documentation for any purpose is hereby granted without
14  * royalty, subject to the terms and conditions defined in the \ref
15  * LICENSE file provided with this distribution.
16  *
17  * <hr>
18  */
19 /*****************************************************************************/
20 
21 /*
22  * Copyright (c) 1996,1997
23  * Silicon Graphics Computer Systems, Inc.
24  *
25  * Permission to use, copy, modify, distribute and sell this software
26  * and its documentation for any purpose is hereby granted without fee,
27  * provided that the above copyright notice appear in all copies and
28  * that both that copyright notice and this permission notice appear
29  * in supporting documentation. Silicon Graphics makes no
30  * representations about the suitability of this software for any
31  * purpose. It is provided "as is" without express or implied warranty.
32  *
33  *
34  * Copyright (c) 1994
35  * Hewlett-Packard Company
36  *
37  * Permission to use, copy, modify, distribute and sell this software
38  * and its documentation for any purpose is hereby granted without fee,
39  * provided that the above copyright notice appear in all copies and
40  * that both that copyright notice and this permission notice appear
41  * in supporting documentation. Hewlett-Packard Company makes no
42  * representations about the suitability of this software for any
43  * purpose. It is provided "as is" without express or implied warranty.
44  *
45  */
46 
47 // this implementation is in essence a subset of the SGI implementation:
48 // http://www.sgi.com/tech/stl/stl_hash_set.h
49 
50 #ifndef _cvc3__hash__hash_set_h_
51 #define _cvc3__hash__hash_set_h_
52 
53 
54 #include "hash_fun.h"
55 #include "hash_table.h"
56 
57 namespace Hash {
58 
59  // identity is an extension taken from the SGI
60  // implementation of the STL file functional:
61  // http://www.sgi.com/tech/stl/stl_function.h
62  template <class _Tp>
63  struct _Identity : public std::unary_function<_Tp,_Tp> {
64  const _Tp& operator()(const _Tp& __x) const { return __x; }
65  };
66 
67 
68  /*! hash set implementation based on the sgi interface:
69  http://www.sgi.com/tech/stl/hash_set.html
70 
71  _Key: hash key type
72  _HashFcn: functional class providing a hash function: size_type (_Key)
73  _EqualKey: functional class providing a comparison function: bool(_Key, _Key)
74  returns true iff two keys are considered to be equal
75  */
76  template <class _Key, class _HashFcn = hash<_Key>,
77  class _EqualKey = std::equal_to<_Key> >
78  class hash_set {
79 
80  /// types
81  protected:
83 
84  public:
85  // typedefs as custom for other implementations
87  typedef typename _hash_table::key_type key_type;
89  typedef typename _hash_table::hasher hasher;
91 
92  public:
93  // iterators
94  typedef typename _hash_table::iterator iterator;
96 
97 
98 
99  /// variables
100 
101  protected:
102  // the hash table
103  _hash_table d_table;
104 
105 
106  /// methods
107 
108  public:
109  /// constructors
110 
111  // default size is 16 buckets
113  d_table()
114  { };
115 
116  // specifiy initial number of buckets - must be positive
117  hash_set(size_type initial_capacity) :
118  d_table(initial_capacity)
119  { };
120 
121  // specifiy initial number of buckets and hash function
122  hash_set(size_type initial_capacity, const _HashFcn& hash) :
123  d_table(initial_capacity, hash)
124  { };
125 
126  // specifiy initial number of buckets, hash and equal function
127  hash_set(size_type initial_capacity,
128  const _HashFcn& hash, const _EqualKey& equal) :
129  d_table(initial_capacity, hash, equal)
130  { };
131 
132  // copy hash map.
133  hash_set(const hash_set& other) :
134  d_table(other.d_table)
135  { };
136 
137  // assign hash map
138  hash_set& operator=(const hash_set& other) {
139  if (this != &other) {
140  d_table = other.d_table;
141  }
142 
143  return *this;
144  }
145 
146  void swap(hash_set& other) {
147  d_table.swap(other.d_table);
148  }
149 
150  // removes all entries, number of buckets is not reduced.
151  void clear() {
152  d_table.clear();
153  };
154 
155 
156 
157  /// operations
158 
159 
160  // returns end iterator if key was not bound
161  iterator find(const key_type& key) {
162  return d_table.find(key);
163  }
164 
165  // const version of find
166  const_iterator find(const key_type& key) const {
167  return d_table.find(key);
168  }
169 
170 
171  // adds the mapping from key to data, if key is still unbound
172  // otherwise returns false
173  std::pair<iterator, bool> insert(const value_type& entry) {
174  return d_table.insert(entry);
175  }
176 
177  // removes binding of key
178  // returns number of keys removed,
179  // i.e. 1 if key was bound, 0 if key was not bound.
180  size_type erase(const key_type& key) {
181  return d_table.erase(key);
182  }
183 
184 
185 
186  /// status
187 
188  // is the key bound?
189  bool contains(const key_type& key) const {
190  return d_table.contains(key);
191  }
192 
193  // returns the number of times a key is bound,
194  // i.e. 0 or 1
195  size_type count(const _Key& key) const {
196  return d_table.count(key);
197  }
198 
199  // is the hash map empty?
200  bool empty() const {
201  return d_table.empty();
202  }
203 
204  // the number of elements in the hash map
205  size_type size() const {
206  return d_table.size();
207  }
208 
209  // the number of buckets in the hash map
210  size_type bucket_count() const {
211  return d_table.bucket_count();
212  }
213 
214  // returns the average number of elements per bucket
215  float load_factor() const {
216  return d_table.load_factor();
217  }
218 
219 
220 
221  /// iterators
222 
223  // returns forward iterator to iterate over all key/data pairs
224  iterator begin() {
225  return d_table.begin();
226  }
227 
228  // const version of begin
229  const_iterator begin() const {
230  return d_table.begin();
231  }
232 
233 
234  // returns end iterator
235  iterator end() {
236  return d_table.end();
237  }
238 
239  // const version of end
240  const_iterator end() const {
241  return d_table.end();
242  }
243  };
244 
245 }
246 
247 #endif
_hash_table::hasher hasher
Definition: hash_set.h:89
bool empty() const
Definition: hash_table.h:555
hash_set(const hash_set &other)
Definition: hash_set.h:133
float load_factor() const
Definition: hash_set.h:215
void clear()
Definition: hash_set.h:151
const_iterator begin() const
Definition: hash_set.h:229
size_type count(const _Key &key) const
Definition: hash_set.h:195
const_iterator end() const
Definition: hash_set.h:240
hash_set()
methods
Definition: hash_set.h:112
void swap(hash_table &other)
Definition: hash_table.h:370
_hash_table::iterator iterator
Definition: hash_set.h:94
_hash_table::value_type value_type
Definition: hash_set.h:88
const _Tp & operator()(const _Tp &__x) const
Definition: hash_set.h:64
size_type size() const
Definition: hash_set.h:205
iterator begin()
iterators
Definition: hash_table.h:579
float load_factor() const
Definition: hash_table.h:570
hash_set(size_type initial_capacity, const _HashFcn &hash)
Definition: hash_set.h:122
_hash_table::key_equal key_equal
Definition: hash_set.h:90
size_type bucket_count() const
Definition: hash_set.h:210
hash_set(size_type initial_capacity, const _HashFcn &hash, const _EqualKey &equal)
Definition: hash_set.h:127
size_type erase(const key_type &key)
Definition: hash_set.h:180
size_type count(const _Key &key) const
Definition: hash_table.h:545
iterator end()
Definition: hash_table.h:612
_hash_table d_table
variables
Definition: hash_set.h:103
iterator begin()
iterators
Definition: hash_set.h:224
hash_set & operator=(const hash_set &other)
Definition: hash_set.h:138
Definition: expr_hash.h:32
iterator find(const key_type &key)
operations
Definition: hash_table.h:406
_hash_table::key_type key_type
Definition: hash_set.h:87
std::pair< iterator, bool > insert(const value_type &entry)
Definition: hash_set.h:173
hash functions
size_type bucket_count() const
Definition: hash_table.h:565
size_type size() const
Definition: hash_table.h:560
hash table implementation
hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > > _hash_table
types
Definition: hash_set.h:82
iterator end()
Definition: hash_set.h:235
const_iterator find(const key_type &key) const
Definition: hash_set.h:166
bool contains(const key_type &key) const
status
Definition: hash_table.h:539
bool contains(const key_type &key) const
status
Definition: hash_set.h:189
hash_set(size_type initial_capacity)
Definition: hash_set.h:117
bool empty() const
Definition: hash_set.h:200
std::pair< iterator, bool > insert(const value_type &value)
Definition: hash_table.h:428
_hash_table::const_iterator const_iterator
Definition: hash_set.h:95
size_type erase(const key_type &key)
Definition: hash_table.h:475
iterator find(const key_type &key)
operations
Definition: hash_set.h:161
void swap(hash_set &other)
Definition: hash_set.h:146
_hash_table::size_type size_type
Definition: hash_set.h:86