raw_hash_map.h
Go to the documentation of this file.
1 // Copyright 2018 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
15 #ifndef ABSL_CONTAINER_INTERNAL_RAW_HASH_MAP_H_
16 #define ABSL_CONTAINER_INTERNAL_RAW_HASH_MAP_H_
17 
18 #include <tuple>
19 #include <type_traits>
20 #include <utility>
21 
23 #include "absl/container/internal/raw_hash_set.h" // IWYU pragma: export
24 
25 namespace absl {
26 namespace container_internal {
27 
28 template <class Policy, class Hash, class Eq, class Alloc>
29 class raw_hash_map : public raw_hash_set<Policy, Hash, Eq, Alloc> {
30  // P is Policy. It's passed as a template argument to support maps that have
31  // incomplete types as values, as in unordered_map<K, IncompleteType>.
32  // MappedReference<> may be a non-reference type.
33  template <class P>
34  using MappedReference = decltype(P::value(
35  std::addressof(std::declval<typename raw_hash_map::reference>())));
36 
37  // MappedConstReference<> may be a non-reference type.
38  template <class P>
39  using MappedConstReference = decltype(P::value(
40  std::addressof(std::declval<typename raw_hash_map::const_reference>())));
41 
42  using KeyArgImpl =
44 
45  public:
46  using key_type = typename Policy::key_type;
47  using mapped_type = typename Policy::mapped_type;
48  template <class K>
49  using key_arg = typename KeyArgImpl::template type<K, key_type>;
50 
51  static_assert(!std::is_reference<key_type>::value, "");
52  // TODO(alkis): remove this assertion and verify that reference mapped_type is
53  // supported.
54  static_assert(!std::is_reference<mapped_type>::value, "");
55 
56  using iterator = typename raw_hash_map::raw_hash_set::iterator;
57  using const_iterator = typename raw_hash_map::raw_hash_set::const_iterator;
58 
60  using raw_hash_map::raw_hash_set::raw_hash_set;
61 
62  // The last two template parameters ensure that both arguments are rvalues
63  // (lvalue arguments are handled by the overloads below). This is necessary
64  // for supporting bitfield arguments.
65  //
66  // union { int n : 1; };
67  // flat_hash_map<int, int> m;
68  // m.insert_or_assign(n, n);
69  template <class K = key_type, class V = mapped_type, K* = nullptr,
70  V* = nullptr>
71  std::pair<iterator, bool> insert_or_assign(key_arg<K>&& k, V&& v) {
72  return insert_or_assign_impl(std::forward<K>(k), std::forward<V>(v));
73  }
74 
75  template <class K = key_type, class V = mapped_type, K* = nullptr>
76  std::pair<iterator, bool> insert_or_assign(key_arg<K>&& k, const V& v) {
77  return insert_or_assign_impl(std::forward<K>(k), v);
78  }
79 
80  template <class K = key_type, class V = mapped_type, V* = nullptr>
81  std::pair<iterator, bool> insert_or_assign(const key_arg<K>& k, V&& v) {
82  return insert_or_assign_impl(k, std::forward<V>(v));
83  }
84 
85  template <class K = key_type, class V = mapped_type>
86  std::pair<iterator, bool> insert_or_assign(const key_arg<K>& k, const V& v) {
87  return insert_or_assign_impl(k, v);
88  }
89 
90  template <class K = key_type, class V = mapped_type, K* = nullptr,
91  V* = nullptr>
93  return insert_or_assign(std::forward<K>(k), std::forward<V>(v)).first;
94  }
95 
96  template <class K = key_type, class V = mapped_type, K* = nullptr>
98  return insert_or_assign(std::forward<K>(k), v).first;
99  }
100 
101  template <class K = key_type, class V = mapped_type, V* = nullptr>
103  return insert_or_assign(k, std::forward<V>(v)).first;
104  }
105 
106  template <class K = key_type, class V = mapped_type>
108  return insert_or_assign(k, v).first;
109  }
110 
111  template <class K = key_type, class... Args,
112  typename std::enable_if<
114  K* = nullptr>
115  std::pair<iterator, bool> try_emplace(key_arg<K>&& k, Args&&... args) {
116  return try_emplace_impl(std::forward<K>(k), std::forward<Args>(args)...);
117  }
118 
119  template <class K = key_type, class... Args,
120  typename std::enable_if<
122  std::pair<iterator, bool> try_emplace(const key_arg<K>& k, Args&&... args) {
123  return try_emplace_impl(k, std::forward<Args>(args)...);
124  }
125 
126  template <class K = key_type, class... Args, K* = nullptr>
128  return try_emplace(std::forward<K>(k), std::forward<Args>(args)...).first;
129  }
130 
131  template <class K = key_type, class... Args>
132  iterator try_emplace(const_iterator, const key_arg<K>& k, Args&&... args) {
133  return try_emplace(k, std::forward<Args>(args)...).first;
134  }
135 
136  template <class K = key_type, class P = Policy>
138  auto it = this->find(key);
139  if (it == this->end()) std::abort();
140  return Policy::value(&*it);
141  }
142 
143  template <class K = key_type, class P = Policy>
145  auto it = this->find(key);
146  if (it == this->end()) std::abort();
147  return Policy::value(&*it);
148  }
149 
150  template <class K = key_type, class P = Policy, K* = nullptr>
152  return Policy::value(&*try_emplace(std::forward<K>(key)).first);
153  }
154 
155  template <class K = key_type, class P = Policy>
157  return Policy::value(&*try_emplace(key).first);
158  }
159 
160  private:
161  template <class K, class V>
162  std::pair<iterator, bool> insert_or_assign_impl(K&& k, V&& v) {
163  auto res = this->find_or_prepare_insert(k);
164  if (res.second)
165  this->emplace_at(res.first, std::forward<K>(k), std::forward<V>(v));
166  else
167  Policy::value(&*this->iterator_at(res.first)) = std::forward<V>(v);
168  return {this->iterator_at(res.first), res.second};
169  }
170 
171  template <class K = key_type, class... Args>
172  std::pair<iterator, bool> try_emplace_impl(K&& k, Args&&... args) {
173  auto res = this->find_or_prepare_insert(k);
174  if (res.second)
175  this->emplace_at(res.first, std::piecewise_construct,
176  std::forward_as_tuple(std::forward<K>(k)),
177  std::forward_as_tuple(std::forward<Args>(args)...));
178  return {this->iterator_at(res.first), res.second};
179  }
180 };
181 
182 } // namespace container_internal
183 } // namespace absl
184 
185 #endif // ABSL_CONTAINER_INTERNAL_RAW_HASH_MAP_H_
int v
Definition: variant_test.cc:81
iterator insert_or_assign(const_iterator, const key_arg< K > &k, const V &v)
Definition: raw_hash_map.h:107
MappedReference< P > operator[](const key_arg< K > &key)
Definition: raw_hash_map.h:156
std::pair< iterator, bool > insert_or_assign(key_arg< K > &&k, const V &v)
Definition: raw_hash_map.h:76
iterator insert_or_assign(const_iterator, key_arg< K > &&k, V &&v)
Definition: raw_hash_map.h:92
iterator insert_or_assign(const_iterator, const key_arg< K > &k, V &&v)
Definition: raw_hash_map.h:102
std::pair< iterator, bool > insert_or_assign(const key_arg< K > &k, V &&v)
Definition: raw_hash_map.h:81
std::pair< iterator, bool > try_emplace(key_arg< K > &&k, Args &&...args)
Definition: raw_hash_map.h:115
std::pair< iterator, bool > try_emplace_impl(K &&k, Args &&...args)
Definition: raw_hash_map.h:172
void emplace_at(size_t i, Args &&...args)
Definition: algorithm.h:29
MappedReference< P > operator[](key_arg< K > &&key)
Definition: raw_hash_map.h:151
MappedReference< P > at(const key_arg< K > &key)
Definition: raw_hash_map.h:137
iterator try_emplace(const_iterator, key_arg< K > &&k, Args &&...args)
Definition: raw_hash_map.h:127
size_t value
typename absl::container_internal::FlatHashMapPolicy< K, V >::mapped_type mapped_type
Definition: raw_hash_map.h:47
decltype(P::value(std::addressof(std::declval< typename raw_hash_map::reference >()))) MappedReference
Definition: raw_hash_map.h:35
MappedConstReference< P > at(const key_arg< K > &key) const
Definition: raw_hash_map.h:144
std::pair< size_t, bool > find_or_prepare_insert(const K &key)
iterator insert_or_assign(const_iterator, key_arg< K > &&k, const V &v)
Definition: raw_hash_map.h:97
std::pair< iterator, bool > insert_or_assign_impl(K &&k, V &&v)
Definition: raw_hash_map.h:162
std::pair< iterator, bool > try_emplace(const key_arg< K > &k, Args &&...args)
Definition: raw_hash_map.h:122
decltype(P::value(std::addressof(std::declval< typename raw_hash_map::const_reference >()))) MappedConstReference
Definition: raw_hash_map.h:40
iterator find(const key_arg< K > &key, size_t hash)
std::pair< iterator, bool > insert_or_assign(key_arg< K > &&k, V &&v)
Definition: raw_hash_map.h:71
iterator try_emplace(const_iterator, const key_arg< K > &k, Args &&...args)
Definition: raw_hash_map.h:132
std::pair< iterator, bool > insert_or_assign(const key_arg< K > &k, const V &v)
Definition: raw_hash_map.h:86


abseil_cpp
Author(s):
autogenerated on Tue Jun 18 2019 19:44:37