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/unordered_map.hpp>
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> > >
39 typedef boost::unordered_map<Key, Value, Hasher, Comparator, Allocator> ImplMap;
42#ifdef SAWYER_HAVE_BOOST_SERIALIZATION
44 friend class boost::serialization::access;
48 void save(S &s,
const unsigned )
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);
60 void load(S & s,
const unsigned ) {
62 s & BOOST_SERIALIZATION_NVP(nElmts);
63 for (
size_t i=0; i<nElmts; ++i) {
65 s & BOOST_SERIALIZATION_NVP(key);
67 s & BOOST_SERIALIZATION_NVP(value);
68 map_.insert(std::make_pair(key, value));
72 BOOST_SERIALIZATION_SPLIT_MEMBER();
75#ifdef SAWYER_HAVE_CEREAL
77 friend class cereal::access;
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));
92 template<
class Archive>
93 void CEREAL_LOAD_FUNCTION_NAME(Archive &archive) {
95 archive(CEREAL_NVP(nElmts));
96 for (
size_t i = 0; i < nElmts; ++i) {
98 archive(CEREAL_NVP(key));
100 archive(CEREAL_NVP(key));
101 map_.insert(std::make_pair(key, value));
111 class Node:
private ImplMap::value_type {
114 explicit Node(
const std::pair<const Key, Value> &pair)
115 : std::pair<const Key, Value>(pair) {}
118 : std::pair<const Key, Value>(
key,
value) {}
123 const Key&
key()
const {
return this->first; }
139 template<
class Derived,
class Value,
class BaseIterator>
140 class ForwardIterator {
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&;
152 ForwardIterator(
const BaseIterator &base): base_(base) {}
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_; }
161 Derived* derived() {
return static_cast<Derived*
>(
this); }
162 const Derived* derived()
const {
return static_cast<const Derived*
>(
this); }
170 class NodeIterator:
public ForwardIterator<NodeIterator, Node, typename ImplMap::iterator> {
171 typedef ForwardIterator<NodeIterator, Node, typename ImplMap::iterator> Super;
175 Node& operator*()
const {
return *(
Node*)&*this->base_; }
176 Node* operator->()
const {
return (
Node*)&*this->base_; }
179 NodeIterator(
const typename ImplMap::iterator &base): Super(base) {}
186 class ConstNodeIterator:
public ForwardIterator<ConstNodeIterator, const Node, typename ImplMap::const_iterator> {
187 typedef ForwardIterator<ConstNodeIterator, const Node, typename ImplMap::const_iterator> Super;
192 const Node& operator*()
const {
return *(
const Node*)&*this->base_; }
193 const Node* operator->()
const {
return (
const Node*)&*this->base_; }
197 ConstNodeIterator(
const typename ImplMap::iterator &base): Super(
typename ImplMap::const_iterator(base)) {}
204 class ConstKeyIterator:
public ForwardIterator<ConstKeyIterator, const Key, typename ImplMap::const_iterator> {
205 typedef ForwardIterator<ConstKeyIterator, const Key, typename ImplMap::const_iterator> Super;
211 const Key& operator*()
const {
return this->base()->first; }
212 const Key* operator->()
const {
return &this->base()->first; }
219 class ValueIterator:
public ForwardIterator<ValueIterator, Value, typename ImplMap::iterator> {
220 typedef ForwardIterator<ValueIterator, Value, typename ImplMap::iterator> Super;
225 Value& operator*()
const {
return this->base()->second; }
226 Value* operator->()
const {
return &this->base()->second; }
233 class ConstValueIterator:
public ForwardIterator<ConstValueIterator, const Value, typename ImplMap::const_iterator> {
234 typedef ForwardIterator<ConstValueIterator, const Value, typename ImplMap::const_iterator> Super;
241 const Value& operator*()
const {
return this->base()->second; }
242 const Value* operator->()
const {
return &this->base()->second; }
257 : map_(n, hasher, cmp, alloc) {}
261 : map_(other.map_) {}
267 template<
class K2,
class T2,
class H2,
class C2,
class A2>
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())));
276 template<
class K2,
class T2,
class H2,
class C2,
class A2>
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())));
296 boost::iterator_range<NodeIterator>
nodes() {
299 boost::iterator_range<ConstNodeIterator>
nodes()
const {
309 boost::iterator_range<ConstKeyIterator>
keys() {
312 boost::iterator_range<ConstKeyIterator>
keys()
const {
323 boost::iterator_range<ValueIterator>
values() {
326 boost::iterator_range<ConstValueIterator>
values()
const {
353 return map_.bucket_count();
358 return map_.load_factor();
365 return map_.max_load_factor();
368 map_.max_load_factor(mlf);
389 return map_.find(key);
392 return map_.find(key);
401 return map_.find(key) != map_.end();
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;
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;
474 typename ImplMap::const_iterator found = map_.find(key);
486 typename ImplMap::iterator found = map_.find(key);
487 return found == map_.end() ? dflt : found->second;
490 typename ImplMap::const_iterator found = map_.find(key);
491 return found == map_.end() ? dflt : found->second;
500 static const Value dflt;
501 typename ImplMap::const_iterator found = map_.find(key);
502 return found==map_.end() ? dflt : found->second;
517 std::pair<typename ImplMap::iterator, bool> inserted = map_.
insert(std::make_pair(key, value));
518 if (!inserted.second)
519 inserted.first->second = value;
550 template<
class OtherNodeIterator>
552 for (OtherNodeIterator otherIter = begin; otherIter != end; ++otherIter)
556 template<
class OtherNodeIterator>
570 return map_.insert(std::make_pair(key, value)).first->second;
590 template<
class OtherNodeIterator>
592 for (OtherNodeIterator otherIter = range.begin(); otherIter != range.end(); ++otherIter)
624 template<
class OtherKeyIterator>
626 for (OtherKeyIterator otherIter = range.begin(); otherIter != range.end(); ++otherIter)
639 map_.
erase(iter.base());
643 map_.
erase(iter.base());
647 map_.
erase(iter.base());
661 map_.
erase(begin.base(), end.base());
666 map_.
erase(range.begin().base(), range.end().base());
Forward iterator over keys.
Forward iterator over key/value nodes.
Forward iterator over values.
Forward iterator over key/value nodes.
const Key & key() const
Key part of key/value node.
Value & value()
Value part of key/value node.
const Value & value() const
Value part of key/value node.
Forward iterator over values.
Container associating values with keys.
size_t nBuckets() const
Number of buckets.
HashMap & eraseAtMultiple(const Iter &begin, const Iter &end)
Remove multiple nodes by iterator range.
Value & operator[](const Key &key)
Return a reference to an existing value.
void rehash(size_t nBuckets)
Change number of buckets.
C Comparator
Functor for comparing keys.
void maxLoadFactor(double mlf)
Property: Maximum allowed load faster before automatic rehash.
HashMap & eraseAt(const ValueIterator &iter)
Remove a node by iterator.
A Allocator
Functor for allocating node memory.
HashMap & eraseMultiple(const boost::iterator_range< OtherKeyIterator > &range)
Remove keys stored in another HashMap.
boost::iterator_range< ValueIterator > values()
Iterators for container values.
HashMap & eraseAt(const NodeIterator &iter)
Remove a node by iterator.
HashMap()
Default constructor.
const Value & operator[](const Key &key) const
Return a reference to an existing value.
boost::iterator_range< ConstValueIterator > values() const
Iterators for container values.
HashMap(const HashMap &other)
Copy constructor.
double maxLoadFactor() const
Property: Maximum allowed load faster before automatic rehash.
H Hasher
Functor for hashing keys.
Value & getOrElse(const Key &key, Value &dflt)
Lookup and return a value or something else.
Value & insertMaybeDefault(const Key &key)
Conditionally insert a new key with default value.
HashMap & insertMaybeMultiple(const boost::iterator_range< OtherNodeIterator > &range)
Conditionally insert multiple key/value pairs.
const Value & get(const Key &key) const
Lookup and retun an existing value.
ConstNodeIterator find(const Key &key) const
Find a node by key.
NodeIterator find(const Key &key)
Find a node by key.
HashMap & eraseAt(const ConstKeyIterator &iter)
Remove a node by iterator.
const Value & getOrElse(const Key &key, const Value &dflt) const
Lookup and return a value or something else.
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.
Value & insertMaybe(const Key &key, const Value &value)
Conditionally insert a new key/value pair.
boost::iterator_range< ConstNodeIterator > nodes() const
Iterators for container nodes.
boost::iterator_range< NodeIterator > nodes()
Iterators for container nodes.
size_t size() const
Number of nodes, keys, or values in this container.
HashMap & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
HashMap & eraseAtMultiple(const boost::iterator_range< Iter > &range)
Remove multiple nodes by iterator range.
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
HashMap & operator=(const HashMap< K2, T2, H2, C2, A2 > &other)
Assignment operator.
boost::iterator_range< ConstKeyIterator > keys()
Iterators for container keys.
HashMap & insertDefault(const Key &key)
Insert or update a key with a default value.
boost::iterator_range< ConstKeyIterator > keys() const
Iterators for container keys.
HashMap & erase(const Key &key)
Remove a node with specified key.
const Value & getOrDefault(const Key &key) const
Lookup and return a value or a default.
bool isEmpty() const
Determine whether this container is empty.
HashMap & insertMultiple(const OtherNodeIterator &begin, const OtherNodeIterator &end)
Insert multiple values.
Value & get(const Key &key)
Lookup and retun an existing value.
HashMap(const HashMap< K2, T2, H2, C2, A2 > &other)
Copy constructor.
HashMap & clear()
Remove all nodes.
double loadFactor() const
Average number of nodes per bucket.
bool exists(const Key &key) const
Determine if a key exists.
HashMap & insertMultiple(const boost::iterator_range< OtherNodeIterator > &range)
Insert multiple values.
Holds a value or nothing.