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  // c++14: template<typename Pair> auto& operator()(Pair&& p) const { return p.first; }
17 
18  template<typename First, typename Second>
19  inline First& operator()( std::pair<First, Second>& p) const { return p.first; }
20 
21  template<typename First, typename Second>
22  inline const First& operator()(const std::pair<First, Second>& p) const { return p.first; }
23 };
24 
25 } // namespace hash_set_impl
26 
27 
28 // hash_map
29 //
30 // A hash-map implementation with an STL-like interface.
31 //
32 // It builds upon hash-set, see there for more details.
33 template<typename Key,
34  typename Value,
35  typename Hasher = std::hash<Key>,
36  typename Equal = EqualTo>
37 class hash_map : public hash_set<std::pair<Key, Value>, hash_set_impl::ExtractFirst, Hasher, Equal>
38 {
40 public:
41  using key_type = Key;
42  using mapped_type = Value;
43  using value_type = std::pair<Key, Value>;
44  using iterator = typename BaseType:: iterator;
45  using const_iterator = typename BaseType::const_iterator;
46 
47  explicit hash_map(unsigned initialSize = 0,
48  Hasher hasher_ = Hasher(),
49  Equal equal_ = Equal())
50  : BaseType(initialSize, hash_set_impl::ExtractFirst(), hasher_, equal_)
51  {
52  }
53 
54  template<typename K>
55  Value& operator[](K&& key)
56  {
57  auto it = this->find(key);
58  if (it == this->end()) {
59  auto p = this->insert(value_type(std::forward<K>(key), Value()));
60  it = p.first;
61  }
62  return it->second;
63  }
64 
65  // Proposed for C++17. Is equivalent to 'operator[](key) = value', but:
66  // - also works for non-default-constructible types
67  // - returns more information
68  // - is slightly more efficient
69  template<typename K, typename V>
70  std::pair<iterator, bool> insert_or_assign(K&& key, V&& value)
71  {
72  auto it = this->find(key);
73  if (it == this->end()) {
74  // insert, return pair<iterator, true>
75  return this->insert(value_type(std::forward<K>(key), std::forward<V>(value)));
76  } else {
77  // assign, return pair<iterator, false>
78  it->second = std::forward<V>(value);
79  return std::make_pair(it, false);
80  }
81  }
82 };
83 
84 #endif
string_ref::const_iterator end(const string_ref &x)
Definition: string_ref.hh:167
std::pair< std::string, openmsx::CommandCompleter * > value_type
Definition: hash_map.hh:43
Value & operator[](K &&key)
Definition: hash_map.hh:55
First & operator()(std::pair< First, Second > &p) const
Definition: hash_map.hh:19
Definition: stl.hh:19
const First & operator()(const std::pair< First, Second > &p) const
Definition: hash_map.hh:22
std::pair< iterator, bool > insert_or_assign(K &&key, V &&value)
Definition: hash_map.hh:70
hash_map(unsigned initialSize=0, Hasher hasher_=Hasher(), Equal equal_=Equal())
Definition: hash_map.hh:47