1// Copyright 2017 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "base/containers/flat_map.h"
6
7#include <string>
8#include <vector>
9
10#include "base/macros.h"
11#include "base/test/move_only_int.h"
12#include "testing/gmock/include/gmock/gmock.h"
13#include "testing/gtest/include/gtest/gtest.h"
14
15// A flat_map is basically a interface to flat_tree. So several basic
16// operations are tested to make sure things are set up properly, but the bulk
17// of the tests are in flat_tree_unittests.cc.
18
19using ::testing::ElementsAre;
20
21namespace base {
22
23TEST(FlatMap, IncompleteType) {
24 struct A {
25 using Map = flat_map<A, A>;
26 int data;
27 Map set_with_incomplete_type;
28 Map::iterator it;
29 Map::const_iterator cit;
30
31 // We do not declare operator< because clang complains that it's unused.
32 };
33
34 A a;
35}
36
37TEST(FlatMap, RangeConstructor) {
38 flat_map<int, int>::value_type input_vals[] = {
39 {1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}};
40
41 flat_map<int, int> first(std::begin(input_vals), std::end(input_vals));
42 EXPECT_THAT(first, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 1),
43 std::make_pair(3, 1)));
44
45 flat_map<int, int> last(std::begin(input_vals), std::end(input_vals),
46 KEEP_LAST_OF_DUPES);
47 EXPECT_THAT(last, ElementsAre(std::make_pair(1, 3), std::make_pair(2, 3),
48 std::make_pair(3, 3)));
49}
50
51TEST(FlatMap, MoveConstructor) {
52 using pair = std::pair<MoveOnlyInt, MoveOnlyInt>;
53
54 flat_map<MoveOnlyInt, MoveOnlyInt> original;
55 original.insert(pair(MoveOnlyInt(1), MoveOnlyInt(1)));
56 original.insert(pair(MoveOnlyInt(2), MoveOnlyInt(2)));
57 original.insert(pair(MoveOnlyInt(3), MoveOnlyInt(3)));
58 original.insert(pair(MoveOnlyInt(4), MoveOnlyInt(4)));
59
60 flat_map<MoveOnlyInt, MoveOnlyInt> moved(std::move(original));
61
62 EXPECT_EQ(1U, moved.count(MoveOnlyInt(1)));
63 EXPECT_EQ(1U, moved.count(MoveOnlyInt(2)));
64 EXPECT_EQ(1U, moved.count(MoveOnlyInt(3)));
65 EXPECT_EQ(1U, moved.count(MoveOnlyInt(4)));
66}
67
68TEST(FlatMap, VectorConstructor) {
69 using IntPair = std::pair<int, int>;
70 using IntMap = flat_map<int, int>;
71 {
72 std::vector<IntPair> vect{{1, 1}, {1, 2}, {2, 1}};
73 IntMap map(std::move(vect));
74 EXPECT_THAT(map, ElementsAre(IntPair(1, 1), IntPair(2, 1)));
75 }
76 {
77 std::vector<IntPair> vect{{1, 1}, {1, 2}, {2, 1}};
78 IntMap map(std::move(vect), KEEP_LAST_OF_DUPES);
79 EXPECT_THAT(map, ElementsAre(IntPair(1, 2), IntPair(2, 1)));
80 }
81}
82
83TEST(FlatMap, InitializerListConstructor) {
84 {
85 flat_map<int, int> cont(
86 {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {1, 2}, {10, 10}, {8, 8}});
87 EXPECT_THAT(cont, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2),
88 std::make_pair(3, 3), std::make_pair(4, 4),
89 std::make_pair(5, 5), std::make_pair(8, 8),
90 std::make_pair(10, 10)));
91 }
92 {
93 flat_map<int, int> cont(
94 {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {1, 2}, {10, 10}, {8, 8}},
95 KEEP_LAST_OF_DUPES);
96 EXPECT_THAT(cont, ElementsAre(std::make_pair(1, 2), std::make_pair(2, 2),
97 std::make_pair(3, 3), std::make_pair(4, 4),
98 std::make_pair(5, 5), std::make_pair(8, 8),
99 std::make_pair(10, 10)));
100 }
101}
102
103TEST(FlatMap, InitializerListAssignment) {
104 flat_map<int, int> cont;
105 cont = {{1, 1}, {2, 2}};
106 EXPECT_THAT(cont, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2)));
107}
108
109TEST(FlatMap, InsertFindSize) {
110 base::flat_map<int, int> s;
111 s.insert(std::make_pair(1, 1));
112 s.insert(std::make_pair(1, 1));
113 s.insert(std::make_pair(2, 2));
114
115 EXPECT_EQ(2u, s.size());
116 EXPECT_EQ(std::make_pair(1, 1), *s.find(1));
117 EXPECT_EQ(std::make_pair(2, 2), *s.find(2));
118 EXPECT_EQ(s.end(), s.find(7));
119}
120
121TEST(FlatMap, CopySwap) {
122 base::flat_map<int, int> original;
123 original.insert({1, 1});
124 original.insert({2, 2});
125 EXPECT_THAT(original,
126 ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2)));
127
128 base::flat_map<int, int> copy(original);
129 EXPECT_THAT(copy, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2)));
130
131 copy.erase(copy.begin());
132 copy.insert({10, 10});
133 EXPECT_THAT(copy, ElementsAre(std::make_pair(2, 2), std::make_pair(10, 10)));
134
135 original.swap(copy);
136 EXPECT_THAT(original,
137 ElementsAre(std::make_pair(2, 2), std::make_pair(10, 10)));
138 EXPECT_THAT(copy, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2)));
139}
140
141// operator[](const Key&)
142TEST(FlatMap, SubscriptConstKey) {
143 base::flat_map<std::string, int> m;
144
145 // Default construct elements that don't exist yet.
146 int& s = m["a"];
147 EXPECT_EQ(0, s);
148 EXPECT_EQ(1u, m.size());
149
150 // The returned mapped reference should refer into the map.
151 s = 22;
152 EXPECT_EQ(22, m["a"]);
153
154 // Overwrite existing elements.
155 m["a"] = 44;
156 EXPECT_EQ(44, m["a"]);
157}
158
159// operator[](Key&&)
160TEST(FlatMap, SubscriptMoveOnlyKey) {
161 base::flat_map<MoveOnlyInt, int> m;
162
163 // Default construct elements that don't exist yet.
164 int& s = m[MoveOnlyInt(1)];
165 EXPECT_EQ(0, s);
166 EXPECT_EQ(1u, m.size());
167
168 // The returned mapped reference should refer into the map.
169 s = 22;
170 EXPECT_EQ(22, m[MoveOnlyInt(1)]);
171
172 // Overwrite existing elements.
173 m[MoveOnlyInt(1)] = 44;
174 EXPECT_EQ(44, m[MoveOnlyInt(1)]);
175}
176
177// insert_or_assign(K&&, M&&)
178TEST(FlatMap, InsertOrAssignMoveOnlyKey) {
179 base::flat_map<MoveOnlyInt, MoveOnlyInt> m;
180
181 // Initial insertion should return an iterator to the element and set the
182 // second pair member to |true|. The inserted key and value should be moved
183 // from.
184 MoveOnlyInt key(1);
185 MoveOnlyInt val(22);
186 auto result = m.insert_or_assign(std::move(key), std::move(val));
187 EXPECT_EQ(1, result.first->first.data());
188 EXPECT_EQ(22, result.first->second.data());
189 EXPECT_TRUE(result.second);
190 EXPECT_EQ(1u, m.size());
191 EXPECT_EQ(0, key.data()); // moved from
192 EXPECT_EQ(0, val.data()); // moved from
193
194 // Second call with same key should result in an assignment, overwriting the
195 // old value. Assignment should be indicated by setting the second pair member
196 // to |false|. Only the inserted value should be moved from, the key should be
197 // left intact.
198 key = MoveOnlyInt(1);
199 val = MoveOnlyInt(44);
200 result = m.insert_or_assign(std::move(key), std::move(val));
201 EXPECT_EQ(1, result.first->first.data());
202 EXPECT_EQ(44, result.first->second.data());
203 EXPECT_FALSE(result.second);
204 EXPECT_EQ(1u, m.size());
205 EXPECT_EQ(1, key.data()); // not moved from
206 EXPECT_EQ(0, val.data()); // moved from
207
208 // Check that random insertion results in sorted range.
209 base::flat_map<MoveOnlyInt, int> map;
210 for (int i : {3, 1, 5, 6, 8, 7, 0, 9, 4, 2}) {
211 map.insert_or_assign(MoveOnlyInt(i), i);
212 EXPECT_TRUE(std::is_sorted(map.begin(), map.end()));
213 }
214}
215
216// insert_or_assign(const_iterator hint, K&&, M&&)
217TEST(FlatMap, InsertOrAssignMoveOnlyKeyWithHint) {
218 base::flat_map<MoveOnlyInt, MoveOnlyInt> m;
219
220 // Initial insertion should return an iterator to the element. The inserted
221 // key and value should be moved from.
222 MoveOnlyInt key(1);
223 MoveOnlyInt val(22);
224 auto result = m.insert_or_assign(m.end(), std::move(key), std::move(val));
225 EXPECT_EQ(1, result->first.data());
226 EXPECT_EQ(22, result->second.data());
227 EXPECT_EQ(1u, m.size());
228 EXPECT_EQ(0, key.data()); // moved from
229 EXPECT_EQ(0, val.data()); // moved from
230
231 // Second call with same key should result in an assignment, overwriting the
232 // old value. Only the inserted value should be moved from, the key should be
233 // left intact.
234 key = MoveOnlyInt(1);
235 val = MoveOnlyInt(44);
236 result = m.insert_or_assign(m.end(), std::move(key), std::move(val));
237 EXPECT_EQ(1, result->first.data());
238 EXPECT_EQ(44, result->second.data());
239 EXPECT_EQ(1u, m.size());
240 EXPECT_EQ(1, key.data()); // not moved from
241 EXPECT_EQ(0, val.data()); // moved from
242
243 // Check that random insertion results in sorted range.
244 base::flat_map<MoveOnlyInt, int> map;
245 for (int i : {3, 1, 5, 6, 8, 7, 0, 9, 4, 2}) {
246 map.insert_or_assign(map.end(), MoveOnlyInt(i), i);
247 EXPECT_TRUE(std::is_sorted(map.begin(), map.end()));
248 }
249}
250
251// try_emplace(K&&, Args&&...)
252TEST(FlatMap, TryEmplaceMoveOnlyKey) {
253 base::flat_map<MoveOnlyInt, std::pair<MoveOnlyInt, MoveOnlyInt>> m;
254
255 // Trying to emplace into an empty map should succeed. Insertion should return
256 // an iterator to the element and set the second pair member to |true|. The
257 // inserted key and value should be moved from.
258 MoveOnlyInt key(1);
259 MoveOnlyInt val1(22);
260 MoveOnlyInt val2(44);
261 // Test piecewise construction of mapped_type.
262 auto result = m.try_emplace(std::move(key), std::move(val1), std::move(val2));
263 EXPECT_EQ(1, result.first->first.data());
264 EXPECT_EQ(22, result.first->second.first.data());
265 EXPECT_EQ(44, result.first->second.second.data());
266 EXPECT_TRUE(result.second);
267 EXPECT_EQ(1u, m.size());
268 EXPECT_EQ(0, key.data()); // moved from
269 EXPECT_EQ(0, val1.data()); // moved from
270 EXPECT_EQ(0, val2.data()); // moved from
271
272 // Second call with same key should result in a no-op, returning an iterator
273 // to the existing element and returning false as the second pair member.
274 // Key and values that were attempted to be inserted should be left intact.
275 key = MoveOnlyInt(1);
276 auto paired_val = std::make_pair(MoveOnlyInt(33), MoveOnlyInt(55));
277 // Test construction of mapped_type from pair.
278 result = m.try_emplace(std::move(key), std::move(paired_val));
279 EXPECT_EQ(1, result.first->first.data());
280 EXPECT_EQ(22, result.first->second.first.data());
281 EXPECT_EQ(44, result.first->second.second.data());
282 EXPECT_FALSE(result.second);
283 EXPECT_EQ(1u, m.size());
284 EXPECT_EQ(1, key.data()); // not moved from
285 EXPECT_EQ(33, paired_val.first.data()); // not moved from
286 EXPECT_EQ(55, paired_val.second.data()); // not moved from
287
288 // Check that random insertion results in sorted range.
289 base::flat_map<MoveOnlyInt, int> map;
290 for (int i : {3, 1, 5, 6, 8, 7, 0, 9, 4, 2}) {
291 map.try_emplace(MoveOnlyInt(i), i);
292 EXPECT_TRUE(std::is_sorted(map.begin(), map.end()));
293 }
294}
295
296// try_emplace(const_iterator hint, K&&, Args&&...)
297TEST(FlatMap, TryEmplaceMoveOnlyKeyWithHint) {
298 base::flat_map<MoveOnlyInt, std::pair<MoveOnlyInt, MoveOnlyInt>> m;
299
300 // Trying to emplace into an empty map should succeed. Insertion should return
301 // an iterator to the element. The inserted key and value should be moved
302 // from.
303 MoveOnlyInt key(1);
304 MoveOnlyInt val1(22);
305 MoveOnlyInt val2(44);
306 // Test piecewise construction of mapped_type.
307 auto result =
308 m.try_emplace(m.end(), std::move(key), std::move(val1), std::move(val2));
309 EXPECT_EQ(1, result->first.data());
310 EXPECT_EQ(22, result->second.first.data());
311 EXPECT_EQ(44, result->second.second.data());
312 EXPECT_EQ(1u, m.size());
313 EXPECT_EQ(0, key.data()); // moved from
314 EXPECT_EQ(0, val1.data()); // moved from
315 EXPECT_EQ(0, val2.data()); // moved from
316
317 // Second call with same key should result in a no-op, returning an iterator
318 // to the existing element. Key and values that were attempted to be inserted
319 // should be left intact.
320 key = MoveOnlyInt(1);
321 val1 = MoveOnlyInt(33);
322 val2 = MoveOnlyInt(55);
323 auto paired_val = std::make_pair(MoveOnlyInt(33), MoveOnlyInt(55));
324 // Test construction of mapped_type from pair.
325 result = m.try_emplace(m.end(), std::move(key), std::move(paired_val));
326 EXPECT_EQ(1, result->first.data());
327 EXPECT_EQ(22, result->second.first.data());
328 EXPECT_EQ(44, result->second.second.data());
329 EXPECT_EQ(1u, m.size());
330 EXPECT_EQ(1, key.data()); // not moved from
331 EXPECT_EQ(33, paired_val.first.data()); // not moved from
332 EXPECT_EQ(55, paired_val.second.data()); // not moved from
333
334 // Check that random insertion results in sorted range.
335 base::flat_map<MoveOnlyInt, int> map;
336 for (int i : {3, 1, 5, 6, 8, 7, 0, 9, 4, 2}) {
337 map.try_emplace(map.end(), MoveOnlyInt(i), i);
338 EXPECT_TRUE(std::is_sorted(map.begin(), map.end()));
339 }
340}
341
342TEST(FlatMap, UsingTransparentCompare) {
343 using ExplicitInt = base::MoveOnlyInt;
344 base::flat_map<ExplicitInt, int> m;
345 const auto& m1 = m;
346 int x = 0;
347
348 // Check if we can use lookup functions without converting to key_type.
349 // Correctness is checked in flat_tree tests.
350 m.count(x);
351 m1.count(x);
352 m.find(x);
353 m1.find(x);
354 m.equal_range(x);
355 m1.equal_range(x);
356 m.lower_bound(x);
357 m1.lower_bound(x);
358 m.upper_bound(x);
359 m1.upper_bound(x);
360 m.erase(x);
361
362 // Check if we broke overload resolution.
363 m.emplace(ExplicitInt(0), 0);
364 m.emplace(ExplicitInt(1), 0);
365 m.erase(m.begin());
366 m.erase(m.cbegin());
367}
368
369} // namespace base
370