ROSE  0.9.10.91
HashMap.h
1 // WARNING: Changes to this file must be contributed back to Sawyer or else they will
2 // be clobbered by the next update from Sawyer. The Sawyer repository is at
3 // https://github.com/matzke1/sawyer.
4 
5 
6 
7 
8 #ifndef Sawyer_HashMap_H
9 #define Sawyer_HashMap_H
10 
11 #include <Sawyer/Optional.h>
12 #include <Sawyer/Sawyer.h>
13 
14 #include <boost/range/iterator_range.hpp>
15 #include <boost/serialization/access.hpp>
16 #include <boost/serialization/nvp.hpp>
17 #include <boost/serialization/split_member.hpp>
18 #include <boost/unordered_map.hpp>
19 #include <stdexcept>
20 
21 namespace Sawyer {
22 namespace Container {
23 
31 template<class K, class T, class H = boost::hash<K>, class C = std::equal_to<K>,
32  class A = std::allocator<std::pair<const K, T> > >
33 class HashMap {
34 public:
35  typedef K Key;
36  typedef T Value;
37  typedef H Hasher;
38  typedef C Comparator;
39  typedef A Allocator;
41 private:
42  typedef boost::unordered_map<Key, Value, Hasher, Comparator, Allocator> ImplMap;
43  ImplMap map_;
44 
45 private:
46  friend class boost::serialization::access;
47 
48  // Apparently no serialization functions for boost::unordered_map, so do it the hard way.
49  template<class S>
50  void save(S &s, const unsigned /*verion*/) const {
51  size_t nElmts = map_.size();
52  s & BOOST_SERIALIZATION_NVP(nElmts);
53  for (typename ImplMap::const_iterator iter = map_.begin(); iter != map_.end(); ++iter) {
54  const Key &key = iter->first;
55  s & BOOST_SERIALIZATION_NVP(key);
56  const Value &value = iter->second;
57  s & BOOST_SERIALIZATION_NVP(value);
58  }
59  }
60 
61  template<class S>
62  void load(S & s, const unsigned /*version*/) {
63  size_t nElmts;
64  s & BOOST_SERIALIZATION_NVP(nElmts);
65  for (size_t i=0; i<nElmts; ++i) {
66  Key key;
67  s & BOOST_SERIALIZATION_NVP(key);
68  Value value;
69  s & BOOST_SERIALIZATION_NVP(value);
70  map_.insert(std::make_pair(key, value));
71  }
72  }
73 
74  BOOST_SERIALIZATION_SPLIT_MEMBER();
75 
76 public:
80  class Node: private ImplMap::value_type {
81  // This class MUST be binary compatible with ImplMap::value_type
82  public:
83  explicit Node(const std::pair<const Key, Value> &pair)
84  : std::pair<const Key, Value>(pair) {}
85 
86  Node(const Key &key, Value &value)
87  : std::pair<const Key, Value>(key, value) {}
88 
92  const Key& key() const { return this->first; }
93 
99  Value& value() { return this->second; }
100  const Value& value() const { return this->second; }
102  };
103 
105  // Iterators
107 private:
108  template<class Derived, class Value, class BaseIterator>
109  class ForwardIterator: public std::iterator<std::forward_iterator_tag, Value> {
110  protected:
111  BaseIterator base_;
112  ForwardIterator() {}
113  ForwardIterator(const BaseIterator &base): base_(base) {}
114  public:
115  Derived& operator=(const Derived &other) { base_ = other.base_; return *derived(); }
116  Derived& operator++() { ++base_; return *derived(); }
117  Derived operator++(int) { Derived old = *derived(); ++*this; return old; }
118  template<class OtherIter> bool operator==(const OtherIter &other) const { return base_ == other.base(); }
119  template<class OtherIter> bool operator!=(const OtherIter &other) const { return base_ != other.base(); }
120  const BaseIterator& base() const { return base_; }
121  protected:
122  Derived* derived() { return static_cast<Derived*>(this); }
123  const Derived* derived() const { return static_cast<const Derived*>(this); }
124  };
125 
126 public:
131  class NodeIterator: public ForwardIterator<NodeIterator, Node, typename ImplMap::iterator> {
132  typedef ForwardIterator<NodeIterator, Node, typename ImplMap::iterator> Super;
133  public:
134  NodeIterator() {}
135  NodeIterator(const NodeIterator &other): Super(other) {}
136  Node& operator*() const { return *(Node*)&*this->base_; } // boost iter's value cast to our own node type
137  Node* operator->() const { return (Node*)&*this->base_; }
138  private:
139  friend class HashMap;
140  NodeIterator(const typename ImplMap::iterator &base): Super(base) {}
141  };
142 
147  class ConstNodeIterator: public ForwardIterator<ConstNodeIterator, const Node, typename ImplMap::const_iterator> {
148  typedef ForwardIterator<ConstNodeIterator, const Node, typename ImplMap::const_iterator> Super;
149  public:
150  ConstNodeIterator() {}
151  ConstNodeIterator(const ConstNodeIterator &other): Super(other) {}
152  ConstNodeIterator(const NodeIterator &other): Super(typename ImplMap::const_iterator(other.base())) {}
153  const Node& operator*() const { return *(const Node*)&*this->base_; }
154  const Node* operator->() const { return (const Node*)&*this->base_; }
155  private:
156  friend class HashMap;
157  ConstNodeIterator(const typename ImplMap::const_iterator &base): Super(base) {}
158  ConstNodeIterator(const typename ImplMap::iterator &base): Super(typename ImplMap::const_iterator(base)) {}
159  };
160 
165  class ConstKeyIterator: public ForwardIterator<ConstKeyIterator, const Key, typename ImplMap::const_iterator> {
166  typedef ForwardIterator<ConstKeyIterator, const Key, typename ImplMap::const_iterator> Super;
167  public:
168  ConstKeyIterator() {}
169  ConstKeyIterator(const ConstKeyIterator &other): Super(other) {}
170  ConstKeyIterator(const NodeIterator &other): Super(typename ImplMap::const_iterator(other.base())) {}
171  ConstKeyIterator(const ConstNodeIterator &other): Super(other.base()) {}
172  const Key& operator*() const { return this->base()->first; }
173  const Key* operator->() const { return &this->base()->first; }
174  };
175 
180  class ValueIterator: public ForwardIterator<ValueIterator, Value, typename ImplMap::iterator> {
181  typedef ForwardIterator<ValueIterator, Value, typename ImplMap::iterator> Super;
182  public:
183  ValueIterator() {}
184  ValueIterator(const ValueIterator &other): Super(other) {}
185  ValueIterator(const NodeIterator &other): Super(other.base()) {}
186  Value& operator*() const { return this->base()->second; }
187  Value* operator->() const { return &this->base()->second; }
188  };
189 
194  class ConstValueIterator: public ForwardIterator<ConstValueIterator, const Value, typename ImplMap::const_iterator> {
195  typedef ForwardIterator<ConstValueIterator, const Value, typename ImplMap::const_iterator> Super;
196  public:
197  ConstValueIterator() {}
198  ConstValueIterator(const ConstValueIterator &other): Super(other) {}
199  ConstValueIterator(const ValueIterator &other): Super(typename ImplMap::const_iterator(other.base())) {}
200  ConstValueIterator(const ConstNodeIterator &other): Super(other.base()) {}
201  ConstValueIterator(const NodeIterator &other): Super(typename ImplMap::const_iterator(other.base())) {}
202  const Value& operator*() const { return this->base()->second; }
203  const Value* operator->() const { return &this->base()->second; }
204  };
205 
207  // Constructors
209 public:
210 
214  HashMap() {}
215 
217  HashMap(size_t n, const Hasher &hasher = Hasher(), const Comparator &cmp = Comparator(), const Allocator& alloc = Allocator())
218  : map_(n, hasher, cmp, alloc) {}
219 
221  HashMap(const HashMap& other)
222  : map_(other.map_) {}
223 
228  template<class K2, class T2, class H2, class C2, class A2>
230  typedef typename HashMap<K2, T2, H2, C2, A2>::ConstNodeIterator OtherIterator;
231  boost::iterator_range<OtherIterator> otherNodes = other.nodes();
232  for (OtherIterator otherIter = otherNodes.begin(); otherIter != otherNodes.end(); ++otherIter)
233  map_.insert(std::make_pair(Key(otherIter->key()), Value(otherIter->value())));
234  }
235 
237  template<class K2, class T2, class H2, class C2, class A2>
239  typedef typename HashMap<K2, T2, H2, C2, A2>::ConstNodeIterator OtherIterator;
240  clear();
241  boost::iterator_range<OtherIterator> otherNodes = other.nodes();
242  for (OtherIterator otherIter = otherNodes.begin(); otherIter != otherNodes.end(); ++otherIter)
243  map_.insert(std::make_pair(Key(otherIter->key()), Value(otherIter->value())));
244  return *this;
245  }
246 
248  // Iteration
250 public:
251 
257  boost::iterator_range<NodeIterator> nodes() {
258  return boost::iterator_range<NodeIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
259  }
260  boost::iterator_range<ConstNodeIterator> nodes() const {
261  return boost::iterator_range<ConstNodeIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
262  }
270  boost::iterator_range<ConstKeyIterator> keys() {
271  return boost::iterator_range<ConstKeyIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
272  }
273  boost::iterator_range<ConstKeyIterator> keys() const {
274  return boost::iterator_range<ConstKeyIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
275  }
284  boost::iterator_range<ValueIterator> values() {
285  return boost::iterator_range<ValueIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
286  }
287  boost::iterator_range<ConstValueIterator> values() const {
288  return boost::iterator_range<ConstValueIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
289  }
292  // Size and capacity
295 public:
296 
300  bool isEmpty() const {
301  return map_.empty();
302  }
303 
308  size_t size() const {
309  return map_.size();
310  }
311 
313  size_t nBuckets() const {
314  return map_.bucket_count();
315  }
316 
318  double loadFactor() const {
319  return map_.load_factor();
320  }
321 
325  double maxLoadFactor() const {
326  return map_.max_load_factor();
327  }
328  void maxLoadFactor(double mlf) {
329  map_.max_load_factor(mlf);
330  }
334  void rehash(size_t nBuckets) {
335  map_.rehash(nBuckets);
336  }
337 
339  // Searching
341 public:
342 
349  NodeIterator find(const Key &key) {
350  return map_.find(key);
351  }
352  ConstNodeIterator find(const Key &key) const {
353  return map_.find(key);
354  }
361  bool exists(const Key &key) const {
362  return map_.find(key) != map_.end();
363  }
364 
366  // Accessors
368 public:
369 
382  Value& operator[](const Key &key) {
383  return get(key);
384  }
385  const Value& operator[](const Key &key) const {
386  return get(key);
387  }
398  Value& get(const Key &key) {
399  typename ImplMap::iterator found = map_.find(key);
400  if (found == map_.end())
401  throw std::domain_error("key lookup failure; key is not in map domain");
402  return found->second;
403  }
404  const Value& get(const Key &key) const {
405  typename ImplMap::const_iterator found = map_.find(key);
406  if (found == map_.end())
407  throw std::domain_error("key lookup failure; key is not in map domain");
408  return found->second;
409  }
434  Optional<Value> getOptional(const Key &key) const {
435  typename ImplMap::const_iterator found = map_.find(key);
436  return found == map_.end() ? Optional<Value>() : Optional<Value>(found->second);
437  }
438 
446  Value& getOrElse(const Key &key, Value &dflt) {
447  typename ImplMap::iterator found = map_.find(key);
448  return found == map_.end() ? dflt : found->second;
449  }
450  const Value& getOrElse(const Key &key, const Value &dflt) const {
451  typename ImplMap::const_iterator found = map_.find(key);
452  return found == map_.end() ? dflt : found->second;
453  }
460  const Value& getOrDefault(const Key &key) const {
461  static const Value dflt;
462  typename ImplMap::const_iterator found = map_.find(key);
463  return found==map_.end() ? dflt : found->second;
464  }
465 
467  // Mutators
469 public:
470 
477  HashMap& insert(const Key &key, const Value &value) {
478  std::pair<typename ImplMap::iterator, bool> inserted = map_.insert(std::make_pair(key, value));
479  if (!inserted.second)
480  inserted.first->second = value;
481  return *this;
482  }
483 
490  HashMap& insertDefault(const Key &key) {
491  return insert(key, Value());
492  }
493 
511  template<class OtherNodeIterator>
512  HashMap& insertMultiple(const OtherNodeIterator &begin, const OtherNodeIterator &end) {
513  for (OtherNodeIterator otherIter = begin; otherIter != end; ++otherIter)
514  insert(Key(otherIter->key()), Value(otherIter->value()));
515  return *this;
516  }
517  template<class OtherNodeIterator>
518  HashMap& insertMultiple(const boost::iterator_range<OtherNodeIterator> &range) {
519  return insertMultiple(range.begin(), range.end());
520  }
530  Value& insertMaybe(const Key &key, const Value &value) {
531  return map_.insert(std::make_pair(key, value)).first->second;
532  }
533 
541  Value& insertMaybeDefault(const Key &key) {
542  return insertMaybe(key, Value());
543  }
544 
551  template<class OtherNodeIterator>
552  HashMap& insertMaybeMultiple(const boost::iterator_range<OtherNodeIterator> &range) {
553  for (OtherNodeIterator otherIter = range.begin(); otherIter != range.end(); ++otherIter)
554  insertMaybe(Key(otherIter->key()), Value(otherIter->value()));
555  return *this;
556  }
557 
563  map_.clear();
564  return *this;
565  }
566 
573  HashMap& erase(const Key &key) {
574  map_.erase(key);
575  return *this;
576  }
577 
585  template<class OtherKeyIterator>
586  HashMap& eraseMultiple(const boost::iterator_range<OtherKeyIterator> &range) {
587  for (OtherKeyIterator otherIter = range.begin(); otherIter != range.end(); ++otherIter)
588  map_.erase(Key(*otherIter));
589  return *this;
590  }
591 
599  HashMap& eraseAt(const NodeIterator &iter) {
600  map_.erase(iter.base());
601  return *this;
602  }
603  HashMap& eraseAt(const ConstKeyIterator &iter) {
604  map_.erase(iter.base());
605  return *this;
606  }
607  HashMap& eraseAt(const ValueIterator &iter) {
608  map_.erase(iter.base());
609  return *this;
610  }
620  template<class Iter>
621  HashMap& eraseAtMultiple(const Iter &begin, const Iter &end) {
622  map_.erase(begin.base(), end.base());
623  return *this;
624  }
625  template<class Iter>
626  HashMap& eraseAtMultiple(const boost::iterator_range<Iter> &range) {
627  map_.erase(range.begin().base(), range.end().base());
628  return *this;
629  }
631 };
632 
633 } // namespace
634 } // namespace
635 
636 #endif
boost::iterator_range< ConstNodeIterator > nodes() const
Iterators for container nodes.
Definition: HashMap.h:260
boost::iterator_range< ConstKeyIterator > keys()
Iterators for container keys.
Definition: HashMap.h:270
Value & insertMaybeDefault(const Key &key)
Conditionally insert a new key with default value.
Definition: HashMap.h:541
boost::iterator_range< ValueIterator > values()
Iterators for container values.
Definition: HashMap.h:284
boost::iterator_range< NodeIterator > nodes()
Iterators for container nodes.
Definition: HashMap.h:257
boost::iterator_range< ConstKeyIterator > keys() const
Iterators for container keys.
Definition: HashMap.h:273
const Value & operator[](const Key &key) const
Return a reference to an existing value.
Definition: HashMap.h:385
H Hasher
Functor for hashing keys.
Definition: HashMap.h:37
HashMap & insertMultiple(const boost::iterator_range< OtherNodeIterator > &range)
Insert multiple values.
Definition: HashMap.h:518
Value & getOrElse(const Key &key, Value &dflt)
Lookup and return a value or something else.
Definition: HashMap.h:446
const Key & key() const
Key part of key/value node.
Definition: HashMap.h:92
HashMap(const HashMap< K2, T2, H2, C2, A2 > &other)
Copy constructor.
Definition: HashMap.h:229
ConstNodeIterator find(const Key &key) const
Find a node by key.
Definition: HashMap.h:352
HashMap & insertMaybeMultiple(const boost::iterator_range< OtherNodeIterator > &range)
Conditionally insert multiple key/value pairs.
Definition: HashMap.h:552
Value & value()
Value part of key/value node.
Definition: HashMap.h:99
Forward iterator over key/value nodes.
Definition: HashMap.h:131
Forward iterator over values.
Definition: HashMap.h:180
const Value & getOrElse(const Key &key, const Value &dflt) const
Lookup and return a value or something else.
Definition: HashMap.h:450
bool isEmpty() const
Determine whether this container is empty.
Definition: HashMap.h:300
HashMap & operator=(const HashMap< K2, T2, H2, C2, A2 > &other)
Assignment operator.
Definition: HashMap.h:238
double maxLoadFactor() const
Property: Maximum allowed load faster before automatic rehash.
Definition: HashMap.h:325
Name space for the entire library.
Definition: Access.h:13
void maxLoadFactor(double mlf)
Property: Maximum allowed load faster before automatic rehash.
Definition: HashMap.h:328
size_t size() const
Number of nodes, keys, or values in this container.
Definition: HashMap.h:308
HashMap()
Default constructor.
Definition: HashMap.h:214
HashMap & insertDefault(const Key &key)
Insert or update a key with a default value.
Definition: HashMap.h:490
Type for stored nodes.
Definition: HashMap.h:80
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
Definition: HashMap.h:434
A Allocator
Functor for allocating node memory.
Definition: HashMap.h:39
HashMap & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
Definition: HashMap.h:477
HashMap & eraseAtMultiple(const Iter &begin, const Iter &end)
Remove multiple nodes by iterator range.
Definition: HashMap.h:621
HashMap & eraseAt(const NodeIterator &iter)
Remove a node by iterator.
Definition: HashMap.h:599
boost::iterator_range< ConstValueIterator > values() const
Iterators for container values.
Definition: HashMap.h:287
NodeIterator find(const Key &key)
Find a node by key.
Definition: HashMap.h:349
HashMap & eraseMultiple(const boost::iterator_range< OtherKeyIterator > &range)
Remove keys stored in another HashMap.
Definition: HashMap.h:586
HashMap(size_t n, const Hasher &hasher=Hasher(), const Comparator &cmp=Comparator(), const Allocator &alloc=Allocator())
Constructs a hash map with at least n buckets.
Definition: HashMap.h:217
HashMap & eraseAt(const ValueIterator &iter)
Remove a node by iterator.
Definition: HashMap.h:607
Value & insertMaybe(const Key &key, const Value &value)
Conditionally insert a new key/value pair.
Definition: HashMap.h:530
Container associating values with keys.
Definition: HashMap.h:33
void rehash(size_t nBuckets)
Change number of buckets.
Definition: HashMap.h:334
Forward iterator over key/value nodes.
Definition: HashMap.h:147
const Value & value() const
Value part of key/value node.
Definition: HashMap.h:100
HashMap(const HashMap &other)
Copy constructor.
Definition: HashMap.h:221
HashMap & clear()
Remove all nodes.
Definition: HashMap.h:562
Forward iterator over values.
Definition: HashMap.h:194
K Key
Type of keys.
Definition: HashMap.h:35
Value & operator[](const Key &key)
Return a reference to an existing value.
Definition: HashMap.h:382
C Comparator
Functor for comparing keys.
Definition: HashMap.h:38
double loadFactor() const
Average number of nodes per bucket.
Definition: HashMap.h:318
HashMap & eraseAtMultiple(const boost::iterator_range< Iter > &range)
Remove multiple nodes by iterator range.
Definition: HashMap.h:626
HashMap & eraseAt(const ConstKeyIterator &iter)
Remove a node by iterator.
Definition: HashMap.h:603
const Value & getOrDefault(const Key &key) const
Lookup and return a value or a default.
Definition: HashMap.h:460
Forward iterator over keys.
Definition: HashMap.h:165
size_t nBuckets() const
Number of buckets.
Definition: HashMap.h:313
bool exists(const Key &key) const
Determine if a key exists.
Definition: HashMap.h:361
T Value
Type of values.
Definition: HashMap.h:36
HashMap & erase(const Key &key)
Remove a node with specified key.
Definition: HashMap.h:573
HashMap & insertMultiple(const OtherNodeIterator &begin, const OtherNodeIterator &end)
Insert multiple values.
Definition: HashMap.h:512