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_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 // compilation and this is what we do in flat_set_unittest/flat_map_unittest. | |
17 // * No tests with TemplateConstructor. | 18 // * No tests with TemplateConstructor. |
18 // Library working group issue: LWG #2059 | 19 // Library working group issue: LWG #2059 |
19 // http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#2059 | 20 // 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 // 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 // if key has a templated constructor. We have to fix this. |
jdoerrie
2017/06/20 23:51:09
Is this comment still relevant?
dyaroshev
2017/06/22 10:41:43
Thanks. Added the test.
| |
22 // * No tests for max_size() | 23 // * No tests for max_size() |
23 // Has to do with allocator support. | 24 // Has to do with allocator support. |
24 // * No tests with DefaultOnly. | 25 // * No tests with DefaultOnly. |
25 // Standard containers allocate each element in the separate node on the heap | 26 // 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 // 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 // contiguous memory and move them around, type is required to be movable. |
28 // * No tests for N3644. | 29 // * No tests for N3644. |
29 // This proposal suggests that all default constructed iterators compare | 30 // This proposal suggests that all default constructed iterators compare |
30 // equal. Currently we use std::vector iterators and they don't implement | 31 // equal. Currently we use std::vector iterators and they don't implement |
31 // this. | 32 // this. |
(...skipping 100 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
132 }; | 133 }; |
133 | 134 |
134 template <class PairType> | 135 template <class PairType> |
135 struct LessByFirst { | 136 struct LessByFirst { |
136 bool operator()(const PairType& lhs, const PairType& rhs) const { | 137 bool operator()(const PairType& lhs, const PairType& rhs) const { |
137 return lhs.first < rhs.first; | 138 return lhs.first < rhs.first; |
138 } | 139 } |
139 }; | 140 }; |
140 | 141 |
141 // Common test trees. | 142 // 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 = | 143 using IntTree = |
148 flat_tree<int, int, GetKeyFromValueIdentity<int>, std::less<int>>; | 144 flat_tree<int, int, GetKeyFromValueIdentity<int>, std::less<int>>; |
149 using IntPair = std::pair<int, int>; | 145 using IntPair = std::pair<int, int>; |
150 using IntPairTree = flat_tree<IntPair, | 146 using IntPairTree = flat_tree<IntPair, |
151 IntPair, | 147 IntPair, |
152 GetKeyFromValueIdentity<IntPair>, | 148 GetKeyFromValueIdentity<IntPair>, |
153 LessByFirst<IntPair>>; | 149 LessByFirst<IntPair>>; |
154 using MoveOnlyTree = flat_tree<MoveOnlyInt, | 150 using MoveOnlyTree = flat_tree<MoveOnlyInt, |
155 MoveOnlyInt, | 151 MoveOnlyInt, |
156 GetKeyFromValueIdentity<MoveOnlyInt>, | 152 GetKeyFromValueIdentity<MoveOnlyInt>, |
(...skipping 594 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
751 EXPECT_EQ(std::prev(cont.end()), result); | 747 EXPECT_EQ(std::prev(cont.end()), result); |
752 EXPECT_EQ(3U, cont.size()); | 748 EXPECT_EQ(3U, cont.size()); |
753 EXPECT_EQ(3, result->data()); | 749 EXPECT_EQ(3, result->data()); |
754 } | 750 } |
755 | 751 |
756 // template <class InputIterator> | 752 // template <class InputIterator> |
757 // void insert(InputIterator first, InputIterator last); | 753 // void insert(InputIterator first, InputIterator last); |
758 | 754 |
759 TEST(FlatTree, InsertIterIter) { | 755 TEST(FlatTree, InsertIterIter) { |
760 struct GetKeyFromIntIntPair { | 756 struct GetKeyFromIntIntPair { |
761 int operator()(const std::pair<int, int>& p) const { return p.first; } | 757 const int& operator()(const std::pair<int, int>& p) const { |
758 return p.first; | |
759 } | |
762 }; | 760 }; |
763 | 761 |
764 using IntIntMap = | 762 using IntIntMap = |
765 flat_tree<int, IntPair, GetKeyFromIntIntPair, std::less<int>>; | 763 flat_tree<int, IntPair, GetKeyFromIntIntPair, std::less<int>>; |
766 | 764 |
767 { | 765 { |
768 IntIntMap cont; | 766 IntIntMap cont; |
769 IntPair int_pairs[] = {{3, 1}, {1, 1}, {4, 1}, {2, 1}}; | 767 IntPair int_pairs[] = {{3, 1}, {1, 1}, {4, 1}, {2, 1}}; |
770 cont.insert(std::begin(int_pairs), std::end(int_pairs), | 768 cont.insert(std::begin(int_pairs), std::end(int_pairs), |
771 KEEP_FIRST_OF_DUPES); | 769 KEEP_FIRST_OF_DUPES); |
(...skipping 278 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
1050 std::inserter(cont, cont.end())); | 1048 std::inserter(cont, cont.end())); |
1051 EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.value_comp())); | 1049 EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.value_comp())); |
1052 } | 1050 } |
1053 | 1051 |
1054 // ---------------------------------------------------------------------------- | 1052 // ---------------------------------------------------------------------------- |
1055 // Search operations. | 1053 // Search operations. |
1056 | 1054 |
1057 // size_type count(const key_type& key) const | 1055 // size_type count(const key_type& key) const |
1058 | 1056 |
1059 TEST(FlatTree, Count) { | 1057 TEST(FlatTree, Count) { |
1060 { | |
1061 const IntTree cont({5, 6, 7, 8, 9, 10, 11, 12}, KEEP_FIRST_OF_DUPES); | 1058 const IntTree cont({5, 6, 7, 8, 9, 10, 11, 12}, KEEP_FIRST_OF_DUPES); |
1062 | 1059 |
1063 EXPECT_EQ(1U, cont.count(5)); | 1060 EXPECT_EQ(1U, cont.count(5)); |
1064 EXPECT_EQ(1U, cont.count(6)); | 1061 EXPECT_EQ(1U, cont.count(6)); |
1065 EXPECT_EQ(1U, cont.count(7)); | 1062 EXPECT_EQ(1U, cont.count(7)); |
1066 EXPECT_EQ(1U, cont.count(8)); | 1063 EXPECT_EQ(1U, cont.count(8)); |
1067 EXPECT_EQ(1U, cont.count(9)); | 1064 EXPECT_EQ(1U, cont.count(9)); |
1068 EXPECT_EQ(1U, cont.count(10)); | 1065 EXPECT_EQ(1U, cont.count(10)); |
1069 EXPECT_EQ(1U, cont.count(11)); | 1066 EXPECT_EQ(1U, cont.count(11)); |
1070 EXPECT_EQ(1U, cont.count(12)); | 1067 EXPECT_EQ(1U, cont.count(12)); |
1071 EXPECT_EQ(0U, cont.count(4)); | 1068 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 | 1069 |
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 } | 1070 } |
1088 | 1071 |
1089 // iterator find(const key_type& key) | 1072 // iterator find(const key_type& key) |
1090 // const_iterator find(const key_type& key) const | 1073 // const_iterator find(const key_type& key) const |
1091 | 1074 |
1092 TEST(FlatTree, Find) { | 1075 TEST(FlatTree, Find) { |
1093 { | 1076 { |
1094 IntTree cont({5, 6, 7, 8, 9, 10, 11, 12}, KEEP_FIRST_OF_DUPES); | 1077 IntTree cont({5, 6, 7, 8, 9, 10, 11, 12}, KEEP_FIRST_OF_DUPES); |
1095 | 1078 |
1096 EXPECT_EQ(cont.begin(), cont.find(5)); | 1079 EXPECT_EQ(cont.begin(), cont.find(5)); |
(...skipping 12 matching lines...) Expand all Loading... | |
1109 EXPECT_EQ(cont.begin(), cont.find(5)); | 1092 EXPECT_EQ(cont.begin(), cont.find(5)); |
1110 EXPECT_EQ(std::next(cont.begin()), cont.find(6)); | 1093 EXPECT_EQ(std::next(cont.begin()), cont.find(6)); |
1111 EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7)); | 1094 EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7)); |
1112 EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8)); | 1095 EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8)); |
1113 EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9)); | 1096 EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9)); |
1114 EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10)); | 1097 EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10)); |
1115 EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11)); | 1098 EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11)); |
1116 EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12)); | 1099 EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12)); |
1117 EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4)); | 1100 EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4)); |
1118 } | 1101 } |
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 } | 1102 } |
1133 | 1103 |
1134 // pair<iterator, iterator> equal_range(const key_type& key) | 1104 // pair<iterator, iterator> equal_range(const key_type& key) |
1135 // pair<const_iterator, const_iterator> equal_range(const key_type& key) const | 1105 // pair<const_iterator, const_iterator> equal_range(const key_type& key) const |
1136 | 1106 |
1137 TEST(FlatTree, EqualRange) { | 1107 TEST(FlatTree, EqualRange) { |
1138 { | 1108 { |
1139 IntTree cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES); | 1109 IntTree cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES); |
1140 | 1110 |
1141 std::pair<IntTree::iterator, IntTree::iterator> result = | 1111 std::pair<IntTree::iterator, IntTree::iterator> result = |
(...skipping 98 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
1240 result = cont.equal_range(16); | 1210 result = cont.equal_range(16); |
1241 EXPECT_EQ(std::next(cont.begin(), 6), result.first); | 1211 EXPECT_EQ(std::next(cont.begin(), 6), result.first); |
1242 EXPECT_EQ(std::next(cont.begin(), 6), result.second); | 1212 EXPECT_EQ(std::next(cont.begin(), 6), result.second); |
1243 result = cont.equal_range(18); | 1213 result = cont.equal_range(18); |
1244 EXPECT_EQ(std::next(cont.begin(), 7), result.first); | 1214 EXPECT_EQ(std::next(cont.begin(), 7), result.first); |
1245 EXPECT_EQ(std::next(cont.begin(), 7), result.second); | 1215 EXPECT_EQ(std::next(cont.begin(), 7), result.second); |
1246 result = cont.equal_range(20); | 1216 result = cont.equal_range(20); |
1247 EXPECT_EQ(std::next(cont.begin(), 8), result.first); | 1217 EXPECT_EQ(std::next(cont.begin(), 8), result.first); |
1248 EXPECT_EQ(std::next(cont.begin(), 8), result.second); | 1218 EXPECT_EQ(std::next(cont.begin(), 8), result.second); |
1249 } | 1219 } |
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 } | 1220 } |
1307 | 1221 |
1308 // iterator lower_bound(const key_type& key); | 1222 // iterator lower_bound(const key_type& key); |
1309 // const_iterator lower_bound(const key_type& key) const; | 1223 // const_iterator lower_bound(const key_type& key) const; |
1310 | 1224 |
1311 TEST(FlatTree, LowerBound) { | 1225 TEST(FlatTree, LowerBound) { |
1312 { | 1226 { |
1313 IntTree cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES); | 1227 IntTree cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES); |
1314 | 1228 |
1315 EXPECT_EQ(cont.begin(), cont.lower_bound(5)); | 1229 EXPECT_EQ(cont.begin(), cont.lower_bound(5)); |
(...skipping 28 matching lines...) Expand all Loading... | |
1344 EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4)); | 1258 EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4)); |
1345 EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6)); | 1259 EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6)); |
1346 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8)); | 1260 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8)); |
1347 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10)); | 1261 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10)); |
1348 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12)); | 1262 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12)); |
1349 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14)); | 1263 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14)); |
1350 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16)); | 1264 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16)); |
1351 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18)); | 1265 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18)); |
1352 EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20)); | 1266 EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20)); |
1353 } | 1267 } |
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 } | 1268 } |
1376 | 1269 |
1377 // iterator upper_bound(const key_type& key) | 1270 // iterator upper_bound(const key_type& key) |
1378 // const_iterator upper_bound(const key_type& key) const | 1271 // const_iterator upper_bound(const key_type& key) const |
1379 | 1272 |
1380 TEST(FlatTree, UpperBound) { | 1273 TEST(FlatTree, UpperBound) { |
1381 { | 1274 { |
1382 IntTree cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES); | 1275 IntTree cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES); |
1383 | 1276 |
1384 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5)); | 1277 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5)); |
(...skipping 28 matching lines...) Expand all Loading... | |
1413 EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4)); | 1306 EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4)); |
1414 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6)); | 1307 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6)); |
1415 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8)); | 1308 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8)); |
1416 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10)); | 1309 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10)); |
1417 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12)); | 1310 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12)); |
1418 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14)); | 1311 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14)); |
1419 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16)); | 1312 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16)); |
1420 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18)); | 1313 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18)); |
1421 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20)); | 1314 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20)); |
1422 } | 1315 } |
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 } | 1316 } |
1445 | 1317 |
1446 // ---------------------------------------------------------------------------- | 1318 // ---------------------------------------------------------------------------- |
1447 // General operations. | 1319 // General operations. |
1448 | 1320 |
1449 // void swap(flat_tree& other) | 1321 // void swap(flat_tree& other) |
1450 // void swap(flat_tree& lhs, flat_tree& rhs) | 1322 // void swap(flat_tree& lhs, flat_tree& rhs) |
1451 | 1323 |
1452 TEST(FlatTreeOurs, Swap) { | 1324 TEST(FlatTreeOurs, Swap) { |
1453 IntTree x({1, 2, 3}, KEEP_FIRST_OF_DUPES); | 1325 IntTree x({1, 2, 3}, KEEP_FIRST_OF_DUPES); |
(...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
1493 EraseIf(x, [](int elem) { return !(elem & 1); }); | 1365 EraseIf(x, [](int elem) { return !(elem & 1); }); |
1494 EXPECT_THAT(x, ElementsAre(1, 3)); | 1366 EXPECT_THAT(x, ElementsAre(1, 3)); |
1495 | 1367 |
1496 x = {1, 2, 3, 4}; | 1368 x = {1, 2, 3, 4}; |
1497 EraseIf(x, [](int elem) { return elem & 1; }); | 1369 EraseIf(x, [](int elem) { return elem & 1; }); |
1498 EXPECT_THAT(x, ElementsAre(2, 4)); | 1370 EXPECT_THAT(x, ElementsAre(2, 4)); |
1499 } | 1371 } |
1500 | 1372 |
1501 } // namespace internal | 1373 } // namespace internal |
1502 } // namespace base | 1374 } // namespace base |
OLD | NEW |