CVC3  2.4.1
hash_map.h
Go to the documentation of this file.
1 /*****************************************************************************/
2 /*!
3  *\file hash_map.h
4  *\brief hash map implementation
5  *
6  * Author: Alexander Fuchs
7  *
8  * Created: Fri Oct 13 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_map.h
49 
50 #ifndef _cvc3__hash__hash_map_h_
51 #define _cvc3__hash__hash_map_h_
52 
53 #include "hash_fun.h"
54 #include "hash_table.h"
55 #include <functional>
56 #include <utility>
57 
58 namespace Hash {
59 
60  // select1st is an extension taken from the SGI
61  // implementation of the STL file functional:
62  // http://www.sgi.com/tech/stl/stl_function.h
63  template <class _Pair>
64  struct _Select1st : public std::unary_function<_Pair, typename _Pair::first_type> {
65  const typename _Pair::first_type& operator()(const _Pair& __x) const {
66  return __x.first;
67  }
68  };
69 
70 
71  /*! hash map implementation based on the sgi interface:
72  http://www.sgi.com/tech/stl/hash_map.html
73 
74  _Key: hash key type
75  _Data: data to store
76  _HashFcn: functional class providing a hash function: size_type (_Key)
77  _EqualKey: functional class providing a comparison function: bool(_Key, _Key)
78  returns true iff two keys are considered to be equal
79  */
80  template <class _Key, class _Data, class _HashFcn = hash<_Key>,
81  class _EqualKey = std::equal_to<_Key> >
82  class hash_map {
83 
84  /// types
85  protected:
86  // note: const _Key must be used for _Value and _ExtractKey.
87  // if one is const and the other is not,
88  // then extracting a key will require a conversion and a temporary
89  // (at least in debug mode),
90  // so that the reference returned by _ExtractKey point to a temporary.
92  _HashFcn, _EqualKey, _Select1st<std::pair<const _Key, _Data> > >
94 
95  public:
96  // typedefs as custom for other implementations
98  typedef typename _hash_table::key_type key_type;
99  typedef _Data data_type;
101  typedef typename _hash_table::hasher hasher;
103 
104  public:
105  // iterators
106  typedef typename _hash_table::iterator iterator;
108 
109  /// variables
110 
111  protected:
112  // the hash table
114 
115 
116  /// methods
117 
118  public:
119  /// constructors
120 
121  // default size is 16 buckets
123  d_table()
124  { };
125 
126  // specifiy initial number of buckets - must be positive
127  hash_map(size_type initial_capacity) :
128  d_table(initial_capacity)
129  { };
130 
131  // specifiy initial number of buckets and hash function
132  hash_map(size_type initial_capacity, const _HashFcn& hash) :
133  d_table(initial_capacity, hash)
134  { };
135 
136  // specifiy initial number of buckets, hash and equal function
137  hash_map(size_type initial_capacity,
138  const _HashFcn& hash, const _EqualKey& equal) :
139  d_table(initial_capacity, hash, equal)
140  { };
141 
142  // copy hash map.
143  hash_map(const hash_map& other) :
144  d_table(other.d_table)
145  { };
146 
147  // assign hash map
148  hash_map& operator=(const hash_map& other) {
149  if (this != &other) {
150  d_table = other.d_table;
151  }
152 
153  return *this;
154  }
155 
156  void swap(hash_map& other) {
157  d_table.swap(other.d_table);
158  }
159 
160  // removes all entries, number of buckets is not reduced.
161  void clear() {
162  d_table.clear();
163  };
164 
165 
166 
167  /// operations
168 
169 
170  // returns end iterator if key was not bound
171  iterator find(const key_type& key) {
172  return d_table.find(key);
173  }
174 
175  // const version of find
176  const_iterator find(const key_type& key) const {
177  return d_table.find(key);
178  }
179 
180  // if key in value is already bound,
181  // returns that binding,
182  // otherwise inserts a default value and returns a reference to it.
184  return d_table.find_or_insert(std::make_pair(key, data_type())).second;
185  }
186 
187 
188  // adds the mapping from key to data, if key is still unbound
189  // otherwise returns false
190  std::pair<iterator, bool> insert(const value_type& entry) {
191  return d_table.insert(entry);
192  }
193 
194  // removes binding of key
195  // returns number of keys removed,
196  // i.e. 1 if key was bound, 0 if key was not bound.
197  size_type erase(const key_type& key) {
198  return d_table.erase(key);
199  }
200 
201  // removes element pointed to by iter,
202  // returns element after iter.
204  return d_table.erase(i);
205  }
206 
207 
208  /// status
209 
210  // is the key bound?
211  bool contains(const key_type& key) const {
212  return d_table.contains(key);
213  }
214 
215  // returns the number of times a key is bound,
216  // i.e. 0 or 1
217  size_type count(const _Key& key) const {
218  return d_table.count(key);
219  }
220 
221  // is the hash map empty?
222  bool empty() const {
223  return d_table.empty();
224  }
225 
226  // the number of elements in the hash map
227  size_type size() const {
228  return d_table.size();
229  }
230 
231  // the number of buckets in the hash map
233  return d_table.bucket_count();
234  }
235 
236  // returns the average number of elements per bucket
237  float load_factor() const {
238  return d_table.load_factor();
239  }
240 
241 
242 
243  /// iterators
244 
245  // returns forward iterator to iterate over all key/data pairs
247  return d_table.begin();
248  }
249 
250  // const version of begin
252  return d_table.begin();
253  }
254 
255 
256  // returns end iterator
258  return d_table.end();
259  }
260 
261  // const version of end
262  const_iterator end() const {
263  return d_table.end();
264  }
265  };
266 
267 }
268 
269 #endif
bool empty() const
Definition: hash_table.h:555
_hash_table::iterator iterator
Definition: hash_map.h:106
size_type count(const _Key &key) const
Definition: hash_map.h:217
hash_map()
methods
Definition: hash_map.h:122
size_type size() const
Definition: hash_map.h:227
const_iterator find(const key_type &key) const
Definition: hash_map.h:176
const_iterator end() const
Definition: hash_map.h:262
void swap(hash_table &other)
Definition: hash_table.h:370
hash_map(const hash_map &other)
Definition: hash_map.h:143
iterator begin()
iterators
Definition: hash_table.h:579
hash_map(size_type initial_capacity, const _HashFcn &hash, const _EqualKey &equal)
Definition: hash_map.h:137
data_type & operator[](const key_type &key)
Definition: hash_map.h:183
_hash_table::key_type key_type
Definition: hash_map.h:98
_hash_table::const_iterator const_iterator
Definition: hash_map.h:107
float load_factor() const
Definition: hash_table.h:570
const _Pair::first_type & operator()(const _Pair &__x) const
Definition: hash_map.h:65
iterator find(const key_type &key)
operations
Definition: hash_map.h:171
size_type erase(const key_type &key)
Definition: hash_map.h:197
bool contains(const key_type &key) const
status
Definition: hash_map.h:211
float load_factor() const
Definition: hash_map.h:237
_hash_table::size_type size_type
Definition: hash_map.h:97
_hash_table::hasher hasher
Definition: hash_map.h:101
iterator begin()
iterators
Definition: hash_map.h:246
void swap(hash_map &other)
Definition: hash_map.h:156
hash_map(size_type initial_capacity, const _HashFcn &hash)
Definition: hash_map.h:132
void clear()
Definition: hash_map.h:161
size_type count(const _Key &key) const
Definition: hash_table.h:545
std::pair< iterator, bool > insert(const value_type &entry)
Definition: hash_map.h:190
iterator end()
Definition: hash_table.h:612
iterator find(const key_type &key)
operations
Definition: hash_table.h:406
hash functions
const_iterator begin() const
Definition: hash_map.h:251
hash_map(size_type initial_capacity)
Definition: hash_map.h:127
size_type bucket_count() const
Definition: hash_table.h:565
size_type bucket_count() const
Definition: hash_map.h:232
size_type size() const
Definition: hash_table.h:560
value_type & find_or_insert(const value_type &value)
Definition: hash_table.h:451
hash_map & operator=(const hash_map &other)
Definition: hash_map.h:148
hash table implementation
_hash_table::value_type value_type
Definition: hash_map.h:100
bool contains(const key_type &key) const
status
Definition: hash_table.h:539
_Data data_type
Definition: hash_map.h:99
_hash_table d_table
variables
Definition: hash_map.h:113
bool empty() const
Definition: hash_map.h:222
std::pair< iterator, bool > insert(const value_type &value)
Definition: hash_table.h:428
size_type erase(const key_type &key)
Definition: hash_table.h:475
hash_table< _Key, std::pair< const _Key, _Data >, _HashFcn, _EqualKey, _Select1st< std::pair< const _Key, _Data > > > _hash_table
types
Definition: hash_map.h:93
_hash_table::key_equal key_equal
Definition: hash_map.h:102
iterator end()
Definition: hash_map.h:257
const_iterator erase(const const_iterator &i)
Definition: hash_map.h:203