ROSE 0.11.145.147
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://gitlab.com/charger7534/sawyer.git.
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/unordered_map.hpp>
16#include <stdexcept>
17
18namespace Sawyer {
19namespace Container {
20
28template<class K, class T, class H = boost::hash<K>, class C = std::equal_to<K>,
29 class A = std::allocator<std::pair<const K, T> > >
30class HashMap {
31public:
32 typedef K Key;
33 typedef T Value;
34 typedef H Hasher;
35 typedef C Comparator;
36 typedef A Allocator;
38private:
39 typedef boost::unordered_map<Key, Value, Hasher, Comparator, Allocator> ImplMap;
40 ImplMap map_;
41
42#ifdef SAWYER_HAVE_BOOST_SERIALIZATION
43private:
44 friend class boost::serialization::access;
45
46 // Apparently no serialization functions for boost::unordered_map, so do it the hard way.
47 template<class S>
48 void save(S &s, const unsigned /*verion*/) const {
49 size_t nElmts = map_.size();
50 s & BOOST_SERIALIZATION_NVP(nElmts);
51 for (typename ImplMap::const_iterator iter = map_.begin(); iter != map_.end(); ++iter) {
52 const Key &key = iter->first;
53 s & BOOST_SERIALIZATION_NVP(key);
54 const Value &value = iter->second;
55 s & BOOST_SERIALIZATION_NVP(value);
56 }
57 }
58
59 template<class S>
60 void load(S & s, const unsigned /*version*/) {
61 size_t nElmts;
62 s & BOOST_SERIALIZATION_NVP(nElmts);
63 for (size_t i=0; i<nElmts; ++i) {
64 Key key;
65 s & BOOST_SERIALIZATION_NVP(key);
66 Value value;
67 s & BOOST_SERIALIZATION_NVP(value);
68 map_.insert(std::make_pair(key, value));
69 }
70 }
71
72 BOOST_SERIALIZATION_SPLIT_MEMBER();
73#endif
74
75#ifdef SAWYER_HAVE_CEREAL
76private:
77 friend class cereal::access;
78
79 // Apparently no serialization functions for boost::unordered_map, so do it the hard way.
80 template<class Archive>
81 void CEREAL_SAVE_FUNCTION_NAME(Archive &archive) const {
82 size_t nElmts = map_.size();
83 archive(CEREAL_NVP(nElmts));
84 for (typename ImplMap::const_iterator iter = map_.begin(); iter != map_.end(); ++iter) {
85 const Key &key = iter->first;
86 archive(CEREAL_NVP(key));
87 const Value &value = iter->second;
88 archive(CEREAL_NVP(value));
89 }
90 }
91
92 template<class Archive>
93 void CEREAL_LOAD_FUNCTION_NAME(Archive &archive) {
94 size_t nElmts;
95 archive(CEREAL_NVP(nElmts));
96 for (size_t i = 0; i < nElmts; ++i) {
97 Key key;
98 archive(CEREAL_NVP(key));
99 Value value;
100 archive(CEREAL_NVP(key));
101 map_.insert(std::make_pair(key, value));
102 }
103 }
104#endif
105
106
107public:
111 class Node: private ImplMap::value_type {
112 // This class MUST be binary compatible with ImplMap::value_type
113 public:
114 explicit Node(const std::pair<const Key, Value> &pair)
115 : std::pair<const Key, Value>(pair) {}
116
117 Node(const Key &key, Value &value)
118 : std::pair<const Key, Value>(key, value) {}
119
123 const Key& key() const { return this->first; }
124
130 Value& value() { return this->second; }
131 const Value& value() const { return this->second; }
133 };
134
136 // Iterators
138private:
139 template<class Derived, class Value, class BaseIterator>
140 class ForwardIterator {
141 public:
142 // Five standard iterator types
143 using iterator_category = std::forward_iterator_tag;
144 using value_type = Value;
145 using difference_type = std::ptrdiff_t;
146 using pointer = Value*;
147 using reference = Value&;
148
149 protected:
150 BaseIterator base_;
151 ForwardIterator() {}
152 ForwardIterator(const BaseIterator &base): base_(base) {}
153 public:
154 Derived& operator=(const Derived &other) { base_ = other.base_; return *derived(); }
155 Derived& operator++() { ++base_; return *derived(); }
156 Derived operator++(int) { Derived old = *derived(); ++*this; return old; }
157 template<class OtherIter> bool operator==(const OtherIter &other) const { return base_ == other.base(); }
158 template<class OtherIter> bool operator!=(const OtherIter &other) const { return base_ != other.base(); }
159 const BaseIterator& base() const { return base_; }
160 protected:
161 Derived* derived() { return static_cast<Derived*>(this); }
162 const Derived* derived() const { return static_cast<const Derived*>(this); }
163 };
164
165public:
170 class NodeIterator: public ForwardIterator<NodeIterator, Node, typename ImplMap::iterator> {
171 typedef ForwardIterator<NodeIterator, Node, typename ImplMap::iterator> Super;
172 public:
173 NodeIterator() {}
174 NodeIterator(const NodeIterator &other): Super(other) {}
175 Node& operator*() const { return *(Node*)&*this->base_; } // boost iter's value cast to our own node type
176 Node* operator->() const { return (Node*)&*this->base_; }
177 private:
178 friend class HashMap;
179 NodeIterator(const typename ImplMap::iterator &base): Super(base) {}
180 };
181
186 class ConstNodeIterator: public ForwardIterator<ConstNodeIterator, const Node, typename ImplMap::const_iterator> {
187 typedef ForwardIterator<ConstNodeIterator, const Node, typename ImplMap::const_iterator> Super;
188 public:
190 ConstNodeIterator(const ConstNodeIterator &other): Super(other) {}
191 ConstNodeIterator(const NodeIterator &other): Super(typename ImplMap::const_iterator(other.base())) {}
192 const Node& operator*() const { return *(const Node*)&*this->base_; }
193 const Node* operator->() const { return (const Node*)&*this->base_; }
194 private:
195 friend class HashMap;
196 ConstNodeIterator(const typename ImplMap::const_iterator &base): Super(base) {}
197 ConstNodeIterator(const typename ImplMap::iterator &base): Super(typename ImplMap::const_iterator(base)) {}
198 };
199
204 class ConstKeyIterator: public ForwardIterator<ConstKeyIterator, const Key, typename ImplMap::const_iterator> {
205 typedef ForwardIterator<ConstKeyIterator, const Key, typename ImplMap::const_iterator> Super;
206 public:
208 ConstKeyIterator(const ConstKeyIterator &other): Super(other) {}
209 ConstKeyIterator(const NodeIterator &other): Super(typename ImplMap::const_iterator(other.base())) {}
210 ConstKeyIterator(const ConstNodeIterator &other): Super(other.base()) {}
211 const Key& operator*() const { return this->base()->first; }
212 const Key* operator->() const { return &this->base()->first; }
213 };
214
219 class ValueIterator: public ForwardIterator<ValueIterator, Value, typename ImplMap::iterator> {
220 typedef ForwardIterator<ValueIterator, Value, typename ImplMap::iterator> Super;
221 public:
222 ValueIterator() {}
223 ValueIterator(const ValueIterator &other): Super(other) {}
224 ValueIterator(const NodeIterator &other): Super(other.base()) {}
225 Value& operator*() const { return this->base()->second; }
226 Value* operator->() const { return &this->base()->second; }
227 };
228
233 class ConstValueIterator: public ForwardIterator<ConstValueIterator, const Value, typename ImplMap::const_iterator> {
234 typedef ForwardIterator<ConstValueIterator, const Value, typename ImplMap::const_iterator> Super;
235 public:
237 ConstValueIterator(const ConstValueIterator &other): Super(other) {}
238 ConstValueIterator(const ValueIterator &other): Super(typename ImplMap::const_iterator(other.base())) {}
239 ConstValueIterator(const ConstNodeIterator &other): Super(other.base()) {}
240 ConstValueIterator(const NodeIterator &other): Super(typename ImplMap::const_iterator(other.base())) {}
241 const Value& operator*() const { return this->base()->second; }
242 const Value* operator->() const { return &this->base()->second; }
243 };
244
246 // Constructors
248public:
249
254
256 HashMap(size_t n, const Hasher &hasher = Hasher(), const Comparator &cmp = Comparator(), const Allocator& alloc = Allocator())
257 : map_(n, hasher, cmp, alloc) {}
258
260 HashMap(const HashMap& other)
261 : map_(other.map_) {}
262
267 template<class K2, class T2, class H2, class C2, class A2>
269 typedef typename HashMap<K2, T2, H2, C2, A2>::ConstNodeIterator OtherIterator;
270 boost::iterator_range<OtherIterator> otherNodes = other.nodes();
271 for (OtherIterator otherIter = otherNodes.begin(); otherIter != otherNodes.end(); ++otherIter)
272 map_.insert(std::make_pair(Key(otherIter->key()), Value(otherIter->value())));
273 }
274
276 template<class K2, class T2, class H2, class C2, class A2>
278 typedef typename HashMap<K2, T2, H2, C2, A2>::ConstNodeIterator OtherIterator;
279 clear();
280 boost::iterator_range<OtherIterator> otherNodes = other.nodes();
281 for (OtherIterator otherIter = otherNodes.begin(); otherIter != otherNodes.end(); ++otherIter)
282 map_.insert(std::make_pair(Key(otherIter->key()), Value(otherIter->value())));
283 return *this;
284 }
285
287 // Iteration
289public:
290
296 boost::iterator_range<NodeIterator> nodes() {
297 return boost::iterator_range<NodeIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
298 }
299 boost::iterator_range<ConstNodeIterator> nodes() const {
300 return boost::iterator_range<ConstNodeIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
301 }
309 boost::iterator_range<ConstKeyIterator> keys() {
310 return boost::iterator_range<ConstKeyIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
311 }
312 boost::iterator_range<ConstKeyIterator> keys() const {
313 return boost::iterator_range<ConstKeyIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
314 }
323 boost::iterator_range<ValueIterator> values() {
324 return boost::iterator_range<ValueIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
325 }
326 boost::iterator_range<ConstValueIterator> values() const {
327 return boost::iterator_range<ConstValueIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
328 }
332 // Size and capacity
334public:
335
339 bool isEmpty() const {
340 return map_.empty();
341 }
342
347 size_t size() const {
348 return map_.size();
349 }
350
352 size_t nBuckets() const {
353 return map_.bucket_count();
354 }
355
357 double loadFactor() const {
358 return map_.load_factor();
359 }
360
364 double maxLoadFactor() const {
365 return map_.max_load_factor();
366 }
367 void maxLoadFactor(double mlf) {
368 map_.max_load_factor(mlf);
369 }
373 void rehash(size_t nBuckets) {
374 map_.rehash(nBuckets);
375 }
376
378 // Searching
380public:
381
388 NodeIterator find(const Key &key) {
389 return map_.find(key);
390 }
391 ConstNodeIterator find(const Key &key) const {
392 return map_.find(key);
393 }
400 bool exists(const Key &key) const {
401 return map_.find(key) != map_.end();
402 }
403
405 // Accessors
407public:
408
421 Value& operator[](const Key &key) {
422 return get(key);
423 }
424 const Value& operator[](const Key &key) const {
425 return get(key);
426 }
437 Value& get(const Key &key) {
438 typename ImplMap::iterator found = map_.find(key);
439 if (found == map_.end())
440 throw std::domain_error("key lookup failure; key is not in map domain");
441 return found->second;
442 }
443 const Value& get(const Key &key) const {
444 typename ImplMap::const_iterator found = map_.find(key);
445 if (found == map_.end())
446 throw std::domain_error("key lookup failure; key is not in map domain");
447 return found->second;
448 }
473 Optional<Value> getOptional(const Key &key) const {
474 typename ImplMap::const_iterator found = map_.find(key);
475 return found == map_.end() ? Optional<Value>() : Optional<Value>(found->second);
476 }
477
485 Value& getOrElse(const Key &key, Value &dflt) {
486 typename ImplMap::iterator found = map_.find(key);
487 return found == map_.end() ? dflt : found->second;
488 }
489 const Value& getOrElse(const Key &key, const Value &dflt) const {
490 typename ImplMap::const_iterator found = map_.find(key);
491 return found == map_.end() ? dflt : found->second;
492 }
499 const Value& getOrDefault(const Key &key) const {
500 static const Value dflt;
501 typename ImplMap::const_iterator found = map_.find(key);
502 return found==map_.end() ? dflt : found->second;
503 }
504
506 // Mutators
508public:
509
516 HashMap& insert(const Key &key, const Value &value) {
517 std::pair<typename ImplMap::iterator, bool> inserted = map_.insert(std::make_pair(key, value));
518 if (!inserted.second)
519 inserted.first->second = value;
520 return *this;
521 }
522
529 HashMap& insertDefault(const Key &key) {
530 return insert(key, Value());
531 }
532
550 template<class OtherNodeIterator>
551 HashMap& insertMultiple(const OtherNodeIterator &begin, const OtherNodeIterator &end) {
552 for (OtherNodeIterator otherIter = begin; otherIter != end; ++otherIter)
553 insert(Key(otherIter->key()), Value(otherIter->value()));
554 return *this;
555 }
556 template<class OtherNodeIterator>
557 HashMap& insertMultiple(const boost::iterator_range<OtherNodeIterator> &range) {
558 return insertMultiple(range.begin(), range.end());
559 }
569 Value& insertMaybe(const Key &key, const Value &value) {
570 return map_.insert(std::make_pair(key, value)).first->second;
571 }
572
581 return insertMaybe(key, Value());
582 }
583
590 template<class OtherNodeIterator>
591 HashMap& insertMaybeMultiple(const boost::iterator_range<OtherNodeIterator> &range) {
592 for (OtherNodeIterator otherIter = range.begin(); otherIter != range.end(); ++otherIter)
593 insertMaybe(Key(otherIter->key()), Value(otherIter->value()));
594 return *this;
595 }
596
602 map_.clear();
603 return *this;
604 }
605
612 HashMap& erase(const Key &key) {
613 map_.erase(key);
614 return *this;
615 }
616
624 template<class OtherKeyIterator>
625 HashMap& eraseMultiple(const boost::iterator_range<OtherKeyIterator> &range) {
626 for (OtherKeyIterator otherIter = range.begin(); otherIter != range.end(); ++otherIter)
627 map_.erase(Key(*otherIter));
628 return *this;
629 }
630
639 map_.erase(iter.base());
640 return *this;
641 }
643 map_.erase(iter.base());
644 return *this;
645 }
647 map_.erase(iter.base());
648 return *this;
649 }
659 template<class Iter>
660 HashMap& eraseAtMultiple(const Iter &begin, const Iter &end) {
661 map_.erase(begin.base(), end.base());
662 return *this;
663 }
664 template<class Iter>
665 HashMap& eraseAtMultiple(const boost::iterator_range<Iter> &range) {
666 map_.erase(range.begin().base(), range.end().base());
667 return *this;
668 }
670};
671
672} // namespace
673} // namespace
674
675#endif
Forward iterator over keys.
Definition HashMap.h:204
Forward iterator over key/value nodes.
Definition HashMap.h:186
Forward iterator over values.
Definition HashMap.h:233
Forward iterator over key/value nodes.
Definition HashMap.h:170
Type for stored nodes.
Definition HashMap.h:111
const Key & key() const
Key part of key/value node.
Definition HashMap.h:123
Value & value()
Value part of key/value node.
Definition HashMap.h:130
const Value & value() const
Value part of key/value node.
Definition HashMap.h:131
Forward iterator over values.
Definition HashMap.h:219
Container associating values with keys.
Definition HashMap.h:30
size_t nBuckets() const
Number of buckets.
Definition HashMap.h:352
HashMap & eraseAtMultiple(const Iter &begin, const Iter &end)
Remove multiple nodes by iterator range.
Definition HashMap.h:660
Value & operator[](const Key &key)
Return a reference to an existing value.
Definition HashMap.h:421
void rehash(size_t nBuckets)
Change number of buckets.
Definition HashMap.h:373
C Comparator
Functor for comparing keys.
Definition HashMap.h:35
void maxLoadFactor(double mlf)
Property: Maximum allowed load faster before automatic rehash.
Definition HashMap.h:367
HashMap & eraseAt(const ValueIterator &iter)
Remove a node by iterator.
Definition HashMap.h:646
A Allocator
Functor for allocating node memory.
Definition HashMap.h:36
HashMap & eraseMultiple(const boost::iterator_range< OtherKeyIterator > &range)
Remove keys stored in another HashMap.
Definition HashMap.h:625
boost::iterator_range< ValueIterator > values()
Iterators for container values.
Definition HashMap.h:323
HashMap & eraseAt(const NodeIterator &iter)
Remove a node by iterator.
Definition HashMap.h:638
HashMap()
Default constructor.
Definition HashMap.h:253
const Value & operator[](const Key &key) const
Return a reference to an existing value.
Definition HashMap.h:424
boost::iterator_range< ConstValueIterator > values() const
Iterators for container values.
Definition HashMap.h:326
T Value
Type of values.
Definition HashMap.h:33
HashMap(const HashMap &other)
Copy constructor.
Definition HashMap.h:260
double maxLoadFactor() const
Property: Maximum allowed load faster before automatic rehash.
Definition HashMap.h:364
H Hasher
Functor for hashing keys.
Definition HashMap.h:34
Value & getOrElse(const Key &key, Value &dflt)
Lookup and return a value or something else.
Definition HashMap.h:485
Value & insertMaybeDefault(const Key &key)
Conditionally insert a new key with default value.
Definition HashMap.h:580
HashMap & insertMaybeMultiple(const boost::iterator_range< OtherNodeIterator > &range)
Conditionally insert multiple key/value pairs.
Definition HashMap.h:591
const Value & get(const Key &key) const
Lookup and retun an existing value.
Definition HashMap.h:443
ConstNodeIterator find(const Key &key) const
Find a node by key.
Definition HashMap.h:391
NodeIterator find(const Key &key)
Find a node by key.
Definition HashMap.h:388
HashMap & eraseAt(const ConstKeyIterator &iter)
Remove a node by iterator.
Definition HashMap.h:642
const Value & getOrElse(const Key &key, const Value &dflt) const
Lookup and return a value or something else.
Definition HashMap.h:489
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:256
Value & insertMaybe(const Key &key, const Value &value)
Conditionally insert a new key/value pair.
Definition HashMap.h:569
boost::iterator_range< ConstNodeIterator > nodes() const
Iterators for container nodes.
Definition HashMap.h:299
boost::iterator_range< NodeIterator > nodes()
Iterators for container nodes.
Definition HashMap.h:296
size_t size() const
Number of nodes, keys, or values in this container.
Definition HashMap.h:347
HashMap & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
Definition HashMap.h:516
HashMap & eraseAtMultiple(const boost::iterator_range< Iter > &range)
Remove multiple nodes by iterator range.
Definition HashMap.h:665
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
Definition HashMap.h:473
HashMap & operator=(const HashMap< K2, T2, H2, C2, A2 > &other)
Assignment operator.
Definition HashMap.h:277
boost::iterator_range< ConstKeyIterator > keys()
Iterators for container keys.
Definition HashMap.h:309
HashMap & insertDefault(const Key &key)
Insert or update a key with a default value.
Definition HashMap.h:529
boost::iterator_range< ConstKeyIterator > keys() const
Iterators for container keys.
Definition HashMap.h:312
HashMap & erase(const Key &key)
Remove a node with specified key.
Definition HashMap.h:612
K Key
Type of keys.
Definition HashMap.h:32
const Value & getOrDefault(const Key &key) const
Lookup and return a value or a default.
Definition HashMap.h:499
bool isEmpty() const
Determine whether this container is empty.
Definition HashMap.h:339
HashMap & insertMultiple(const OtherNodeIterator &begin, const OtherNodeIterator &end)
Insert multiple values.
Definition HashMap.h:551
Value & get(const Key &key)
Lookup and retun an existing value.
Definition HashMap.h:437
HashMap(const HashMap< K2, T2, H2, C2, A2 > &other)
Copy constructor.
Definition HashMap.h:268
HashMap & clear()
Remove all nodes.
Definition HashMap.h:601
double loadFactor() const
Average number of nodes per bucket.
Definition HashMap.h:357
bool exists(const Key &key) const
Determine if a key exists.
Definition HashMap.h:400
HashMap & insertMultiple(const boost::iterator_range< OtherNodeIterator > &range)
Insert multiple values.
Definition HashMap.h:557
Holds a value or nothing.
Definition Optional.h:56
Sawyer support library.