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