8 #ifndef Sawyer_HashMap_H
9 #define Sawyer_HashMap_H
11 #include <Sawyer/Optional.h>
12 #include <Sawyer/Sawyer.h>
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>
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> > >
42 typedef boost::unordered_map<Key, Value, Hasher, Comparator, Allocator> ImplMap;
46 friend class boost::serialization::access;
50 void save(S &s,
const unsigned )
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);
62 void load(S & s,
const unsigned ) {
64 s & BOOST_SERIALIZATION_NVP(nElmts);
65 for (
size_t i=0; i<nElmts; ++i) {
67 s & BOOST_SERIALIZATION_NVP(key);
69 s & BOOST_SERIALIZATION_NVP(value);
70 map_.insert(std::make_pair(key, value));
74 BOOST_SERIALIZATION_SPLIT_MEMBER();
80 class Node:
private ImplMap::value_type {
83 explicit Node(
const std::pair<const Key, Value> &pair)
84 : std::pair<const Key, Value>(pair) {}
87 : std::pair<const Key, Value>(
key,
value) {}
92 const Key&
key()
const {
return this->first; }
108 template<
class Derived,
class Value,
class BaseIterator>
109 class ForwardIterator {
112 using iterator_category = std::forward_iterator_tag;
113 using value_type =
Value;
114 using difference_type = std::ptrdiff_t;
115 using pointer =
Value*;
116 using reference =
Value&;
121 ForwardIterator(
const BaseIterator &base): base_(base) {}
123 Derived&
operator=(
const Derived &other) { base_ = other.base_;
return *derived(); }
124 Derived& operator++() { ++base_;
return *derived(); }
125 Derived operator++(
int) { Derived old = *derived(); ++*
this;
return old; }
126 template<
class OtherIter>
bool operator==(
const OtherIter &other)
const {
return base_ == other.base(); }
127 template<
class OtherIter>
bool operator!=(
const OtherIter &other)
const {
return base_ != other.base(); }
128 const BaseIterator& base()
const {
return base_; }
130 Derived* derived() {
return static_cast<Derived*
>(
this); }
131 const Derived* derived()
const {
return static_cast<const Derived*
>(
this); }
139 class NodeIterator:
public ForwardIterator<NodeIterator, Node, typename ImplMap::iterator> {
140 typedef ForwardIterator<NodeIterator, Node, typename ImplMap::iterator> Super;
144 Node& operator*()
const {
return *(
Node*)&*this->base_; }
145 Node* operator->()
const {
return (
Node*)&*this->base_; }
148 NodeIterator(
const typename ImplMap::iterator &base): Super(base) {}
155 class ConstNodeIterator:
public ForwardIterator<ConstNodeIterator, const Node, typename ImplMap::const_iterator> {
156 typedef ForwardIterator<ConstNodeIterator, const Node, typename ImplMap::const_iterator> Super;
161 const Node& operator*()
const {
return *(
const Node*)&*this->base_; }
162 const Node* operator->()
const {
return (
const Node*)&*this->base_; }
166 ConstNodeIterator(
const typename ImplMap::iterator &base): Super(
typename ImplMap::const_iterator(base)) {}
173 class ConstKeyIterator:
public ForwardIterator<ConstKeyIterator, const Key, typename ImplMap::const_iterator> {
174 typedef ForwardIterator<ConstKeyIterator, const Key, typename ImplMap::const_iterator> Super;
180 const Key& operator*()
const {
return this->base()->first; }
181 const Key* operator->()
const {
return &this->base()->first; }
188 class ValueIterator:
public ForwardIterator<ValueIterator, Value, typename ImplMap::iterator> {
189 typedef ForwardIterator<ValueIterator, Value, typename ImplMap::iterator> Super;
194 Value& operator*()
const {
return this->base()->second; }
195 Value* operator->()
const {
return &this->base()->second; }
202 class ConstValueIterator:
public ForwardIterator<ConstValueIterator, const Value, typename ImplMap::const_iterator> {
203 typedef ForwardIterator<ConstValueIterator, const Value, typename ImplMap::const_iterator> Super;
210 const Value& operator*()
const {
return this->base()->second; }
211 const Value* operator->()
const {
return &this->base()->second; }
226 : map_(n, hasher, cmp, alloc) {}
230 : map_(other.map_) {}
236 template<
class K2,
class T2,
class H2,
class C2,
class A2>
239 boost::iterator_range<OtherIterator> otherNodes = other.
nodes();
240 for (OtherIterator otherIter = otherNodes.begin(); otherIter != otherNodes.end(); ++otherIter)
241 map_.insert(std::make_pair(
Key(otherIter->key()),
Value(otherIter->value())));
245 template<
class K2,
class T2,
class H2,
class C2,
class A2>
249 boost::iterator_range<OtherIterator> otherNodes = other.
nodes();
250 for (OtherIterator otherIter = otherNodes.begin(); otherIter != otherNodes.end(); ++otherIter)
251 map_.insert(std::make_pair(
Key(otherIter->key()),
Value(otherIter->value())));
265 boost::iterator_range<NodeIterator>
nodes() {
268 boost::iterator_range<ConstNodeIterator>
nodes()
const {
278 boost::iterator_range<ConstKeyIterator>
keys() {
281 boost::iterator_range<ConstKeyIterator>
keys()
const {
292 boost::iterator_range<ValueIterator>
values() {
295 boost::iterator_range<ConstValueIterator>
values()
const {
322 return map_.bucket_count();
327 return map_.load_factor();
334 return map_.max_load_factor();
337 map_.max_load_factor(mlf);
358 return map_.find(key);
361 return map_.find(key);
370 return map_.find(key) != map_.end();
407 typename ImplMap::iterator found = map_.find(key);
408 if (found == map_.end())
409 throw std::domain_error(
"key lookup failure; key is not in map domain");
410 return found->second;
413 typename ImplMap::const_iterator found = map_.find(key);
414 if (found == map_.end())
415 throw std::domain_error(
"key lookup failure; key is not in map domain");
416 return found->second;
443 typename ImplMap::const_iterator found = map_.find(key);
455 typename ImplMap::iterator found = map_.find(key);
456 return found == map_.end() ? dflt : found->second;
459 typename ImplMap::const_iterator found = map_.find(key);
460 return found == map_.end() ? dflt : found->second;
469 static const Value dflt;
470 typename ImplMap::const_iterator found = map_.find(key);
471 return found==map_.end() ? dflt : found->second;
486 std::pair<typename ImplMap::iterator, bool> inserted = map_.
insert(std::make_pair(key, value));
487 if (!inserted.second)
488 inserted.first->second = value;
519 template<
class OtherNodeIterator>
521 for (OtherNodeIterator otherIter = begin; otherIter != end; ++otherIter)
525 template<
class OtherNodeIterator>
539 return map_.insert(std::make_pair(key, value)).first->second;
559 template<
class OtherNodeIterator>
561 for (OtherNodeIterator otherIter = range.begin(); otherIter != range.end(); ++otherIter)
593 template<
class OtherKeyIterator>
595 for (OtherKeyIterator otherIter = range.begin(); otherIter != range.end(); ++otherIter)
608 map_.
erase(iter.base());
612 map_.
erase(iter.base());
616 map_.
erase(iter.base());
630 map_.
erase(begin.base(), end.base());
635 map_.
erase(range.begin().base(), range.end().base());