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 
11 namespace 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.
15 struct ExtractFirst {
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.
27 template<typename Key,
28  typename Value,
29  typename Hasher = std::hash<Key>,
30  typename Equal = std::equal_to<>>
31 class hash_map : public hash_set<std::pair<Key, Value>, hash_set_impl::ExtractFirst, Hasher, Equal>
32 {
34 public:
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  // Proposed for C++17. Is equivalent to 'operator[](key) = value', but:
65  // - also works for non-default-constructible types
66  // - returns more information
67  // - is slightly more efficient
68  template<typename K, typename V>
69  std::pair<iterator, bool> insert_or_assign(K&& key, V&& value)
70  {
71  auto it = this->find(key);
72  if (it == this->end()) {
73  // insert, return pair<iterator, true>
74  return this->insert(value_type(std::forward<K>(key), std::forward<V>(value)));
75  } else {
76  // assign, return pair<iterator, false>
77  it->second = std::forward<V>(value);
78  return std::pair(it, false);
79  }
80  }
81 
82  template<typename K>
83  [[nodiscard]] bool contains(const K& k) const
84  {
85  return this->find(k) != this->end();
86  }
87 };
88 
89 
90 template<typename Key, typename Value, typename Hasher, typename Equal, typename Key2>
91 [[nodiscard]] const Value* lookup(const hash_map<Key, Value, Hasher, Equal>& map, const Key2& key)
92 {
93  auto it = map.find(key);
94  return (it != map.end()) ? &it->second : nullptr;
95 }
96 
97 template<typename Key, typename Value, typename Hasher, typename Equal, typename Key2>
98 [[nodiscard]] Value* lookup(hash_map<Key, Value, Hasher, Equal>& map, const Key2& key)
99 {
100  auto it = map.find(key);
101  return (it != map.end()) ? &it->second : nullptr;
102 }
103 
104 #endif
bool contains(const K &k) const
Definition: hash_map.hh:83
auto find(InputRange &&range, const T &value)
Definition: ranges.hh:107
std::pair< std::string, openmsx::CommandCompleter * > value_type
Definition: hash_map.hh:37
const Value * lookup(const hash_map< Key, Value, Hasher, Equal > &map, const Key2 &key)
Definition: hash_map.hh:91
Value & operator[](K &&key)
Definition: hash_map.hh:54
hash_map(std::initializer_list< std::pair< Key, Value >> list)
Definition: hash_map.hh:48
auto & operator()(Pair &&p) const
Definition: hash_map.hh:16
std::pair< iterator, bool > insert_or_assign(K &&key, V &&value)
Definition: hash_map.hh:69
hash_map(unsigned initialSize=0, Hasher hasher_=Hasher(), Equal equal_=Equal())
Definition: hash_map.hh:41