OLD | NEW |
1 // Copyright 2017 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "base/containers/flat_set.h" | 5 #include "base/containers/flat_set.h" |
6 | 6 |
7 // Following tests are ported and extended tests from libcpp for std::set. | |
8 // They can be found here: | |
9 // https://github.com/llvm-mirror/libcxx/tree/master/test/std/containers/associa
tive/set | |
10 // | |
11 // Not ported tests: | |
12 // * No tests with PrivateConstructor and std::less<> changed to std::less<T> | |
13 // These tests have to do with C++14 std::less<> | |
14 // http://en.cppreference.com/w/cpp/utility/functional/less_void | |
15 // and add support for templated versions of lookup functions. | |
16 // Current implementation of flat containers doesn't support it. | |
17 // * No tests with TemplateConstructor. | |
18 // Library working group issue: LWG #2059 | |
19 // http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#2059 | |
20 // There is an ambiguity between erase with an iterator and erase with a key, | |
21 // if key has a templated constructor. We have to fix this. | |
22 // * No tests for max_size() | |
23 // Has to do with allocator support. | |
24 // * No tests with DefaultOnly. | |
25 // Standard containers allocate each element in the separate node on the heap | |
26 // and then manipulate these nodes. Flat containers store their elements in | |
27 // contiguous memory and move them around, type is required to be movable. | |
28 // * No tests for N3644. | |
29 // This proposal suggests that all default constructed iterators compare | |
30 // equal. Currently we use std::vector iterators and they don't implement | |
31 // this. | |
32 // * No tests with min_allocator and no tests counting allocations. | |
33 // Flat sets currently don't support allocators. | |
34 // * No tests for range insertion. Flat sets currently do not support this | |
35 // functionality. | |
36 | |
37 #include <string> | 7 #include <string> |
38 #include <vector> | 8 #include <vector> |
39 | 9 |
| 10 #include "base/containers/container_test_utils.h" |
40 #include "base/macros.h" | 11 #include "base/macros.h" |
41 #include "testing/gmock/include/gmock/gmock.h" | 12 #include "testing/gmock/include/gmock/gmock.h" |
42 #include "testing/gtest/include/gtest/gtest.h" | 13 #include "testing/gtest/include/gtest/gtest.h" |
43 | 14 |
44 namespace { | 15 // A flat_set is basically a interface to flat_tree. So several basic |
45 | 16 // operations are tested to make sure things are set up properly, but the bulk |
46 class MoveOnly { | 17 // of the tests are in flat_tree_unittests.cc. |
47 public: | |
48 explicit MoveOnly(int data = 1) : data_(data) {} | |
49 MoveOnly(MoveOnly&& other) : data_(other.data_) { other.data_ = 0; } | |
50 MoveOnly& operator=(MoveOnly&& other) { | |
51 data_ = other.data_; | |
52 other.data_ = 0; | |
53 return *this; | |
54 } | |
55 | |
56 friend bool operator<(const MoveOnly& lhs, const MoveOnly& rhs) { | |
57 return lhs.data_ < rhs.data_; | |
58 } | |
59 | |
60 int data() const { return data_; } | |
61 | |
62 private: | |
63 int data_; | |
64 | |
65 DISALLOW_COPY_AND_ASSIGN(MoveOnly); | |
66 }; | |
67 | |
68 template <class It> | |
69 class InputIterator { | |
70 public: | |
71 using iterator_category = std::input_iterator_tag; | |
72 using value_type = typename std::iterator_traits<It>::value_type; | |
73 using difference_type = typename std::iterator_traits<It>::difference_type; | |
74 using pointer = It; | |
75 using reference = typename std::iterator_traits<It>::reference; | |
76 | |
77 InputIterator() : it_() {} | |
78 explicit InputIterator(It it) : it_(it) {} | |
79 | |
80 reference operator*() const { return *it_; } | |
81 pointer operator->() const { return it_; } | |
82 | |
83 InputIterator& operator++() { | |
84 ++it_; | |
85 return *this; | |
86 } | |
87 InputIterator operator++(int) { | |
88 InputIterator tmp(*this); | |
89 ++(*this); | |
90 return tmp; | |
91 } | |
92 | |
93 friend bool operator==(const InputIterator& lhs, const InputIterator& rhs) { | |
94 return lhs.it_ == rhs.it_; | |
95 } | |
96 friend bool operator!=(const InputIterator& lhs, const InputIterator& rhs) { | |
97 return !(lhs == rhs); | |
98 } | |
99 | |
100 private: | |
101 It it_; | |
102 }; | |
103 | |
104 template <typename It> | |
105 InputIterator<It> MakeInputIterator(It it) { | |
106 return InputIterator<It>(it); | |
107 } | |
108 | |
109 class Emplaceable { | |
110 public: | |
111 Emplaceable() : Emplaceable(0, 0.0) {} | |
112 Emplaceable(int i, double d) : int_(i), double_(d) {} | |
113 Emplaceable(Emplaceable&& other) : int_(other.int_), double_(other.double_) { | |
114 other.int_ = 0; | |
115 other.double_ = 0.0; | |
116 } | |
117 | |
118 Emplaceable& operator=(Emplaceable&& other) { | |
119 int_ = other.int_; | |
120 other.int_ = 0; | |
121 double_ = other.double_; | |
122 other.double_ = 0.0; | |
123 return *this; | |
124 } | |
125 | |
126 friend bool operator==(const Emplaceable& lhs, const Emplaceable& rhs) { | |
127 return std::tie(lhs.int_, lhs.double_) == std::tie(rhs.int_, rhs.double_); | |
128 } | |
129 | |
130 friend bool operator<(const Emplaceable& lhs, const Emplaceable& rhs) { | |
131 return std::tie(lhs.int_, lhs.double_) < std::tie(rhs.int_, rhs.double_); | |
132 } | |
133 | |
134 private: | |
135 int int_; | |
136 double double_; | |
137 | |
138 DISALLOW_COPY_AND_ASSIGN(Emplaceable); | |
139 }; | |
140 | |
141 class NonDefaultConstructibleCompare { | |
142 public: | |
143 explicit NonDefaultConstructibleCompare(int) {} | |
144 | |
145 template <typename T> | |
146 bool operator()(const T& lhs, const T& rhs) { | |
147 return std::less<T>()(lhs, rhs); | |
148 } | |
149 }; | |
150 | |
151 // Common test sets. | |
152 using IntSet = base::flat_set<int>; | |
153 using MoveOnlySet = base::flat_set<MoveOnly>; | |
154 using EmplaceableSet = base::flat_set<Emplaceable>; | |
155 using ReversedSet = base::flat_set<int, std::greater<int>>; | |
156 | |
157 // TODO(dyaroshev): replace less<int> with less<>, once we have it | |
158 // crbug.com/682254. | |
159 using SetWithLess = base::flat_set<int, std::less<int>>; | |
160 | |
161 using SetWithStrangeCompare = | |
162 base::flat_set<int, NonDefaultConstructibleCompare>; | |
163 | 18 |
164 using ::testing::ElementsAre; | 19 using ::testing::ElementsAre; |
165 | 20 |
166 } // namespace | 21 namespace base { |
167 | |
168 // ---------------------------------------------------------------------------- | |
169 // Class. | |
170 | |
171 // Check that base::flat_set and its iterators can be instantiated with an | |
172 // incomplete type. | |
173 | 22 |
174 TEST(FlatSet, IncompleteType) { | 23 TEST(FlatSet, IncompleteType) { |
175 struct A { | 24 struct A { |
176 using Set = base::flat_set<A>; | 25 using Set = flat_set<A>; |
177 int data; | 26 int data; |
178 Set set_with_incomplete_type; | 27 Set set_with_incomplete_type; |
179 Set::iterator it; | 28 Set::iterator it; |
180 Set::const_iterator cit; | 29 Set::const_iterator cit; |
181 | 30 |
182 // We do not declare operator< because clang complains that it's unused. | 31 // We do not declare operator< because clang complains that it's unused. |
183 }; | 32 }; |
184 | 33 |
185 A a; | 34 A a; |
186 } | 35 } |
187 | 36 |
188 TEST(FlatSet, Stability) { | 37 TEST(FlatSet, RangeConstructor) { |
189 using Pair = std::pair<int, int>; | 38 flat_set<int>::value_type input_vals[] = {1, 1, 1, 2, 2, 2, 3, 3, 3}; |
190 | 39 |
191 struct LessByFirst { | 40 flat_set<int> cont(std::begin(input_vals), std::end(input_vals)); |
192 bool operator()(const Pair& lhs, const Pair& rhs) { | 41 EXPECT_THAT(cont, ElementsAre(1, 2, 3)); |
193 return lhs.first < rhs.first; | |
194 } | |
195 }; | |
196 | |
197 using Set = base::flat_set<Pair, LessByFirst>; | |
198 | |
199 // Constructors are not stable. | |
200 Set cont{{0, 0}, {1, 0}, {0, 1}, {2, 0}, {0, 2}, {1, 1}}; | |
201 | |
202 auto NoneOfSecondsAreTwo = [&cont] { | |
203 return std::none_of(cont.begin(), cont.end(), | |
204 [](const Pair& elem) { return elem.second == 2; }); | |
205 }; | |
206 | |
207 // Should not replace existing. | |
208 cont.insert(Pair(0, 2)); | |
209 cont.insert(Pair(1, 2)); | |
210 cont.insert(Pair(2, 2)); | |
211 | |
212 EXPECT_TRUE(NoneOfSecondsAreTwo()) | |
213 << "insert should be stable with respect to constructor"; | |
214 | |
215 cont.insert(Pair(3, 0)); | |
216 cont.insert(Pair(3, 2)); | |
217 | |
218 EXPECT_TRUE(NoneOfSecondsAreTwo()) | |
219 << "insert should be stable with respect to previous insert"; | |
220 } | 42 } |
221 | 43 |
222 // ---------------------------------------------------------------------------- | |
223 // Types. | |
224 | |
225 // key_type | |
226 // key_compare | |
227 // value_type | |
228 // value_compare | |
229 // pointer | |
230 // const_pointer | |
231 // reference | |
232 // const_reference | |
233 // size_type | |
234 // difference_type | |
235 // iterator | |
236 // const_iterator | |
237 // reverse_iterator | |
238 // const_reverse_iterator | |
239 | |
240 TEST(FlatSet, Types) { | |
241 // These are guaranteed to be portable. | |
242 static_assert((std::is_same<int, IntSet::key_type>::value), ""); | |
243 static_assert((std::is_same<int, IntSet::value_type>::value), ""); | |
244 static_assert((std::is_same<std::less<int>, IntSet::key_compare>::value), ""); | |
245 static_assert((std::is_same<std::less<int>, IntSet::value_compare>::value), | |
246 ""); | |
247 static_assert((std::is_same<int&, IntSet::reference>::value), ""); | |
248 static_assert((std::is_same<const int&, IntSet::const_reference>::value), ""); | |
249 static_assert((std::is_same<int*, IntSet::pointer>::value), ""); | |
250 static_assert((std::is_same<const int*, IntSet::const_pointer>::value), ""); | |
251 } | |
252 | |
253 // ---------------------------------------------------------------------------- | |
254 // Lifetime. | |
255 | |
256 // flat_set() | |
257 // flat_set(const Compare& comp) | |
258 | |
259 TEST(FlatSet, DefaultConstructor) { | |
260 { | |
261 IntSet cont; | |
262 EXPECT_THAT(cont, ElementsAre()); | |
263 } | |
264 | |
265 { | |
266 SetWithStrangeCompare cont(NonDefaultConstructibleCompare(0)); | |
267 EXPECT_THAT(cont, ElementsAre()); | |
268 } | |
269 } | |
270 | |
271 // flat_set(InputIterator first, | |
272 // InputIterator last, | |
273 // const Compare& comp = Compare()) | |
274 | |
275 TEST(FlatSet, RangeConstructor) { | |
276 { | |
277 IntSet::value_type input_vals[] = {1, 1, 1, 2, 2, 2, 3, 3, 3}; | |
278 | |
279 IntSet cont(MakeInputIterator(std::begin(input_vals)), | |
280 MakeInputIterator(std::end(input_vals))); | |
281 EXPECT_THAT(cont, ElementsAre(1, 2, 3)); | |
282 } | |
283 { | |
284 SetWithStrangeCompare::value_type input_vals[] = {1, 1, 1, 2, 2, | |
285 2, 3, 3, 3}; | |
286 | |
287 SetWithStrangeCompare cont(MakeInputIterator(std::begin(input_vals)), | |
288 MakeInputIterator(std::end(input_vals)), | |
289 NonDefaultConstructibleCompare(0)); | |
290 EXPECT_THAT(cont, ElementsAre(1, 2, 3)); | |
291 } | |
292 } | |
293 | |
294 // flat_set(const flat_set& x) | |
295 | |
296 TEST(FlatSet, CopyConstructor) { | |
297 IntSet original{1, 2, 3, 4}; | |
298 IntSet copied(original); | |
299 | |
300 EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4)); | |
301 | |
302 EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4)); | |
303 EXPECT_THAT(original, ElementsAre(1, 2, 3, 4)); | |
304 EXPECT_EQ(original, copied); | |
305 } | |
306 | |
307 // flat_set(flat_set&& x) | |
308 | |
309 TEST(FlatSet, MoveConstructor) { | 44 TEST(FlatSet, MoveConstructor) { |
310 int input_range[] = {1, 2, 3, 4}; | 45 int input_range[] = {1, 2, 3, 4}; |
311 | 46 |
312 MoveOnlySet original(std::begin(input_range), std::end(input_range)); | 47 flat_set<MoveOnlyInt> original(std::begin(input_range), |
313 MoveOnlySet moved(std::move(original)); | 48 std::end(input_range)); |
| 49 flat_set<MoveOnlyInt> moved(std::move(original)); |
314 | 50 |
315 EXPECT_EQ(1U, moved.count(MoveOnly(1))); | 51 EXPECT_EQ(1U, moved.count(MoveOnlyInt(1))); |
316 EXPECT_EQ(1U, moved.count(MoveOnly(2))); | 52 EXPECT_EQ(1U, moved.count(MoveOnlyInt(2))); |
317 EXPECT_EQ(1U, moved.count(MoveOnly(3))); | 53 EXPECT_EQ(1U, moved.count(MoveOnlyInt(3))); |
318 EXPECT_EQ(1U, moved.count(MoveOnly(4))); | 54 EXPECT_EQ(1U, moved.count(MoveOnlyInt(4))); |
319 } | 55 } |
320 | 56 |
321 // flat_set(std::initializer_list<value_type> ilist, | |
322 // const Compare& comp = Compare()) | |
323 | |
324 TEST(FlatSet, InitializerListConstructor) { | 57 TEST(FlatSet, InitializerListConstructor) { |
325 { | 58 flat_set<int> cont{1, 2, 3, 4, 5, 6, 10, 8}; |
326 IntSet cont{1, 2, 3, 4, 5, 6, 10, 8}; | |
327 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10)); | |
328 } | |
329 { | |
330 SetWithStrangeCompare cont({1, 2, 3, 4, 5, 6, 10, 8}, | |
331 NonDefaultConstructibleCompare(0)); | |
332 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10)); | |
333 } | |
334 } | |
335 | |
336 // ---------------------------------------------------------------------------- | |
337 // Assignments. | |
338 | |
339 // flat_set& operator=(const flat_set&) | |
340 | |
341 TEST(FlatSet, CopyAssignable) { | |
342 IntSet original{1, 2, 3, 4}; | |
343 IntSet copied; | |
344 copied = original; | |
345 | |
346 EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4)); | |
347 EXPECT_THAT(original, ElementsAre(1, 2, 3, 4)); | |
348 EXPECT_EQ(original, copied); | |
349 } | |
350 | |
351 // flat_set& operator=(flat_set&&) | |
352 | |
353 TEST(FlatSet, MoveAssignable) { | |
354 int input_range[] = {1, 2, 3, 4}; | |
355 | |
356 MoveOnlySet original(std::begin(input_range), std::end(input_range)); | |
357 MoveOnlySet moved; | |
358 moved = std::move(original); | |
359 | |
360 EXPECT_EQ(1U, moved.count(MoveOnly(1))); | |
361 EXPECT_EQ(1U, moved.count(MoveOnly(2))); | |
362 EXPECT_EQ(1U, moved.count(MoveOnly(3))); | |
363 EXPECT_EQ(1U, moved.count(MoveOnly(4))); | |
364 } | |
365 | |
366 // flat_set& operator=(std::initializer_list<value_type> ilist) | |
367 | |
368 TEST(FlatSet, InitializerListAssignable) { | |
369 IntSet cont{0}; | |
370 cont = {1, 2, 3, 4, 5, 6, 10, 8}; | |
371 | |
372 EXPECT_EQ(0U, cont.count(0)); | |
373 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10)); | 59 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10)); |
374 } | 60 } |
375 | 61 |
376 // -------------------------------------------------------------------------- | 62 TEST(FlatSet, InsertFindSize) { |
377 // Memory management. | 63 base::flat_set<int> s; |
| 64 s.insert(1); |
| 65 s.insert(1); |
| 66 s.insert(2); |
378 | 67 |
379 // void reserve(size_type new_capacity) | 68 EXPECT_EQ(2u, s.size()); |
380 | 69 EXPECT_EQ(1, *s.find(1)); |
381 TEST(FlatSet, Reserve) { | 70 EXPECT_EQ(2, *s.find(2)); |
382 IntSet cont{1, 2, 3}; | 71 EXPECT_EQ(s.end(), s.find(7)); |
383 | |
384 cont.reserve(5); | |
385 EXPECT_LE(5U, cont.capacity()); | |
386 } | 72 } |
387 | 73 |
388 // size_type capacity() const | 74 TEST(FlatSet, CopySwap) { |
| 75 base::flat_set<int> original; |
| 76 original.insert(1); |
| 77 original.insert(2); |
| 78 EXPECT_THAT(original, ElementsAre(1, 2)); |
389 | 79 |
390 TEST(FlatSet, Capacity) { | 80 base::flat_set<int> copy(original); |
391 IntSet cont{1, 2, 3}; | 81 EXPECT_THAT(copy, ElementsAre(1, 2)); |
392 | 82 |
393 EXPECT_LE(cont.size(), cont.capacity()); | 83 copy.erase(copy.begin()); |
394 cont.reserve(5); | 84 copy.insert(10); |
395 EXPECT_LE(cont.size(), cont.capacity()); | 85 EXPECT_THAT(copy, ElementsAre(2, 10)); |
| 86 |
| 87 original.swap(copy); |
| 88 EXPECT_THAT(original, ElementsAre(2, 10)); |
| 89 EXPECT_THAT(copy, ElementsAre(1, 2)); |
396 } | 90 } |
397 | 91 |
398 // void shrink_to_fit() | 92 } // namespace base |
399 | |
400 TEST(FlatSet, ShrinkToFit) { | |
401 IntSet cont{1, 2, 3}; | |
402 | |
403 IntSet::size_type capacity_before = cont.capacity(); | |
404 cont.shrink_to_fit(); | |
405 EXPECT_GE(capacity_before, cont.capacity()); | |
406 } | |
407 | |
408 // ---------------------------------------------------------------------------- | |
409 // Size management. | |
410 | |
411 // void clear() | |
412 | |
413 TEST(FlatSet, Clear) { | |
414 IntSet cont{1, 2, 3, 4, 5, 6, 7, 8}; | |
415 cont.clear(); | |
416 EXPECT_THAT(cont, ElementsAre()); | |
417 } | |
418 | |
419 // size_type size() const | |
420 | |
421 TEST(FlatSet, Size) { | |
422 IntSet cont; | |
423 | |
424 EXPECT_EQ(0U, cont.size()); | |
425 cont.insert(2); | |
426 EXPECT_EQ(1U, cont.size()); | |
427 cont.insert(1); | |
428 EXPECT_EQ(2U, cont.size()); | |
429 cont.insert(3); | |
430 EXPECT_EQ(3U, cont.size()); | |
431 cont.erase(cont.begin()); | |
432 EXPECT_EQ(2U, cont.size()); | |
433 cont.erase(cont.begin()); | |
434 EXPECT_EQ(1U, cont.size()); | |
435 cont.erase(cont.begin()); | |
436 EXPECT_EQ(0U, cont.size()); | |
437 } | |
438 | |
439 // bool empty() const | |
440 | |
441 TEST(FlatSet, Empty) { | |
442 IntSet cont; | |
443 | |
444 EXPECT_TRUE(cont.empty()); | |
445 cont.insert(1); | |
446 EXPECT_FALSE(cont.empty()); | |
447 cont.clear(); | |
448 EXPECT_TRUE(cont.empty()); | |
449 } | |
450 | |
451 // ---------------------------------------------------------------------------- | |
452 // Iterators. | |
453 | |
454 // iterator begin() | |
455 // const_iterator begin() const | |
456 // iterator end() | |
457 // const_iterator end() const | |
458 // | |
459 // reverse_iterator rbegin() | |
460 // const_reverse_iterator rbegin() const | |
461 // reverse_iterator rend() | |
462 // const_reverse_iterator rend() const | |
463 // | |
464 // const_iterator cbegin() const | |
465 // const_iterator cend() const | |
466 // const_reverse_iterator crbegin() const | |
467 // const_reverse_iterator crend() const | |
468 | |
469 TEST(FlatSet, Iterators) { | |
470 IntSet cont{1, 2, 3, 4, 5, 6, 7, 8}; | |
471 | |
472 auto size = static_cast<IntSet::difference_type>(cont.size()); | |
473 | |
474 EXPECT_EQ(size, std::distance(cont.begin(), cont.end())); | |
475 EXPECT_EQ(size, std::distance(cont.cbegin(), cont.cend())); | |
476 EXPECT_EQ(size, std::distance(cont.rbegin(), cont.rend())); | |
477 EXPECT_EQ(size, std::distance(cont.crbegin(), cont.crend())); | |
478 | |
479 { | |
480 IntSet::iterator it = cont.begin(); | |
481 IntSet::const_iterator c_it = cont.cbegin(); | |
482 EXPECT_EQ(it, c_it); | |
483 for (int j = 1; it != cont.end(); ++it, ++c_it, ++j) { | |
484 EXPECT_EQ(j, *it); | |
485 EXPECT_EQ(j, *c_it); | |
486 } | |
487 } | |
488 { | |
489 IntSet::reverse_iterator rit = cont.rbegin(); | |
490 IntSet::const_reverse_iterator c_rit = cont.crbegin(); | |
491 EXPECT_EQ(rit, c_rit); | |
492 for (int j = static_cast<int>(size); rit != cont.rend(); | |
493 ++rit, ++c_rit, --j) { | |
494 EXPECT_EQ(j, *rit); | |
495 EXPECT_EQ(j, *c_rit); | |
496 } | |
497 } | |
498 } | |
499 | |
500 // ---------------------------------------------------------------------------- | |
501 // Insert operations. | |
502 | |
503 // pair<iterator, bool> insert(const value_type& val) | |
504 | |
505 TEST(FlatSet, InsertLValue) { | |
506 IntSet cont; | |
507 | |
508 int value = 2; | |
509 std::pair<IntSet::iterator, bool> result = cont.insert(value); | |
510 EXPECT_TRUE(result.second); | |
511 EXPECT_EQ(cont.begin(), result.first); | |
512 EXPECT_EQ(1U, cont.size()); | |
513 EXPECT_EQ(2, *result.first); | |
514 | |
515 value = 1; | |
516 result = cont.insert(value); | |
517 EXPECT_TRUE(result.second); | |
518 EXPECT_EQ(cont.begin(), result.first); | |
519 EXPECT_EQ(2U, cont.size()); | |
520 EXPECT_EQ(1, *result.first); | |
521 | |
522 value = 3; | |
523 result = cont.insert(value); | |
524 EXPECT_TRUE(result.second); | |
525 EXPECT_EQ(std::prev(cont.end()), result.first); | |
526 EXPECT_EQ(3U, cont.size()); | |
527 EXPECT_EQ(3, *result.first); | |
528 | |
529 value = 3; | |
530 result = cont.insert(value); | |
531 EXPECT_FALSE(result.second); | |
532 EXPECT_EQ(std::prev(cont.end()), result.first); | |
533 EXPECT_EQ(3U, cont.size()); | |
534 EXPECT_EQ(3, *result.first); | |
535 } | |
536 | |
537 // pair<iterator, bool> insert(value_type&& val) | |
538 | |
539 TEST(FlatSet, InsertRValue) { | |
540 MoveOnlySet cont; | |
541 | |
542 std::pair<MoveOnlySet::iterator, bool> result = cont.insert(MoveOnly(2)); | |
543 EXPECT_TRUE(result.second); | |
544 EXPECT_EQ(cont.begin(), result.first); | |
545 EXPECT_EQ(1U, cont.size()); | |
546 EXPECT_EQ(2, result.first->data()); | |
547 | |
548 result = cont.insert(MoveOnly(1)); | |
549 EXPECT_TRUE(result.second); | |
550 EXPECT_EQ(cont.begin(), result.first); | |
551 EXPECT_EQ(2U, cont.size()); | |
552 EXPECT_EQ(1, result.first->data()); | |
553 | |
554 result = cont.insert(MoveOnly(3)); | |
555 EXPECT_TRUE(result.second); | |
556 EXPECT_EQ(std::prev(cont.end()), result.first); | |
557 EXPECT_EQ(3U, cont.size()); | |
558 EXPECT_EQ(3, result.first->data()); | |
559 | |
560 result = cont.insert(MoveOnly(3)); | |
561 EXPECT_FALSE(result.second); | |
562 EXPECT_EQ(std::prev(cont.end()), result.first); | |
563 EXPECT_EQ(3U, cont.size()); | |
564 EXPECT_EQ(3, result.first->data()); | |
565 } | |
566 | |
567 // iterator insert(const_iterator position_hint, const value_type& val) | |
568 | |
569 TEST(FlatSet, InsertPositionLValue) { | |
570 IntSet cont; | |
571 | |
572 IntSet::iterator result = cont.insert(cont.cend(), 2); | |
573 EXPECT_EQ(cont.begin(), result); | |
574 EXPECT_EQ(1U, cont.size()); | |
575 EXPECT_EQ(2, *result); | |
576 | |
577 result = cont.insert(cont.cend(), 1); | |
578 EXPECT_EQ(cont.begin(), result); | |
579 EXPECT_EQ(2U, cont.size()); | |
580 EXPECT_EQ(1, *result); | |
581 | |
582 result = cont.insert(cont.cend(), 3); | |
583 EXPECT_EQ(std::prev(cont.end()), result); | |
584 EXPECT_EQ(3U, cont.size()); | |
585 EXPECT_EQ(3, *result); | |
586 | |
587 result = cont.insert(cont.cend(), 3); | |
588 EXPECT_EQ(std::prev(cont.end()), result); | |
589 EXPECT_EQ(3U, cont.size()); | |
590 EXPECT_EQ(3, *result); | |
591 } | |
592 | |
593 // iterator insert(const_iterator position_hint, value_type&& val) | |
594 | |
595 TEST(FlatSet, InsertPositionRValue) { | |
596 MoveOnlySet cont; | |
597 | |
598 MoveOnlySet::iterator result = cont.insert(cont.cend(), MoveOnly(2)); | |
599 EXPECT_EQ(cont.begin(), result); | |
600 EXPECT_EQ(1U, cont.size()); | |
601 EXPECT_EQ(2, result->data()); | |
602 | |
603 result = cont.insert(cont.cend(), MoveOnly(1)); | |
604 EXPECT_EQ(cont.begin(), result); | |
605 EXPECT_EQ(2U, cont.size()); | |
606 EXPECT_EQ(1, result->data()); | |
607 | |
608 result = cont.insert(cont.cend(), MoveOnly(3)); | |
609 EXPECT_EQ(std::prev(cont.end()), result); | |
610 EXPECT_EQ(3U, cont.size()); | |
611 EXPECT_EQ(3, result->data()); | |
612 | |
613 result = cont.insert(cont.cend(), MoveOnly(3)); | |
614 EXPECT_EQ(std::prev(cont.end()), result); | |
615 EXPECT_EQ(3U, cont.size()); | |
616 EXPECT_EQ(3, result->data()); | |
617 } | |
618 | |
619 // template <class... Args> | |
620 // pair<iterator, bool> emplace(Args&&... args) | |
621 | |
622 TEST(FlatSet, Emplace) { | |
623 { | |
624 EmplaceableSet cont; | |
625 | |
626 std::pair<EmplaceableSet::iterator, bool> result = cont.emplace(); | |
627 EXPECT_TRUE(result.second); | |
628 EXPECT_EQ(cont.begin(), result.first); | |
629 EXPECT_EQ(1U, cont.size()); | |
630 EXPECT_EQ(Emplaceable(), *cont.begin()); | |
631 | |
632 result = cont.emplace(2, 3.5); | |
633 EXPECT_TRUE(result.second); | |
634 EXPECT_EQ(std::next(cont.begin()), result.first); | |
635 EXPECT_EQ(2U, cont.size()); | |
636 EXPECT_EQ(Emplaceable(2, 3.5), *result.first); | |
637 | |
638 result = cont.emplace(2, 3.5); | |
639 EXPECT_FALSE(result.second); | |
640 EXPECT_EQ(std::next(cont.begin()), result.first); | |
641 EXPECT_EQ(2U, cont.size()); | |
642 EXPECT_EQ(Emplaceable(2, 3.5), *result.first); | |
643 } | |
644 { | |
645 IntSet cont; | |
646 | |
647 std::pair<IntSet::iterator, bool> result = cont.emplace(2); | |
648 EXPECT_TRUE(result.second); | |
649 EXPECT_EQ(cont.begin(), result.first); | |
650 EXPECT_EQ(1U, cont.size()); | |
651 EXPECT_EQ(2, *result.first); | |
652 } | |
653 } | |
654 | |
655 // template <class... Args> | |
656 // iterator emplace_hint(const_iterator position_hint, Args&&... args) | |
657 | |
658 TEST(FlatSet, EmplacePosition) { | |
659 { | |
660 EmplaceableSet cont; | |
661 | |
662 EmplaceableSet::iterator result = cont.emplace_hint(cont.cend()); | |
663 EXPECT_EQ(cont.begin(), result); | |
664 EXPECT_EQ(1U, cont.size()); | |
665 EXPECT_EQ(Emplaceable(), *cont.begin()); | |
666 | |
667 result = cont.emplace_hint(cont.cend(), 2, 3.5); | |
668 EXPECT_EQ(std::next(cont.begin()), result); | |
669 EXPECT_EQ(2U, cont.size()); | |
670 EXPECT_EQ(Emplaceable(2, 3.5), *result); | |
671 | |
672 result = cont.emplace_hint(cont.cbegin(), 2, 3.5); | |
673 EXPECT_EQ(std::next(cont.begin()), result); | |
674 EXPECT_EQ(2U, cont.size()); | |
675 EXPECT_EQ(Emplaceable(2, 3.5), *result); | |
676 } | |
677 { | |
678 IntSet cont; | |
679 | |
680 IntSet::iterator result = cont.emplace_hint(cont.cend(), 2); | |
681 EXPECT_EQ(cont.begin(), result); | |
682 EXPECT_EQ(1U, cont.size()); | |
683 EXPECT_EQ(2, *result); | |
684 } | |
685 } | |
686 | |
687 // ---------------------------------------------------------------------------- | |
688 // Erase operations. | |
689 | |
690 // iterator erase(const_iterator position_hint) | |
691 | |
692 TEST(FlatSet, ErasePosition) { | |
693 IntSet cont{1, 2, 3, 4, 5, 6, 7, 8}; | |
694 | |
695 IntSet::iterator it = cont.erase(std::next(cont.cbegin(), 3)); | |
696 EXPECT_EQ(std::next(cont.begin(), 3), it); | |
697 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8)); | |
698 | |
699 it = cont.erase(std::next(cont.cbegin(), 0)); | |
700 EXPECT_EQ(cont.begin(), it); | |
701 EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7, 8)); | |
702 | |
703 it = cont.erase(std::next(cont.cbegin(), 5)); | |
704 EXPECT_EQ(cont.end(), it); | |
705 EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7)); | |
706 | |
707 it = cont.erase(std::next(cont.cbegin(), 1)); | |
708 EXPECT_EQ(std::next(cont.begin()), it); | |
709 EXPECT_THAT(cont, ElementsAre(2, 5, 6, 7)); | |
710 | |
711 it = cont.erase(std::next(cont.cbegin(), 2)); | |
712 EXPECT_EQ(std::next(cont.begin(), 2), it); | |
713 EXPECT_THAT(cont, ElementsAre(2, 5, 7)); | |
714 | |
715 it = cont.erase(std::next(cont.cbegin(), 2)); | |
716 EXPECT_EQ(std::next(cont.begin(), 2), it); | |
717 EXPECT_THAT(cont, ElementsAre(2, 5)); | |
718 | |
719 it = cont.erase(std::next(cont.cbegin(), 0)); | |
720 EXPECT_EQ(std::next(cont.begin(), 0), it); | |
721 EXPECT_THAT(cont, ElementsAre(5)); | |
722 | |
723 it = cont.erase(cont.cbegin()); | |
724 EXPECT_EQ(cont.begin(), it); | |
725 EXPECT_EQ(cont.end(), it); | |
726 } | |
727 | |
728 // iterator erase(const_iterator first, const_iterator last) | |
729 | |
730 TEST(FlatSet, EraseRange) { | |
731 IntSet cont{1, 2, 3, 4, 5, 6, 7, 8}; | |
732 | |
733 IntSet::iterator it = | |
734 cont.erase(std::next(cont.cbegin(), 5), std::next(cont.cbegin(), 5)); | |
735 EXPECT_EQ(std::next(cont.begin(), 5), it); | |
736 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 7, 8)); | |
737 | |
738 it = cont.erase(std::next(cont.cbegin(), 3), std::next(cont.cbegin(), 4)); | |
739 EXPECT_EQ(std::next(cont.begin(), 3), it); | |
740 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8)); | |
741 | |
742 it = cont.erase(std::next(cont.cbegin(), 2), std::next(cont.cbegin(), 5)); | |
743 EXPECT_EQ(std::next(cont.begin(), 2), it); | |
744 EXPECT_THAT(cont, ElementsAre(1, 2, 7, 8)); | |
745 | |
746 it = cont.erase(std::next(cont.cbegin(), 0), std::next(cont.cbegin(), 2)); | |
747 EXPECT_EQ(std::next(cont.begin(), 0), it); | |
748 EXPECT_THAT(cont, ElementsAre(7, 8)); | |
749 | |
750 it = cont.erase(cont.cbegin(), cont.cend()); | |
751 EXPECT_EQ(cont.begin(), it); | |
752 EXPECT_EQ(cont.end(), it); | |
753 } | |
754 | |
755 // size_type erase(const key_type& key) | |
756 | |
757 TEST(FlatSet, EraseKey) { | |
758 IntSet cont{1, 2, 3, 4, 5, 6, 7, 8}; | |
759 | |
760 EXPECT_EQ(0U, cont.erase(9)); | |
761 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 7, 8)); | |
762 | |
763 EXPECT_EQ(1U, cont.erase(4)); | |
764 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8)); | |
765 | |
766 EXPECT_EQ(1U, cont.erase(1)); | |
767 EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7, 8)); | |
768 | |
769 EXPECT_EQ(1U, cont.erase(8)); | |
770 EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7)); | |
771 | |
772 EXPECT_EQ(1U, cont.erase(3)); | |
773 EXPECT_THAT(cont, ElementsAre(2, 5, 6, 7)); | |
774 | |
775 EXPECT_EQ(1U, cont.erase(6)); | |
776 EXPECT_THAT(cont, ElementsAre(2, 5, 7)); | |
777 | |
778 EXPECT_EQ(1U, cont.erase(7)); | |
779 EXPECT_THAT(cont, ElementsAre(2, 5)); | |
780 | |
781 EXPECT_EQ(1U, cont.erase(2)); | |
782 EXPECT_THAT(cont, ElementsAre(5)); | |
783 | |
784 EXPECT_EQ(1U, cont.erase(5)); | |
785 EXPECT_THAT(cont, ElementsAre()); | |
786 } | |
787 | |
788 // ---------------------------------------------------------------------------- | |
789 // Comparators. | |
790 | |
791 // key_compare key_comp() const | |
792 | |
793 TEST(FlatSet, KeyComp) { | |
794 ReversedSet cont{1, 2, 3, 4, 5}; | |
795 | |
796 EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.key_comp())); | |
797 int new_elements[] = {6, 7, 8, 9, 10}; | |
798 std::copy(std::begin(new_elements), std::end(new_elements), | |
799 std::inserter(cont, cont.end())); | |
800 EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.key_comp())); | |
801 } | |
802 | |
803 // value_compare value_comp() const | |
804 | |
805 TEST(FlatSet, ValueComp) { | |
806 ReversedSet cont{1, 2, 3, 4, 5}; | |
807 | |
808 EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.value_comp())); | |
809 int new_elements[] = {6, 7, 8, 9, 10}; | |
810 std::copy(std::begin(new_elements), std::end(new_elements), | |
811 std::inserter(cont, cont.end())); | |
812 EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.value_comp())); | |
813 } | |
814 | |
815 // ---------------------------------------------------------------------------- | |
816 // Search operations. | |
817 | |
818 // size_type count(const key_type& key) const | |
819 | |
820 TEST(FlatSet, Count) { | |
821 { | |
822 const IntSet cont{5, 6, 7, 8, 9, 10, 11, 12}; | |
823 | |
824 EXPECT_EQ(1U, cont.count(5)); | |
825 EXPECT_EQ(1U, cont.count(6)); | |
826 EXPECT_EQ(1U, cont.count(7)); | |
827 EXPECT_EQ(1U, cont.count(8)); | |
828 EXPECT_EQ(1U, cont.count(9)); | |
829 EXPECT_EQ(1U, cont.count(10)); | |
830 EXPECT_EQ(1U, cont.count(11)); | |
831 EXPECT_EQ(1U, cont.count(12)); | |
832 EXPECT_EQ(0U, cont.count(4)); | |
833 } | |
834 { | |
835 const SetWithLess cont{5, 6, 7, 8, 9, 10, 11, 12}; | |
836 | |
837 EXPECT_EQ(1U, cont.count(5)); | |
838 EXPECT_EQ(1U, cont.count(6)); | |
839 EXPECT_EQ(1U, cont.count(7)); | |
840 EXPECT_EQ(1U, cont.count(8)); | |
841 EXPECT_EQ(1U, cont.count(9)); | |
842 EXPECT_EQ(1U, cont.count(10)); | |
843 EXPECT_EQ(1U, cont.count(11)); | |
844 EXPECT_EQ(1U, cont.count(12)); | |
845 EXPECT_EQ(0U, cont.count(4)); | |
846 } | |
847 } | |
848 | |
849 // iterator find(const key_type& key) | |
850 // const_iterator find(const key_type& key) const | |
851 | |
852 TEST(FlatSet, Find) { | |
853 { | |
854 IntSet cont{5, 6, 7, 8, 9, 10, 11, 12}; | |
855 | |
856 EXPECT_EQ(cont.begin(), cont.find(5)); | |
857 EXPECT_EQ(std::next(cont.begin()), cont.find(6)); | |
858 EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7)); | |
859 EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8)); | |
860 EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9)); | |
861 EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10)); | |
862 EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11)); | |
863 EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12)); | |
864 EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4)); | |
865 } | |
866 { | |
867 const IntSet cont{5, 6, 7, 8, 9, 10, 11, 12}; | |
868 | |
869 EXPECT_EQ(cont.begin(), cont.find(5)); | |
870 EXPECT_EQ(std::next(cont.begin()), cont.find(6)); | |
871 EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7)); | |
872 EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8)); | |
873 EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9)); | |
874 EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10)); | |
875 EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11)); | |
876 EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12)); | |
877 EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4)); | |
878 } | |
879 { | |
880 SetWithLess cont{5, 6, 7, 8, 9, 10, 11, 12}; | |
881 | |
882 EXPECT_EQ(cont.begin(), cont.find(5)); | |
883 EXPECT_EQ(std::next(cont.begin()), cont.find(6)); | |
884 EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7)); | |
885 EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8)); | |
886 EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9)); | |
887 EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10)); | |
888 EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11)); | |
889 EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12)); | |
890 EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4)); | |
891 } | |
892 } | |
893 | |
894 // pair<iterator, iterator> equal_range(const key_type& key) | |
895 // pair<const_iterator, const_iterator> equal_range(const key_type& key) const | |
896 | |
897 TEST(FlatSet, EqualRange) { | |
898 { | |
899 IntSet cont{5, 7, 9, 11, 13, 15, 17, 19}; | |
900 | |
901 std::pair<IntSet::iterator, IntSet::iterator> result = cont.equal_range(5); | |
902 EXPECT_EQ(std::next(cont.begin(), 0), result.first); | |
903 EXPECT_EQ(std::next(cont.begin(), 1), result.second); | |
904 result = cont.equal_range(7); | |
905 EXPECT_EQ(std::next(cont.begin(), 1), result.first); | |
906 EXPECT_EQ(std::next(cont.begin(), 2), result.second); | |
907 result = cont.equal_range(9); | |
908 EXPECT_EQ(std::next(cont.begin(), 2), result.first); | |
909 EXPECT_EQ(std::next(cont.begin(), 3), result.second); | |
910 result = cont.equal_range(11); | |
911 EXPECT_EQ(std::next(cont.begin(), 3), result.first); | |
912 EXPECT_EQ(std::next(cont.begin(), 4), result.second); | |
913 result = cont.equal_range(13); | |
914 EXPECT_EQ(std::next(cont.begin(), 4), result.first); | |
915 EXPECT_EQ(std::next(cont.begin(), 5), result.second); | |
916 result = cont.equal_range(15); | |
917 EXPECT_EQ(std::next(cont.begin(), 5), result.first); | |
918 EXPECT_EQ(std::next(cont.begin(), 6), result.second); | |
919 result = cont.equal_range(17); | |
920 EXPECT_EQ(std::next(cont.begin(), 6), result.first); | |
921 EXPECT_EQ(std::next(cont.begin(), 7), result.second); | |
922 result = cont.equal_range(19); | |
923 EXPECT_EQ(std::next(cont.begin(), 7), result.first); | |
924 EXPECT_EQ(std::next(cont.begin(), 8), result.second); | |
925 result = cont.equal_range(4); | |
926 EXPECT_EQ(std::next(cont.begin(), 0), result.first); | |
927 EXPECT_EQ(std::next(cont.begin(), 0), result.second); | |
928 result = cont.equal_range(6); | |
929 EXPECT_EQ(std::next(cont.begin(), 1), result.first); | |
930 EXPECT_EQ(std::next(cont.begin(), 1), result.second); | |
931 result = cont.equal_range(8); | |
932 EXPECT_EQ(std::next(cont.begin(), 2), result.first); | |
933 EXPECT_EQ(std::next(cont.begin(), 2), result.second); | |
934 result = cont.equal_range(10); | |
935 EXPECT_EQ(std::next(cont.begin(), 3), result.first); | |
936 EXPECT_EQ(std::next(cont.begin(), 3), result.second); | |
937 result = cont.equal_range(12); | |
938 EXPECT_EQ(std::next(cont.begin(), 4), result.first); | |
939 EXPECT_EQ(std::next(cont.begin(), 4), result.second); | |
940 result = cont.equal_range(14); | |
941 EXPECT_EQ(std::next(cont.begin(), 5), result.first); | |
942 EXPECT_EQ(std::next(cont.begin(), 5), result.second); | |
943 result = cont.equal_range(16); | |
944 EXPECT_EQ(std::next(cont.begin(), 6), result.first); | |
945 EXPECT_EQ(std::next(cont.begin(), 6), result.second); | |
946 result = cont.equal_range(18); | |
947 EXPECT_EQ(std::next(cont.begin(), 7), result.first); | |
948 EXPECT_EQ(std::next(cont.begin(), 7), result.second); | |
949 result = cont.equal_range(20); | |
950 EXPECT_EQ(std::next(cont.begin(), 8), result.first); | |
951 EXPECT_EQ(std::next(cont.begin(), 8), result.second); | |
952 } | |
953 { | |
954 const IntSet cont{5, 7, 9, 11, 13, 15, 17, 19}; | |
955 | |
956 std::pair<IntSet::const_iterator, IntSet::const_iterator> result = | |
957 cont.equal_range(5); | |
958 EXPECT_EQ(std::next(cont.begin(), 0), result.first); | |
959 EXPECT_EQ(std::next(cont.begin(), 1), result.second); | |
960 result = cont.equal_range(7); | |
961 EXPECT_EQ(std::next(cont.begin(), 1), result.first); | |
962 EXPECT_EQ(std::next(cont.begin(), 2), result.second); | |
963 result = cont.equal_range(9); | |
964 EXPECT_EQ(std::next(cont.begin(), 2), result.first); | |
965 EXPECT_EQ(std::next(cont.begin(), 3), result.second); | |
966 result = cont.equal_range(11); | |
967 EXPECT_EQ(std::next(cont.begin(), 3), result.first); | |
968 EXPECT_EQ(std::next(cont.begin(), 4), result.second); | |
969 result = cont.equal_range(13); | |
970 EXPECT_EQ(std::next(cont.begin(), 4), result.first); | |
971 EXPECT_EQ(std::next(cont.begin(), 5), result.second); | |
972 result = cont.equal_range(15); | |
973 EXPECT_EQ(std::next(cont.begin(), 5), result.first); | |
974 EXPECT_EQ(std::next(cont.begin(), 6), result.second); | |
975 result = cont.equal_range(17); | |
976 EXPECT_EQ(std::next(cont.begin(), 6), result.first); | |
977 EXPECT_EQ(std::next(cont.begin(), 7), result.second); | |
978 result = cont.equal_range(19); | |
979 EXPECT_EQ(std::next(cont.begin(), 7), result.first); | |
980 EXPECT_EQ(std::next(cont.begin(), 8), result.second); | |
981 result = cont.equal_range(4); | |
982 EXPECT_EQ(std::next(cont.begin(), 0), result.first); | |
983 EXPECT_EQ(std::next(cont.begin(), 0), result.second); | |
984 result = cont.equal_range(6); | |
985 EXPECT_EQ(std::next(cont.begin(), 1), result.first); | |
986 EXPECT_EQ(std::next(cont.begin(), 1), result.second); | |
987 result = cont.equal_range(8); | |
988 EXPECT_EQ(std::next(cont.begin(), 2), result.first); | |
989 EXPECT_EQ(std::next(cont.begin(), 2), result.second); | |
990 result = cont.equal_range(10); | |
991 EXPECT_EQ(std::next(cont.begin(), 3), result.first); | |
992 EXPECT_EQ(std::next(cont.begin(), 3), result.second); | |
993 result = cont.equal_range(12); | |
994 EXPECT_EQ(std::next(cont.begin(), 4), result.first); | |
995 EXPECT_EQ(std::next(cont.begin(), 4), result.second); | |
996 result = cont.equal_range(14); | |
997 EXPECT_EQ(std::next(cont.begin(), 5), result.first); | |
998 EXPECT_EQ(std::next(cont.begin(), 5), result.second); | |
999 result = cont.equal_range(16); | |
1000 EXPECT_EQ(std::next(cont.begin(), 6), result.first); | |
1001 EXPECT_EQ(std::next(cont.begin(), 6), result.second); | |
1002 result = cont.equal_range(18); | |
1003 EXPECT_EQ(std::next(cont.begin(), 7), result.first); | |
1004 EXPECT_EQ(std::next(cont.begin(), 7), result.second); | |
1005 result = cont.equal_range(20); | |
1006 EXPECT_EQ(std::next(cont.begin(), 8), result.first); | |
1007 EXPECT_EQ(std::next(cont.begin(), 8), result.second); | |
1008 } | |
1009 { | |
1010 SetWithLess cont{5, 7, 9, 11, 13, 15, 17, 19}; | |
1011 | |
1012 std::pair<SetWithLess::iterator, SetWithLess::iterator> result = | |
1013 cont.equal_range(5); | |
1014 EXPECT_EQ(std::next(cont.begin(), 0), result.first); | |
1015 EXPECT_EQ(std::next(cont.begin(), 1), result.second); | |
1016 result = cont.equal_range(7); | |
1017 EXPECT_EQ(std::next(cont.begin(), 1), result.first); | |
1018 EXPECT_EQ(std::next(cont.begin(), 2), result.second); | |
1019 result = cont.equal_range(9); | |
1020 EXPECT_EQ(std::next(cont.begin(), 2), result.first); | |
1021 EXPECT_EQ(std::next(cont.begin(), 3), result.second); | |
1022 result = cont.equal_range(11); | |
1023 EXPECT_EQ(std::next(cont.begin(), 3), result.first); | |
1024 EXPECT_EQ(std::next(cont.begin(), 4), result.second); | |
1025 result = cont.equal_range(13); | |
1026 EXPECT_EQ(std::next(cont.begin(), 4), result.first); | |
1027 EXPECT_EQ(std::next(cont.begin(), 5), result.second); | |
1028 result = cont.equal_range(15); | |
1029 EXPECT_EQ(std::next(cont.begin(), 5), result.first); | |
1030 EXPECT_EQ(std::next(cont.begin(), 6), result.second); | |
1031 result = cont.equal_range(17); | |
1032 EXPECT_EQ(std::next(cont.begin(), 6), result.first); | |
1033 EXPECT_EQ(std::next(cont.begin(), 7), result.second); | |
1034 result = cont.equal_range(19); | |
1035 EXPECT_EQ(std::next(cont.begin(), 7), result.first); | |
1036 EXPECT_EQ(std::next(cont.begin(), 8), result.second); | |
1037 result = cont.equal_range(4); | |
1038 EXPECT_EQ(std::next(cont.begin(), 0), result.first); | |
1039 EXPECT_EQ(std::next(cont.begin(), 0), result.second); | |
1040 result = cont.equal_range(6); | |
1041 EXPECT_EQ(std::next(cont.begin(), 1), result.first); | |
1042 EXPECT_EQ(std::next(cont.begin(), 1), result.second); | |
1043 result = cont.equal_range(8); | |
1044 EXPECT_EQ(std::next(cont.begin(), 2), result.first); | |
1045 EXPECT_EQ(std::next(cont.begin(), 2), result.second); | |
1046 result = cont.equal_range(10); | |
1047 EXPECT_EQ(std::next(cont.begin(), 3), result.first); | |
1048 EXPECT_EQ(std::next(cont.begin(), 3), result.second); | |
1049 result = cont.equal_range(12); | |
1050 EXPECT_EQ(std::next(cont.begin(), 4), result.first); | |
1051 EXPECT_EQ(std::next(cont.begin(), 4), result.second); | |
1052 result = cont.equal_range(14); | |
1053 EXPECT_EQ(std::next(cont.begin(), 5), result.first); | |
1054 EXPECT_EQ(std::next(cont.begin(), 5), result.second); | |
1055 result = cont.equal_range(16); | |
1056 EXPECT_EQ(std::next(cont.begin(), 6), result.first); | |
1057 EXPECT_EQ(std::next(cont.begin(), 6), result.second); | |
1058 result = cont.equal_range(18); | |
1059 EXPECT_EQ(std::next(cont.begin(), 7), result.first); | |
1060 EXPECT_EQ(std::next(cont.begin(), 7), result.second); | |
1061 result = cont.equal_range(20); | |
1062 EXPECT_EQ(std::next(cont.begin(), 8), result.first); | |
1063 EXPECT_EQ(std::next(cont.begin(), 8), result.second); | |
1064 } | |
1065 } | |
1066 | |
1067 // iterator lower_bound(const key_type& key); | |
1068 // const_iterator lower_bound(const key_type& key) const; | |
1069 | |
1070 TEST(FlatSet, LowerBound) { | |
1071 { | |
1072 IntSet cont{5, 7, 9, 11, 13, 15, 17, 19}; | |
1073 | |
1074 EXPECT_EQ(cont.begin(), cont.lower_bound(5)); | |
1075 EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7)); | |
1076 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(9)); | |
1077 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(11)); | |
1078 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(13)); | |
1079 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(15)); | |
1080 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(17)); | |
1081 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(19)); | |
1082 EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4)); | |
1083 EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6)); | |
1084 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8)); | |
1085 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10)); | |
1086 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12)); | |
1087 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14)); | |
1088 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16)); | |
1089 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18)); | |
1090 EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20)); | |
1091 } | |
1092 { | |
1093 const IntSet cont{5, 7, 9, 11, 13, 15, 17, 19}; | |
1094 | |
1095 EXPECT_EQ(cont.begin(), cont.lower_bound(5)); | |
1096 EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7)); | |
1097 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(9)); | |
1098 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(11)); | |
1099 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(13)); | |
1100 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(15)); | |
1101 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(17)); | |
1102 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(19)); | |
1103 EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4)); | |
1104 EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6)); | |
1105 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8)); | |
1106 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10)); | |
1107 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12)); | |
1108 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14)); | |
1109 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16)); | |
1110 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18)); | |
1111 EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20)); | |
1112 } | |
1113 { | |
1114 SetWithLess cont{5, 7, 9, 11, 13, 15, 17, 19}; | |
1115 | |
1116 EXPECT_EQ(cont.begin(), cont.lower_bound(5)); | |
1117 EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7)); | |
1118 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(9)); | |
1119 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(11)); | |
1120 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(13)); | |
1121 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(15)); | |
1122 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(17)); | |
1123 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(19)); | |
1124 EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4)); | |
1125 EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6)); | |
1126 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8)); | |
1127 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10)); | |
1128 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12)); | |
1129 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14)); | |
1130 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16)); | |
1131 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18)); | |
1132 EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20)); | |
1133 } | |
1134 } | |
1135 | |
1136 // iterator upper_bound(const key_type& key) | |
1137 // const_iterator upper_bound(const key_type& key) const | |
1138 | |
1139 TEST(FlatSet, UpperBound) { | |
1140 { | |
1141 IntSet cont{5, 7, 9, 11, 13, 15, 17, 19}; | |
1142 | |
1143 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5)); | |
1144 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7)); | |
1145 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(9)); | |
1146 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(11)); | |
1147 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(13)); | |
1148 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(15)); | |
1149 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(17)); | |
1150 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(19)); | |
1151 EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4)); | |
1152 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6)); | |
1153 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8)); | |
1154 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10)); | |
1155 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12)); | |
1156 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14)); | |
1157 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16)); | |
1158 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18)); | |
1159 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20)); | |
1160 } | |
1161 { | |
1162 const IntSet cont{5, 7, 9, 11, 13, 15, 17, 19}; | |
1163 | |
1164 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5)); | |
1165 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7)); | |
1166 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(9)); | |
1167 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(11)); | |
1168 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(13)); | |
1169 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(15)); | |
1170 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(17)); | |
1171 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(19)); | |
1172 EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4)); | |
1173 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6)); | |
1174 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8)); | |
1175 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10)); | |
1176 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12)); | |
1177 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14)); | |
1178 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16)); | |
1179 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18)); | |
1180 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20)); | |
1181 } | |
1182 { | |
1183 SetWithLess cont{5, 7, 9, 11, 13, 15, 17, 19}; | |
1184 | |
1185 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5)); | |
1186 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7)); | |
1187 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(9)); | |
1188 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(11)); | |
1189 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(13)); | |
1190 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(15)); | |
1191 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(17)); | |
1192 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(19)); | |
1193 EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4)); | |
1194 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6)); | |
1195 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8)); | |
1196 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10)); | |
1197 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12)); | |
1198 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14)); | |
1199 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16)); | |
1200 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18)); | |
1201 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20)); | |
1202 } | |
1203 } | |
1204 | |
1205 // ---------------------------------------------------------------------------- | |
1206 // General operations. | |
1207 | |
1208 // void swap(flat_set& other) | |
1209 // void swap(flat_set& lhs, flat_set& rhs) | |
1210 | |
1211 TEST(FlatSetOurs, Swap) { | |
1212 IntSet x{1, 2, 3}; | |
1213 IntSet y{4}; | |
1214 swap(x, y); | |
1215 EXPECT_THAT(x, ElementsAre(4)); | |
1216 EXPECT_THAT(y, ElementsAre(1, 2, 3)); | |
1217 | |
1218 y.swap(x); | |
1219 EXPECT_THAT(x, ElementsAre(1, 2, 3)); | |
1220 EXPECT_THAT(y, ElementsAre(4)); | |
1221 } | |
1222 | |
1223 // bool operator==(const flat_set& lhs, const flat_set& rhs) | |
1224 // bool operator!=(const flat_set& lhs, const flat_set& rhs) | |
1225 // bool operator<(const flat_set& lhs, const flat_set& rhs) | |
1226 // bool operator>(const flat_set& lhs, const flat_set& rhs) | |
1227 // bool operator<=(const flat_set& lhs, const flat_set& rhs) | |
1228 // bool operator>=(const flat_set& lhs, const flat_set& rhs) | |
1229 | |
1230 TEST(FlatSet, Comparison) { | |
1231 // Provided comparator does not participate in comparison. | |
1232 ReversedSet biggest{3}; | |
1233 ReversedSet smallest{1}; | |
1234 ReversedSet middle{1, 2}; | |
1235 | |
1236 EXPECT_EQ(biggest, biggest); | |
1237 EXPECT_NE(biggest, smallest); | |
1238 EXPECT_LT(smallest, middle); | |
1239 EXPECT_LE(smallest, middle); | |
1240 EXPECT_LE(middle, middle); | |
1241 EXPECT_GT(biggest, middle); | |
1242 EXPECT_GE(biggest, middle); | |
1243 EXPECT_GE(biggest, biggest); | |
1244 } | |
1245 | |
1246 TEST(FlatSet, EraseIf) { | |
1247 IntSet x; | |
1248 base::EraseIf(x, [](int) { return false; }); | |
1249 EXPECT_THAT(x, ElementsAre()); | |
1250 | |
1251 x = {1, 2, 3}; | |
1252 base::EraseIf(x, [](int elem) { return !(elem & 1); }); | |
1253 EXPECT_THAT(x, ElementsAre(1, 3)); | |
1254 | |
1255 x = {1, 2, 3, 4}; | |
1256 base::EraseIf(x, [](int elem) { return elem & 1; }); | |
1257 EXPECT_THAT(x, ElementsAre(2, 4)); | |
1258 } | |
OLD | NEW |