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