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_set.h"
6
7 #include <string>
8 #include <vector>
9
10 #include "base/macros.h"
11 #include "base/memory/ptr_util.h"
12 #include "base/test/move_only_int.h"
13 #include "testing/gmock/include/gmock/gmock.h"
14 #include "testing/gtest/include/gtest/gtest.h"
15
16 // A flat_set is basically a interface to flat_tree. So several basic
17 // operations are tested to make sure things are set up properly, but the bulk
18 // of the tests are in flat_tree_unittests.cc.
19
20 using ::testing::ElementsAre;
21
22 namespace base {
23
TEST(FlatSet,IncompleteType)24 TEST(FlatSet, IncompleteType) {
25 struct A {
26 using Set = flat_set<A>;
27 int data;
28 Set set_with_incomplete_type;
29 Set::iterator it;
30 Set::const_iterator cit;
31
32 // We do not declare operator< because clang complains that it's unused.
33 };
34
35 A a;
36 }
37
TEST(FlatSet,RangeConstructor)38 TEST(FlatSet, RangeConstructor) {
39 flat_set<int>::value_type input_vals[] = {1, 1, 1, 2, 2, 2, 3, 3, 3};
40
41 flat_set<int> cont(std::begin(input_vals), std::end(input_vals),
42 base::KEEP_FIRST_OF_DUPES);
43 EXPECT_THAT(cont, ElementsAre(1, 2, 3));
44 }
45
TEST(FlatSet,MoveConstructor)46 TEST(FlatSet, MoveConstructor) {
47 int input_range[] = {1, 2, 3, 4};
48
49 flat_set<MoveOnlyInt> original(std::begin(input_range), std::end(input_range),
50 base::KEEP_FIRST_OF_DUPES);
51 flat_set<MoveOnlyInt> moved(std::move(original));
52
53 EXPECT_EQ(1U, moved.count(MoveOnlyInt(1)));
54 EXPECT_EQ(1U, moved.count(MoveOnlyInt(2)));
55 EXPECT_EQ(1U, moved.count(MoveOnlyInt(3)));
56 EXPECT_EQ(1U, moved.count(MoveOnlyInt(4)));
57 }
58
TEST(FlatSet,InitializerListConstructor)59 TEST(FlatSet, InitializerListConstructor) {
60 flat_set<int> cont({1, 2, 3, 4, 5, 6, 10, 8}, KEEP_FIRST_OF_DUPES);
61 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
62 }
63
TEST(FlatSet,InsertFindSize)64 TEST(FlatSet, InsertFindSize) {
65 base::flat_set<int> s;
66 s.insert(1);
67 s.insert(1);
68 s.insert(2);
69
70 EXPECT_EQ(2u, s.size());
71 EXPECT_EQ(1, *s.find(1));
72 EXPECT_EQ(2, *s.find(2));
73 EXPECT_EQ(s.end(), s.find(7));
74 }
75
TEST(FlatSet,CopySwap)76 TEST(FlatSet, CopySwap) {
77 base::flat_set<int> original;
78 original.insert(1);
79 original.insert(2);
80 EXPECT_THAT(original, ElementsAre(1, 2));
81
82 base::flat_set<int> copy(original);
83 EXPECT_THAT(copy, ElementsAre(1, 2));
84
85 copy.erase(copy.begin());
86 copy.insert(10);
87 EXPECT_THAT(copy, ElementsAre(2, 10));
88
89 original.swap(copy);
90 EXPECT_THAT(original, ElementsAre(2, 10));
91 EXPECT_THAT(copy, ElementsAre(1, 2));
92 }
93
TEST(FlatSet,UsingTransparentCompare)94 TEST(FlatSet, UsingTransparentCompare) {
95 using ExplicitInt = base::MoveOnlyInt;
96 base::flat_set<ExplicitInt> s;
97 const auto& s1 = s;
98 int x = 0;
99
100 // Check if we can use lookup functions without converting to key_type.
101 // Correctness is checked in flat_tree tests.
102 s.count(x);
103 s1.count(x);
104 s.find(x);
105 s1.find(x);
106 s.equal_range(x);
107 s1.equal_range(x);
108 s.lower_bound(x);
109 s1.lower_bound(x);
110 s.upper_bound(x);
111 s1.upper_bound(x);
112 s.erase(x);
113
114 // Check if we broke overload resolution.
115 s.emplace(0);
116 s.emplace(1);
117 s.erase(s.begin());
118 s.erase(s.cbegin());
119 }
120
121 } // namespace base
122