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 modified and extended tests from libcpp for std::set. | |
Peter Kasting
2016/12/16 08:09:08
You say "extended" here, but below you document on
dyaroshev
2016/12/18 22:27:23
Changed the description a bit. I think removed tes
| |
8 // They can be found here: | |
9 // https://github.com/llvm-mirror/libcxx/tree/master/test/std/containers/associa tive/set | |
10 // | |
11 // Removed 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 | |
Peter Kasting
2016/12/16 08:09:08
Nit: No comma
dyaroshev
2016/12/18 22:27:24
Done.
| |
36 // patterns than std::sets and we do not consider them to be a part of the | |
37 // interface. | |
38 | |
39 #include "testing/gtest/include/gtest/gtest.h" | |
40 | |
41 namespace { | |
42 | |
43 class MoveOnly { | |
44 MoveOnly(const MoveOnly&); | |
Peter Kasting
2016/12/16 08:09:07
Nit: As much as possible, declare private section
dyaroshev
2016/12/18 22:27:24
Done.
| |
45 MoveOnly& operator=(const MoveOnly&); | |
Peter Kasting
2016/12/16 08:09:07
Nit: Use DISALLOW_COPY_AND_ASSIGN to remove these.
dyaroshev
2016/12/18 22:27:24
Done.
| |
46 | |
47 int data_; | |
48 | |
49 public: | |
50 MoveOnly(int data = 1) : data_(data) {} | |
51 MoveOnly(MoveOnly&& x) : data_(x.data_) { x.data_ = 0; } | |
Peter Kasting
2016/12/16 08:09:07
Nit: |rhs| may be a more idiomatic name than |x|.
dyaroshev
2016/12/18 22:27:23
Replied in other comment
| |
52 MoveOnly& operator=(MoveOnly&& x) { | |
53 data_ = x.data_; | |
54 x.data_ = 0; | |
Peter Kasting
2016/12/16 08:09:08
Why set x.data_ at all? So behavior failures will
dyaroshev
2016/12/18 22:27:23
We check that we don't leave moved out elements.
| |
55 return *this; | |
56 } | |
57 | |
58 int get() const { return data_; } | |
Peter Kasting
2016/12/16 08:09:07
Nit: Accessors should be named like the underlying
dyaroshev
2016/12/18 22:27:23
Done.
| |
59 | |
60 bool operator==(const MoveOnly& x) const { return data_ == x.data_; } | |
61 bool operator<(const MoveOnly& x) const { return data_ < x.data_; } | |
62 }; | |
63 | |
64 template <class It, class ItTraits = It> | |
65 class input_iterator { | |
66 typedef std::iterator_traits<ItTraits> Traits; | |
67 It it_; | |
68 | |
69 template <class U, class T> | |
70 friend class input_iterator; | |
71 | |
72 public: | |
73 typedef std::input_iterator_tag iterator_category; | |
74 typedef typename Traits::value_type value_type; | |
75 typedef typename Traits::difference_type difference_type; | |
76 typedef It pointer; | |
77 typedef typename Traits::reference reference; | |
78 | |
79 It base() const { return it_; } | |
80 | |
81 input_iterator() : it_() {} | |
82 explicit input_iterator(It it) : it_(it) {} | |
83 template <class U, class T> | |
84 input_iterator(const input_iterator<U, T>& u) : it_(u.it_) {} | |
85 | |
86 reference operator*() const { return *it_; } | |
87 pointer operator->() const { return it_; } | |
88 | |
89 input_iterator& operator++() { | |
90 ++it_; | |
91 return *this; | |
92 } | |
93 input_iterator operator++(int) { | |
94 input_iterator tmp(*this); | |
95 ++(*this); | |
96 return tmp; | |
97 } | |
98 | |
99 friend bool operator==(const input_iterator& x, const input_iterator& y) { | |
100 return x.it_ == y.it_; | |
101 } | |
102 friend bool operator!=(const input_iterator& x, const input_iterator& y) { | |
103 return !(x == y); | |
104 } | |
105 | |
106 template <class T> | |
107 void operator,(T const&) = delete; | |
Peter Kasting
2016/12/16 08:09:08
Why?
dyaroshev
2016/12/18 22:27:23
Copied from libc++. I think this is to avoid some
| |
108 }; | |
109 | |
110 template <class T, class TV, class U, class UV> | |
111 inline bool operator==(const input_iterator<T, TV>& x, | |
112 const input_iterator<U, UV>& y) { | |
113 return x.base() == y.base(); | |
114 } | |
115 | |
116 template <class T, class TV, class U, class UV> | |
117 inline bool operator!=(const input_iterator<T, TV>& x, | |
118 const input_iterator<U, UV>& y) { | |
119 return !(x == y); | |
120 } | |
121 | |
122 class Emplaceable { | |
123 Emplaceable(const Emplaceable&); | |
124 Emplaceable& operator=(const Emplaceable&); | |
125 | |
126 int int_; | |
127 double double_; | |
128 | |
129 public: | |
130 Emplaceable() : int_(0), double_(0) {} | |
131 Emplaceable(int i, double d) : int_(i), double_(d) {} | |
132 Emplaceable(Emplaceable&& x) : int_(x.int_), double_(x.double_) { | |
133 x.int_ = 0; | |
134 x.double_ = 0; | |
135 } | |
136 Emplaceable& operator=(Emplaceable&& x) { | |
137 int_ = x.int_; | |
138 x.int_ = 0; | |
139 double_ = x.double_; | |
140 x.double_ = 0; | |
141 return *this; | |
142 } | |
143 | |
144 bool operator==(const Emplaceable& x) const { | |
145 return int_ == x.int_ && double_ == x.double_; | |
146 } | |
147 bool operator<(const Emplaceable& x) const { | |
148 return int_ < x.int_ || (int_ == x.int_ && double_ < x.double_); | |
149 } | |
150 | |
151 int get() const { return int_; } | |
152 }; | |
153 | |
154 class NonDefaultConstructibleCompare { | |
155 public: | |
156 NonDefaultConstructibleCompare(int) {} | |
157 | |
158 template <typename T> | |
159 bool operator()(const T& lhs, const T& rhs) { | |
160 return std::less<T>()(lhs, rhs); | |
161 } | |
162 }; | |
163 | |
164 } // namespace | |
165 | |
166 // ---------------------------------------------------------------------------- | |
167 // Class: | |
168 | |
169 // Check that base::flat_set and it's iterators can be instantiated with an | |
Peter Kasting
2016/12/16 08:09:07
Nit: its
dyaroshev
2016/12/18 22:27:24
Done.
| |
170 // incomplete type. | |
171 | |
172 TEST(FlatSet, IncompleteType) { | |
173 struct A { | |
174 typedef base::flat_set<A> Set; | |
175 int data; | |
176 Set m; | |
177 Set::iterator it; | |
178 Set::const_iterator cit; | |
179 }; | |
180 | |
181 // libcpp tests define operator< for A, but clang is complaining that it's | |
182 // unused | |
Peter Kasting
2016/12/16 08:09:08
Nit: Not a complete sentence, too vague to be usef
dyaroshev
2016/12/18 22:27:23
It's just strange to declare a set of type without
| |
183 | |
184 A a; | |
185 } | |
186 | |
187 // ---------------------------------------------------------------------------- | |
188 // Types: | |
189 | |
190 // class flat_set | |
Peter Kasting
2016/12/16 08:09:08
Nit: No need to "// class flat_set" above all thes
dyaroshev
2016/12/18 22:27:23
Done.
| |
191 | |
192 // // types: | |
193 // typedef Key key_type; | |
194 // typedef key_type value_type; | |
195 // typedef Compare key_compare; | |
196 // typedef key_compare value_compare; | |
197 // typedef Allocator allocator_type; | |
198 // typedef typename allocator_type::reference reference; | |
199 // typedef typename allocator_type::const_reference const_reference; | |
200 // typedef typename allocator_type::pointer pointer; | |
201 // typedef typename allocator_type::const_pointer const_pointer; | |
202 // typedef typename allocator_type::size_type size_type; | |
203 // typedef typename allocator_type::difference_type difference_type; | |
204 | |
205 TEST(FlatSet, Types) { | |
206 { | |
Peter Kasting
2016/12/16 08:09:07
Nit: Avoid these {} blocks in tests except where y
dyaroshev
2016/12/18 22:27:24
Done.
| |
207 typedef base::flat_set<int> C; | |
Peter Kasting
2016/12/16 08:09:08
Nit: "using" type aliases seem slightly more reada
dyaroshev
2016/12/18 22:27:23
Done.
| |
208 static_assert((std::is_same<C::key_type, int>::value), ""); | |
209 static_assert((std::is_same<C::value_type, int>::value), ""); | |
210 static_assert((std::is_same<C::key_compare, std::less<int>>::value), ""); | |
211 static_assert((std::is_same<C::value_compare, std::less<int>>::value), ""); | |
212 static_assert((std::is_same<C::allocator_type, std::allocator<int>>::value), | |
213 ""); | |
214 static_assert((std::is_same<C::reference, int&>::value), ""); | |
dyaroshev
2016/12/15 16:10:59
Tests for reference/pointer etc are libc++ specifi
dyaroshev
2016/12/18 22:27:24
Done.
| |
215 static_assert((std::is_same<C::const_reference, const int&>::value), ""); | |
216 static_assert((std::is_same<C::pointer, int*>::value), ""); | |
217 static_assert((std::is_same<C::const_pointer, const int*>::value), ""); | |
218 static_assert((std::is_same<C::size_type, std::size_t>::value), ""); | |
Peter Kasting
2016/12/16 08:09:07
Nit: For better or worse, Chromium code does not q
dyaroshev
2016/12/18 22:27:24
Done.
| |
219 static_assert((std::is_same<C::difference_type, std::ptrdiff_t>::value), | |
220 ""); | |
221 } | |
222 } | |
223 | |
224 // ---------------------------------------------------------------------------- | |
225 // Lifetime. | |
226 | |
227 // class flat_set | |
228 | |
229 // flat_set() | |
230 // flat_set(const Compare& comp, const Allocator& alloc = Allocator()) | |
231 // flat_set(const Allocator& alloc) | |
232 | |
233 TEST(FlatSet, DefaultConstructor) { | |
234 { | |
235 typedef base::flat_set<int> M; | |
236 | |
237 M m; | |
238 EXPECT_EQ(m.size(), static_cast<M::size_type>(0)); | |
Peter Kasting
2016/12/16 08:09:07
Nit: Say 0U instead of casting to size_type. (The
dyaroshev
2016/12/18 22:27:24
Done.
| |
239 } | |
240 | |
241 { | |
242 typedef base::flat_set<int, NonDefaultConstructibleCompare> M; | |
243 | |
244 M m{NonDefaultConstructibleCompare(0)}; | |
245 EXPECT_EQ(m.size(), static_cast<M::size_type>(0)); | |
246 } | |
247 } | |
248 | |
249 // class flat_set | |
250 | |
251 // flat_set(InputIterator first, | |
252 // InputIterator last, | |
253 // const Compare& comp = Compare(), | |
254 // const Allocator& alloc = Allocator()) | |
255 // flat_set(InputIterator first, InputIterator last, const Allocator& alloc) | |
256 | |
257 TEST(FlatSet, RangeConstructor) { | |
258 { | |
259 typedef base::flat_set<int> M; | |
260 typedef int V; | |
261 | |
262 V ar[] = {1, 1, 1, 2, 2, 2, 3, 3, 3}; | |
263 | |
264 M m(input_iterator<const V*>(ar), | |
265 input_iterator<const V*>(ar + sizeof(ar) / sizeof(ar[0]))); | |
266 EXPECT_EQ(m.size(), static_cast<M::size_type>(3)); | |
267 EXPECT_EQ(*m.begin(), 1); | |
268 EXPECT_EQ(*next(m.begin()), 2); | |
Peter Kasting
2016/12/16 08:09:08
Nit: Shouldn't this be std::next()? (many places)
dyaroshev
2016/12/18 22:27:24
Worked because of ADL lookup. Copied from libc++ t
| |
269 EXPECT_EQ(*next(m.begin(), 2), 3); | |
270 } | |
271 { | |
272 typedef base::flat_set<int, NonDefaultConstructibleCompare> M; | |
273 typedef int V; | |
274 | |
275 V ar[] = {1, 1, 1, 2, 2, 2, 3, 3, 3}; | |
276 | |
277 M m(input_iterator<const V*>(ar), | |
278 input_iterator<const V*>(ar + sizeof(ar) / sizeof(ar[0])), | |
279 NonDefaultConstructibleCompare(0)); | |
280 EXPECT_EQ(m.size(), static_cast<M::size_type>(3)); | |
281 EXPECT_EQ(*m.begin(), 1); | |
282 EXPECT_EQ(*next(m.begin()), 2); | |
283 EXPECT_EQ(*next(m.begin(), 2), 3); | |
284 } | |
285 } | |
286 | |
287 // class flat_set | |
288 | |
289 // flat_set(const flat_set& x) | |
290 // flat_set(const flat_set& x, const Allocator& alloc) | |
291 | |
292 TEST(FlatSet, CopyConstructor) { | |
293 { | |
294 typedef base::flat_set<int> M; | |
295 typedef int V; | |
296 | |
297 V ar[] = {1, 2, 3, 4}; | |
298 | |
299 M m(ar, ar + sizeof(ar) / sizeof(ar[0])); | |
300 M m2(m); | |
301 | |
302 EXPECT_EQ(m2.count(1), static_cast<M::size_type>(1)); | |
303 EXPECT_EQ(m2.count(2), static_cast<M::size_type>(1)); | |
304 EXPECT_EQ(m2.count(3), static_cast<M::size_type>(1)); | |
305 EXPECT_EQ(m2.count(4), static_cast<M::size_type>(1)); | |
Peter Kasting
2016/12/16 08:09:08
Nit: Here and a lot of places below it seems like
dyaroshev
2016/12/18 22:27:23
Done.
| |
306 } | |
307 } | |
308 | |
309 // class flat_set | |
310 | |
311 // flat_set(flat_set&& x) | |
312 // flat_set(flat_set&& x, const Allocator& alloc) | |
313 | |
314 TEST(FlatSet, MoveConstructor) { | |
315 { | |
316 typedef base::flat_set<MoveOnly> M; | |
317 typedef int V; | |
318 | |
319 V ar[] = {1, 2, 3, 4}; | |
320 | |
321 M m(ar, ar + sizeof(ar) / sizeof(ar[0])); | |
322 M m2(std::move(m)); | |
323 | |
324 EXPECT_EQ(m2.count(1), static_cast<M::size_type>(1)); | |
325 EXPECT_EQ(m2.count(2), static_cast<M::size_type>(1)); | |
326 EXPECT_EQ(m2.count(3), static_cast<M::size_type>(1)); | |
327 EXPECT_EQ(m2.count(4), static_cast<M::size_type>(1)); | |
328 } | |
329 } | |
330 | |
331 // class flat_set | |
332 | |
333 // flat_set(std::initializer_list<value_type> il, | |
334 // const Compare& comp = Compare(), | |
335 // const Allocator& alloc = Allocator()) | |
336 // flat_set(std::initializer_list<value_type> il, const Allocator& a) | |
337 | |
338 TEST(FlatSet, InitializerListConstructor) { | |
339 { | |
340 typedef base::flat_set<int> M; | |
341 typedef M::value_type V; | |
Peter Kasting
2016/12/16 08:09:07
Nit: Just use int directly, and don't bother with
dyaroshev
2016/12/18 22:27:24
Done.
| |
342 | |
343 M m{1, 2, 3, 4, 5, 6, 10, 8}; | |
344 EXPECT_EQ(m.size(), static_cast<M::size_type>(8)); | |
345 EXPECT_EQ(distance(m.begin(), m.end()), | |
Peter Kasting
2016/12/16 08:09:08
Nit: Shouldn't this be std::distance? (3 places)
dyaroshev
2016/12/18 22:27:24
Done.
| |
346 static_cast<M::difference_type>(m.size())); | |
Peter Kasting
2016/12/16 08:09:07
Nit: Use ptrdiff_t directly (many places)
dyaroshev
2016/12/18 22:27:24
I don't think that the standard guaranties this. A
Peter Kasting
2016/12/18 22:47:43
The standard doesn't, but your static_assertions a
| |
347 M::const_iterator i = m.cbegin(); | |
348 EXPECT_EQ(*i, V(1)); | |
349 EXPECT_EQ(*++i, V(2)); | |
350 EXPECT_EQ(*++i, V(3)); | |
351 EXPECT_EQ(*++i, V(4)); | |
352 EXPECT_EQ(*++i, V(5)); | |
353 EXPECT_EQ(*++i, V(6)); | |
354 EXPECT_EQ(*++i, V(8)); | |
355 EXPECT_EQ(*++i, V(10)); | |
356 } | |
357 { | |
358 typedef base::flat_set<int, NonDefaultConstructibleCompare> M; | |
359 typedef M::value_type V; | |
360 | |
361 M m({1, 2, 3, 4, 5, 6, 10, 8}, NonDefaultConstructibleCompare(0)); | |
362 EXPECT_EQ(m.size(), static_cast<M::size_type>(8)); | |
363 EXPECT_EQ(distance(m.begin(), m.end()), | |
364 static_cast<M::difference_type>(m.size())); | |
365 M::const_iterator i = m.cbegin(); | |
366 EXPECT_EQ(*i, V(1)); | |
367 EXPECT_EQ(*++i, V(2)); | |
368 EXPECT_EQ(*++i, V(3)); | |
369 EXPECT_EQ(*++i, V(4)); | |
370 EXPECT_EQ(*++i, V(5)); | |
371 EXPECT_EQ(*++i, V(6)); | |
372 EXPECT_EQ(*++i, V(8)); | |
373 EXPECT_EQ(*++i, V(10)); | |
374 } | |
375 } | |
376 | |
377 // ---------------------------------------------------------------------------- | |
378 // Assignments. | |
379 | |
380 // class flat_set | |
381 | |
382 // flat_set& operator=(const flat_set& x) | |
383 | |
384 TEST(FlatSet, CopyAssignable) { | |
385 { | |
386 typedef base::flat_set<int> M; | |
387 typedef int V; | |
388 | |
389 V ar[] = {1, 2, 3, 4}; | |
390 | |
391 M m(ar, ar + sizeof(ar) / sizeof(ar[0])); | |
Peter Kasting
2016/12/16 08:09:08
Nit: use arraysize(). (Multiple places)
dyaroshev
2016/12/18 22:27:23
Changed to using initiailizer lists and begin/end
| |
392 M m2; | |
393 m2 = m; | |
394 | |
395 EXPECT_EQ(m2.count(1), static_cast<M::size_type>(1)); | |
396 EXPECT_EQ(m2.count(2), static_cast<M::size_type>(1)); | |
397 EXPECT_EQ(m2.count(3), static_cast<M::size_type>(1)); | |
398 EXPECT_EQ(m2.count(4), static_cast<M::size_type>(1)); | |
399 } | |
400 } | |
401 | |
402 // class flat_set | |
403 | |
404 // flat_set& operator=(flat_set&& x) | |
405 | |
406 TEST(FlatSet, MoveAssignable) { | |
407 { | |
408 typedef base::flat_set<MoveOnly> M; | |
409 typedef int V; | |
410 | |
411 V ar[] = {1, 2, 3, 4}; | |
412 | |
413 M m(ar, ar + sizeof(ar) / sizeof(ar[0])); | |
414 M m2; | |
415 m2 = std::move(m); | |
416 | |
417 EXPECT_EQ(m2.count(1), static_cast<M::size_type>(1)); | |
418 EXPECT_EQ(m2.count(2), static_cast<M::size_type>(1)); | |
419 EXPECT_EQ(m2.count(3), static_cast<M::size_type>(1)); | |
420 EXPECT_EQ(m2.count(4), static_cast<M::size_type>(1)); | |
421 } | |
422 } | |
423 | |
424 // class flat_set | |
425 | |
426 // flat_set& operator=(std::initializer_list<value_type> il) | |
427 | |
428 TEST(FlatSet, InitializerListAssignable) { | |
429 { | |
430 typedef base::flat_set<int> M; | |
431 typedef M::value_type V; | |
432 | |
433 M m{0}; | |
434 m = {1, 2, 3, 4, 5, 6, 10, 8}; | |
435 | |
436 EXPECT_EQ(m.count(0), static_cast<M::size_type>(0)); | |
437 EXPECT_EQ(m.size(), static_cast<M::size_type>(8)); | |
438 EXPECT_EQ(distance(m.begin(), m.end()), | |
439 static_cast<M::difference_type>(m.size())); | |
440 M::const_iterator i = m.cbegin(); | |
441 EXPECT_EQ(*i, V(1)); | |
442 EXPECT_EQ(*++i, V(2)); | |
443 EXPECT_EQ(*++i, V(3)); | |
444 EXPECT_EQ(*++i, V(4)); | |
445 EXPECT_EQ(*++i, V(5)); | |
446 EXPECT_EQ(*++i, V(6)); | |
447 EXPECT_EQ(*++i, V(8)); | |
448 EXPECT_EQ(*++i, V(10)); | |
449 } | |
450 } | |
451 | |
452 // -------------------------------------------------------------------------- | |
453 // Memory management. | |
454 | |
455 // class flat_set | |
456 | |
457 // void reserve(size_type size) | |
458 | |
459 TEST(FlatSet, Reserve) { | |
460 { | |
461 typedef base::flat_set<int> M; | |
462 M m{1, 2, 3}; | |
463 | |
464 m.reserve(5); | |
465 EXPECT_GE(m.capacity(), static_cast<M::size_type>(5)); | |
466 } | |
467 } | |
468 | |
469 // class flat_set | |
470 | |
471 // size_type capacity() const | |
472 | |
473 TEST(FlatSet, Capacity) { | |
474 { | |
475 typedef base::flat_set<int> M; | |
476 M m{1, 2, 3}; | |
477 EXPECT_GE(m.capacity(), m.size()); | |
478 } | |
479 } | |
480 | |
481 // class flat_set | |
482 | |
483 // void shrink_to_fit() | |
484 | |
485 TEST(FlatSet, ShrinkToFit) { | |
486 { | |
487 typedef base::flat_set<int> M; | |
488 M m{1, 2, 3}; | |
489 | |
490 M::size_type capacity_before = m.capacity(); | |
491 m.shrink_to_fit(); | |
492 EXPECT_GE(capacity_before, m.capacity()); | |
Peter Kasting
2016/12/16 08:09:08
Maybe a stronger test would be to reserve() more s
dyaroshev
2016/12/18 22:27:23
I've checked against the spec: shrink_to_fit can d
Peter Kasting
2016/12/18 22:47:43
Wow. That seems unfortunate.
I would add an expl
| |
493 } | |
494 } | |
495 | |
496 // ---------------------------------------------------------------------------- | |
497 // Size management. | |
498 | |
499 // class flat_set | |
500 | |
501 // void clear(); | |
502 | |
503 TEST(FlatSet, Clear) { | |
504 typedef base::flat_set<int> M; | |
505 typedef int V; | |
506 | |
507 V ar[] = {1, 2, 3, 4, 5, 6, 7, 8}; | |
508 | |
509 M m(ar, ar + sizeof(ar) / sizeof(ar[0])); | |
510 EXPECT_EQ(m.size(), static_cast<M::size_type>(8)); | |
511 m.clear(); | |
512 EXPECT_EQ(m.size(), static_cast<M::size_type>(0)); | |
513 } | |
514 | |
515 // class flat_set | |
516 | |
517 // size_type size() const; | |
518 | |
519 TEST(FlatSet, Size) { | |
520 { | |
521 typedef base::flat_set<int> M; | |
522 M m; | |
523 EXPECT_EQ(m.size(), static_cast<M::size_type>(0)); | |
524 m.insert(M::value_type(2)); | |
525 EXPECT_EQ(m.size(), static_cast<M::size_type>(1)); | |
526 m.insert(M::value_type(1)); | |
527 EXPECT_EQ(m.size(), static_cast<M::size_type>(2)); | |
528 m.insert(M::value_type(3)); | |
529 EXPECT_EQ(m.size(), static_cast<M::size_type>(3)); | |
530 m.erase(m.begin()); | |
531 EXPECT_EQ(m.size(), static_cast<M::size_type>(2)); | |
532 m.erase(m.begin()); | |
533 EXPECT_EQ(m.size(), static_cast<M::size_type>(1)); | |
534 m.erase(m.begin()); | |
535 EXPECT_EQ(m.size(), static_cast<M::size_type>(0)); | |
536 } | |
537 } | |
538 | |
539 // class flat_set | |
540 | |
541 // bool empty() const; | |
542 | |
543 TEST(FlatSet, Empty) { | |
544 typedef base::flat_set<int> M; | |
545 M m; | |
546 EXPECT_TRUE(m.empty()); | |
547 m.insert(M::value_type(1)); | |
548 EXPECT_FALSE(m.empty()); | |
549 m.clear(); | |
550 EXPECT_TRUE(m.empty()); | |
551 } | |
552 | |
553 // ---------------------------------------------------------------------------- | |
554 // Iterators. | |
555 | |
556 // class flat_set | |
557 | |
558 // iterator begin(); | |
559 // const_iterator begin() const; | |
560 // iterator end(); | |
561 // const_iterator end() const; | |
562 // | |
563 // reverse_iterator rbegin(); | |
564 // const_reverse_iterator rbegin() const; | |
565 // reverse_iterator rend(); | |
566 // const_reverse_iterator rend() const; | |
567 // | |
568 // const_iterator cbegin() const; | |
569 // const_iterator cend() const; | |
570 // const_reverse_iterator crbegin() const; | |
571 // const_reverse_iterator crend() const; | |
572 | |
573 TEST(FlatSet, Iterators) { | |
574 { | |
575 typedef int V; | |
576 | |
577 V ar[] = {1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, | |
578 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8}; | |
579 | |
580 base::flat_set<int> m(ar, ar + sizeof(ar) / sizeof(ar[0])); | |
581 EXPECT_EQ(std::distance(m.begin(), m.end()), | |
582 static_cast<base::flat_set<int>::difference_type>(m.size())); | |
583 EXPECT_EQ(std::distance(m.rbegin(), m.rend()), | |
584 static_cast<base::flat_set<int>::difference_type>(m.size())); | |
585 base::flat_set<int>::iterator i; | |
586 i = m.begin(); | |
587 base::flat_set<int>::const_iterator k = i; | |
588 EXPECT_EQ(i, k); | |
589 for (int j = 1; static_cast<std::size_t>(j) <= m.size(); ++j, ++i) | |
Peter Kasting
2016/12/16 08:09:08
Nit: What about:
for (int j = 1; i != m.end();
dyaroshev
2016/12/18 22:27:23
Done.
| |
590 EXPECT_EQ(*i, j); | |
591 } | |
592 { | |
593 typedef int V; | |
594 | |
595 V ar[] = {1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, | |
596 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8}; | |
597 | |
598 const base::flat_set<int> m(ar, ar + sizeof(ar) / sizeof(ar[0])); | |
599 EXPECT_EQ(std::distance(m.begin(), m.end()), | |
600 static_cast<base::flat_set<int>::difference_type>(m.size())); | |
601 EXPECT_EQ(std::distance(m.cbegin(), m.cend()), | |
602 static_cast<base::flat_set<int>::difference_type>(m.size())); | |
603 EXPECT_EQ(std::distance(m.rbegin(), m.rend()), | |
604 static_cast<base::flat_set<int>::difference_type>(m.size())); | |
605 EXPECT_EQ(std::distance(m.crbegin(), m.crend()), | |
606 static_cast<base::flat_set<int>::difference_type>(m.size())); | |
607 base::flat_set<int>::const_iterator i; | |
608 i = m.begin(); | |
609 for (int j = 1; static_cast<std::size_t>(j) <= m.size(); ++j, ++i) | |
610 EXPECT_EQ(*i, j); | |
611 } | |
612 } | |
613 | |
614 // ---------------------------------------------------------------------------- | |
615 // Insert/Erase operations. | |
616 | |
617 // class flat_set | |
618 | |
619 // pair<iterator, bool> insert(const value_type& v); | |
620 | |
621 TEST(FlatSet, InsertCV) { | |
622 { | |
623 typedef base::flat_set<int> M; | |
624 typedef M::value_type V; | |
625 typedef std::pair<M::iterator, bool> R; | |
626 | |
627 M m; | |
628 V v(2); | |
629 R r = m.insert(v); | |
630 EXPECT_TRUE(r.second); | |
631 EXPECT_EQ(r.first, m.begin()); | |
632 EXPECT_EQ(m.size(), static_cast<M::size_type>(1)); | |
633 EXPECT_EQ(*r.first, 2); | |
634 | |
635 v = 1; | |
636 r = m.insert(v); | |
637 EXPECT_TRUE(r.second); | |
638 EXPECT_EQ(r.first, m.begin()); | |
639 EXPECT_EQ(m.size(), static_cast<M::size_type>(2)); | |
640 EXPECT_EQ(*r.first, 1); | |
641 | |
642 v = 3; | |
643 r = m.insert(v); | |
644 EXPECT_TRUE(r.second); | |
645 EXPECT_EQ(r.first, prev(m.end())); | |
646 EXPECT_EQ(m.size(), static_cast<M::size_type>(3)); | |
647 EXPECT_EQ(*r.first, 3); | |
648 | |
649 v = 3; | |
650 r = m.insert(v); | |
651 EXPECT_FALSE(r.second); | |
652 EXPECT_EQ(r.first, prev(m.end())); | |
653 EXPECT_EQ(m.size(), static_cast<M::size_type>(3)); | |
654 EXPECT_EQ(*r.first, 3); | |
655 } | |
656 } | |
657 | |
658 // class flat_set | |
659 | |
660 // pair<iterator, bool> insert(value_type&& v); | |
661 | |
662 TEST(FlatSet, InsertRV) { | |
663 { | |
664 typedef base::flat_set<MoveOnly> M; | |
665 typedef std::pair<M::iterator, bool> R; | |
666 M m; | |
667 R r = m.insert(M::value_type(2)); | |
668 EXPECT_TRUE(r.second); | |
669 EXPECT_EQ(r.first, m.begin()); | |
670 EXPECT_EQ(m.size(), static_cast<M::size_type>(1)); | |
671 EXPECT_EQ(*r.first, 2); | |
672 | |
673 r = m.insert(M::value_type(1)); | |
674 EXPECT_TRUE(r.second); | |
675 EXPECT_EQ(r.first, m.begin()); | |
676 EXPECT_EQ(m.size(), static_cast<M::size_type>(2)); | |
677 EXPECT_EQ(*r.first, 1); | |
678 | |
679 r = m.insert(M::value_type(3)); | |
680 EXPECT_TRUE(r.second); | |
681 EXPECT_EQ(r.first, prev(m.end())); | |
682 EXPECT_EQ(m.size(), static_cast<M::size_type>(3)); | |
683 EXPECT_EQ(*r.first, 3); | |
684 | |
685 r = m.insert(M::value_type(3)); | |
686 EXPECT_FALSE(r.second); | |
687 EXPECT_EQ(r.first, prev(m.end())); | |
688 EXPECT_EQ(m.size(), static_cast<M::size_type>(3)); | |
689 EXPECT_EQ(*r.first, static_cast<M::size_type>(3)); | |
690 } | |
691 } | |
692 | |
693 // class flat_set | |
694 | |
695 // iterator insert(const_iterator position, const value_type& v); | |
696 | |
697 TEST(FlatSet, InsertIterCV) { | |
698 { | |
699 typedef base::flat_set<int> M; | |
700 typedef M::iterator R; | |
701 M m; | |
702 R r = m.insert(m.cend(), M::value_type(2)); | |
703 EXPECT_EQ(r, m.begin()); | |
704 EXPECT_EQ(m.size(), static_cast<M::size_type>(1)); | |
705 EXPECT_EQ(*r, 2); | |
706 | |
707 r = m.insert(m.cend(), M::value_type(1)); | |
708 EXPECT_EQ(r, m.begin()); | |
709 EXPECT_EQ(m.size(), static_cast<M::size_type>(2)); | |
710 EXPECT_EQ(*r, 1); | |
711 | |
712 r = m.insert(m.cend(), M::value_type(3)); | |
713 EXPECT_EQ(r, prev(m.end())); | |
714 EXPECT_EQ(m.size(), static_cast<M::size_type>(3)); | |
715 EXPECT_EQ(*r, 3); | |
716 | |
717 r = m.insert(m.cend(), M::value_type(3)); | |
718 EXPECT_EQ(r, prev(m.end())); | |
719 EXPECT_EQ(m.size(), static_cast<M::size_type>(3)); | |
720 EXPECT_EQ(*r, 3); | |
721 } | |
722 } | |
723 | |
724 // class flat_set | |
725 | |
726 // iterator insert(const_iterator position, value_type&& v); | |
727 | |
728 TEST(FlatSet, InsertIterRV) { | |
729 { | |
730 typedef base::flat_set<MoveOnly> M; | |
731 typedef M::iterator R; | |
732 M m; | |
733 R r = m.insert(m.cend(), M::value_type(2)); | |
734 EXPECT_EQ(r, m.begin()); | |
735 EXPECT_EQ(m.size(), static_cast<M::size_type>(1)); | |
736 EXPECT_EQ(*r, 2); | |
737 | |
738 r = m.insert(m.cend(), M::value_type(1)); | |
739 EXPECT_EQ(r, m.begin()); | |
740 EXPECT_EQ(m.size(), static_cast<M::size_type>(2)); | |
741 EXPECT_EQ(*r, 1); | |
742 | |
743 r = m.insert(m.cend(), M::value_type(3)); | |
744 EXPECT_EQ(r, prev(m.end())); | |
745 EXPECT_EQ(m.size(), static_cast<M::size_type>(3)); | |
746 EXPECT_EQ(*r, 3); | |
747 | |
748 r = m.insert(m.cend(), M::value_type(3)); | |
749 EXPECT_EQ(r, prev(m.end())); | |
750 EXPECT_EQ(m.size(), static_cast<M::size_type>(3)); | |
751 EXPECT_EQ(*r, 3); | |
752 } | |
753 } | |
754 | |
755 // class flat_set | |
756 | |
757 // template <class InputIterator> | |
758 // void insert(InputIterator first, InputIterator last); | |
759 | |
760 TEST(FlatSet, InsertRange) { | |
dyaroshev
2016/12/15 16:10:59
Add tests for stability.
dyaroshev
2016/12/18 22:27:23
Done.
| |
761 { | |
762 typedef base::flat_set<int> M; | |
763 typedef int V; | |
764 | |
765 V ar[] = {1, 1, 1, 2, 2, 2, 3, 3, 3}; | |
766 | |
767 M m; | |
768 m.insert(input_iterator<const V*>(ar), | |
769 input_iterator<const V*>(ar + sizeof(ar) / sizeof(ar[0]))); | |
770 EXPECT_EQ(m.size(), static_cast<M::size_type>(3)); | |
771 EXPECT_EQ(*m.begin(), 1); | |
772 EXPECT_EQ(*next(m.begin()), 2); | |
773 EXPECT_EQ(*next(m.begin(), 2), 3); | |
774 } | |
775 } | |
776 | |
777 // class flat_set | |
778 | |
779 // void insert(initializer_list<value_type> il); | |
780 | |
781 TEST(FlatSet, InsertInitializerList) { | |
782 { | |
783 typedef base::flat_set<int> M; | |
784 typedef M::value_type V; | |
785 M m = {10, 8}; | |
786 m.insert({1, 2, 3, 4, 5, 6}); | |
787 EXPECT_EQ(m.size(), static_cast<M::size_type>(8)); | |
788 EXPECT_EQ(distance(m.begin(), m.end()), | |
789 static_cast<M::difference_type>(m.size())); | |
790 M::const_iterator i = m.cbegin(); | |
791 EXPECT_EQ(*i, V(1)); | |
792 EXPECT_EQ(*++i, V(2)); | |
793 EXPECT_EQ(*++i, V(3)); | |
794 EXPECT_EQ(*++i, V(4)); | |
795 EXPECT_EQ(*++i, V(5)); | |
796 EXPECT_EQ(*++i, V(6)); | |
797 EXPECT_EQ(*++i, V(8)); | |
798 EXPECT_EQ(*++i, V(10)); | |
799 } | |
800 } | |
801 | |
802 // class flat_set | |
803 | |
804 // template <class... Args> | |
805 // pair<iterator, bool> emplace(Args&&... args); | |
806 | |
807 TEST(FlatSet, Emplace) { | |
808 { | |
809 typedef base::flat_set<Emplaceable> M; | |
810 typedef std::pair<M::iterator, bool> R; | |
811 M m; | |
812 R r = m.emplace(); | |
813 EXPECT_TRUE(r.second); | |
814 EXPECT_EQ(r.first, m.begin()); | |
815 EXPECT_EQ(m.size(), static_cast<M::size_type>(1)); | |
816 EXPECT_EQ(*m.begin(), Emplaceable()); | |
817 r = m.emplace(2, 3.5); | |
818 EXPECT_TRUE(r.second); | |
819 EXPECT_EQ(r.first, next(m.begin())); | |
820 EXPECT_EQ(m.size(), static_cast<M::size_type>(2)); | |
821 EXPECT_EQ(*r.first, Emplaceable(2, 3.5)); | |
822 r = m.emplace(2, 3.5); | |
823 EXPECT_TRUE(!r.second); | |
Peter Kasting
2016/12/16 08:09:08
Nit: EXPECT_FALSE(r.second)
dyaroshev
2016/12/18 22:27:24
Done.
| |
824 EXPECT_EQ(r.first, next(m.begin())); | |
825 EXPECT_EQ(m.size(), static_cast<M::size_type>(2)); | |
826 EXPECT_EQ(*r.first, Emplaceable(2, 3.5)); | |
827 } | |
828 { | |
829 typedef base::flat_set<int> M; | |
830 typedef std::pair<M::iterator, bool> R; | |
831 M m; | |
832 R r = m.emplace(M::value_type(2)); | |
833 EXPECT_TRUE(r.second); | |
834 EXPECT_EQ(r.first, m.begin()); | |
835 EXPECT_EQ(m.size(), static_cast<M::size_type>(1)); | |
836 EXPECT_EQ(*r.first, 2); | |
837 } | |
838 } | |
839 | |
840 // class flat_set | |
841 | |
842 // template <class... Args> | |
843 // iterator emplace_hint(const_iterator position, Args&&... args); | |
844 | |
845 TEST(FlatSet, EmplaceHint) { | |
846 { | |
847 typedef base::flat_set<Emplaceable> M; | |
848 typedef M::iterator R; | |
849 M m; | |
850 R r = m.emplace_hint(m.cend()); | |
851 EXPECT_EQ(r, m.begin()); | |
852 EXPECT_EQ(m.size(), static_cast<M::size_type>(1)); | |
853 EXPECT_EQ(*m.begin(), Emplaceable()); | |
854 r = m.emplace_hint(m.cend(), 2, 3.5); | |
855 EXPECT_EQ(r, next(m.begin())); | |
856 EXPECT_EQ(m.size(), static_cast<M::size_type>(2)); | |
857 EXPECT_EQ(*r, Emplaceable(2, 3.5)); | |
858 r = m.emplace_hint(m.cbegin(), 2, 3.5); | |
859 EXPECT_EQ(r, next(m.begin())); | |
860 EXPECT_EQ(m.size(), static_cast<M::size_type>(2)); | |
861 EXPECT_EQ(*r, Emplaceable(2, 3.5)); | |
862 } | |
863 { | |
864 typedef base::flat_set<int> M; | |
865 typedef M::iterator R; | |
866 M m; | |
867 R r = m.emplace_hint(m.cend(), M::value_type(2)); | |
868 EXPECT_EQ(r, m.begin()); | |
869 EXPECT_EQ(m.size(), static_cast<M::size_type>(1)); | |
870 EXPECT_EQ(*r, 2); | |
871 } | |
872 } | |
873 | |
874 // class flat_set | |
875 | |
876 // iterator erase(const_iterator position); | |
877 | |
878 TEST(FlatSet, EraseCIter) { | |
879 { | |
880 typedef base::flat_set<int> M; | |
881 typedef int V; | |
882 typedef M::iterator I; | |
883 | |
884 V ar[] = {1, 2, 3, 4, 5, 6, 7, 8}; | |
885 | |
886 M m(ar, ar + sizeof(ar) / sizeof(ar[0])); | |
887 EXPECT_EQ(m.size(), static_cast<M::size_type>(8)); | |
888 I i = m.erase(next(m.cbegin(), 3)); | |
889 EXPECT_EQ(m.size(), static_cast<M::size_type>(7)); | |
890 EXPECT_EQ(i, next(m.begin(), 3)); | |
891 EXPECT_EQ(*next(m.begin(), 0), 1); | |
892 EXPECT_EQ(*next(m.begin(), 1), 2); | |
893 EXPECT_EQ(*next(m.begin(), 2), 3); | |
894 EXPECT_EQ(*next(m.begin(), 3), 5); | |
895 EXPECT_EQ(*next(m.begin(), 4), 6); | |
896 EXPECT_EQ(*next(m.begin(), 5), 7); | |
897 EXPECT_EQ(*next(m.begin(), 6), 8); | |
898 | |
899 i = m.erase(next(m.cbegin(), 0)); | |
900 EXPECT_EQ(m.size(), static_cast<M::size_type>(6)); | |
901 EXPECT_EQ(i, m.begin()); | |
902 EXPECT_EQ(*next(m.begin(), 0), 2); | |
903 EXPECT_EQ(*next(m.begin(), 1), 3); | |
904 EXPECT_EQ(*next(m.begin(), 2), 5); | |
905 EXPECT_EQ(*next(m.begin(), 3), 6); | |
906 EXPECT_EQ(*next(m.begin(), 4), 7); | |
907 EXPECT_EQ(*next(m.begin(), 5), 8); | |
908 | |
909 i = m.erase(next(m.cbegin(), 5)); | |
910 EXPECT_EQ(m.size(), static_cast<M::size_type>(5)); | |
911 EXPECT_EQ(i, m.end()); | |
912 EXPECT_EQ(*next(m.begin(), 0), 2); | |
913 EXPECT_EQ(*next(m.begin(), 1), 3); | |
914 EXPECT_EQ(*next(m.begin(), 2), 5); | |
915 EXPECT_EQ(*next(m.begin(), 3), 6); | |
916 EXPECT_EQ(*next(m.begin(), 4), 7); | |
917 | |
918 i = m.erase(next(m.cbegin(), 1)); | |
919 EXPECT_EQ(m.size(), static_cast<M::size_type>(4)); | |
920 EXPECT_EQ(i, next(m.begin())); | |
921 EXPECT_EQ(*next(m.begin(), 0), 2); | |
922 EXPECT_EQ(*next(m.begin(), 1), 5); | |
923 EXPECT_EQ(*next(m.begin(), 2), 6); | |
924 EXPECT_EQ(*next(m.begin(), 3), 7); | |
925 | |
926 i = m.erase(next(m.cbegin(), 2)); | |
927 EXPECT_EQ(m.size(), static_cast<M::size_type>(3)); | |
928 EXPECT_EQ(i, next(m.begin(), 2)); | |
929 EXPECT_EQ(*next(m.begin(), 0), 2); | |
930 EXPECT_EQ(*next(m.begin(), 1), 5); | |
931 EXPECT_EQ(*next(m.begin(), 2), 7); | |
932 | |
933 i = m.erase(next(m.cbegin(), 2)); | |
934 EXPECT_EQ(m.size(), static_cast<M::size_type>(2)); | |
935 EXPECT_EQ(i, next(m.begin(), 2)); | |
936 EXPECT_EQ(*next(m.begin(), 0), 2); | |
937 EXPECT_EQ(*next(m.begin(), 1), 5); | |
938 | |
939 i = m.erase(next(m.cbegin(), 0)); | |
940 EXPECT_EQ(m.size(), static_cast<M::size_type>(1)); | |
941 EXPECT_EQ(i, next(m.begin(), 0)); | |
942 EXPECT_EQ(*next(m.begin(), 0), 5); | |
943 | |
944 i = m.erase(m.cbegin()); | |
945 EXPECT_EQ(m.size(), static_cast<M::size_type>(0)); | |
946 EXPECT_EQ(i, m.begin()); | |
947 EXPECT_EQ(i, m.end()); | |
948 } | |
949 } | |
950 | |
951 // class flat_set | |
952 | |
953 // iterator erase(const_iterator first, const_iterator last); | |
954 | |
955 TEST(FlatSet, EraseCIterCIter) { | |
956 { | |
957 typedef base::flat_set<int> M; | |
958 typedef int V; | |
959 typedef M::iterator I; | |
960 | |
961 V ar[] = {1, 2, 3, 4, 5, 6, 7, 8}; | |
962 | |
963 M m(ar, ar + sizeof(ar) / sizeof(ar[0])); | |
964 EXPECT_EQ(m.size(), static_cast<M::size_type>(8)); | |
965 I i = m.erase(next(m.cbegin(), 5), next(m.cbegin(), 5)); | |
966 EXPECT_EQ(m.size(), static_cast<M::size_type>(8)); | |
967 EXPECT_EQ(i, next(m.begin(), 5)); | |
968 EXPECT_EQ(*next(m.begin(), 0), 1); | |
969 EXPECT_EQ(*next(m.begin(), 1), 2); | |
970 EXPECT_EQ(*next(m.begin(), 2), 3); | |
971 EXPECT_EQ(*next(m.begin(), 3), 4); | |
972 EXPECT_EQ(*next(m.begin(), 4), 5); | |
973 EXPECT_EQ(*next(m.begin(), 5), 6); | |
974 EXPECT_EQ(*next(m.begin(), 6), 7); | |
975 EXPECT_EQ(*next(m.begin(), 7), 8); | |
976 | |
977 i = m.erase(next(m.cbegin(), 3), next(m.cbegin(), 4)); | |
978 EXPECT_EQ(m.size(), static_cast<M::size_type>(7)); | |
979 EXPECT_EQ(i, next(m.begin(), 3)); | |
980 EXPECT_EQ(*next(m.begin(), 0), 1); | |
981 EXPECT_EQ(*next(m.begin(), 1), 2); | |
982 EXPECT_EQ(*next(m.begin(), 2), 3); | |
983 EXPECT_EQ(*next(m.begin(), 3), 5); | |
984 EXPECT_EQ(*next(m.begin(), 4), 6); | |
985 EXPECT_EQ(*next(m.begin(), 5), 7); | |
986 EXPECT_EQ(*next(m.begin(), 6), 8); | |
987 | |
988 i = m.erase(next(m.cbegin(), 2), next(m.cbegin(), 5)); | |
989 EXPECT_EQ(m.size(), static_cast<M::size_type>(4)); | |
990 EXPECT_EQ(i, next(m.begin(), 2)); | |
991 EXPECT_EQ(*next(m.begin(), 0), 1); | |
992 EXPECT_EQ(*next(m.begin(), 1), 2); | |
993 EXPECT_EQ(*next(m.begin(), 2), 7); | |
994 EXPECT_EQ(*next(m.begin(), 3), 8); | |
995 | |
996 i = m.erase(next(m.cbegin(), 0), next(m.cbegin(), 2)); | |
997 EXPECT_EQ(m.size(), static_cast<M::size_type>(2)); | |
998 EXPECT_EQ(i, next(m.begin(), 0)); | |
999 EXPECT_EQ(*next(m.begin(), 0), 7); | |
1000 EXPECT_EQ(*next(m.begin(), 1), 8); | |
1001 | |
1002 i = m.erase(m.cbegin(), m.cend()); | |
1003 EXPECT_EQ(m.size(), static_cast<M::size_type>(0)); | |
1004 EXPECT_EQ(i, m.end()); | |
1005 } | |
1006 } | |
1007 | |
1008 // class set | |
1009 | |
1010 // size_type erase(const key_type& k); | |
1011 | |
1012 TEST(FlatSet, EraseKey) { | |
1013 { | |
1014 typedef base::flat_set<int> M; | |
1015 typedef int V; | |
1016 typedef M::size_type I; | |
1017 | |
1018 V ar[] = {1, 2, 3, 4, 5, 6, 7, 8}; | |
1019 | |
1020 M m(ar, ar + sizeof(ar) / sizeof(ar[0])); | |
1021 EXPECT_EQ(m.size(), static_cast<M::size_type>(8)); | |
1022 I i = m.erase(9); | |
1023 EXPECT_EQ(m.size(), static_cast<M::size_type>(8)); | |
1024 EXPECT_EQ(i, static_cast<M::size_type>(0)); | |
1025 EXPECT_EQ(*next(m.begin(), 0), 1); | |
1026 EXPECT_EQ(*next(m.begin(), 1), 2); | |
1027 EXPECT_EQ(*next(m.begin(), 2), 3); | |
1028 EXPECT_EQ(*next(m.begin(), 3), 4); | |
1029 EXPECT_EQ(*next(m.begin(), 4), 5); | |
1030 EXPECT_EQ(*next(m.begin(), 5), 6); | |
1031 EXPECT_EQ(*next(m.begin(), 6), 7); | |
1032 EXPECT_EQ(*next(m.begin(), 7), 8); | |
1033 | |
1034 i = m.erase(4); | |
1035 EXPECT_EQ(m.size(), static_cast<M::size_type>(7)); | |
1036 EXPECT_EQ(i, static_cast<M::size_type>(1)); | |
1037 EXPECT_EQ(*next(m.begin(), 0), 1); | |
1038 EXPECT_EQ(*next(m.begin(), 1), 2); | |
1039 EXPECT_EQ(*next(m.begin(), 2), 3); | |
1040 EXPECT_EQ(*next(m.begin(), 3), 5); | |
1041 EXPECT_EQ(*next(m.begin(), 4), 6); | |
1042 EXPECT_EQ(*next(m.begin(), 5), 7); | |
1043 EXPECT_EQ(*next(m.begin(), 6), 8); | |
1044 | |
1045 i = m.erase(1); | |
1046 EXPECT_EQ(m.size(), static_cast<M::size_type>(6)); | |
1047 EXPECT_EQ(i, static_cast<M::size_type>(1)); | |
1048 EXPECT_EQ(*next(m.begin(), 0), 2); | |
1049 EXPECT_EQ(*next(m.begin(), 1), 3); | |
1050 EXPECT_EQ(*next(m.begin(), 2), 5); | |
1051 EXPECT_EQ(*next(m.begin(), 3), 6); | |
1052 EXPECT_EQ(*next(m.begin(), 4), 7); | |
1053 EXPECT_EQ(*next(m.begin(), 5), 8); | |
1054 | |
1055 i = m.erase(8); | |
1056 EXPECT_EQ(m.size(), static_cast<M::size_type>(5)); | |
1057 EXPECT_EQ(i, static_cast<M::size_type>(1)); | |
1058 EXPECT_EQ(*next(m.begin(), 0), 2); | |
1059 EXPECT_EQ(*next(m.begin(), 1), 3); | |
1060 EXPECT_EQ(*next(m.begin(), 2), 5); | |
1061 EXPECT_EQ(*next(m.begin(), 3), 6); | |
1062 EXPECT_EQ(*next(m.begin(), 4), 7); | |
1063 | |
1064 i = m.erase(3); | |
1065 EXPECT_EQ(m.size(), static_cast<M::size_type>(4)); | |
1066 EXPECT_EQ(i, static_cast<M::size_type>(1)); | |
1067 EXPECT_EQ(*next(m.begin(), 0), 2); | |
1068 EXPECT_EQ(*next(m.begin(), 1), 5); | |
1069 EXPECT_EQ(*next(m.begin(), 2), 6); | |
1070 EXPECT_EQ(*next(m.begin(), 3), 7); | |
1071 | |
1072 i = m.erase(6); | |
1073 EXPECT_EQ(m.size(), static_cast<M::size_type>(3)); | |
1074 EXPECT_EQ(i, static_cast<M::size_type>(1)); | |
1075 EXPECT_EQ(*next(m.begin(), 0), 2); | |
1076 EXPECT_EQ(*next(m.begin(), 1), 5); | |
1077 EXPECT_EQ(*next(m.begin(), 2), 7); | |
1078 | |
1079 i = m.erase(7); | |
1080 EXPECT_EQ(m.size(), static_cast<M::size_type>(2)); | |
1081 EXPECT_EQ(i, static_cast<M::size_type>(1)); | |
1082 EXPECT_EQ(*next(m.begin(), 0), 2); | |
1083 EXPECT_EQ(*next(m.begin(), 1), 5); | |
1084 | |
1085 i = m.erase(2); | |
1086 EXPECT_EQ(m.size(), static_cast<M::size_type>(1)); | |
1087 EXPECT_EQ(i, static_cast<M::size_type>(1)); | |
1088 EXPECT_EQ(*next(m.begin(), 0), 5); | |
1089 | |
1090 i = m.erase(5); | |
1091 EXPECT_EQ(m.size(), static_cast<M::size_type>(0)); | |
1092 EXPECT_EQ(i, static_cast<M::size_type>(1)); | |
1093 } | |
1094 } | |
1095 | |
1096 // ---------------------------------------------------------------------------- | |
1097 // Comparators. | |
dyaroshev
2016/12/15 16:10:59
Add test that flat_set is sorted with provided com
dyaroshev
2016/12/18 22:27:24
Done.
| |
1098 | |
1099 // ---------------------------------------------------------------------------- | |
1100 // Binary search operations. | |
1101 | |
1102 // class flat_set | |
1103 | |
1104 // size_type count(const key_type& k) const; | |
1105 | |
1106 TEST(FlatSet, Count) { | |
1107 { | |
1108 typedef int V; | |
1109 typedef base::flat_set<int> M; | |
1110 typedef M::size_type R; | |
1111 | |
1112 V ar[] = {5, 6, 7, 8, 9, 10, 11, 12}; | |
1113 | |
1114 const M m(ar, ar + sizeof(ar) / sizeof(ar[0])); | |
1115 R r = m.count(5); | |
Peter Kasting
2016/12/16 08:09:07
Nit: Avoid unneeded temps, e.g.
EXPECT_EQ(1U, m
dyaroshev
2016/12/18 22:27:25
Done, where seemed appropriate.
| |
1116 EXPECT_EQ(r, static_cast<M::size_type>(1)); | |
1117 r = m.count(6); | |
1118 EXPECT_EQ(r, static_cast<M::size_type>(1)); | |
1119 r = m.count(7); | |
1120 EXPECT_EQ(r, static_cast<M::size_type>(1)); | |
1121 r = m.count(8); | |
1122 EXPECT_EQ(r, static_cast<M::size_type>(1)); | |
1123 r = m.count(9); | |
1124 EXPECT_EQ(r, static_cast<M::size_type>(1)); | |
1125 r = m.count(10); | |
1126 EXPECT_EQ(r, static_cast<M::size_type>(1)); | |
1127 r = m.count(11); | |
1128 EXPECT_EQ(r, static_cast<M::size_type>(1)); | |
1129 r = m.count(12); | |
1130 EXPECT_EQ(r, static_cast<M::size_type>(1)); | |
1131 r = m.count(4); | |
1132 EXPECT_EQ(r, static_cast<M::size_type>(0)); | |
1133 } | |
1134 { | |
1135 typedef int V; | |
1136 typedef base::flat_set<int, std::less<V>> M; | |
1137 typedef M::size_type R; | |
1138 | |
1139 V ar[] = {5, 6, 7, 8, 9, 10, 11, 12}; | |
1140 | |
1141 const M m(ar, ar + sizeof(ar) / sizeof(ar[0])); | |
1142 R r = m.count(5); | |
1143 EXPECT_EQ(r, static_cast<M::size_type>(1)); | |
1144 r = m.count(6); | |
1145 EXPECT_EQ(r, static_cast<M::size_type>(1)); | |
1146 r = m.count(7); | |
1147 EXPECT_EQ(r, static_cast<M::size_type>(1)); | |
1148 r = m.count(8); | |
1149 EXPECT_EQ(r, static_cast<M::size_type>(1)); | |
1150 r = m.count(9); | |
1151 EXPECT_EQ(r, static_cast<M::size_type>(1)); | |
1152 r = m.count(10); | |
1153 EXPECT_EQ(r, static_cast<M::size_type>(1)); | |
1154 r = m.count(11); | |
1155 EXPECT_EQ(r, static_cast<M::size_type>(1)); | |
1156 r = m.count(12); | |
1157 EXPECT_EQ(r, static_cast<M::size_type>(1)); | |
1158 r = m.count(4); | |
1159 EXPECT_EQ(r, static_cast<M::size_type>(0)); | |
1160 } | |
1161 } | |
1162 | |
1163 // class set | |
1164 | |
1165 // iterator find(const key_type& k); | |
1166 // const_iterator find(const key_type& k) const; | |
1167 | |
1168 TEST(FlatSet, Find) { | |
1169 { | |
1170 typedef int V; | |
1171 typedef base::flat_set<V> M; | |
1172 { | |
1173 typedef M::iterator R; | |
1174 | |
1175 V ar[] = {5, 6, 7, 8, 9, 10, 11, 12}; | |
1176 | |
1177 M m(ar, ar + sizeof(ar) / sizeof(ar[0])); | |
1178 R r = m.find(5); | |
1179 EXPECT_EQ(r, m.begin()); | |
1180 r = m.find(6); | |
1181 EXPECT_EQ(r, next(m.begin())); | |
1182 r = m.find(7); | |
1183 EXPECT_EQ(r, next(m.begin(), 2)); | |
1184 r = m.find(8); | |
1185 EXPECT_EQ(r, next(m.begin(), 3)); | |
1186 r = m.find(9); | |
1187 EXPECT_EQ(r, next(m.begin(), 4)); | |
1188 r = m.find(10); | |
1189 EXPECT_EQ(r, next(m.begin(), 5)); | |
1190 r = m.find(11); | |
1191 EXPECT_EQ(r, next(m.begin(), 6)); | |
1192 r = m.find(12); | |
1193 EXPECT_EQ(r, next(m.begin(), 7)); | |
1194 r = m.find(4); | |
1195 EXPECT_EQ(r, next(m.begin(), 8)); | |
1196 } | |
1197 { | |
1198 typedef M::const_iterator R; | |
1199 | |
1200 V ar[] = {5, 6, 7, 8, 9, 10, 11, 12}; | |
1201 | |
1202 const M m(ar, ar + sizeof(ar) / sizeof(ar[0])); | |
1203 R r = m.find(5); | |
1204 EXPECT_EQ(r, m.begin()); | |
1205 r = m.find(6); | |
1206 EXPECT_EQ(r, next(m.begin())); | |
1207 r = m.find(7); | |
1208 EXPECT_EQ(r, next(m.begin(), 2)); | |
1209 r = m.find(8); | |
1210 EXPECT_EQ(r, next(m.begin(), 3)); | |
1211 r = m.find(9); | |
1212 EXPECT_EQ(r, next(m.begin(), 4)); | |
1213 r = m.find(10); | |
1214 EXPECT_EQ(r, next(m.begin(), 5)); | |
1215 r = m.find(11); | |
1216 EXPECT_EQ(r, next(m.begin(), 6)); | |
1217 r = m.find(12); | |
1218 EXPECT_EQ(r, next(m.begin(), 7)); | |
1219 r = m.find(4); | |
1220 EXPECT_EQ(r, next(m.begin(), 8)); | |
1221 } | |
1222 } | |
1223 { | |
1224 typedef int V; | |
1225 typedef base::flat_set<V, std::less<V>> M; | |
1226 typedef M::iterator R; | |
1227 | |
1228 V ar[] = {5, 6, 7, 8, 9, 10, 11, 12}; | |
1229 | |
1230 M m(ar, ar + sizeof(ar) / sizeof(ar[0])); | |
1231 R r = m.find(5); | |
1232 EXPECT_EQ(r, m.begin()); | |
1233 r = m.find(6); | |
1234 EXPECT_EQ(r, next(m.begin())); | |
1235 r = m.find(7); | |
1236 EXPECT_EQ(r, next(m.begin(), 2)); | |
1237 r = m.find(8); | |
1238 EXPECT_EQ(r, next(m.begin(), 3)); | |
1239 r = m.find(9); | |
1240 EXPECT_EQ(r, next(m.begin(), 4)); | |
1241 r = m.find(10); | |
1242 EXPECT_EQ(r, next(m.begin(), 5)); | |
1243 r = m.find(11); | |
1244 EXPECT_EQ(r, next(m.begin(), 6)); | |
1245 r = m.find(12); | |
1246 EXPECT_EQ(r, next(m.begin(), 7)); | |
1247 r = m.find(4); | |
1248 EXPECT_EQ(r, next(m.begin(), 8)); | |
1249 } | |
1250 } | |
1251 | |
1252 // class flat_set | |
1253 | |
1254 // pair<iterator,iterator> equal_range(const key_type& k); | |
1255 // pair<const_iterator,const_iterator> equal_range(const key_type& k) const; | |
1256 | |
1257 TEST(FlatSet, EqualRange) { | |
1258 { | |
1259 typedef int V; | |
1260 typedef base::flat_set<int> M; | |
1261 { | |
1262 typedef std::pair<M::iterator, M::iterator> R; | |
1263 | |
1264 V ar[] = {5, 7, 9, 11, 13, 15, 17, 19}; | |
1265 | |
1266 M m(ar, ar + sizeof(ar) / sizeof(ar[0])); | |
1267 R r = m.equal_range(5); | |
1268 EXPECT_EQ(r.first, next(m.begin(), 0)); | |
1269 EXPECT_EQ(r.second, next(m.begin(), 1)); | |
1270 r = m.equal_range(7); | |
1271 EXPECT_EQ(r.first, next(m.begin(), 1)); | |
1272 EXPECT_EQ(r.second, next(m.begin(), 2)); | |
1273 r = m.equal_range(9); | |
1274 EXPECT_EQ(r.first, next(m.begin(), 2)); | |
1275 EXPECT_EQ(r.second, next(m.begin(), 3)); | |
1276 r = m.equal_range(11); | |
1277 EXPECT_EQ(r.first, next(m.begin(), 3)); | |
1278 EXPECT_EQ(r.second, next(m.begin(), 4)); | |
1279 r = m.equal_range(13); | |
1280 EXPECT_EQ(r.first, next(m.begin(), 4)); | |
1281 EXPECT_EQ(r.second, next(m.begin(), 5)); | |
1282 r = m.equal_range(15); | |
1283 EXPECT_EQ(r.first, next(m.begin(), 5)); | |
1284 EXPECT_EQ(r.second, next(m.begin(), 6)); | |
1285 r = m.equal_range(17); | |
1286 EXPECT_EQ(r.first, next(m.begin(), 6)); | |
1287 EXPECT_EQ(r.second, next(m.begin(), 7)); | |
1288 r = m.equal_range(19); | |
1289 EXPECT_EQ(r.first, next(m.begin(), 7)); | |
1290 EXPECT_EQ(r.second, next(m.begin(), 8)); | |
1291 r = m.equal_range(4); | |
1292 EXPECT_EQ(r.first, next(m.begin(), 0)); | |
1293 EXPECT_EQ(r.second, next(m.begin(), 0)); | |
1294 r = m.equal_range(6); | |
1295 EXPECT_EQ(r.first, next(m.begin(), 1)); | |
1296 EXPECT_EQ(r.second, next(m.begin(), 1)); | |
1297 r = m.equal_range(8); | |
1298 EXPECT_EQ(r.first, next(m.begin(), 2)); | |
1299 EXPECT_EQ(r.second, next(m.begin(), 2)); | |
1300 r = m.equal_range(10); | |
1301 EXPECT_EQ(r.first, next(m.begin(), 3)); | |
1302 EXPECT_EQ(r.second, next(m.begin(), 3)); | |
1303 r = m.equal_range(12); | |
1304 EXPECT_EQ(r.first, next(m.begin(), 4)); | |
1305 EXPECT_EQ(r.second, next(m.begin(), 4)); | |
1306 r = m.equal_range(14); | |
1307 EXPECT_EQ(r.first, next(m.begin(), 5)); | |
1308 EXPECT_EQ(r.second, next(m.begin(), 5)); | |
1309 r = m.equal_range(16); | |
1310 EXPECT_EQ(r.first, next(m.begin(), 6)); | |
1311 EXPECT_EQ(r.second, next(m.begin(), 6)); | |
1312 r = m.equal_range(18); | |
1313 EXPECT_EQ(r.first, next(m.begin(), 7)); | |
1314 EXPECT_EQ(r.second, next(m.begin(), 7)); | |
1315 r = m.equal_range(20); | |
1316 EXPECT_EQ(r.first, next(m.begin(), 8)); | |
1317 EXPECT_EQ(r.second, next(m.begin(), 8)); | |
1318 } | |
1319 { | |
1320 typedef std::pair<M::const_iterator, M::const_iterator> R; | |
1321 | |
1322 V ar[] = {5, 7, 9, 11, 13, 15, 17, 19}; | |
1323 | |
1324 const M m(ar, ar + sizeof(ar) / sizeof(ar[0])); | |
1325 R r = m.equal_range(5); | |
1326 EXPECT_EQ(r.first, next(m.begin(), 0)); | |
1327 EXPECT_EQ(r.second, next(m.begin(), 1)); | |
1328 r = m.equal_range(7); | |
1329 EXPECT_EQ(r.first, next(m.begin(), 1)); | |
1330 EXPECT_EQ(r.second, next(m.begin(), 2)); | |
1331 r = m.equal_range(9); | |
1332 EXPECT_EQ(r.first, next(m.begin(), 2)); | |
1333 EXPECT_EQ(r.second, next(m.begin(), 3)); | |
1334 r = m.equal_range(11); | |
1335 EXPECT_EQ(r.first, next(m.begin(), 3)); | |
1336 EXPECT_EQ(r.second, next(m.begin(), 4)); | |
1337 r = m.equal_range(13); | |
1338 EXPECT_EQ(r.first, next(m.begin(), 4)); | |
1339 EXPECT_EQ(r.second, next(m.begin(), 5)); | |
1340 r = m.equal_range(15); | |
1341 EXPECT_EQ(r.first, next(m.begin(), 5)); | |
1342 EXPECT_EQ(r.second, next(m.begin(), 6)); | |
1343 r = m.equal_range(17); | |
1344 EXPECT_EQ(r.first, next(m.begin(), 6)); | |
1345 EXPECT_EQ(r.second, next(m.begin(), 7)); | |
1346 r = m.equal_range(19); | |
1347 EXPECT_EQ(r.first, next(m.begin(), 7)); | |
1348 EXPECT_EQ(r.second, next(m.begin(), 8)); | |
1349 r = m.equal_range(4); | |
1350 EXPECT_EQ(r.first, next(m.begin(), 0)); | |
1351 EXPECT_EQ(r.second, next(m.begin(), 0)); | |
1352 r = m.equal_range(6); | |
1353 EXPECT_EQ(r.first, next(m.begin(), 1)); | |
1354 EXPECT_EQ(r.second, next(m.begin(), 1)); | |
1355 r = m.equal_range(8); | |
1356 EXPECT_EQ(r.first, next(m.begin(), 2)); | |
1357 EXPECT_EQ(r.second, next(m.begin(), 2)); | |
1358 r = m.equal_range(10); | |
1359 EXPECT_EQ(r.first, next(m.begin(), 3)); | |
1360 EXPECT_EQ(r.second, next(m.begin(), 3)); | |
1361 r = m.equal_range(12); | |
1362 EXPECT_EQ(r.first, next(m.begin(), 4)); | |
1363 EXPECT_EQ(r.second, next(m.begin(), 4)); | |
1364 r = m.equal_range(14); | |
1365 EXPECT_EQ(r.first, next(m.begin(), 5)); | |
1366 EXPECT_EQ(r.second, next(m.begin(), 5)); | |
1367 r = m.equal_range(16); | |
1368 EXPECT_EQ(r.first, next(m.begin(), 6)); | |
1369 EXPECT_EQ(r.second, next(m.begin(), 6)); | |
1370 r = m.equal_range(18); | |
1371 EXPECT_EQ(r.first, next(m.begin(), 7)); | |
1372 EXPECT_EQ(r.second, next(m.begin(), 7)); | |
1373 r = m.equal_range(20); | |
1374 EXPECT_EQ(r.first, next(m.begin(), 8)); | |
1375 EXPECT_EQ(r.second, next(m.begin(), 8)); | |
1376 } | |
1377 } | |
1378 | |
1379 { | |
1380 typedef int V; | |
1381 typedef base::flat_set<V, std::less<V>> M; | |
1382 { | |
1383 typedef std::pair<M::iterator, M::iterator> R; | |
1384 | |
1385 V ar[] = {5, 7, 9, 11, 13, 15, 17, 19}; | |
1386 | |
1387 M m(ar, ar + sizeof(ar) / sizeof(ar[0])); | |
1388 R r = m.equal_range(5); | |
1389 EXPECT_EQ(r.first, next(m.begin(), 0)); | |
1390 EXPECT_EQ(r.second, next(m.begin(), 1)); | |
1391 r = m.equal_range(7); | |
1392 EXPECT_EQ(r.first, next(m.begin(), 1)); | |
1393 EXPECT_EQ(r.second, next(m.begin(), 2)); | |
1394 r = m.equal_range(9); | |
1395 EXPECT_EQ(r.first, next(m.begin(), 2)); | |
1396 EXPECT_EQ(r.second, next(m.begin(), 3)); | |
1397 r = m.equal_range(11); | |
1398 EXPECT_EQ(r.first, next(m.begin(), 3)); | |
1399 EXPECT_EQ(r.second, next(m.begin(), 4)); | |
1400 r = m.equal_range(13); | |
1401 EXPECT_EQ(r.first, next(m.begin(), 4)); | |
1402 EXPECT_EQ(r.second, next(m.begin(), 5)); | |
1403 r = m.equal_range(15); | |
1404 EXPECT_EQ(r.first, next(m.begin(), 5)); | |
1405 EXPECT_EQ(r.second, next(m.begin(), 6)); | |
1406 r = m.equal_range(17); | |
1407 EXPECT_EQ(r.first, next(m.begin(), 6)); | |
1408 EXPECT_EQ(r.second, next(m.begin(), 7)); | |
1409 r = m.equal_range(19); | |
1410 EXPECT_EQ(r.first, next(m.begin(), 7)); | |
1411 EXPECT_EQ(r.second, next(m.begin(), 8)); | |
1412 r = m.equal_range(4); | |
1413 EXPECT_EQ(r.first, next(m.begin(), 0)); | |
1414 EXPECT_EQ(r.second, next(m.begin(), 0)); | |
1415 r = m.equal_range(6); | |
1416 EXPECT_EQ(r.first, next(m.begin(), 1)); | |
1417 EXPECT_EQ(r.second, next(m.begin(), 1)); | |
1418 r = m.equal_range(8); | |
1419 EXPECT_EQ(r.first, next(m.begin(), 2)); | |
1420 EXPECT_EQ(r.second, next(m.begin(), 2)); | |
1421 r = m.equal_range(10); | |
1422 EXPECT_EQ(r.first, next(m.begin(), 3)); | |
1423 EXPECT_EQ(r.second, next(m.begin(), 3)); | |
1424 r = m.equal_range(12); | |
1425 EXPECT_EQ(r.first, next(m.begin(), 4)); | |
1426 EXPECT_EQ(r.second, next(m.begin(), 4)); | |
1427 r = m.equal_range(14); | |
1428 EXPECT_EQ(r.first, next(m.begin(), 5)); | |
1429 EXPECT_EQ(r.second, next(m.begin(), 5)); | |
1430 r = m.equal_range(16); | |
1431 EXPECT_EQ(r.first, next(m.begin(), 6)); | |
1432 EXPECT_EQ(r.second, next(m.begin(), 6)); | |
1433 r = m.equal_range(18); | |
1434 EXPECT_EQ(r.first, next(m.begin(), 7)); | |
1435 EXPECT_EQ(r.second, next(m.begin(), 7)); | |
1436 r = m.equal_range(20); | |
1437 EXPECT_EQ(r.first, next(m.begin(), 8)); | |
1438 EXPECT_EQ(r.second, next(m.begin(), 8)); | |
1439 } | |
1440 } | |
1441 } | |
1442 | |
1443 // class flat_set | |
1444 | |
1445 // iterator lower_bound(const key_type& k); | |
1446 // const_iterator lower_bound(const key_type& k) const; | |
1447 | |
1448 TEST(FlatSet, LowerBound) { | |
1449 { | |
1450 typedef int V; | |
1451 typedef base::flat_set<int> M; | |
1452 { | |
1453 typedef M::iterator R; | |
1454 | |
1455 V ar[] = {5, 7, 9, 11, 13, 15, 17, 19}; | |
1456 | |
1457 M m(ar, ar + sizeof(ar) / sizeof(ar[0])); | |
1458 R r = m.lower_bound(5); | |
1459 EXPECT_EQ(r, m.begin()); | |
1460 r = m.lower_bound(7); | |
1461 EXPECT_EQ(r, next(m.begin())); | |
1462 r = m.lower_bound(9); | |
1463 EXPECT_EQ(r, next(m.begin(), 2)); | |
1464 r = m.lower_bound(11); | |
1465 EXPECT_EQ(r, next(m.begin(), 3)); | |
1466 r = m.lower_bound(13); | |
1467 EXPECT_EQ(r, next(m.begin(), 4)); | |
1468 r = m.lower_bound(15); | |
1469 EXPECT_EQ(r, next(m.begin(), 5)); | |
1470 r = m.lower_bound(17); | |
1471 EXPECT_EQ(r, next(m.begin(), 6)); | |
1472 r = m.lower_bound(19); | |
1473 EXPECT_EQ(r, next(m.begin(), 7)); | |
1474 r = m.lower_bound(4); | |
1475 EXPECT_EQ(r, next(m.begin(), 0)); | |
1476 r = m.lower_bound(6); | |
1477 EXPECT_EQ(r, next(m.begin(), 1)); | |
1478 r = m.lower_bound(8); | |
1479 EXPECT_EQ(r, next(m.begin(), 2)); | |
1480 r = m.lower_bound(10); | |
1481 EXPECT_EQ(r, next(m.begin(), 3)); | |
1482 r = m.lower_bound(12); | |
1483 EXPECT_EQ(r, next(m.begin(), 4)); | |
1484 r = m.lower_bound(14); | |
1485 EXPECT_EQ(r, next(m.begin(), 5)); | |
1486 r = m.lower_bound(16); | |
1487 EXPECT_EQ(r, next(m.begin(), 6)); | |
1488 r = m.lower_bound(18); | |
1489 EXPECT_EQ(r, next(m.begin(), 7)); | |
1490 r = m.lower_bound(20); | |
1491 EXPECT_EQ(r, next(m.begin(), 8)); | |
1492 } | |
1493 { | |
1494 typedef M::const_iterator R; | |
1495 | |
1496 V ar[] = {5, 7, 9, 11, 13, 15, 17, 19}; | |
1497 | |
1498 const M m(ar, ar + sizeof(ar) / sizeof(ar[0])); | |
1499 R r = m.lower_bound(5); | |
1500 EXPECT_EQ(r, m.begin()); | |
1501 r = m.lower_bound(7); | |
1502 EXPECT_EQ(r, next(m.begin())); | |
1503 r = m.lower_bound(9); | |
1504 EXPECT_EQ(r, next(m.begin(), 2)); | |
1505 r = m.lower_bound(11); | |
1506 EXPECT_EQ(r, next(m.begin(), 3)); | |
1507 r = m.lower_bound(13); | |
1508 EXPECT_EQ(r, next(m.begin(), 4)); | |
1509 r = m.lower_bound(15); | |
1510 EXPECT_EQ(r, next(m.begin(), 5)); | |
1511 r = m.lower_bound(17); | |
1512 EXPECT_EQ(r, next(m.begin(), 6)); | |
1513 r = m.lower_bound(19); | |
1514 EXPECT_EQ(r, next(m.begin(), 7)); | |
1515 r = m.lower_bound(4); | |
1516 EXPECT_EQ(r, next(m.begin(), 0)); | |
1517 r = m.lower_bound(6); | |
1518 EXPECT_EQ(r, next(m.begin(), 1)); | |
1519 r = m.lower_bound(8); | |
1520 EXPECT_EQ(r, next(m.begin(), 2)); | |
1521 r = m.lower_bound(10); | |
1522 EXPECT_EQ(r, next(m.begin(), 3)); | |
1523 r = m.lower_bound(12); | |
1524 EXPECT_EQ(r, next(m.begin(), 4)); | |
1525 r = m.lower_bound(14); | |
1526 EXPECT_EQ(r, next(m.begin(), 5)); | |
1527 r = m.lower_bound(16); | |
1528 EXPECT_EQ(r, next(m.begin(), 6)); | |
1529 r = m.lower_bound(18); | |
1530 EXPECT_EQ(r, next(m.begin(), 7)); | |
1531 r = m.lower_bound(20); | |
1532 EXPECT_EQ(r, next(m.begin(), 8)); | |
1533 } | |
1534 } | |
1535 { | |
1536 typedef int V; | |
1537 typedef base::flat_set<V, std::less<V>> M; | |
1538 typedef M::iterator R; | |
1539 | |
1540 V ar[] = {5, 7, 9, 11, 13, 15, 17, 19}; | |
1541 | |
1542 M m(ar, ar + sizeof(ar) / sizeof(ar[0])); | |
1543 R r = m.lower_bound(5); | |
1544 EXPECT_EQ(r, m.begin()); | |
1545 r = m.lower_bound(7); | |
1546 EXPECT_EQ(r, next(m.begin())); | |
1547 r = m.lower_bound(9); | |
1548 EXPECT_EQ(r, next(m.begin(), 2)); | |
1549 r = m.lower_bound(11); | |
1550 EXPECT_EQ(r, next(m.begin(), 3)); | |
1551 r = m.lower_bound(13); | |
1552 EXPECT_EQ(r, next(m.begin(), 4)); | |
1553 r = m.lower_bound(15); | |
1554 EXPECT_EQ(r, next(m.begin(), 5)); | |
1555 r = m.lower_bound(17); | |
1556 EXPECT_EQ(r, next(m.begin(), 6)); | |
1557 r = m.lower_bound(19); | |
1558 EXPECT_EQ(r, next(m.begin(), 7)); | |
1559 r = m.lower_bound(4); | |
1560 EXPECT_EQ(r, next(m.begin(), 0)); | |
1561 r = m.lower_bound(6); | |
1562 EXPECT_EQ(r, next(m.begin(), 1)); | |
1563 r = m.lower_bound(8); | |
1564 EXPECT_EQ(r, next(m.begin(), 2)); | |
1565 r = m.lower_bound(10); | |
1566 EXPECT_EQ(r, next(m.begin(), 3)); | |
1567 r = m.lower_bound(12); | |
1568 EXPECT_EQ(r, next(m.begin(), 4)); | |
1569 r = m.lower_bound(14); | |
1570 EXPECT_EQ(r, next(m.begin(), 5)); | |
1571 r = m.lower_bound(16); | |
1572 EXPECT_EQ(r, next(m.begin(), 6)); | |
1573 r = m.lower_bound(18); | |
1574 EXPECT_EQ(r, next(m.begin(), 7)); | |
1575 r = m.lower_bound(20); | |
1576 EXPECT_EQ(r, next(m.begin(), 8)); | |
1577 } | |
1578 } | |
1579 | |
1580 // class flat_set | |
1581 | |
1582 // iterator upper_bound(const key_type& k); | |
1583 // const_iterator upper_bound(const key_type& k) const; | |
1584 | |
1585 TEST(FlatSet, UpperBound) { | |
1586 { | |
1587 typedef int V; | |
1588 typedef base::flat_set<int> M; | |
1589 { | |
1590 typedef M::iterator R; | |
1591 | |
1592 V ar[] = {5, 7, 9, 11, 13, 15, 17, 19}; | |
1593 | |
1594 M m(ar, ar + sizeof(ar) / sizeof(ar[0])); | |
1595 R r = m.upper_bound(5); | |
1596 EXPECT_EQ(r, next(m.begin(), 1)); | |
1597 r = m.upper_bound(7); | |
1598 EXPECT_EQ(r, next(m.begin(), 2)); | |
1599 r = m.upper_bound(9); | |
1600 EXPECT_EQ(r, next(m.begin(), 3)); | |
1601 r = m.upper_bound(11); | |
1602 EXPECT_EQ(r, next(m.begin(), 4)); | |
1603 r = m.upper_bound(13); | |
1604 EXPECT_EQ(r, next(m.begin(), 5)); | |
1605 r = m.upper_bound(15); | |
1606 EXPECT_EQ(r, next(m.begin(), 6)); | |
1607 r = m.upper_bound(17); | |
1608 EXPECT_EQ(r, next(m.begin(), 7)); | |
1609 r = m.upper_bound(19); | |
1610 EXPECT_EQ(r, next(m.begin(), 8)); | |
1611 r = m.upper_bound(4); | |
1612 EXPECT_EQ(r, next(m.begin(), 0)); | |
1613 r = m.upper_bound(6); | |
1614 EXPECT_EQ(r, next(m.begin(), 1)); | |
1615 r = m.upper_bound(8); | |
1616 EXPECT_EQ(r, next(m.begin(), 2)); | |
1617 r = m.upper_bound(10); | |
1618 EXPECT_EQ(r, next(m.begin(), 3)); | |
1619 r = m.upper_bound(12); | |
1620 EXPECT_EQ(r, next(m.begin(), 4)); | |
1621 r = m.upper_bound(14); | |
1622 EXPECT_EQ(r, next(m.begin(), 5)); | |
1623 r = m.upper_bound(16); | |
1624 EXPECT_EQ(r, next(m.begin(), 6)); | |
1625 r = m.upper_bound(18); | |
1626 EXPECT_EQ(r, next(m.begin(), 7)); | |
1627 r = m.upper_bound(20); | |
1628 EXPECT_EQ(r, next(m.begin(), 8)); | |
1629 } | |
1630 { | |
1631 typedef M::const_iterator R; | |
1632 | |
1633 V ar[] = {5, 7, 9, 11, 13, 15, 17, 19}; | |
1634 | |
1635 const M m(ar, ar + sizeof(ar) / sizeof(ar[0])); | |
1636 R r = m.upper_bound(5); | |
1637 EXPECT_EQ(r, next(m.begin(), 1)); | |
1638 r = m.upper_bound(7); | |
1639 EXPECT_EQ(r, next(m.begin(), 2)); | |
1640 r = m.upper_bound(9); | |
1641 EXPECT_EQ(r, next(m.begin(), 3)); | |
1642 r = m.upper_bound(11); | |
1643 EXPECT_EQ(r, next(m.begin(), 4)); | |
1644 r = m.upper_bound(13); | |
1645 EXPECT_EQ(r, next(m.begin(), 5)); | |
1646 r = m.upper_bound(15); | |
1647 EXPECT_EQ(r, next(m.begin(), 6)); | |
1648 r = m.upper_bound(17); | |
1649 EXPECT_EQ(r, next(m.begin(), 7)); | |
1650 r = m.upper_bound(19); | |
1651 EXPECT_EQ(r, next(m.begin(), 8)); | |
1652 r = m.upper_bound(4); | |
1653 EXPECT_EQ(r, next(m.begin(), 0)); | |
1654 r = m.upper_bound(6); | |
1655 EXPECT_EQ(r, next(m.begin(), 1)); | |
1656 r = m.upper_bound(8); | |
1657 EXPECT_EQ(r, next(m.begin(), 2)); | |
1658 r = m.upper_bound(10); | |
1659 EXPECT_EQ(r, next(m.begin(), 3)); | |
1660 r = m.upper_bound(12); | |
1661 EXPECT_EQ(r, next(m.begin(), 4)); | |
1662 r = m.upper_bound(14); | |
1663 EXPECT_EQ(r, next(m.begin(), 5)); | |
1664 r = m.upper_bound(16); | |
1665 EXPECT_EQ(r, next(m.begin(), 6)); | |
1666 r = m.upper_bound(18); | |
1667 EXPECT_EQ(r, next(m.begin(), 7)); | |
1668 r = m.upper_bound(20); | |
1669 EXPECT_EQ(r, next(m.begin(), 8)); | |
1670 } | |
1671 } | |
1672 { | |
1673 typedef int V; | |
1674 typedef base::flat_set<V, std::less<V>> M; | |
1675 typedef M::iterator R; | |
1676 | |
1677 V ar[] = {5, 7, 9, 11, 13, 15, 17, 19}; | |
1678 | |
1679 M m(ar, ar + sizeof(ar) / sizeof(ar[0])); | |
1680 R r = m.upper_bound(5); | |
1681 EXPECT_EQ(r, next(m.begin(), 1)); | |
1682 r = m.upper_bound(7); | |
1683 EXPECT_EQ(r, next(m.begin(), 2)); | |
1684 r = m.upper_bound(9); | |
1685 EXPECT_EQ(r, next(m.begin(), 3)); | |
1686 r = m.upper_bound(11); | |
1687 EXPECT_EQ(r, next(m.begin(), 4)); | |
1688 r = m.upper_bound(13); | |
1689 EXPECT_EQ(r, next(m.begin(), 5)); | |
1690 r = m.upper_bound(15); | |
1691 EXPECT_EQ(r, next(m.begin(), 6)); | |
1692 r = m.upper_bound(17); | |
1693 EXPECT_EQ(r, next(m.begin(), 7)); | |
1694 r = m.upper_bound(19); | |
1695 EXPECT_EQ(r, next(m.begin(), 8)); | |
1696 r = m.upper_bound(4); | |
1697 EXPECT_EQ(r, next(m.begin(), 0)); | |
1698 r = m.upper_bound(6); | |
1699 EXPECT_EQ(r, next(m.begin(), 1)); | |
1700 r = m.upper_bound(8); | |
1701 EXPECT_EQ(r, next(m.begin(), 2)); | |
1702 r = m.upper_bound(10); | |
1703 EXPECT_EQ(r, next(m.begin(), 3)); | |
1704 r = m.upper_bound(12); | |
1705 EXPECT_EQ(r, next(m.begin(), 4)); | |
1706 r = m.upper_bound(14); | |
1707 EXPECT_EQ(r, next(m.begin(), 5)); | |
1708 r = m.upper_bound(16); | |
1709 EXPECT_EQ(r, next(m.begin(), 6)); | |
1710 r = m.upper_bound(18); | |
1711 EXPECT_EQ(r, next(m.begin(), 7)); | |
1712 r = m.upper_bound(20); | |
1713 EXPECT_EQ(r, next(m.begin(), 8)); | |
1714 } | |
1715 } | |
1716 | |
1717 // ---------------------------------------------------------------------------- | |
1718 // Regular type operations | |
1719 | |
1720 // class flat_set | |
1721 | |
1722 // void swap(flat_set& x) | |
1723 // void swap(flat_set& x, flat_set& y) | |
1724 | |
1725 TEST(FlatSetOurs, Swap) { | |
1726 using M = base::flat_set<int>; | |
1727 M lhs{1, 2, 3}; | |
1728 M rhs{4}; | |
1729 swap(lhs, rhs); | |
1730 EXPECT_EQ(lhs.size(), static_cast<M::size_type>(1)); | |
1731 EXPECT_EQ(rhs.size(), static_cast<M::size_type>(3)); | |
1732 EXPECT_EQ(rhs.count(1), static_cast<M::size_type>(1)); | |
1733 EXPECT_EQ(rhs.count(2), static_cast<M::size_type>(1)); | |
1734 EXPECT_EQ(rhs.count(3), static_cast<M::size_type>(1)); | |
1735 EXPECT_EQ(lhs.count(1), static_cast<M::size_type>(0)); | |
1736 EXPECT_EQ(lhs.count(4), static_cast<M::size_type>(1)); | |
1737 | |
1738 rhs.swap(lhs); // member function works too; | |
1739 } | |
1740 | |
1741 // class flat_set | |
1742 | |
1743 // bool operator==(const flat_set& x, const flat_set& y) | |
1744 // bool operator!=(const flat_set& x, const flat_set& y) | |
1745 // bool operator<(const flat_set& x, const flat_set& y) | |
1746 // bool operator>(const flat_set& x, const flat_set& y) | |
1747 // bool operator<=(const flat_set& x, const flat_set& y) | |
1748 // bool operator>=(const flat_set& x, const flat_set& y) | |
1749 | |
1750 TEST(FlatSet, Comparison) { | |
1751 using M = base::flat_set<int>; | |
1752 M biggest{3}; | |
1753 M smallest{1}; | |
1754 M middle{1, 2}; | |
1755 | |
1756 EXPECT_EQ(biggest, biggest); | |
1757 EXPECT_NE(biggest, smallest); | |
1758 EXPECT_LT(smallest, middle); | |
1759 EXPECT_LE(smallest, middle); | |
1760 EXPECT_LE(middle, middle); | |
1761 EXPECT_GT(biggest, middle); | |
1762 EXPECT_GE(biggest, middle); | |
1763 EXPECT_GE(biggest, biggest); | |
1764 } | |
OLD | NEW |