OLD | NEW |
---|---|
(Empty) | |
1 // Copyright 2016 The Chromium Authors. All rights reserved. | |
2 // Use of this source code is governed by a BSD-style license that can be | |
3 // found in the LICENSE file. | |
4 | |
5 #include "base/containers/flat_set.h" | |
6 | |
7 // Following tests are ported and extended tests from libcpp for std::set. | |
8 // They can be found here: | |
9 // https://github.com/llvm-mirror/libcxx/tree/master/test/std/containers/associa tive/set | |
10 // | |
11 // Not ported tests: | |
12 // * No tests with PrivateConstructor and std::less<> changed to std::less<T> | |
13 // These tests have to do with C++14 std::less<> | |
14 // http://en.cppreference.com/w/cpp/utility/functional/less_void | |
15 // and add support for templated versions of lookup functions. | |
16 // Current implementation of flat containers doesn't support it. | |
17 // * No tests with TemplateConstructor. | |
18 // Library working group issue: LWG #2059 | |
19 // http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#2059 | |
20 // There is an ambiguity between erase with an iterator and erase with a key, | |
21 // if key has a templated constructor. We have to fix this. | |
22 // * No tests for max_size() | |
23 // Has to do with allocator support. | |
24 // * No tests with DefaultOnly. | |
25 // Standard containers allocate each element in the separate node on the heap | |
26 // and then manipulate these nodes. Flat containers store their elements in | |
27 // contiguous memory and move them around, type is required to be movable. | |
28 // * No tests for N3644. | |
29 // This proposal suggests that all default constructed iterators compare | |
30 // equal. Currently we use std::vector iterators and they don't implement | |
31 // this. | |
32 // * No tests with min_allocator. | |
33 // Allocators are not widely used in Chromium, and how we are going to | |
34 // customize underlying data (if we are going to) is still up to debate. | |
35 // * No tests counting allocations. Flat sets have different allocation | |
36 // patterns than std::sets and we do not consider them to be a part of the | |
37 // interface. | |
38 | |
39 #include <string> | |
40 #include <vector> | |
41 | |
42 #include "base/macros.h" | |
43 #include "testing/gtest/include/gtest/gtest.h" | |
44 | |
45 namespace { | |
46 | |
47 class MoveOnly { | |
48 public: | |
49 MoveOnly(int data = 1) : data_(data) {} | |
50 MoveOnly(MoveOnly&& x) : data_(x.data_) { x.data_ = 0; } | |
51 MoveOnly& operator=(MoveOnly&& x) { | |
52 data_ = x.data_; | |
53 x.data_ = 0; | |
54 return *this; | |
55 } | |
56 | |
57 friend bool operator==(const MoveOnly& x, const MoveOnly& y) { | |
Peter Kasting
2016/12/20 02:33:51
Any particular reason to prefer member vs. non-mem
dyaroshev
2016/12/20 21:59:55
1. This type is implicitly convertible from int (t
| |
58 return x.data_ == y.data_; | |
59 } | |
60 | |
61 friend bool operator<(const MoveOnly& x, const MoveOnly& y) { | |
62 return x.data_ < y.data_; | |
63 } | |
64 | |
65 int data() const { return data_; } | |
66 | |
67 private: | |
68 int data_; | |
69 | |
70 DISALLOW_COPY_AND_ASSIGN(MoveOnly); | |
71 }; | |
72 | |
73 template <class It> | |
74 class InputIterator { | |
75 public: | |
76 using iterator_category = std::input_iterator_tag; | |
77 using value_type = typename std::iterator_traits<It>::value_type; | |
78 using difference_type = typename std::iterator_traits<It>::difference_type; | |
79 using pointer = It; | |
80 using reference = typename std::iterator_traits<It>::reference; | |
81 | |
82 InputIterator() : it_() {} | |
83 explicit InputIterator(It it) : it_(it) {} | |
84 InputIterator(const InputIterator& x) : it_(x.it_) {} | |
85 | |
86 reference operator*() const { return *it_; } | |
87 pointer operator->() const { return it_; } | |
88 | |
89 InputIterator& operator++() { | |
90 ++it_; | |
91 return *this; | |
92 } | |
93 InputIterator operator++(int) { | |
94 InputIterator tmp(*this); | |
95 ++(*this); | |
96 return tmp; | |
97 } | |
98 | |
99 friend bool operator==(const InputIterator& x, const InputIterator& y) { | |
100 return x.it_ == y.it_; | |
101 } | |
102 friend bool operator!=(const InputIterator& x, const InputIterator& y) { | |
103 return !(x == y); | |
104 } | |
105 | |
106 private: | |
107 It it_; | |
108 }; | |
109 | |
110 template <typename It> | |
111 InputIterator<It> MakeInputIterator(It it) { | |
112 return InputIterator<It>(it); | |
113 } | |
114 | |
115 class Emplaceable { | |
116 public: | |
117 Emplaceable() = default; | |
118 Emplaceable(int i, double d) : int_(i), double_(d) {} | |
119 Emplaceable(Emplaceable&& x) : int_(x.int_), double_(x.double_) { | |
120 x.int_ = 0; | |
121 x.double_ = 0.0; | |
122 } | |
123 | |
124 Emplaceable& operator=(Emplaceable&& x) { | |
125 int_ = x.int_; | |
126 x.int_ = 0; | |
127 double_ = x.double_; | |
128 x.double_ = 0.0; | |
129 return *this; | |
130 } | |
131 | |
132 friend bool operator==(const Emplaceable& x, const Emplaceable& y) { | |
133 return x.int_ == y.int_ && x.double_ == y.double_; | |
134 } | |
135 | |
136 friend bool operator<(const Emplaceable& x, const Emplaceable& y) { | |
137 return std::tie(x.int_, x.double_) < std::tie(y.int_, y.double_); | |
138 } | |
139 | |
140 private: | |
141 int int_ = 0; | |
142 double double_ = 0.0; | |
Peter Kasting
2016/12/20 02:33:51
Nit: I dunno that I'm as big a fan of these initia
dyaroshev
2016/12/20 21:59:55
Done.
| |
143 | |
144 DISALLOW_COPY_AND_ASSIGN(Emplaceable); | |
145 }; | |
146 | |
147 class NonDefaultConstructibleCompare { | |
148 public: | |
149 NonDefaultConstructibleCompare(int) {} | |
150 | |
151 template <typename T> | |
152 bool operator()(const T& lhs, const T& rhs) { | |
153 return std::less<T>()(lhs, rhs); | |
154 } | |
155 }; | |
156 | |
157 template <typename T> | |
158 std::string ToString(const T& val) { | |
159 return std::to_string(val); | |
160 } | |
161 | |
162 std::string ToString(const MoveOnly& val) { | |
163 return std::to_string(val.data()); | |
164 } | |
165 | |
166 template <typename XRange, typename YRange> | |
167 // Requires: | |
168 // XRange is ForwardRange | |
169 // YRange is ForwardRange | |
170 // ValueType<XRange> is EqualityComparable to ValueType<YRange> | |
171 bool EqualRange(const XRange& x_range, const YRange& y_range) { | |
172 if (std::distance(x_range.begin(), x_range.end()) != | |
173 std::distance(y_range.begin(), y_range.end())) | |
174 return false; | |
175 | |
176 return std::equal(x_range.begin(), x_range.end(), y_range.begin()); | |
Peter Kasting
2016/12/20 02:33:50
Nit: Or just:
return (std::distance(x_range.beg
dyaroshev
2016/12/20 21:59:55
Done.
| |
177 } | |
178 | |
179 template <typename Range> | |
180 // Requires: | |
181 // Range is InputRange | |
182 // ValueType<Range> is ConvertibleToString. | |
183 std::string RangeToString(const Range& range) { | |
184 std::string res = "["; | |
185 for (const auto& val : range) { | |
Peter Kasting
2016/12/20 02:33:51
Nit: {} unnecessary
dyaroshev
2016/12/20 21:59:55
Done.
| |
186 res += ToString(val) + ", "; | |
187 } | |
188 res += ']'; | |
189 return res; | |
190 } | |
191 | |
192 template <typename TestedRange> | |
193 // Requires: | |
194 // TestedRange is ForwardRange | |
195 // ExpectedRange is ForwardRange | |
196 // ValueType<TestedRange> is EqualityComparable to int | |
197 // ValueType<TestedRange> is ConvertibleToString. | |
198 void ExpectRange(const TestedRange& tested_range, | |
199 const std::vector<int>& expected_range) { | |
200 EXPECT_TRUE(EqualRange(tested_range, expected_range)) | |
201 << "Expected: " << RangeToString(expected_range) | |
202 << " Actual: " << RangeToString(tested_range); | |
Peter Kasting
2016/12/20 02:33:51
Nit: Maybe put a comma at the beginning of this se
dyaroshev
2016/12/20 21:59:55
Done.
| |
203 } | |
204 | |
205 } // namespace | |
206 | |
207 // ---------------------------------------------------------------------------- | |
208 // Class. | |
209 | |
210 // Check that base::flat_set and its iterators can be instantiated with an | |
211 // incomplete type. | |
212 | |
213 TEST(FlatSet, IncompleteType) { | |
214 struct A { | |
215 using Set = base::flat_set<A>; | |
216 int data; | |
217 Set m; | |
218 Set::iterator it; | |
219 Set::const_iterator cit; | |
220 | |
221 // We do not declare operator< because clang complains that it's unused. | |
222 }; | |
223 | |
224 A a; | |
225 } | |
226 | |
227 TEST(FlatSet, Stability) { | |
228 using Pair = std::pair<int, int>; | |
229 | |
230 struct LessByFirst { | |
231 bool operator()(const Pair& x, const Pair& y) { return x.first < y.first; } | |
232 }; | |
233 | |
234 using Set = base::flat_set<Pair, LessByFirst>; | |
235 | |
236 auto AllSecondAreZero = [](const Set& cont) { | |
237 return std::all_of(cont.begin(), cont.end(), | |
238 [](const Pair& elem) { return elem.second == 0; }); | |
239 }; | |
240 | |
241 Set cont{{0, 0}, {1, 0}, {0, 1}, {2, 0}, {0, 2}, {1, 1}}; | |
242 EXPECT_TRUE(AllSecondAreZero(cont)) << "initializer_list constructor"; | |
243 | |
244 cont.insert(Pair(0, 1)); | |
245 EXPECT_TRUE(AllSecondAreZero(cont)) << "single insert"; | |
246 | |
247 cont.insert({{3, 0}, {0, 1}, {1, 1}, {3, 1}, {2, 1}, {3, 2}}); | |
248 EXPECT_TRUE(AllSecondAreZero(cont)) << "initializer_list insert"; | |
249 } | |
250 | |
251 // ---------------------------------------------------------------------------- | |
252 // Types. | |
253 | |
254 // key_type | |
255 // key_compare | |
256 // value_type | |
257 // value_compare | |
258 // allocator_type | |
259 // pointer | |
260 // const_pointer | |
261 // reference | |
262 // const_reference | |
263 // size_type | |
264 // difference_type | |
265 // iterator | |
266 // const_iterator | |
267 // reverse_iterator | |
268 // const_reverse_iterator | |
269 | |
270 TEST(FlatSet, Types) { | |
271 using Set = base::flat_set<int>; | |
272 | |
273 // These are guarantied to be portable. | |
Peter Kasting
2016/12/20 02:33:51
Nit: guaranteed
dyaroshev
2016/12/20 21:59:55
Done.
| |
274 static_assert((std::is_same<int, Set::key_type>::value), ""); | |
275 static_assert((std::is_same<int, Set::value_type>::value), ""); | |
276 static_assert((std::is_same<std::less<int>, Set::key_compare>::value), ""); | |
277 static_assert((std::is_same<std::less<int>, Set::value_compare>::value), ""); | |
278 static_assert((std::is_same<int&, Set::reference>::value), ""); | |
279 static_assert((std::is_same<const int&, Set::const_reference>::value), ""); | |
280 static_assert((std::is_same<int*, Set::pointer>::value), ""); | |
281 static_assert((std::is_same<const int*, Set::const_pointer>::value), ""); | |
282 } | |
283 | |
284 // ---------------------------------------------------------------------------- | |
285 // Lifetime. | |
286 | |
287 // flat_set() | |
288 // flat_set(const Compare& comp, const Allocator& alloc = Allocator()) | |
289 // flat_set(const Allocator& alloc) | |
290 | |
291 TEST(FlatSet, DefaultConstructor) { | |
292 { | |
293 using Set = base::flat_set<int>; | |
Peter Kasting
2016/12/20 02:33:50
This alias appears in basically every test. Maybe
dyaroshev
2016/12/20 21:59:55
Moved all common typedefs in anonymous namespace.
| |
294 | |
295 Set cont; | |
296 ExpectRange(cont, {}); | |
297 } | |
298 | |
299 { | |
300 using Set = base::flat_set<int, NonDefaultConstructibleCompare>; | |
301 | |
302 Set cont{NonDefaultConstructibleCompare(0)}; | |
Peter Kasting
2016/12/20 02:33:51
Do you really need to use {} here? (Maybe it avoi
dyaroshev
2016/12/20 21:59:55
Done.
| |
303 ExpectRange(cont, {}); | |
304 } | |
305 } | |
306 | |
307 // flat_set(InputIterator first, | |
308 // InputIterator last, | |
309 // const Compare& comp = Compare(), | |
310 // const Allocator& alloc = Allocator()) | |
311 // flat_set(InputIterator first, InputIterator last, const Allocator& alloc) | |
312 | |
313 TEST(FlatSet, RangeConstructor) { | |
314 { | |
315 using Set = base::flat_set<int>; | |
316 | |
317 Set::value_type ar[] = {1, 1, 1, 2, 2, 2, 3, 3, 3}; | |
318 | |
319 Set cont(MakeInputIterator(std::begin(ar)), | |
320 MakeInputIterator(std::end(ar))); | |
321 ExpectRange(cont, {1, 2, 3}); | |
322 } | |
323 { | |
324 using Set = base::flat_set<int, NonDefaultConstructibleCompare>; | |
325 | |
326 Set::value_type ar[] = {1, 1, 1, 2, 2, 2, 3, 3, 3}; | |
327 | |
328 Set cont(MakeInputIterator(std::begin(ar)), MakeInputIterator(std::end(ar)), | |
329 NonDefaultConstructibleCompare(0)); | |
330 ExpectRange(cont, {1, 2, 3}); | |
331 } | |
332 } | |
333 | |
334 // flat_set(const flat_set& x) | |
335 // flat_set(const flat_set& x, const Allocator& alloc) | |
336 | |
337 TEST(FlatSet, CopyConstructor) { | |
338 using Set = base::flat_set<int>; | |
339 | |
340 Set original{1, 2, 3, 4}; | |
341 Set copied(original); | |
342 | |
343 ExpectRange(copied, {1, 2, 3, 4}); | |
344 ExpectRange(original, {1, 2, 3, 4}); | |
345 EXPECT_EQ(original, copied); | |
346 } | |
347 | |
348 // flat_set(flat_set&& x) | |
349 // flat_set(flat_set&& x, const Allocator& alloc) | |
350 | |
351 TEST(FlatSet, MoveConstructor) { | |
352 using Set = base::flat_set<MoveOnly>; | |
353 | |
354 int input_range[] = {1, 2, 3, 4}; | |
355 | |
356 Set original(std::begin(input_range), std::end(input_range)); | |
357 Set moved(std::move(original)); | |
358 | |
359 ExpectRange(moved, {1, 2, 3, 4}); | |
360 } | |
361 | |
362 // flat_set(std::initializer_list<value_type> il, | |
363 // const Compare& comp = Compare(), | |
364 // const Allocator& alloc = Allocator()) | |
365 // flat_set(std::initializer_list<value_type> il, const Allocator& a) | |
366 | |
367 TEST(FlatSet, InitializerListConstructor) { | |
368 { | |
369 using Set = base::flat_set<int>; | |
370 | |
371 Set cont{1, 2, 3, 4, 5, 6, 10, 8}; | |
372 ExpectRange(cont, {1, 2, 3, 4, 5, 6, 8, 10}); | |
373 } | |
374 { | |
375 using Set = base::flat_set<int, NonDefaultConstructibleCompare>; | |
376 | |
377 Set cont({1, 2, 3, 4, 5, 6, 10, 8}, NonDefaultConstructibleCompare(0)); | |
378 ExpectRange(cont, {1, 2, 3, 4, 5, 6, 8, 10}); | |
379 } | |
380 } | |
381 | |
382 // ---------------------------------------------------------------------------- | |
383 // Assignments. | |
384 | |
385 // flat_set& operator=(const flat_set& x) | |
386 | |
387 TEST(FlatSet, CopyAssignable) { | |
388 using Set = base::flat_set<int>; | |
389 | |
390 Set original{1, 2, 3, 4}; | |
391 Set copied; | |
392 copied = original; | |
393 | |
394 ExpectRange(copied, {1, 2, 3, 4}); | |
395 ExpectRange(original, {1, 2, 3, 4}); | |
396 EXPECT_EQ(original, copied); | |
397 } | |
398 | |
399 // flat_set& operator=(flat_set&& x) | |
400 | |
401 TEST(FlatSet, MoveAssignable) { | |
402 using Set = base::flat_set<MoveOnly>; | |
403 | |
404 int input_range[] = {1, 2, 3, 4}; | |
405 | |
406 Set original(std::begin(input_range), std::end(input_range)); | |
407 Set moved; | |
408 moved = std::move(original); | |
409 | |
410 ExpectRange(moved, {1, 2, 3, 4}); | |
411 } | |
412 | |
413 // flat_set& operator=(std::initializer_list<value_type> il) | |
414 | |
415 TEST(FlatSet, InitializerListAssignable) { | |
416 using Set = base::flat_set<int>; | |
417 | |
418 Set cont{0}; | |
419 cont = {1, 2, 3, 4, 5, 6, 10, 8}; | |
420 | |
421 EXPECT_EQ(static_cast<Set::size_type>(0), cont.count(0)); | |
Peter Kasting
2016/12/20 02:33:51
Nit: I still suggest using "0U" and similar for ca
dyaroshev
2016/12/20 21:59:55
Done.
| |
422 ExpectRange(cont, {1, 2, 3, 4, 5, 6, 8, 10}); | |
423 } | |
424 | |
425 // -------------------------------------------------------------------------- | |
426 // Memory management. | |
427 | |
428 // void reserve(size_type size) | |
429 | |
430 TEST(FlatSet, Reserve) { | |
431 using Set = base::flat_set<int>; | |
432 Set cont{1, 2, 3}; | |
433 | |
434 cont.reserve(5); | |
435 EXPECT_LE(static_cast<Set::size_type>(5), cont.capacity()); | |
436 } | |
437 | |
438 // size_type capacity() const | |
439 | |
440 TEST(FlatSet, Capacity) { | |
441 using Set = base::flat_set<int>; | |
442 Set cont{1, 2, 3}; | |
443 EXPECT_LE(cont.size(), cont.capacity()); | |
444 cont.reserve(5); | |
445 EXPECT_LE(cont.size(), cont.capacity()); | |
446 } | |
447 | |
448 // void shrink_to_fit() | |
449 | |
450 TEST(FlatSet, ShrinkToFit) { | |
451 using Set = base::flat_set<int>; | |
452 Set cont{1, 2, 3}; | |
453 | |
454 Set::size_type capacity_before = cont.capacity(); | |
455 cont.shrink_to_fit(); | |
456 EXPECT_GE(capacity_before, cont.capacity()); | |
457 } | |
458 | |
459 // ---------------------------------------------------------------------------- | |
460 // Size management. | |
461 | |
462 // void clear(); | |
463 | |
464 TEST(FlatSet, Clear) { | |
465 using Set = base::flat_set<int>; | |
466 | |
467 Set cont{1, 2, 3, 4, 5, 6, 7, 8}; | |
468 cont.clear(); | |
469 ExpectRange(cont, {}); | |
470 } | |
471 | |
472 // size_type size() const; | |
473 | |
474 TEST(FlatSet, Size) { | |
475 using Set = base::flat_set<int>; | |
476 Set cont; | |
477 EXPECT_EQ(static_cast<Set::size_type>(0), cont.size()); | |
478 cont.insert(2); | |
479 EXPECT_EQ(static_cast<Set::size_type>(1), cont.size()); | |
480 cont.insert(1); | |
481 EXPECT_EQ(static_cast<Set::size_type>(2), cont.size()); | |
482 cont.insert(3); | |
483 EXPECT_EQ(static_cast<Set::size_type>(3), cont.size()); | |
484 cont.erase(cont.begin()); | |
485 EXPECT_EQ(static_cast<Set::size_type>(2), cont.size()); | |
486 cont.erase(cont.begin()); | |
487 EXPECT_EQ(static_cast<Set::size_type>(1), cont.size()); | |
488 cont.erase(cont.begin()); | |
489 EXPECT_EQ(static_cast<Set::size_type>(0), cont.size()); | |
490 } | |
491 | |
492 // bool empty() const; | |
493 | |
494 TEST(FlatSet, Empty) { | |
495 using Set = base::flat_set<int>; | |
496 Set cont; | |
497 EXPECT_TRUE(cont.empty()); | |
498 cont.insert(1); | |
499 EXPECT_FALSE(cont.empty()); | |
500 cont.clear(); | |
501 EXPECT_TRUE(cont.empty()); | |
502 } | |
503 | |
504 // ---------------------------------------------------------------------------- | |
505 // Iterators. | |
506 | |
507 // iterator begin(); | |
508 // const_iterator begin() const; | |
509 // iterator end(); | |
510 // const_iterator end() const; | |
511 // | |
512 // reverse_iterator rbegin(); | |
513 // const_reverse_iterator rbegin() const; | |
514 // reverse_iterator rend(); | |
515 // const_reverse_iterator rend() const; | |
516 // | |
517 // const_iterator cbegin() const; | |
518 // const_iterator cend() const; | |
519 // const_reverse_iterator crbegin() const; | |
520 // const_reverse_iterator crend() const; | |
521 | |
522 TEST(FlatSet, Iterators) { | |
523 using Set = base::flat_set<int>; | |
524 | |
525 Set cont{1, 2, 3, 4, 5, 6, 7, 8}; | |
526 | |
527 auto size = static_cast<Set::difference_type>(cont.size()); | |
528 | |
529 EXPECT_EQ(size, std::distance(cont.begin(), cont.end())); | |
530 EXPECT_EQ(size, std::distance(cont.cbegin(), cont.cend())); | |
531 EXPECT_EQ(size, std::distance(cont.rbegin(), cont.rend())); | |
532 EXPECT_EQ(size, std::distance(cont.crbegin(), cont.crend())); | |
533 | |
534 { | |
535 Set::iterator it = cont.begin(); | |
536 Set::const_iterator c_it = cont.cbegin(); | |
537 EXPECT_EQ(it, c_it); | |
538 for (int j = 1; it != cont.end(); ++it, ++c_it, ++j) { | |
539 EXPECT_EQ(j, *it); | |
540 EXPECT_EQ(j, *c_it); | |
541 } | |
542 } | |
543 { | |
544 Set::reverse_iterator rit = cont.rbegin(); | |
545 Set::const_reverse_iterator c_rit = cont.crbegin(); | |
546 EXPECT_EQ(rit, c_rit); | |
547 for (int j = static_cast<int>(size); rit != cont.rend(); | |
548 ++rit, ++c_rit, --j) { | |
549 EXPECT_EQ(j, *rit); | |
550 EXPECT_EQ(j, *c_rit); | |
551 } | |
552 } | |
553 } | |
554 | |
555 // ---------------------------------------------------------------------------- | |
556 // Insert operations. | |
557 | |
558 // pair<iterator, bool> insert(const value_type& v); | |
559 | |
560 TEST(FlatSet, InsertCV) { | |
561 using Set = base::flat_set<int>; | |
562 | |
563 Set cont; | |
564 int value = 2; | |
Peter Kasting
2016/12/20 02:33:51
Does this test not test the same thing if you inli
dyaroshev
2016/12/20 21:59:55
I was trying to make emphasise that it calls inser
Peter Kasting
2016/12/20 22:06:38
Yeah, that's a good point.
| |
565 std::pair<Set::iterator, bool> result = cont.insert(value); | |
566 EXPECT_TRUE(result.second); | |
567 EXPECT_EQ(cont.begin(), result.first); | |
568 EXPECT_EQ(static_cast<Set::size_type>(1), cont.size()); | |
569 EXPECT_EQ(2, *result.first); | |
570 | |
571 value = 1; | |
572 result = cont.insert(value); | |
573 EXPECT_TRUE(result.second); | |
574 EXPECT_EQ(cont.begin(), result.first); | |
575 EXPECT_EQ(static_cast<Set::size_type>(2), cont.size()); | |
576 EXPECT_EQ(1, *result.first); | |
577 | |
578 value = 3; | |
579 result = cont.insert(value); | |
580 EXPECT_TRUE(result.second); | |
581 EXPECT_EQ(std::prev(cont.end()), result.first); | |
582 EXPECT_EQ(static_cast<Set::size_type>(3), cont.size()); | |
583 EXPECT_EQ(3, *result.first); | |
584 | |
585 value = 3; | |
586 result = cont.insert(value); | |
587 EXPECT_FALSE(result.second); | |
588 EXPECT_EQ(std::prev(cont.end()), result.first); | |
589 EXPECT_EQ(static_cast<Set::size_type>(3), cont.size()); | |
590 EXPECT_EQ(3, *result.first); | |
591 } | |
592 | |
593 // pair<iterator, bool> insert(value_type&& v); | |
594 | |
595 TEST(FlatSet, InsertRV) { | |
596 using Set = base::flat_set<MoveOnly>; | |
597 | |
598 Set cont; | |
599 std::pair<Set::iterator, bool> result = cont.insert(MoveOnly(2)); | |
600 EXPECT_TRUE(result.second); | |
601 EXPECT_EQ(cont.begin(), result.first); | |
602 EXPECT_EQ(static_cast<Set::size_type>(1), cont.size()); | |
603 EXPECT_EQ(2, *result.first); | |
604 | |
605 result = cont.insert(MoveOnly(1)); | |
606 EXPECT_TRUE(result.second); | |
607 EXPECT_EQ(cont.begin(), result.first); | |
608 EXPECT_EQ(static_cast<Set::size_type>(2), cont.size()); | |
609 EXPECT_EQ(1, *result.first); | |
610 | |
611 result = cont.insert(MoveOnly(3)); | |
612 EXPECT_TRUE(result.second); | |
613 EXPECT_EQ(std::prev(cont.end()), result.first); | |
614 EXPECT_EQ(static_cast<Set::size_type>(3), cont.size()); | |
615 EXPECT_EQ(3, *result.first); | |
616 | |
617 result = cont.insert(MoveOnly(3)); | |
618 EXPECT_FALSE(result.second); | |
619 EXPECT_EQ(std::prev(cont.end()), result.first); | |
620 EXPECT_EQ(static_cast<Set::size_type>(3), cont.size()); | |
621 EXPECT_EQ(static_cast<Set::size_type>(3), *result.first); | |
Peter Kasting
2016/12/20 02:33:51
This cast seems incorrect.
dyaroshev
2016/12/20 21:59:55
Done.
| |
622 } | |
623 | |
624 // iterator insert(const_iterator position, const value_type& v); | |
625 | |
626 TEST(FlatSet, InsertIterCV) { | |
627 using Set = base::flat_set<int>; | |
628 | |
629 Set cont; | |
630 Set::iterator result = cont.insert(cont.cend(), 2); | |
631 EXPECT_EQ(cont.begin(), result); | |
632 EXPECT_EQ(static_cast<Set::size_type>(1), cont.size()); | |
633 EXPECT_EQ(2, *result); | |
634 | |
635 result = cont.insert(cont.cend(), 1); | |
636 EXPECT_EQ(cont.begin(), result); | |
637 EXPECT_EQ(static_cast<Set::size_type>(2), cont.size()); | |
638 EXPECT_EQ(1, *result); | |
639 | |
640 result = cont.insert(cont.cend(), 3); | |
641 EXPECT_EQ(std::prev(cont.end()), result); | |
642 EXPECT_EQ(static_cast<Set::size_type>(3), cont.size()); | |
643 EXPECT_EQ(3, *result); | |
644 | |
645 result = cont.insert(cont.cend(), 3); | |
646 EXPECT_EQ(std::prev(cont.end()), result); | |
647 EXPECT_EQ(static_cast<Set::size_type>(3), cont.size()); | |
648 EXPECT_EQ(3, *result); | |
649 } | |
650 | |
651 // iterator insert(const_iterator position, value_type&& v); | |
652 | |
653 TEST(FlatSet, InsertIterRV) { | |
654 using Set = base::flat_set<MoveOnly>; | |
655 | |
656 Set cont; | |
657 Set::iterator result = cont.insert(cont.cend(), MoveOnly(2)); | |
658 EXPECT_EQ(cont.begin(), result); | |
659 EXPECT_EQ(static_cast<Set::size_type>(1), cont.size()); | |
660 EXPECT_EQ(2, *result); | |
661 | |
662 result = cont.insert(cont.cend(), MoveOnly(1)); | |
663 EXPECT_EQ(cont.begin(), result); | |
664 EXPECT_EQ(static_cast<Set::size_type>(2), cont.size()); | |
665 EXPECT_EQ(1, *result); | |
666 | |
667 result = cont.insert(cont.cend(), MoveOnly(3)); | |
668 EXPECT_EQ(std::prev(cont.end()), result); | |
669 EXPECT_EQ(static_cast<Set::size_type>(3), cont.size()); | |
670 EXPECT_EQ(3, *result); | |
671 | |
672 result = cont.insert(cont.cend(), MoveOnly(3)); | |
673 EXPECT_EQ(std::prev(cont.end()), result); | |
674 EXPECT_EQ(static_cast<Set::size_type>(3), cont.size()); | |
675 EXPECT_EQ(3, *result); | |
676 } | |
677 | |
678 // template <class InputIterator> | |
679 // void insert(InputIterator first, InputIterator last); | |
680 | |
681 TEST(FlatSet, InsertRange) { | |
682 using Set = base::flat_set<int>; | |
683 | |
684 int input[] = {1, 1, 1, 2, 2, 2, 3, 3, 3}; | |
685 | |
686 Set cont; | |
687 cont.insert(MakeInputIterator(std::begin(input)), | |
688 MakeInputIterator(std::end(input))); | |
689 ExpectRange(cont, {1, 2, 3}); | |
690 } | |
691 | |
692 // void insert(initializer_list<value_type> il); | |
693 | |
694 TEST(FlatSet, InsertInitializerList) { | |
695 using Set = base::flat_set<int>; | |
696 | |
697 Set cont = {10, 8}; | |
698 cont.insert({1, 2, 3, 4, 5, 6}); | |
699 ExpectRange(cont, {1, 2, 3, 4, 5, 6, 8, 10}); | |
700 } | |
701 | |
702 // template <class... Args> | |
703 // pair<iterator, bool> emplace(Args&&... args); | |
704 | |
705 TEST(FlatSet, Emplace) { | |
706 { | |
707 using Set = base::flat_set<Emplaceable>; | |
708 | |
709 Set cont; | |
710 std::pair<Set::iterator, bool> result = cont.emplace(); | |
711 EXPECT_TRUE(result.second); | |
712 EXPECT_EQ(cont.begin(), result.first); | |
713 EXPECT_EQ(static_cast<Set::size_type>(1), cont.size()); | |
714 EXPECT_EQ(Emplaceable(), *cont.begin()); | |
715 | |
716 result = cont.emplace(2, 3.5); | |
717 EXPECT_TRUE(result.second); | |
718 EXPECT_EQ(std::next(cont.begin()), result.first); | |
719 EXPECT_EQ(static_cast<Set::size_type>(2), cont.size()); | |
720 EXPECT_EQ(Emplaceable(2, 3.5), *result.first); | |
721 | |
722 result = cont.emplace(2, 3.5); | |
723 EXPECT_FALSE(result.second); | |
724 EXPECT_EQ(std::next(cont.begin()), result.first); | |
725 EXPECT_EQ(static_cast<Set::size_type>(2), cont.size()); | |
726 EXPECT_EQ(Emplaceable(2, 3.5), *result.first); | |
727 } | |
728 { | |
729 using Set = base::flat_set<int>; | |
730 | |
731 Set cont; | |
732 std::pair<Set::iterator, bool> result = cont.emplace(2); | |
733 EXPECT_TRUE(result.second); | |
734 EXPECT_EQ(cont.begin(), result.first); | |
735 EXPECT_EQ(static_cast<Set::size_type>(1), cont.size()); | |
736 EXPECT_EQ(2, *result.first); | |
737 } | |
738 } | |
739 | |
740 // template <class... Args> | |
741 // iterator emplace_hint(const_iterator position, Args&&... args); | |
742 | |
743 TEST(FlatSet, EmplaceHint) { | |
744 { | |
745 using Set = base::flat_set<Emplaceable>; | |
746 | |
747 Set cont; | |
748 Set::iterator result = cont.emplace_hint(cont.cend()); | |
749 EXPECT_EQ(cont.begin(), result); | |
750 EXPECT_EQ(static_cast<Set::size_type>(1), cont.size()); | |
751 EXPECT_EQ(Emplaceable(), *cont.begin()); | |
752 | |
753 result = cont.emplace_hint(cont.cend(), 2, 3.5); | |
754 EXPECT_EQ(std::next(cont.begin()), result); | |
755 EXPECT_EQ(static_cast<Set::size_type>(2), cont.size()); | |
756 EXPECT_EQ(Emplaceable(2, 3.5), *result); | |
757 | |
758 result = cont.emplace_hint(cont.cbegin(), 2, 3.5); | |
759 EXPECT_EQ(std::next(cont.begin()), result); | |
760 EXPECT_EQ(static_cast<Set::size_type>(2), cont.size()); | |
761 EXPECT_EQ(Emplaceable(2, 3.5), *result); | |
762 } | |
763 { | |
764 using Set = base::flat_set<int>; | |
765 | |
766 Set cont; | |
767 Set::iterator result = cont.emplace_hint(cont.cend(), 2); | |
768 EXPECT_EQ(cont.begin(), result); | |
769 EXPECT_EQ(static_cast<Set::size_type>(1), cont.size()); | |
770 EXPECT_EQ(2, *result); | |
771 } | |
772 } | |
773 | |
774 // ---------------------------------------------------------------------------- | |
775 // Erase operations. | |
776 | |
777 // iterator erase(const_iterator position); | |
778 | |
779 TEST(FlatSet, EraseCIter) { | |
780 using Set = base::flat_set<int>; | |
781 | |
782 Set cont{1, 2, 3, 4, 5, 6, 7, 8}; | |
783 | |
784 Set::iterator it = cont.erase(std::next(cont.cbegin(), 3)); | |
785 EXPECT_EQ(std::next(cont.begin(), 3), it); | |
786 ExpectRange(cont, {1, 2, 3, 5, 6, 7, 8}); | |
787 | |
788 it = cont.erase(std::next(cont.cbegin(), 0)); | |
789 EXPECT_EQ(cont.begin(), it); | |
790 ExpectRange(cont, {2, 3, 5, 6, 7, 8}); | |
791 | |
792 it = cont.erase(std::next(cont.cbegin(), 5)); | |
793 EXPECT_EQ(cont.end(), it); | |
794 ExpectRange(cont, {2, 3, 5, 6, 7}); | |
795 | |
796 it = cont.erase(std::next(cont.cbegin(), 1)); | |
797 EXPECT_EQ(std::next(cont.begin()), it); | |
798 ExpectRange(cont, {2, 5, 6, 7}); | |
799 | |
800 it = cont.erase(std::next(cont.cbegin(), 2)); | |
801 EXPECT_EQ(std::next(cont.begin(), 2), it); | |
802 ExpectRange(cont, {2, 5, 7}); | |
803 | |
804 it = cont.erase(std::next(cont.cbegin(), 2)); | |
805 EXPECT_EQ(std::next(cont.begin(), 2), it); | |
806 ExpectRange(cont, {2, 5}); | |
807 | |
808 it = cont.erase(std::next(cont.cbegin(), 0)); | |
809 EXPECT_EQ(std::next(cont.begin(), 0), it); | |
810 ExpectRange(cont, {5}); | |
811 | |
812 it = cont.erase(cont.cbegin()); | |
813 EXPECT_EQ(cont.begin(), it); | |
814 EXPECT_EQ(cont.end(), it); | |
815 } | |
816 | |
817 // iterator erase(const_iterator first, const_iterator last); | |
818 | |
819 TEST(FlatSet, EraseCIterCIter) { | |
820 using Set = base::flat_set<int>; | |
821 | |
822 Set cont{1, 2, 3, 4, 5, 6, 7, 8}; | |
823 | |
824 Set::iterator it = | |
825 cont.erase(std::next(cont.cbegin(), 5), std::next(cont.cbegin(), 5)); | |
826 EXPECT_EQ(std::next(cont.begin(), 5), it); | |
827 ExpectRange(cont, {1, 2, 3, 4, 5, 6, 7, 8}); | |
828 | |
829 it = cont.erase(std::next(cont.cbegin(), 3), std::next(cont.cbegin(), 4)); | |
830 EXPECT_EQ(std::next(cont.begin(), 3), it); | |
831 ExpectRange(cont, {1, 2, 3, 5, 6, 7, 8}); | |
832 | |
833 it = cont.erase(std::next(cont.cbegin(), 2), std::next(cont.cbegin(), 5)); | |
834 EXPECT_EQ(std::next(cont.begin(), 2), it); | |
835 ExpectRange(cont, {1, 2, 7, 8}); | |
836 | |
837 it = cont.erase(std::next(cont.cbegin(), 0), std::next(cont.cbegin(), 2)); | |
838 EXPECT_EQ(std::next(cont.begin(), 0), it); | |
839 ExpectRange(cont, {7, 8}); | |
840 | |
841 it = cont.erase(cont.cbegin(), cont.cend()); | |
842 EXPECT_EQ(cont.begin(), it); | |
843 EXPECT_EQ(cont.end(), it); | |
844 } | |
845 | |
846 // size_type erase(const key_type& k); | |
847 | |
848 TEST(FlatSet, EraseKey) { | |
849 using Set = base::flat_set<int>; | |
850 | |
851 Set cont{1, 2, 3, 4, 5, 6, 7, 8}; | |
852 | |
853 EXPECT_EQ(static_cast<Set::size_type>(0), cont.erase(9)); | |
854 ExpectRange(cont, {1, 2, 3, 4, 5, 6, 7, 8}); | |
855 | |
856 EXPECT_EQ(static_cast<Set::size_type>(1), cont.erase(4)); | |
857 ExpectRange(cont, {1, 2, 3, 5, 6, 7, 8}); | |
858 | |
859 EXPECT_EQ(static_cast<Set::size_type>(1), cont.erase(1)); | |
860 ExpectRange(cont, {2, 3, 5, 6, 7, 8}); | |
861 | |
862 EXPECT_EQ(static_cast<Set::size_type>(1), cont.erase(8)); | |
863 ExpectRange(cont, {2, 3, 5, 6, 7}); | |
864 | |
865 EXPECT_EQ(static_cast<Set::size_type>(1), cont.erase(3)); | |
866 ExpectRange(cont, {2, 5, 6, 7}); | |
867 | |
868 EXPECT_EQ(static_cast<Set::size_type>(1), cont.erase(6)); | |
869 ExpectRange(cont, {2, 5, 7}); | |
870 | |
871 EXPECT_EQ(static_cast<Set::size_type>(1), cont.erase(7)); | |
872 ExpectRange(cont, {2, 5}); | |
873 | |
874 EXPECT_EQ(static_cast<Set::size_type>(1), cont.erase(2)); | |
875 ExpectRange(cont, {5}); | |
876 | |
877 EXPECT_EQ(static_cast<Set::size_type>(1), cont.erase(5)); | |
878 ExpectRange(cont, {}); | |
879 } | |
880 | |
881 // ---------------------------------------------------------------------------- | |
882 // Comparators. | |
883 | |
884 // key_compare key_comp() const | |
885 | |
886 TEST(FlatSet, KeyComp) { | |
887 using Set = base::flat_set<int, std::greater<int>>; | |
888 | |
889 Set cont{1, 2, 3, 4, 5}; | |
890 | |
891 EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.key_comp())); | |
892 cont.insert({6, 7, 8, 9, 10}); | |
893 EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.key_comp())); | |
894 } | |
895 | |
896 // value_compare value_comp() const | |
897 | |
898 TEST(FlatSet, ValueComp) { | |
899 using Set = base::flat_set<int, std::greater<int>>; | |
900 | |
901 Set cont{1, 2, 3, 4, 5}; | |
902 | |
903 EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.value_comp())); | |
904 cont.insert({6, 7, 8, 9, 10}); | |
905 EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.value_comp())); | |
906 } | |
907 | |
908 // ---------------------------------------------------------------------------- | |
909 // Binary search operations. | |
910 | |
911 // size_type count(const key_type& k) const; | |
912 | |
913 TEST(FlatSet, Count) { | |
914 { | |
915 using Set = base::flat_set<int>; | |
916 | |
917 const Set cont{5, 6, 7, 8, 9, 10, 11, 12}; | |
918 | |
919 EXPECT_EQ(static_cast<Set::size_type>(1), cont.count(5)); | |
920 EXPECT_EQ(static_cast<Set::size_type>(1), cont.count(6)); | |
921 EXPECT_EQ(static_cast<Set::size_type>(1), cont.count(7)); | |
922 EXPECT_EQ(static_cast<Set::size_type>(1), cont.count(8)); | |
923 EXPECT_EQ(static_cast<Set::size_type>(1), cont.count(9)); | |
924 EXPECT_EQ(static_cast<Set::size_type>(1), cont.count(10)); | |
925 EXPECT_EQ(static_cast<Set::size_type>(1), cont.count(11)); | |
926 EXPECT_EQ(static_cast<Set::size_type>(1), cont.count(12)); | |
927 EXPECT_EQ(static_cast<Set::size_type>(0), cont.count(4)); | |
928 } | |
929 { | |
930 using Set = base::flat_set<int, std::less<int>>; | |
931 | |
932 const Set cont{5, 6, 7, 8, 9, 10, 11, 12}; | |
933 | |
934 EXPECT_EQ(static_cast<Set::size_type>(1), cont.count(5)); | |
935 EXPECT_EQ(static_cast<Set::size_type>(1), cont.count(6)); | |
936 EXPECT_EQ(static_cast<Set::size_type>(1), cont.count(7)); | |
937 EXPECT_EQ(static_cast<Set::size_type>(1), cont.count(8)); | |
938 EXPECT_EQ(static_cast<Set::size_type>(1), cont.count(9)); | |
939 EXPECT_EQ(static_cast<Set::size_type>(1), cont.count(10)); | |
940 EXPECT_EQ(static_cast<Set::size_type>(1), cont.count(11)); | |
941 EXPECT_EQ(static_cast<Set::size_type>(1), cont.count(12)); | |
942 EXPECT_EQ(static_cast<Set::size_type>(0), cont.count(4)); | |
943 } | |
944 } | |
945 | |
946 // iterator find(const key_type& k); | |
947 // const_iterator find(const key_type& k) const; | |
948 | |
949 TEST(FlatSet, Find) { | |
950 { | |
951 using Set = base::flat_set<int>; | |
952 { | |
953 Set cont{5, 6, 7, 8, 9, 10, 11, 12}; | |
954 | |
955 EXPECT_EQ(cont.begin(), cont.find(5)); | |
956 EXPECT_EQ(std::next(cont.begin()), cont.find(6)); | |
957 EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7)); | |
958 EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8)); | |
959 EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9)); | |
960 EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10)); | |
961 EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11)); | |
962 EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12)); | |
963 EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4)); | |
964 } | |
965 { | |
966 const Set cont{5, 6, 7, 8, 9, 10, 11, 12}; | |
967 | |
968 EXPECT_EQ(cont.begin(), cont.find(5)); | |
969 EXPECT_EQ(std::next(cont.begin()), cont.find(6)); | |
970 EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7)); | |
971 EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8)); | |
972 EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9)); | |
973 EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10)); | |
974 EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11)); | |
975 EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12)); | |
976 EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4)); | |
977 } | |
978 } | |
979 { | |
980 using Set = base::flat_set<int, std::less<int>>; | |
981 | |
982 Set cont{5, 6, 7, 8, 9, 10, 11, 12}; | |
983 | |
984 EXPECT_EQ(cont.begin(), cont.find(5)); | |
985 EXPECT_EQ(std::next(cont.begin()), cont.find(6)); | |
986 EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7)); | |
987 EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8)); | |
988 EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9)); | |
989 EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10)); | |
990 EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11)); | |
991 EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12)); | |
992 EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4)); | |
993 } | |
994 } | |
995 | |
996 // pair<iterator,iterator> equal_range(const key_type& k); | |
997 // pair<const_iterator,const_iterator> equal_range(const key_type& k) const; | |
998 | |
999 TEST(FlatSet, EqualRange) { | |
1000 { | |
1001 using Set = base::flat_set<int>; | |
1002 { | |
1003 Set cont{5, 7, 9, 11, 13, 15, 17, 19}; | |
1004 | |
1005 std::pair<Set::iterator, Set::iterator> result = cont.equal_range(5); | |
1006 EXPECT_EQ(std::next(cont.begin(), 0), result.first); | |
1007 EXPECT_EQ(std::next(cont.begin(), 1), result.second); | |
1008 result = cont.equal_range(7); | |
1009 EXPECT_EQ(std::next(cont.begin(), 1), result.first); | |
1010 EXPECT_EQ(std::next(cont.begin(), 2), result.second); | |
1011 result = cont.equal_range(9); | |
1012 EXPECT_EQ(std::next(cont.begin(), 2), result.first); | |
1013 EXPECT_EQ(std::next(cont.begin(), 3), result.second); | |
1014 result = cont.equal_range(11); | |
1015 EXPECT_EQ(std::next(cont.begin(), 3), result.first); | |
1016 EXPECT_EQ(std::next(cont.begin(), 4), result.second); | |
1017 result = cont.equal_range(13); | |
1018 EXPECT_EQ(std::next(cont.begin(), 4), result.first); | |
1019 EXPECT_EQ(std::next(cont.begin(), 5), result.second); | |
1020 result = cont.equal_range(15); | |
1021 EXPECT_EQ(std::next(cont.begin(), 5), result.first); | |
1022 EXPECT_EQ(std::next(cont.begin(), 6), result.second); | |
1023 result = cont.equal_range(17); | |
1024 EXPECT_EQ(std::next(cont.begin(), 6), result.first); | |
1025 EXPECT_EQ(std::next(cont.begin(), 7), result.second); | |
1026 result = cont.equal_range(19); | |
1027 EXPECT_EQ(std::next(cont.begin(), 7), result.first); | |
1028 EXPECT_EQ(std::next(cont.begin(), 8), result.second); | |
1029 result = cont.equal_range(4); | |
1030 EXPECT_EQ(std::next(cont.begin(), 0), result.first); | |
1031 EXPECT_EQ(std::next(cont.begin(), 0), result.second); | |
1032 result = cont.equal_range(6); | |
1033 EXPECT_EQ(std::next(cont.begin(), 1), result.first); | |
1034 EXPECT_EQ(std::next(cont.begin(), 1), result.second); | |
1035 result = cont.equal_range(8); | |
1036 EXPECT_EQ(std::next(cont.begin(), 2), result.first); | |
1037 EXPECT_EQ(std::next(cont.begin(), 2), result.second); | |
1038 result = cont.equal_range(10); | |
1039 EXPECT_EQ(std::next(cont.begin(), 3), result.first); | |
1040 EXPECT_EQ(std::next(cont.begin(), 3), result.second); | |
1041 result = cont.equal_range(12); | |
1042 EXPECT_EQ(std::next(cont.begin(), 4), result.first); | |
1043 EXPECT_EQ(std::next(cont.begin(), 4), result.second); | |
1044 result = cont.equal_range(14); | |
1045 EXPECT_EQ(std::next(cont.begin(), 5), result.first); | |
1046 EXPECT_EQ(std::next(cont.begin(), 5), result.second); | |
1047 result = cont.equal_range(16); | |
1048 EXPECT_EQ(std::next(cont.begin(), 6), result.first); | |
1049 EXPECT_EQ(std::next(cont.begin(), 6), result.second); | |
1050 result = cont.equal_range(18); | |
1051 EXPECT_EQ(std::next(cont.begin(), 7), result.first); | |
1052 EXPECT_EQ(std::next(cont.begin(), 7), result.second); | |
1053 result = cont.equal_range(20); | |
1054 EXPECT_EQ(std::next(cont.begin(), 8), result.first); | |
1055 EXPECT_EQ(std::next(cont.begin(), 8), result.second); | |
1056 } | |
1057 { | |
1058 const Set cont{5, 7, 9, 11, 13, 15, 17, 19}; | |
1059 | |
1060 std::pair<Set::const_iterator, Set::const_iterator> result = | |
1061 cont.equal_range(5); | |
1062 EXPECT_EQ(std::next(cont.begin(), 0), result.first); | |
1063 EXPECT_EQ(std::next(cont.begin(), 1), result.second); | |
1064 result = cont.equal_range(7); | |
1065 EXPECT_EQ(std::next(cont.begin(), 1), result.first); | |
1066 EXPECT_EQ(std::next(cont.begin(), 2), result.second); | |
1067 result = cont.equal_range(9); | |
1068 EXPECT_EQ(std::next(cont.begin(), 2), result.first); | |
1069 EXPECT_EQ(std::next(cont.begin(), 3), result.second); | |
1070 result = cont.equal_range(11); | |
1071 EXPECT_EQ(std::next(cont.begin(), 3), result.first); | |
1072 EXPECT_EQ(std::next(cont.begin(), 4), result.second); | |
1073 result = cont.equal_range(13); | |
1074 EXPECT_EQ(std::next(cont.begin(), 4), result.first); | |
1075 EXPECT_EQ(std::next(cont.begin(), 5), result.second); | |
1076 result = cont.equal_range(15); | |
1077 EXPECT_EQ(std::next(cont.begin(), 5), result.first); | |
1078 EXPECT_EQ(std::next(cont.begin(), 6), result.second); | |
1079 result = cont.equal_range(17); | |
1080 EXPECT_EQ(std::next(cont.begin(), 6), result.first); | |
1081 EXPECT_EQ(std::next(cont.begin(), 7), result.second); | |
1082 result = cont.equal_range(19); | |
1083 EXPECT_EQ(std::next(cont.begin(), 7), result.first); | |
1084 EXPECT_EQ(std::next(cont.begin(), 8), result.second); | |
1085 result = cont.equal_range(4); | |
1086 EXPECT_EQ(std::next(cont.begin(), 0), result.first); | |
1087 EXPECT_EQ(std::next(cont.begin(), 0), result.second); | |
1088 result = cont.equal_range(6); | |
1089 EXPECT_EQ(std::next(cont.begin(), 1), result.first); | |
1090 EXPECT_EQ(std::next(cont.begin(), 1), result.second); | |
1091 result = cont.equal_range(8); | |
1092 EXPECT_EQ(std::next(cont.begin(), 2), result.first); | |
1093 EXPECT_EQ(std::next(cont.begin(), 2), result.second); | |
1094 result = cont.equal_range(10); | |
1095 EXPECT_EQ(std::next(cont.begin(), 3), result.first); | |
1096 EXPECT_EQ(std::next(cont.begin(), 3), result.second); | |
1097 result = cont.equal_range(12); | |
1098 EXPECT_EQ(std::next(cont.begin(), 4), result.first); | |
1099 EXPECT_EQ(std::next(cont.begin(), 4), result.second); | |
1100 result = cont.equal_range(14); | |
1101 EXPECT_EQ(std::next(cont.begin(), 5), result.first); | |
1102 EXPECT_EQ(std::next(cont.begin(), 5), result.second); | |
1103 result = cont.equal_range(16); | |
1104 EXPECT_EQ(std::next(cont.begin(), 6), result.first); | |
1105 EXPECT_EQ(std::next(cont.begin(), 6), result.second); | |
1106 result = cont.equal_range(18); | |
1107 EXPECT_EQ(std::next(cont.begin(), 7), result.first); | |
1108 EXPECT_EQ(std::next(cont.begin(), 7), result.second); | |
1109 result = cont.equal_range(20); | |
1110 EXPECT_EQ(std::next(cont.begin(), 8), result.first); | |
1111 EXPECT_EQ(std::next(cont.begin(), 8), result.second); | |
1112 } | |
1113 } | |
1114 | |
1115 { | |
1116 using Set = base::flat_set<int, std::less<int>>; | |
1117 | |
1118 Set cont{5, 7, 9, 11, 13, 15, 17, 19}; | |
1119 | |
1120 std::pair<Set::iterator, Set::iterator> result = cont.equal_range(5); | |
1121 EXPECT_EQ(std::next(cont.begin(), 0), result.first); | |
1122 EXPECT_EQ(std::next(cont.begin(), 1), result.second); | |
1123 result = cont.equal_range(7); | |
1124 EXPECT_EQ(std::next(cont.begin(), 1), result.first); | |
1125 EXPECT_EQ(std::next(cont.begin(), 2), result.second); | |
1126 result = cont.equal_range(9); | |
1127 EXPECT_EQ(std::next(cont.begin(), 2), result.first); | |
1128 EXPECT_EQ(std::next(cont.begin(), 3), result.second); | |
1129 result = cont.equal_range(11); | |
1130 EXPECT_EQ(std::next(cont.begin(), 3), result.first); | |
1131 EXPECT_EQ(std::next(cont.begin(), 4), result.second); | |
1132 result = cont.equal_range(13); | |
1133 EXPECT_EQ(std::next(cont.begin(), 4), result.first); | |
1134 EXPECT_EQ(std::next(cont.begin(), 5), result.second); | |
1135 result = cont.equal_range(15); | |
1136 EXPECT_EQ(std::next(cont.begin(), 5), result.first); | |
1137 EXPECT_EQ(std::next(cont.begin(), 6), result.second); | |
1138 result = cont.equal_range(17); | |
1139 EXPECT_EQ(std::next(cont.begin(), 6), result.first); | |
1140 EXPECT_EQ(std::next(cont.begin(), 7), result.second); | |
1141 result = cont.equal_range(19); | |
1142 EXPECT_EQ(std::next(cont.begin(), 7), result.first); | |
1143 EXPECT_EQ(std::next(cont.begin(), 8), result.second); | |
1144 result = cont.equal_range(4); | |
1145 EXPECT_EQ(std::next(cont.begin(), 0), result.first); | |
1146 EXPECT_EQ(std::next(cont.begin(), 0), result.second); | |
1147 result = cont.equal_range(6); | |
1148 EXPECT_EQ(std::next(cont.begin(), 1), result.first); | |
1149 EXPECT_EQ(std::next(cont.begin(), 1), result.second); | |
1150 result = cont.equal_range(8); | |
1151 EXPECT_EQ(std::next(cont.begin(), 2), result.first); | |
1152 EXPECT_EQ(std::next(cont.begin(), 2), result.second); | |
1153 result = cont.equal_range(10); | |
1154 EXPECT_EQ(std::next(cont.begin(), 3), result.first); | |
1155 EXPECT_EQ(std::next(cont.begin(), 3), result.second); | |
1156 result = cont.equal_range(12); | |
1157 EXPECT_EQ(std::next(cont.begin(), 4), result.first); | |
1158 EXPECT_EQ(std::next(cont.begin(), 4), result.second); | |
1159 result = cont.equal_range(14); | |
1160 EXPECT_EQ(std::next(cont.begin(), 5), result.first); | |
1161 EXPECT_EQ(std::next(cont.begin(), 5), result.second); | |
1162 result = cont.equal_range(16); | |
1163 EXPECT_EQ(std::next(cont.begin(), 6), result.first); | |
1164 EXPECT_EQ(std::next(cont.begin(), 6), result.second); | |
1165 result = cont.equal_range(18); | |
1166 EXPECT_EQ(std::next(cont.begin(), 7), result.first); | |
1167 EXPECT_EQ(std::next(cont.begin(), 7), result.second); | |
1168 result = cont.equal_range(20); | |
1169 EXPECT_EQ(std::next(cont.begin(), 8), result.first); | |
1170 EXPECT_EQ(std::next(cont.begin(), 8), result.second); | |
1171 } | |
1172 } | |
1173 | |
1174 // iterator lower_bound(const key_type& k); | |
1175 // const_iterator lower_bound(const key_type& k) const; | |
1176 | |
1177 TEST(FlatSet, LowerBound) { | |
1178 { | |
1179 using Set = base::flat_set<int>; | |
1180 { | |
1181 Set cont{5, 7, 9, 11, 13, 15, 17, 19}; | |
1182 | |
1183 EXPECT_EQ(cont.begin(), cont.lower_bound(5)); | |
1184 EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7)); | |
1185 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(9)); | |
1186 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(11)); | |
1187 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(13)); | |
1188 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(15)); | |
1189 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(17)); | |
1190 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(19)); | |
1191 EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4)); | |
1192 EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6)); | |
1193 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8)); | |
1194 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10)); | |
1195 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12)); | |
1196 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14)); | |
1197 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16)); | |
1198 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18)); | |
1199 EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20)); | |
1200 } | |
1201 { | |
1202 const Set cont{5, 7, 9, 11, 13, 15, 17, 19}; | |
1203 | |
1204 EXPECT_EQ(cont.begin(), cont.lower_bound(5)); | |
1205 EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7)); | |
1206 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(9)); | |
1207 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(11)); | |
1208 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(13)); | |
1209 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(15)); | |
1210 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(17)); | |
1211 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(19)); | |
1212 EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4)); | |
1213 EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6)); | |
1214 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8)); | |
1215 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10)); | |
1216 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12)); | |
1217 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14)); | |
1218 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16)); | |
1219 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18)); | |
1220 EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20)); | |
1221 } | |
1222 } | |
1223 { | |
1224 using Set = base::flat_set<int, std::less<int>>; | |
1225 | |
1226 Set cont{5, 7, 9, 11, 13, 15, 17, 19}; | |
1227 | |
1228 EXPECT_EQ(cont.begin(), cont.lower_bound(5)); | |
1229 EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7)); | |
1230 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(9)); | |
1231 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(11)); | |
1232 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(13)); | |
1233 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(15)); | |
1234 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(17)); | |
1235 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(19)); | |
1236 EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4)); | |
1237 EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6)); | |
1238 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8)); | |
1239 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10)); | |
1240 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12)); | |
1241 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14)); | |
1242 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16)); | |
1243 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18)); | |
1244 EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20)); | |
1245 } | |
1246 } | |
1247 | |
1248 // iterator upper_bound(const key_type& k); | |
1249 // const_iterator upper_bound(const key_type& k) const; | |
1250 | |
1251 TEST(FlatSet, UpperBound) { | |
1252 { | |
1253 using Set = base::flat_set<int>; | |
1254 { | |
1255 Set cont{5, 7, 9, 11, 13, 15, 17, 19}; | |
1256 | |
1257 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5)); | |
1258 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7)); | |
1259 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(9)); | |
1260 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(11)); | |
1261 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(13)); | |
1262 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(15)); | |
1263 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(17)); | |
1264 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(19)); | |
1265 EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4)); | |
1266 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6)); | |
1267 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8)); | |
1268 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10)); | |
1269 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12)); | |
1270 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14)); | |
1271 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16)); | |
1272 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18)); | |
1273 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20)); | |
1274 } | |
1275 { | |
1276 const Set cont{5, 7, 9, 11, 13, 15, 17, 19}; | |
1277 | |
1278 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5)); | |
1279 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7)); | |
1280 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(9)); | |
1281 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(11)); | |
1282 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(13)); | |
1283 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(15)); | |
1284 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(17)); | |
1285 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(19)); | |
1286 EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4)); | |
1287 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6)); | |
1288 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8)); | |
1289 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10)); | |
1290 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12)); | |
1291 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14)); | |
1292 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16)); | |
1293 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18)); | |
1294 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20)); | |
1295 } | |
1296 } | |
1297 { | |
1298 using Set = base::flat_set<int, std::less<int>>; | |
1299 | |
1300 Set cont{5, 7, 9, 11, 13, 15, 17, 19}; | |
1301 | |
1302 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5)); | |
1303 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7)); | |
1304 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(9)); | |
1305 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(11)); | |
1306 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(13)); | |
1307 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(15)); | |
1308 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(17)); | |
1309 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(19)); | |
1310 EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4)); | |
1311 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6)); | |
1312 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8)); | |
1313 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10)); | |
1314 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12)); | |
1315 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14)); | |
1316 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16)); | |
1317 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18)); | |
1318 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20)); | |
1319 } | |
1320 } | |
1321 | |
1322 // ---------------------------------------------------------------------------- | |
1323 // General operations. | |
1324 | |
1325 // void swap(flat_set& x) | |
1326 // void swap(flat_set& x, flat_set& y) | |
1327 | |
1328 TEST(FlatSetOurs, Swap) { | |
1329 using Set = base::flat_set<int>; | |
1330 Set x{1, 2, 3}; | |
1331 Set y{4}; | |
1332 swap(x, y); | |
1333 ExpectRange(x, {4}); | |
1334 ExpectRange(y, {1, 2, 3}); | |
1335 | |
1336 y.swap(x); | |
1337 ExpectRange(x, {1, 2, 3}); | |
1338 ExpectRange(y, {4}); | |
1339 } | |
1340 | |
1341 // bool operator==(const flat_set& x, const flat_set& y) | |
1342 // bool operator!=(const flat_set& x, const flat_set& y) | |
1343 // bool operator<(const flat_set& x, const flat_set& y) | |
1344 // bool operator>(const flat_set& x, const flat_set& y) | |
1345 // bool operator<=(const flat_set& x, const flat_set& y) | |
1346 // bool operator>=(const flat_set& x, const flat_set& y) | |
1347 | |
1348 TEST(FlatSet, Comparison) { | |
1349 // Provided comparator does not participate in comparison. | |
1350 using Cmp = std::greater<int>; | |
1351 using Set = base::flat_set<int, Cmp>; | |
1352 | |
1353 Set biggest{3}; | |
1354 Set smallest{1}; | |
1355 Set middle{1, 2}; | |
1356 | |
1357 EXPECT_EQ(biggest, biggest); | |
1358 EXPECT_NE(biggest, smallest); | |
1359 EXPECT_LT(smallest, middle); | |
1360 EXPECT_LE(smallest, middle); | |
1361 EXPECT_LE(middle, middle); | |
1362 EXPECT_GT(biggest, middle); | |
1363 EXPECT_GE(biggest, middle); | |
1364 EXPECT_GE(biggest, biggest); | |
1365 } | |
OLD | NEW |