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 | |
19 | using ::testing::ElementsAre; |
20 | |
21 | namespace base { |
22 | |
23 | TEST(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 | |
37 | TEST(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 | |
51 | TEST(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 | |
68 | TEST(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 | |
83 | TEST(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 | |
103 | TEST(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 | |
109 | TEST(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 | |
121 | TEST(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&) |
142 | TEST(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&&) |
160 | TEST(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&&) |
178 | TEST(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&&) |
217 | TEST(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&&...) |
252 | TEST(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&&...) |
297 | TEST(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 | |
342 | TEST(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 | |