openMSX
hash_map.hh
Go to the documentation of this file.
1// hash_map
2//
3// Written by Wouter Vermaelen, based upon HashSet/HashMap
4// example code and ideas provided by Jacques Van Damme.
5
6#ifndef HASH_MAP_HH
7#define HASH_MAP_HH
8
9#include "hash_set.hh"
10
11namespace hash_set_impl {
12
13// Takes any (const or non-const) pair reference and returns a reference to
14// the first element of the pair.
16 template<typename Pair> [[nodiscard]] auto& operator()(Pair&& p) const { return p.first; }
17};
18
19} // namespace hash_set_impl
20
21
22// hash_map
23//
24// A hash-map implementation with an STL-like interface.
25//
26// It builds upon hash-set, see there for more details.
27template<typename Key,
28 typename Value,
29 typename Hasher = std::hash<Key>,
30 typename Equal = std::equal_to<>>
31class hash_map : public hash_set<std::pair<Key, Value>, hash_set_impl::ExtractFirst, Hasher, Equal>
32{
34public:
35 using key_type = Key;
36 using mapped_type = Value;
37 using value_type = std::pair<Key, Value>;
38 using iterator = typename BaseType:: iterator;
40
41 explicit hash_map(unsigned initialSize = 0,
42 Hasher hasher_ = Hasher(),
43 Equal equal_ = Equal())
44 : BaseType(initialSize, hash_set_impl::ExtractFirst(), hasher_, equal_)
45 {
46 }
47
48 hash_map(std::initializer_list<std::pair<Key, Value>> list)
49 : BaseType(list)
50 {
51 }
52
53 template<typename K>
54 [[nodiscard]] Value& operator[](K&& key)
55 {
56 auto it = this->find(key);
57 if (it == this->end()) {
58 auto p = this->insert(value_type(std::forward<K>(key), Value()));
59 it = p.first;
60 }
61 return it->second;
62 }
63
64 template<typename K, typename V>
65 std::pair<iterator, bool> try_emplace(K&& key, V&& value)
66 {
67 auto hash = unsigned(this->hasher(key));
68 auto tableIdx = hash & this->allocMask;
69 auto primary = BaseType::invalidIndex;
70
71 if (this->elemCount > 0) {
72 primary = this->table[tableIdx];
73 for (auto elemIdx = primary; elemIdx != BaseType::invalidIndex; ) {
74 auto& elem = this->pool.get(elemIdx);
75 if ((elem.hash == hash) && this->equal(this->extract(elem.value), key)) {
76 // key already exists (possibly value is different)
77 return std::pair(iterator(this, elemIdx), false);
78 }
79 elemIdx = elem.nextIdx;
80 }
81 }
82
83 if (this->elemCount >= ((this->allocMask + 1) / 4 * 3)) {
84 this->grow();
85 tableIdx = hash & this->allocMask;
86 primary = this->table[tableIdx];
87 }
88
89 ++this->elemCount;
90 auto poolIdx = this->pool.emplace(std::forward<K>(key), std::forward<V>(value));
91 auto& poolElem = this->pool.get(poolIdx);
92 poolElem.hash = hash;
93 poolElem.nextIdx = primary;
94 this->table[tableIdx] = poolIdx;
95 return std::pair(iterator(this, poolIdx), true);
96 }
97
98 template<typename K, typename V>
99 std::pair<iterator, bool> insert_or_assign(K&& key, V&& value)
100 {
101 auto result = try_emplace(std::forward<K>(key), std::forward<V>(value));
102 if (!result.second) {
103 // was already present, also overwrite value
104 result.first->second = std::forward<V>(value);
105 }
106 return result;
107 }
108
109 template<typename K>
110 [[nodiscard]] bool contains(const K& k) const
111 {
112 return this->find(k) != this->end();
113 }
114};
115
116
117template<typename Key, typename Value, typename Hasher, typename Equal, typename Key2>
118[[nodiscard]] const Value* lookup(const hash_map<Key, Value, Hasher, Equal>& map, const Key2& key)
119{
120 auto it = map.find(key);
121 return (it != map.end()) ? &it->second : nullptr;
122}
123
124template<typename Key, typename Value, typename Hasher, typename Equal, typename Key2>
125[[nodiscard]] Value* lookup(hash_map<Key, Value, Hasher, Equal>& map, const Key2& key)
126{
127 auto it = map.find(key);
128 return (it != map.end()) ? &it->second : nullptr;
129}
130
131#endif
hash_map(std::initializer_list< std::pair< Key, Value > > list)
Definition: hash_map.hh:48
std::pair< iterator, bool > insert_or_assign(K &&key, V &&value)
Definition: hash_map.hh:99
hash_map(unsigned initialSize=0, Hasher hasher_=Hasher(), Equal equal_=Equal())
Definition: hash_map.hh:41
typename BaseType::const_iterator const_iterator
Definition: hash_map.hh:39
Value mapped_type
Definition: hash_map.hh:36
Key key_type
Definition: hash_map.hh:35
std::pair< iterator, bool > try_emplace(K &&key, V &&value)
Definition: hash_map.hh:65
std::pair< Key, Value > value_type
Definition: hash_map.hh:37
typename BaseType::iterator iterator
Definition: hash_map.hh:38
Value & operator[](K &&key)
Definition: hash_map.hh:54
bool contains(const K &k) const
Definition: hash_map.hh:110
PoolIndex emplace(Args &&... args)
Definition: hash_set.hh:149
Elem & get(PoolIndex idx)
Definition: hash_set.hh:109
Iter< const hash_set, const Value > const_iterator
Definition: hash_set.hh:344
Iter< hash_set, Value > iterator
Definition: hash_set.hh:343
static constexpr auto invalidIndex
Definition: hash_set.hh:273
const Value * lookup(const hash_map< Key, Value, Hasher, Equal > &map, const Key2 &key)
Definition: hash_map.hh:118
auto & operator()(Pair &&p) const
Definition: hash_map.hh:16