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) {}
86 Node(
const Key &key, Value &value)
87 : std::pair<const Key, Value>(
key,
value) {}
92 const Key&
key()
const {
return this->first; }
99 Value&
value() {
return this->second; }
100 const Value&
value()
const {
return this->second; }
108 template<
class Derived,
class Value,
class BaseIterator>
109 class ForwardIterator:
public std::iterator<std::forward_iterator_tag, Value> {
113 ForwardIterator(
const BaseIterator &base): base_(base) {}
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_; }
122 Derived* derived() {
return static_cast<Derived*
>(
this); }
123 const Derived* derived()
const {
return static_cast<const Derived*
>(
this); }
131 class NodeIterator:
public ForwardIterator<NodeIterator, Node, typename ImplMap::iterator> {
132 typedef ForwardIterator<NodeIterator, Node, typename ImplMap::iterator> Super;
136 Node& operator*()
const {
return *(
Node*)&*this->base_; }
137 Node* operator->()
const {
return (
Node*)&*this->base_; }
140 NodeIterator(
const typename ImplMap::iterator &base): Super(base) {}
147 class ConstNodeIterator:
public ForwardIterator<ConstNodeIterator, const Node, typename ImplMap::const_iterator> {
148 typedef ForwardIterator<ConstNodeIterator, const Node, typename ImplMap::const_iterator> Super;
153 const Node& operator*()
const {
return *(
const Node*)&*this->base_; }
154 const Node* operator->()
const {
return (
const Node*)&*this->base_; }
158 ConstNodeIterator(
const typename ImplMap::iterator &base): Super(
typename ImplMap::const_iterator(base)) {}
165 class ConstKeyIterator:
public ForwardIterator<ConstKeyIterator, const Key, typename ImplMap::const_iterator> {
166 typedef ForwardIterator<ConstKeyIterator, const Key, typename ImplMap::const_iterator> Super;
172 const Key& operator*()
const {
return this->base()->first; }
173 const Key* operator->()
const {
return &this->base()->first; }
180 class ValueIterator:
public ForwardIterator<ValueIterator, Value, typename ImplMap::iterator> {
181 typedef ForwardIterator<ValueIterator, Value, typename ImplMap::iterator> Super;
186 Value& operator*()
const {
return this->base()->second; }
187 Value* operator->()
const {
return &this->base()->second; }
194 class ConstValueIterator:
public ForwardIterator<ConstValueIterator, const Value, typename ImplMap::const_iterator> {
195 typedef ForwardIterator<ConstValueIterator, const Value, typename ImplMap::const_iterator> Super;
202 const Value& operator*()
const {
return this->base()->second; }
203 const Value* operator->()
const {
return &this->base()->second; }
218 : map_(n, hasher, cmp, alloc) {}
222 : map_(other.map_) {}
228 template<
class K2,
class T2,
class H2,
class C2,
class A2>
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())));
237 template<
class K2,
class T2,
class H2,
class C2,
class A2>
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())));
257 boost::iterator_range<NodeIterator>
nodes() {
258 return boost::iterator_range<NodeIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
260 boost::iterator_range<ConstNodeIterator>
nodes()
const {
261 return boost::iterator_range<ConstNodeIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
270 boost::iterator_range<ConstKeyIterator>
keys() {
271 return boost::iterator_range<ConstKeyIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
273 boost::iterator_range<ConstKeyIterator>
keys()
const {
274 return boost::iterator_range<ConstKeyIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
284 boost::iterator_range<ValueIterator>
values() {
285 return boost::iterator_range<ValueIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
287 boost::iterator_range<ConstValueIterator>
values()
const {
288 return boost::iterator_range<ConstValueIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
314 return map_.bucket_count();
319 return map_.load_factor();
326 return map_.max_load_factor();
329 map_.max_load_factor(mlf);
335 map_.rehash(nBuckets);
349 NodeIterator
find(
const Key &key) {
350 return map_.find(key);
352 ConstNodeIterator
find(
const Key &key)
const {
353 return map_.find(key);
362 return map_.find(key) != map_.end();
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;
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;
435 typename ImplMap::const_iterator found = map_.find(key);
447 typename ImplMap::iterator found = map_.find(key);
448 return found == map_.end() ? dflt : found->second;
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;
461 static const Value dflt;
462 typename ImplMap::const_iterator found = map_.find(key);
463 return found==map_.end() ? dflt : found->second;
478 std::pair<typename ImplMap::iterator, bool> inserted = map_.
insert(std::make_pair(key, value));
479 if (!inserted.second)
480 inserted.first->second = value;
511 template<
class OtherNodeIterator>
513 for (OtherNodeIterator otherIter = begin; otherIter != end; ++otherIter)
517 template<
class OtherNodeIterator>
531 return map_.insert(std::make_pair(key, value)).first->second;
551 template<
class OtherNodeIterator>
553 for (OtherNodeIterator otherIter = range.begin(); otherIter != range.end(); ++otherIter)
585 template<
class OtherKeyIterator>
587 for (OtherKeyIterator otherIter = range.begin(); otherIter != range.end(); ++otherIter)
588 map_.
erase(Key(*otherIter));
600 map_.
erase(iter.base());
604 map_.
erase(iter.base());
608 map_.
erase(iter.base());
622 map_.
erase(begin.base(), end.base());
627 map_.
erase(range.begin().base(), range.end().base());
boost::iterator_range< ConstNodeIterator > nodes() const
Iterators for container nodes.
boost::iterator_range< ConstKeyIterator > keys()
Iterators for container keys.
Value & insertMaybeDefault(const Key &key)
Conditionally insert a new key with default value.
boost::iterator_range< ValueIterator > values()
Iterators for container values.
boost::iterator_range< NodeIterator > nodes()
Iterators for container nodes.
boost::iterator_range< ConstKeyIterator > keys() const
Iterators for container keys.
const Value & operator[](const Key &key) const
Return a reference to an existing value.
H Hasher
Functor for hashing keys.
HashMap & insertMultiple(const boost::iterator_range< OtherNodeIterator > &range)
Insert multiple values.
Value & getOrElse(const Key &key, Value &dflt)
Lookup and return a value or something else.
const Key & key() const
Key part of key/value node.
HashMap(const HashMap< K2, T2, H2, C2, A2 > &other)
Copy constructor.
ConstNodeIterator find(const Key &key) const
Find a node by key.
HashMap & insertMaybeMultiple(const boost::iterator_range< OtherNodeIterator > &range)
Conditionally insert multiple key/value pairs.
Value & value()
Value part of key/value node.
Forward iterator over key/value nodes.
Forward iterator over values.
const Value & getOrElse(const Key &key, const Value &dflt) const
Lookup and return a value or something else.
bool isEmpty() const
Determine whether this container is empty.
HashMap & operator=(const HashMap< K2, T2, H2, C2, A2 > &other)
Assignment operator.
double maxLoadFactor() const
Property: Maximum allowed load faster before automatic rehash.
Name space for the entire library.
void maxLoadFactor(double mlf)
Property: Maximum allowed load faster before automatic rehash.
size_t size() const
Number of nodes, keys, or values in this container.
HashMap()
Default constructor.
HashMap & insertDefault(const Key &key)
Insert or update a key with a default value.
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
A Allocator
Functor for allocating node memory.
HashMap & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
HashMap & eraseAtMultiple(const Iter &begin, const Iter &end)
Remove multiple nodes by iterator range.
HashMap & eraseAt(const NodeIterator &iter)
Remove a node by iterator.
boost::iterator_range< ConstValueIterator > values() const
Iterators for container values.
NodeIterator find(const Key &key)
Find a node by key.
HashMap & eraseMultiple(const boost::iterator_range< OtherKeyIterator > &range)
Remove keys stored in another HashMap.
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.
HashMap & eraseAt(const ValueIterator &iter)
Remove a node by iterator.
Value & insertMaybe(const Key &key, const Value &value)
Conditionally insert a new key/value pair.
Container associating values with keys.
void rehash(size_t nBuckets)
Change number of buckets.
Forward iterator over key/value nodes.
const Value & value() const
Value part of key/value node.
HashMap(const HashMap &other)
Copy constructor.
HashMap & clear()
Remove all nodes.
Forward iterator over values.
Value & operator[](const Key &key)
Return a reference to an existing value.
C Comparator
Functor for comparing keys.
double loadFactor() const
Average number of nodes per bucket.
HashMap & eraseAtMultiple(const boost::iterator_range< Iter > &range)
Remove multiple nodes by iterator range.
HashMap & eraseAt(const ConstKeyIterator &iter)
Remove a node by iterator.
const Value & getOrDefault(const Key &key) const
Lookup and return a value or a default.
Forward iterator over keys.
size_t nBuckets() const
Number of buckets.
bool exists(const Key &key) const
Determine if a key exists.
HashMap & erase(const Key &key)
Remove a node with specified key.
HashMap & insertMultiple(const OtherNodeIterator &begin, const OtherNodeIterator &end)
Insert multiple values.