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