Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(235)

Side by Side Diff: base/containers/flat_tree_unittest.cc

Issue 2944523002: Improving flat containers interface. (Closed)
Patch Set: Review, round 2. Created 3 years, 6 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
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_tree.h" 5 #include "base/containers/flat_tree.h"
6 6
7 // Following tests are ported and extended tests from libcpp for std::set. 7 // Following tests are ported and extended tests from libcpp for std::set.
8 // They can be found here: 8 // They can be found here:
9 // https://github.com/llvm-mirror/libcxx/tree/master/test/std/containers/associa tive/set 9 // https://github.com/llvm-mirror/libcxx/tree/master/test/std/containers/associa tive/set
10 // 10 //
11 // Not ported tests: 11 // Not ported tests:
12 // * No tests with PrivateConstructor and std::less<> changed to std::less<T> 12 // * No tests with PrivateConstructor and std::less<> changed to std::less<T>
13 // These tests have to do with C++14 std::less<> 13 // These tests have to do with C++14 std::less<>
14 // http://en.cppreference.com/w/cpp/utility/functional/less_void 14 // http://en.cppreference.com/w/cpp/utility/functional/less_void
15 // and add support for templated versions of lookup functions. 15 // and add support for templated versions of lookup functions.
16 // Current implementation of flat containers doesn't support it. 16 // Because we use same implementation, we figured that it's OK just to check
17 // * No tests with TemplateConstructor. 17 // compilation and this is what we do in flat_set_unittest/flat_map_unittest.
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() 18 // * No tests for max_size()
23 // Has to do with allocator support. 19 // Has to do with allocator support.
24 // * No tests with DefaultOnly. 20 // * No tests with DefaultOnly.
25 // Standard containers allocate each element in the separate node on the heap 21 // Standard containers allocate each element in the separate node on the heap
26 // and then manipulate these nodes. Flat containers store their elements in 22 // and then manipulate these nodes. Flat containers store their elements in
27 // contiguous memory and move them around, type is required to be movable. 23 // contiguous memory and move them around, type is required to be movable.
28 // * No tests for N3644. 24 // * No tests for N3644.
29 // This proposal suggests that all default constructed iterators compare 25 // This proposal suggests that all default constructed iterators compare
30 // equal. Currently we use std::vector iterators and they don't implement 26 // equal. Currently we use std::vector iterators and they don't implement
31 // this. 27 // this.
32 // * No tests with min_allocator and no tests counting allocations. 28 // * No tests with min_allocator and no tests counting allocations.
33 // Flat sets currently don't support allocators. 29 // Flat sets currently don't support allocators.
34 30
35 #include <forward_list> 31 #include <forward_list>
36 #include <iterator> 32 #include <iterator>
37 #include <list> 33 #include <list>
38 #include <string> 34 #include <string>
39 #include <vector> 35 #include <vector>
40 36
41 #include "base/containers/container_test_utils.h" 37 #include "base/containers/container_test_utils.h"
38 #include "base/functional.h"
42 #include "base/macros.h" 39 #include "base/macros.h"
43 #include "testing/gmock/include/gmock/gmock.h" 40 #include "testing/gmock/include/gmock/gmock.h"
44 #include "testing/gtest/include/gtest/gtest.h" 41 #include "testing/gtest/include/gtest/gtest.h"
45 42
46 namespace base { 43 namespace base {
47 namespace internal { 44 namespace internal {
48 45
49 namespace { 46 namespace {
50 47
51 template <class It> 48 template <class It>
(...skipping 62 matching lines...) Expand 10 before | Expand all | Expand 10 after
114 return std::tie(lhs.int_, lhs.double_) < std::tie(rhs.int_, rhs.double_); 111 return std::tie(lhs.int_, lhs.double_) < std::tie(rhs.int_, rhs.double_);
115 } 112 }
116 113
117 private: 114 private:
118 int int_; 115 int int_;
119 double double_; 116 double double_;
120 117
121 DISALLOW_COPY_AND_ASSIGN(Emplaceable); 118 DISALLOW_COPY_AND_ASSIGN(Emplaceable);
122 }; 119 };
123 120
121 struct TemplateConstructor {
122 template <typename T>
123 TemplateConstructor(const T&) {}
124
125 friend bool operator<(const TemplateConstructor&,
126 const TemplateConstructor&) {
127 return false;
128 }
129 };
130
124 class NonDefaultConstructibleCompare { 131 class NonDefaultConstructibleCompare {
125 public: 132 public:
126 explicit NonDefaultConstructibleCompare(int) {} 133 explicit NonDefaultConstructibleCompare(int) {}
127 134
128 template <typename T> 135 template <typename T>
129 bool operator()(const T& lhs, const T& rhs) const { 136 bool operator()(const T& lhs, const T& rhs) const {
130 return std::less<T>()(lhs, rhs); 137 return std::less<T>()(lhs, rhs);
131 } 138 }
132 }; 139 };
133 140
134 template <class PairType> 141 template <class PairType>
135 struct LessByFirst { 142 struct LessByFirst {
136 bool operator()(const PairType& lhs, const PairType& rhs) const { 143 bool operator()(const PairType& lhs, const PairType& rhs) const {
137 return lhs.first < rhs.first; 144 return lhs.first < rhs.first;
138 } 145 }
139 }; 146 };
140 147
141 // Common test trees. 148 // Common test trees.
142
143 // TODO(dyaroshev): replace less<int> with less<>, once we have it
144 // crbug.com/682254. This will make it different than IntTree.
145 using IntTreeWithLess =
146 flat_tree<int, int, GetKeyFromValueIdentity<int>, std::less<int>>;
147 using IntTree = 149 using IntTree =
148 flat_tree<int, int, GetKeyFromValueIdentity<int>, std::less<int>>; 150 flat_tree<int, int, GetKeyFromValueIdentity<int>, std::less<int>>;
149 using IntPair = std::pair<int, int>; 151 using IntPair = std::pair<int, int>;
150 using IntPairTree = flat_tree<IntPair, 152 using IntPairTree = flat_tree<IntPair,
151 IntPair, 153 IntPair,
152 GetKeyFromValueIdentity<IntPair>, 154 GetKeyFromValueIdentity<IntPair>,
153 LessByFirst<IntPair>>; 155 LessByFirst<IntPair>>;
154 using MoveOnlyTree = flat_tree<MoveOnlyInt, 156 using MoveOnlyTree = flat_tree<MoveOnlyInt,
155 MoveOnlyInt, 157 MoveOnlyInt,
156 GetKeyFromValueIdentity<MoveOnlyInt>, 158 GetKeyFromValueIdentity<MoveOnlyInt>,
(...skipping 594 matching lines...) Expand 10 before | Expand all | Expand 10 after
751 EXPECT_EQ(std::prev(cont.end()), result); 753 EXPECT_EQ(std::prev(cont.end()), result);
752 EXPECT_EQ(3U, cont.size()); 754 EXPECT_EQ(3U, cont.size());
753 EXPECT_EQ(3, result->data()); 755 EXPECT_EQ(3, result->data());
754 } 756 }
755 757
756 // template <class InputIterator> 758 // template <class InputIterator>
757 // void insert(InputIterator first, InputIterator last); 759 // void insert(InputIterator first, InputIterator last);
758 760
759 TEST(FlatTree, InsertIterIter) { 761 TEST(FlatTree, InsertIterIter) {
760 struct GetKeyFromIntIntPair { 762 struct GetKeyFromIntIntPair {
761 int operator()(const std::pair<int, int>& p) const { return p.first; } 763 const int& operator()(const std::pair<int, int>& p) const {
764 return p.first;
765 }
762 }; 766 };
763 767
764 using IntIntMap = 768 using IntIntMap =
765 flat_tree<int, IntPair, GetKeyFromIntIntPair, std::less<int>>; 769 flat_tree<int, IntPair, GetKeyFromIntIntPair, std::less<int>>;
766 770
767 { 771 {
768 IntIntMap cont; 772 IntIntMap cont;
769 IntPair int_pairs[] = {{3, 1}, {1, 1}, {4, 1}, {2, 1}}; 773 IntPair int_pairs[] = {{3, 1}, {1, 1}, {4, 1}, {2, 1}};
770 cont.insert(std::begin(int_pairs), std::end(int_pairs), 774 cont.insert(std::begin(int_pairs), std::end(int_pairs),
771 KEEP_FIRST_OF_DUPES); 775 KEEP_FIRST_OF_DUPES);
(...skipping 150 matching lines...) Expand 10 before | Expand all | Expand 10 after
922 EXPECT_EQ(2, *result); 926 EXPECT_EQ(2, *result);
923 } 927 }
924 } 928 }
925 929
926 // ---------------------------------------------------------------------------- 930 // ----------------------------------------------------------------------------
927 // Erase operations. 931 // Erase operations.
928 932
929 // iterator erase(const_iterator position_hint) 933 // iterator erase(const_iterator position_hint)
930 934
931 TEST(FlatTree, ErasePosition) { 935 TEST(FlatTree, ErasePosition) {
932 IntTree cont({1, 2, 3, 4, 5, 6, 7, 8}, KEEP_FIRST_OF_DUPES); 936 {
937 IntTree cont({1, 2, 3, 4, 5, 6, 7, 8}, KEEP_FIRST_OF_DUPES);
933 938
934 IntTree::iterator it = cont.erase(std::next(cont.cbegin(), 3)); 939 IntTree::iterator it = cont.erase(std::next(cont.cbegin(), 3));
935 EXPECT_EQ(std::next(cont.begin(), 3), it); 940 EXPECT_EQ(std::next(cont.begin(), 3), it);
936 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8)); 941 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8));
937 942
938 it = cont.erase(std::next(cont.cbegin(), 0)); 943 it = cont.erase(std::next(cont.cbegin(), 0));
939 EXPECT_EQ(cont.begin(), it); 944 EXPECT_EQ(cont.begin(), it);
940 EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7, 8)); 945 EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7, 8));
941 946
942 it = cont.erase(std::next(cont.cbegin(), 5)); 947 it = cont.erase(std::next(cont.cbegin(), 5));
943 EXPECT_EQ(cont.end(), it); 948 EXPECT_EQ(cont.end(), it);
944 EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7)); 949 EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7));
945 950
946 it = cont.erase(std::next(cont.cbegin(), 1)); 951 it = cont.erase(std::next(cont.cbegin(), 1));
947 EXPECT_EQ(std::next(cont.begin()), it); 952 EXPECT_EQ(std::next(cont.begin()), it);
948 EXPECT_THAT(cont, ElementsAre(2, 5, 6, 7)); 953 EXPECT_THAT(cont, ElementsAre(2, 5, 6, 7));
949 954
950 it = cont.erase(std::next(cont.cbegin(), 2)); 955 it = cont.erase(std::next(cont.cbegin(), 2));
951 EXPECT_EQ(std::next(cont.begin(), 2), it); 956 EXPECT_EQ(std::next(cont.begin(), 2), it);
952 EXPECT_THAT(cont, ElementsAre(2, 5, 7)); 957 EXPECT_THAT(cont, ElementsAre(2, 5, 7));
953 958
954 it = cont.erase(std::next(cont.cbegin(), 2)); 959 it = cont.erase(std::next(cont.cbegin(), 2));
955 EXPECT_EQ(std::next(cont.begin(), 2), it); 960 EXPECT_EQ(std::next(cont.begin(), 2), it);
956 EXPECT_THAT(cont, ElementsAre(2, 5)); 961 EXPECT_THAT(cont, ElementsAre(2, 5));
957 962
958 it = cont.erase(std::next(cont.cbegin(), 0)); 963 it = cont.erase(std::next(cont.cbegin(), 0));
959 EXPECT_EQ(std::next(cont.begin(), 0), it); 964 EXPECT_EQ(std::next(cont.begin(), 0), it);
960 EXPECT_THAT(cont, ElementsAre(5)); 965 EXPECT_THAT(cont, ElementsAre(5));
961 966
962 it = cont.erase(cont.cbegin()); 967 it = cont.erase(cont.cbegin());
963 EXPECT_EQ(cont.begin(), it); 968 EXPECT_EQ(cont.begin(), it);
964 EXPECT_EQ(cont.end(), it); 969 EXPECT_EQ(cont.end(), it);
970 }
971 // This is LWG #2059.
972 // There is a potential ambiguity between erase with an iterator and erase
973 // with a key, if key has a templated constructor.
974 {
975 using T = TemplateConstructor;
976
977 flat_tree<T, T, GetKeyFromValueIdentity<T>, base::less> cont;
978 T v(0);
979
980 auto it = cont.find(v);
981 if (it != cont.end())
982 cont.erase(it);
983 }
965 } 984 }
966 985
967 // iterator erase(const_iterator first, const_iterator last) 986 // iterator erase(const_iterator first, const_iterator last)
968 987
969 TEST(FlatTree, EraseRange) { 988 TEST(FlatTree, EraseRange) {
970 IntTree cont({1, 2, 3, 4, 5, 6, 7, 8}, KEEP_FIRST_OF_DUPES); 989 IntTree cont({1, 2, 3, 4, 5, 6, 7, 8}, KEEP_FIRST_OF_DUPES);
971 990
972 IntTree::iterator it = 991 IntTree::iterator it =
973 cont.erase(std::next(cont.cbegin(), 5), std::next(cont.cbegin(), 5)); 992 cont.erase(std::next(cont.cbegin(), 5), std::next(cont.cbegin(), 5));
974 EXPECT_EQ(std::next(cont.begin(), 5), it); 993 EXPECT_EQ(std::next(cont.begin(), 5), it);
(...skipping 75 matching lines...) Expand 10 before | Expand all | Expand 10 after
1050 std::inserter(cont, cont.end())); 1069 std::inserter(cont, cont.end()));
1051 EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.value_comp())); 1070 EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.value_comp()));
1052 } 1071 }
1053 1072
1054 // ---------------------------------------------------------------------------- 1073 // ----------------------------------------------------------------------------
1055 // Search operations. 1074 // Search operations.
1056 1075
1057 // size_type count(const key_type& key) const 1076 // size_type count(const key_type& key) const
1058 1077
1059 TEST(FlatTree, Count) { 1078 TEST(FlatTree, Count) {
1060 {
1061 const IntTree cont({5, 6, 7, 8, 9, 10, 11, 12}, KEEP_FIRST_OF_DUPES); 1079 const IntTree cont({5, 6, 7, 8, 9, 10, 11, 12}, KEEP_FIRST_OF_DUPES);
1062 1080
1063 EXPECT_EQ(1U, cont.count(5)); 1081 EXPECT_EQ(1U, cont.count(5));
1064 EXPECT_EQ(1U, cont.count(6)); 1082 EXPECT_EQ(1U, cont.count(6));
1065 EXPECT_EQ(1U, cont.count(7)); 1083 EXPECT_EQ(1U, cont.count(7));
1066 EXPECT_EQ(1U, cont.count(8)); 1084 EXPECT_EQ(1U, cont.count(8));
1067 EXPECT_EQ(1U, cont.count(9)); 1085 EXPECT_EQ(1U, cont.count(9));
1068 EXPECT_EQ(1U, cont.count(10)); 1086 EXPECT_EQ(1U, cont.count(10));
1069 EXPECT_EQ(1U, cont.count(11)); 1087 EXPECT_EQ(1U, cont.count(11));
1070 EXPECT_EQ(1U, cont.count(12)); 1088 EXPECT_EQ(1U, cont.count(12));
1071 EXPECT_EQ(0U, cont.count(4)); 1089 EXPECT_EQ(0U, cont.count(4));
1072 }
1073 {
1074 const IntTreeWithLess cont({5, 6, 7, 8, 9, 10, 11, 12},
1075 KEEP_FIRST_OF_DUPES);
1076 1090
1077 EXPECT_EQ(1U, cont.count(5));
1078 EXPECT_EQ(1U, cont.count(6));
1079 EXPECT_EQ(1U, cont.count(7));
1080 EXPECT_EQ(1U, cont.count(8));
1081 EXPECT_EQ(1U, cont.count(9));
1082 EXPECT_EQ(1U, cont.count(10));
1083 EXPECT_EQ(1U, cont.count(11));
1084 EXPECT_EQ(1U, cont.count(12));
1085 EXPECT_EQ(0U, cont.count(4));
1086 }
1087 } 1091 }
1088 1092
1089 // iterator find(const key_type& key) 1093 // iterator find(const key_type& key)
1090 // const_iterator find(const key_type& key) const 1094 // const_iterator find(const key_type& key) const
1091 1095
1092 TEST(FlatTree, Find) { 1096 TEST(FlatTree, Find) {
1093 { 1097 {
1094 IntTree cont({5, 6, 7, 8, 9, 10, 11, 12}, KEEP_FIRST_OF_DUPES); 1098 IntTree cont({5, 6, 7, 8, 9, 10, 11, 12}, KEEP_FIRST_OF_DUPES);
1095 1099
1096 EXPECT_EQ(cont.begin(), cont.find(5)); 1100 EXPECT_EQ(cont.begin(), cont.find(5));
(...skipping 12 matching lines...) Expand all
1109 EXPECT_EQ(cont.begin(), cont.find(5)); 1113 EXPECT_EQ(cont.begin(), cont.find(5));
1110 EXPECT_EQ(std::next(cont.begin()), cont.find(6)); 1114 EXPECT_EQ(std::next(cont.begin()), cont.find(6));
1111 EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7)); 1115 EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7));
1112 EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8)); 1116 EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8));
1113 EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9)); 1117 EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9));
1114 EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10)); 1118 EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10));
1115 EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11)); 1119 EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11));
1116 EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12)); 1120 EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12));
1117 EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4)); 1121 EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4));
1118 } 1122 }
1119 {
1120 IntTreeWithLess cont({5, 6, 7, 8, 9, 10, 11, 12}, KEEP_FIRST_OF_DUPES);
1121
1122 EXPECT_EQ(cont.begin(), cont.find(5));
1123 EXPECT_EQ(std::next(cont.begin()), cont.find(6));
1124 EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7));
1125 EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8));
1126 EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9));
1127 EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10));
1128 EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11));
1129 EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12));
1130 EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4));
1131 }
1132 } 1123 }
1133 1124
1134 // pair<iterator, iterator> equal_range(const key_type& key) 1125 // pair<iterator, iterator> equal_range(const key_type& key)
1135 // pair<const_iterator, const_iterator> equal_range(const key_type& key) const 1126 // pair<const_iterator, const_iterator> equal_range(const key_type& key) const
1136 1127
1137 TEST(FlatTree, EqualRange) { 1128 TEST(FlatTree, EqualRange) {
1138 { 1129 {
1139 IntTree cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES); 1130 IntTree cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES);
1140 1131
1141 std::pair<IntTree::iterator, IntTree::iterator> result = 1132 std::pair<IntTree::iterator, IntTree::iterator> result =
(...skipping 98 matching lines...) Expand 10 before | Expand all | Expand 10 after
1240 result = cont.equal_range(16); 1231 result = cont.equal_range(16);
1241 EXPECT_EQ(std::next(cont.begin(), 6), result.first); 1232 EXPECT_EQ(std::next(cont.begin(), 6), result.first);
1242 EXPECT_EQ(std::next(cont.begin(), 6), result.second); 1233 EXPECT_EQ(std::next(cont.begin(), 6), result.second);
1243 result = cont.equal_range(18); 1234 result = cont.equal_range(18);
1244 EXPECT_EQ(std::next(cont.begin(), 7), result.first); 1235 EXPECT_EQ(std::next(cont.begin(), 7), result.first);
1245 EXPECT_EQ(std::next(cont.begin(), 7), result.second); 1236 EXPECT_EQ(std::next(cont.begin(), 7), result.second);
1246 result = cont.equal_range(20); 1237 result = cont.equal_range(20);
1247 EXPECT_EQ(std::next(cont.begin(), 8), result.first); 1238 EXPECT_EQ(std::next(cont.begin(), 8), result.first);
1248 EXPECT_EQ(std::next(cont.begin(), 8), result.second); 1239 EXPECT_EQ(std::next(cont.begin(), 8), result.second);
1249 } 1240 }
1250 {
1251 IntTreeWithLess cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES);
1252
1253 std::pair<IntTree::iterator, IntTree::iterator> result =
1254 cont.equal_range(5);
1255 EXPECT_EQ(std::next(cont.begin(), 0), result.first);
1256 EXPECT_EQ(std::next(cont.begin(), 1), result.second);
1257 result = cont.equal_range(7);
1258 EXPECT_EQ(std::next(cont.begin(), 1), result.first);
1259 EXPECT_EQ(std::next(cont.begin(), 2), result.second);
1260 result = cont.equal_range(9);
1261 EXPECT_EQ(std::next(cont.begin(), 2), result.first);
1262 EXPECT_EQ(std::next(cont.begin(), 3), result.second);
1263 result = cont.equal_range(11);
1264 EXPECT_EQ(std::next(cont.begin(), 3), result.first);
1265 EXPECT_EQ(std::next(cont.begin(), 4), result.second);
1266 result = cont.equal_range(13);
1267 EXPECT_EQ(std::next(cont.begin(), 4), result.first);
1268 EXPECT_EQ(std::next(cont.begin(), 5), result.second);
1269 result = cont.equal_range(15);
1270 EXPECT_EQ(std::next(cont.begin(), 5), result.first);
1271 EXPECT_EQ(std::next(cont.begin(), 6), result.second);
1272 result = cont.equal_range(17);
1273 EXPECT_EQ(std::next(cont.begin(), 6), result.first);
1274 EXPECT_EQ(std::next(cont.begin(), 7), result.second);
1275 result = cont.equal_range(19);
1276 EXPECT_EQ(std::next(cont.begin(), 7), result.first);
1277 EXPECT_EQ(std::next(cont.begin(), 8), result.second);
1278 result = cont.equal_range(4);
1279 EXPECT_EQ(std::next(cont.begin(), 0), result.first);
1280 EXPECT_EQ(std::next(cont.begin(), 0), result.second);
1281 result = cont.equal_range(6);
1282 EXPECT_EQ(std::next(cont.begin(), 1), result.first);
1283 EXPECT_EQ(std::next(cont.begin(), 1), result.second);
1284 result = cont.equal_range(8);
1285 EXPECT_EQ(std::next(cont.begin(), 2), result.first);
1286 EXPECT_EQ(std::next(cont.begin(), 2), result.second);
1287 result = cont.equal_range(10);
1288 EXPECT_EQ(std::next(cont.begin(), 3), result.first);
1289 EXPECT_EQ(std::next(cont.begin(), 3), result.second);
1290 result = cont.equal_range(12);
1291 EXPECT_EQ(std::next(cont.begin(), 4), result.first);
1292 EXPECT_EQ(std::next(cont.begin(), 4), result.second);
1293 result = cont.equal_range(14);
1294 EXPECT_EQ(std::next(cont.begin(), 5), result.first);
1295 EXPECT_EQ(std::next(cont.begin(), 5), result.second);
1296 result = cont.equal_range(16);
1297 EXPECT_EQ(std::next(cont.begin(), 6), result.first);
1298 EXPECT_EQ(std::next(cont.begin(), 6), result.second);
1299 result = cont.equal_range(18);
1300 EXPECT_EQ(std::next(cont.begin(), 7), result.first);
1301 EXPECT_EQ(std::next(cont.begin(), 7), result.second);
1302 result = cont.equal_range(20);
1303 EXPECT_EQ(std::next(cont.begin(), 8), result.first);
1304 EXPECT_EQ(std::next(cont.begin(), 8), result.second);
1305 }
1306 } 1241 }
1307 1242
1308 // iterator lower_bound(const key_type& key); 1243 // iterator lower_bound(const key_type& key);
1309 // const_iterator lower_bound(const key_type& key) const; 1244 // const_iterator lower_bound(const key_type& key) const;
1310 1245
1311 TEST(FlatTree, LowerBound) { 1246 TEST(FlatTree, LowerBound) {
1312 { 1247 {
1313 IntTree cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES); 1248 IntTree cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES);
1314 1249
1315 EXPECT_EQ(cont.begin(), cont.lower_bound(5)); 1250 EXPECT_EQ(cont.begin(), cont.lower_bound(5));
(...skipping 28 matching lines...) Expand all
1344 EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4)); 1279 EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4));
1345 EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6)); 1280 EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6));
1346 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8)); 1281 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8));
1347 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10)); 1282 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10));
1348 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12)); 1283 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12));
1349 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14)); 1284 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14));
1350 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16)); 1285 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16));
1351 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18)); 1286 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18));
1352 EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20)); 1287 EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20));
1353 } 1288 }
1354 {
1355 IntTreeWithLess cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES);
1356
1357 EXPECT_EQ(cont.begin(), cont.lower_bound(5));
1358 EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7));
1359 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(9));
1360 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(11));
1361 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(13));
1362 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(15));
1363 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(17));
1364 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(19));
1365 EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4));
1366 EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6));
1367 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8));
1368 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10));
1369 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12));
1370 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14));
1371 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16));
1372 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18));
1373 EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20));
1374 }
1375 } 1289 }
1376 1290
1377 // iterator upper_bound(const key_type& key) 1291 // iterator upper_bound(const key_type& key)
1378 // const_iterator upper_bound(const key_type& key) const 1292 // const_iterator upper_bound(const key_type& key) const
1379 1293
1380 TEST(FlatTree, UpperBound) { 1294 TEST(FlatTree, UpperBound) {
1381 { 1295 {
1382 IntTree cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES); 1296 IntTree cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES);
1383 1297
1384 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5)); 1298 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5));
(...skipping 28 matching lines...) Expand all
1413 EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4)); 1327 EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4));
1414 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6)); 1328 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6));
1415 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8)); 1329 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8));
1416 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10)); 1330 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10));
1417 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12)); 1331 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12));
1418 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14)); 1332 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14));
1419 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16)); 1333 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16));
1420 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18)); 1334 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18));
1421 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20)); 1335 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20));
1422 } 1336 }
1423 {
1424 IntTreeWithLess cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES);
1425
1426 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5));
1427 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7));
1428 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(9));
1429 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(11));
1430 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(13));
1431 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(15));
1432 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(17));
1433 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(19));
1434 EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4));
1435 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6));
1436 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8));
1437 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10));
1438 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12));
1439 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14));
1440 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16));
1441 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18));
1442 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20));
1443 }
1444 } 1337 }
1445 1338
1446 // ---------------------------------------------------------------------------- 1339 // ----------------------------------------------------------------------------
1447 // General operations. 1340 // General operations.
1448 1341
1449 // void swap(flat_tree& other) 1342 // void swap(flat_tree& other)
1450 // void swap(flat_tree& lhs, flat_tree& rhs) 1343 // void swap(flat_tree& lhs, flat_tree& rhs)
1451 1344
1452 TEST(FlatTreeOurs, Swap) { 1345 TEST(FlatTreeOurs, Swap) {
1453 IntTree x({1, 2, 3}, KEEP_FIRST_OF_DUPES); 1346 IntTree x({1, 2, 3}, KEEP_FIRST_OF_DUPES);
(...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after
1493 EraseIf(x, [](int elem) { return !(elem & 1); }); 1386 EraseIf(x, [](int elem) { return !(elem & 1); });
1494 EXPECT_THAT(x, ElementsAre(1, 3)); 1387 EXPECT_THAT(x, ElementsAre(1, 3));
1495 1388
1496 x = {1, 2, 3, 4}; 1389 x = {1, 2, 3, 4};
1497 EraseIf(x, [](int elem) { return elem & 1; }); 1390 EraseIf(x, [](int elem) { return elem & 1; });
1498 EXPECT_THAT(x, ElementsAre(2, 4)); 1391 EXPECT_THAT(x, ElementsAre(2, 4));
1499 } 1392 }
1500 1393
1501 } // namespace internal 1394 } // namespace internal
1502 } // namespace base 1395 } // namespace base
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698