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