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