Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/c++/15/flat_set
1 // <flat_set> -*- C++ -*- 2 3 // Copyright The GNU Toolchain Authors. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file include/flat_set 26 * This is a Standard C++ Library header. 27 */ 28 29 #ifndef _GLIBCXX_FLAT_SET 30 #define _GLIBCXX_FLAT_SET 1 31 32 #ifdef _GLIBCXX_SYSHDR 33 #pragma GCC system_header 34 #endif 35 36 #define __glibcxx_want_flat_set 37 #include <bits/version.h> 38 39 #ifdef __cpp_lib_flat_set // >= C++23 40 41 #include <compare> 42 #include <initializer_list> 43 44 #include <exception> 45 #include <functional> // not_fn 46 #include <optional> 47 #include <type_traits> 48 #include <vector> 49 #include <bits/functexcept.h> 50 #include <bits/stl_algo.h> 51 #include <bits/stl_function.h> // less 52 #include <bits/stl_pair.h> 53 #include <bits/uses_allocator_args.h> // make_obj_using_allocator 54 #ifdef _GLIBCXX_DEBUG 55 # include <bits/ranges_algo.h> // ranges::is_sorted 56 #endif 57 58 namespace std _GLIBCXX_VISIBILITY(default) 59 { 60 _GLIBCXX_BEGIN_NAMESPACE_VERSION 61 62 template<typename _Key, typename _Compare, 63 typename _KeyContainer> 64 class flat_set; 65 66 template<typename _Key, typename _Compare, 67 typename _KeyContainer> 68 class flat_multiset; 69 70 template<typename _Key, typename _Compare, typename _KeyContainer, bool _Multi> 71 class _Flat_set_impl 72 { 73 static_assert(is_same_v<_Key, typename _KeyContainer::value_type>); 74 static_assert(is_nothrow_swappable_v<_KeyContainer>); 75 76 using _Derived = __conditional_t<_Multi, 77 flat_multiset<_Key, _Compare, _KeyContainer>, 78 flat_set<_Key, _Compare, _KeyContainer>>; 79 using __sorted_t = __conditional_t<_Multi, sorted_equivalent_t, sorted_unique_t>; 80 81 public: 82 using key_type = _Key; 83 using value_type = _Key; 84 using key_compare = _Compare; 85 using value_compare = _Compare; 86 using reference = value_type&; 87 using const_reference = const value_type&; 88 using size_type = typename _KeyContainer::size_type; 89 using difference_type = typename _KeyContainer::difference_type; 90 using iterator = typename _KeyContainer::const_iterator; 91 using const_iterator = typename _KeyContainer::const_iterator; 92 using reverse_iterator = std::reverse_iterator<iterator>; 93 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 94 using container_type = _KeyContainer; 95 96 private: 97 using __emplace_result_t = __conditional_t<_Multi, iterator, pair<iterator, bool>>; 98 99 struct _ClearGuard 100 { 101 container_type* _M_cont; 102 103 _ClearGuard(container_type& __cont) 104 : _M_cont(std::__addressof(__cont)) 105 { } 106 107 ~_ClearGuard() 108 { 109 if (_M_cont) 110 _M_cont->clear(); 111 } 112 113 void 114 _M_disable() 115 { _M_cont = nullptr; } 116 }; 117 118 _ClearGuard 119 _M_make_clear_guard() 120 { return _ClearGuard{this->_M_cont}; } 121 122 public: 123 // constructors 124 _Flat_set_impl() : _Flat_set_impl(key_compare()) { } 125 126 explicit 127 _Flat_set_impl(const key_compare& __comp) 128 : _M_cont(), _M_comp(__comp) 129 { } 130 131 _Flat_set_impl(container_type __cont, const key_compare& __comp = key_compare()) 132 : _M_cont(std::move(__cont)), _M_comp(__comp) 133 { _M_sort_uniq(); } 134 135 _Flat_set_impl(__sorted_t, 136 container_type __cont, const key_compare& __comp = key_compare()) 137 : _M_cont(std::move(__cont)), _M_comp(__comp) 138 { _GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(_M_cont, _M_comp)); } 139 140 template<__has_input_iter_cat _InputIterator> 141 _Flat_set_impl(_InputIterator __first, _InputIterator __last, 142 const key_compare& __comp = key_compare()) 143 : _M_cont(), _M_comp(__comp) 144 { insert(__first, __last); } 145 146 template<__has_input_iter_cat _InputIterator> 147 _Flat_set_impl(__sorted_t __s, 148 _InputIterator __first, _InputIterator __last, 149 const key_compare& __comp = key_compare()) 150 : _M_cont(), _M_comp(__comp) 151 { insert(__s, __first, __last); } 152 153 template<__detail::__container_compatible_range<value_type> _Rg> 154 _Flat_set_impl(from_range_t, _Rg&& __rg) 155 : _Flat_set_impl(from_range, std::forward<_Rg>(__rg), key_compare()) 156 { } 157 158 template<__detail::__container_compatible_range<value_type> _Rg> 159 _Flat_set_impl(from_range_t, _Rg&& __rg, const key_compare& __comp) 160 : _Flat_set_impl(__comp) 161 { insert_range(std::forward<_Rg>(__rg)); } 162 163 _Flat_set_impl(initializer_list<value_type> __il, 164 const key_compare& __comp = key_compare()) 165 : _Flat_set_impl(__il.begin(), __il.end(), __comp) 166 { } 167 168 _Flat_set_impl(__sorted_t __s, 169 initializer_list<value_type> __il, 170 const key_compare& __comp = key_compare()) 171 : _Flat_set_impl(__s, __il.begin(), __il.end(), __comp) 172 { } 173 174 // constructors with allocators 175 176 template<__allocator_for<container_type> _Alloc> 177 explicit 178 _Flat_set_impl(const _Alloc& __a) 179 : _Flat_set_impl(key_compare(), __a) 180 { } 181 182 template<__allocator_for<container_type> _Alloc> 183 _Flat_set_impl(const key_compare& __comp, const _Alloc& __a) 184 : _M_cont(std::make_obj_using_allocator<container_type>(__a)), 185 _M_comp(__comp) 186 { } 187 188 template<__allocator_for<container_type> _Alloc> 189 _Flat_set_impl(const container_type& __cont, const _Alloc& __a) 190 : _Flat_set_impl(__cont, key_compare(), __a) 191 { } 192 193 template<__allocator_for<container_type> _Alloc> 194 _Flat_set_impl(const container_type& __cont, const key_compare& __comp, 195 const _Alloc& __a) 196 : _M_cont(std::make_obj_using_allocator<container_type>(__a, __cont)), 197 _M_comp(__comp) 198 { _M_sort_uniq(); } 199 200 template<__allocator_for<container_type> _Alloc> 201 _Flat_set_impl(__sorted_t __s, const container_type& __cont, const _Alloc& __a) 202 : _Flat_set_impl(__s, __cont, key_compare(), __a) 203 { } 204 205 template<__allocator_for<container_type> _Alloc> 206 _Flat_set_impl(__sorted_t, const container_type& __cont, const key_compare& __comp, 207 const _Alloc& __a) 208 : _M_cont(std::make_obj_using_allocator<container_type>(__a, __cont)), 209 _M_comp(__comp) 210 { _GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(_M_cont, _M_comp)); } 211 212 template<__allocator_for<container_type> _Alloc> 213 _Flat_set_impl(const _Derived& __x, const _Alloc& __a) 214 : _M_cont(std::make_obj_using_allocator<container_type>(__a, __x._M_cont)), 215 _M_comp(__x._M_comp) 216 { } 217 218 template<__allocator_for<container_type> _Alloc> 219 _Flat_set_impl(_Derived&& __x, const _Alloc& __a) 220 : _M_cont(std::make_obj_using_allocator<container_type>(__a, std::move(__x._M_cont))), 221 _M_comp(__x._M_comp) 222 { } 223 224 template<__has_input_iter_cat _InputIterator, __allocator_for<container_type> _Alloc> 225 _Flat_set_impl(_InputIterator __first, _InputIterator __last, 226 const _Alloc& __a) 227 : _Flat_set_impl(std::move(__first), std::move(__last), key_compare(), __a) 228 { } 229 230 template<__has_input_iter_cat _InputIterator, __allocator_for<container_type> _Alloc> 231 _Flat_set_impl(_InputIterator __first, _InputIterator __last, 232 const key_compare& __comp, 233 const _Alloc& __a) 234 : _Flat_set_impl(__comp, __a) 235 { insert(__first, __last); } 236 237 template<__has_input_iter_cat _InputIterator, __allocator_for<container_type> _Alloc> 238 _Flat_set_impl(__sorted_t __s, 239 _InputIterator __first, _InputIterator __last, 240 const _Alloc& __a) 241 : _Flat_set_impl(__s, std::move(__first), std::move(__last), key_compare(), __a) 242 { } 243 244 template<__has_input_iter_cat _InputIterator, __allocator_for<container_type> _Alloc> 245 _Flat_set_impl(__sorted_t __s, 246 _InputIterator __first, _InputIterator __last, 247 const key_compare& __comp, 248 const _Alloc& __a) 249 : _Flat_set_impl(__comp, __a) 250 { insert(__s, __first, __last); } 251 252 template<__detail::__container_compatible_range<value_type> _Rg, 253 __allocator_for<container_type> _Alloc> 254 _Flat_set_impl(from_range_t, _Rg&& __rg, 255 const _Alloc& __a) 256 : _Flat_set_impl(from_range, std::forward<_Rg>(__rg), key_compare(), __a) 257 { } 258 259 template<__detail::__container_compatible_range<value_type> _Rg, 260 __allocator_for<container_type> _Alloc> 261 _Flat_set_impl(from_range_t, _Rg&& __rg, 262 const key_compare& __comp, 263 const _Alloc& __a) 264 : _Flat_set_impl(__comp, __a) 265 { insert_range(std::forward<_Rg>(__rg)); } 266 267 template<__allocator_for<container_type> _Alloc> 268 _Flat_set_impl(initializer_list<value_type> __il, 269 const _Alloc& __a) 270 : _Flat_set_impl(__il, key_compare(), __a) 271 { } 272 273 template<__allocator_for<container_type> _Alloc> 274 _Flat_set_impl(initializer_list<value_type> __il, 275 const key_compare& __comp, 276 const _Alloc& __a) 277 : _Flat_set_impl(__il.begin(), __il.end(), __comp, __a) 278 { } 279 280 template<__allocator_for<container_type> _Alloc> 281 _Flat_set_impl(__sorted_t __s, 282 initializer_list<value_type> __il, 283 const _Alloc& __a) 284 : _Flat_set_impl(__s, __il.begin(), __il.end(), key_compare(), __a) 285 { } 286 287 template<__allocator_for<container_type> _Alloc> 288 _Flat_set_impl(__sorted_t __s, 289 initializer_list<value_type> __il, 290 const key_compare& __comp, 291 const _Alloc& __a) 292 : _Flat_set_impl(__s, __il.begin(), __il.end(), __comp, __a) 293 { } 294 295 _Derived& 296 operator=(initializer_list<value_type> __il) 297 { 298 auto __guard = _M_make_clear_guard(); 299 _M_cont = __il; 300 _M_sort_uniq(); 301 __guard._M_disable(); 302 return static_cast<_Derived&>(*this); 303 } 304 305 // iterators 306 const_iterator 307 begin() const noexcept 308 { return _M_cont.begin(); } 309 310 const_iterator 311 end() const noexcept 312 { return _M_cont.end(); } 313 314 const_reverse_iterator 315 rbegin() const noexcept 316 { return const_reverse_iterator(end()); } 317 318 const_reverse_iterator 319 rend() const noexcept 320 { return const_reverse_iterator(begin()); } 321 322 const_iterator 323 cbegin() const noexcept 324 { return begin(); } 325 326 const_iterator 327 cend() const noexcept 328 { return end(); } 329 330 const_reverse_iterator 331 crbegin() const noexcept 332 { return rbegin(); } 333 334 const_reverse_iterator 335 crend() const noexcept 336 { return rend(); } 337 338 // capacity 339 [[nodiscard]] 340 bool 341 empty() const noexcept 342 { return _M_cont.empty(); } 343 344 size_type 345 size() const noexcept 346 { return _M_cont.size(); } 347 348 size_type 349 max_size() const noexcept 350 { return _M_cont.max_size(); } 351 352 // modifiers 353 template<typename _Arg, typename... _Args> 354 pair<iterator, bool> 355 _M_try_emplace(optional<const_iterator> __hint, _Arg&& __arg, _Args&&... __args) 356 { 357 // TODO: Simplify and audit the hint handling. 358 auto&& __k = [&] -> decltype(auto) { 359 if constexpr (sizeof...(_Args) == 0 360 && same_as<remove_cvref_t<_Arg>, value_type>) 361 return std::forward<_Arg>(__arg); 362 else 363 return value_type(std::forward<_Arg>(__arg), 364 std::forward<_Args>(__args)...); 365 }(); 366 typename container_type::iterator __it; 367 int __r = -1, __s = -1; 368 if (__hint.has_value() 369 && (__hint == cbegin() 370 || (__r = !_M_comp(__k, (*__hint)[-1]))) // k >= hint[-1] 371 && (__hint == cend() 372 || (__s = !_M_comp((*__hint)[0], __k)))) // k <= hint[0] 373 { 374 __it = _M_cont.begin() + (*__hint - begin()); 375 if constexpr (!_Multi) 376 if (__r == 1 && !_M_comp(__it[-1], __k)) // k == hint[-1] 377 return {__it - 1, false}; 378 } 379 else 380 { 381 auto __first = _M_cont.begin(); 382 auto __last = _M_cont.end(); 383 if (__r == 1) // k >= hint[-1] 384 __first += *__hint - _M_cont.begin(); 385 else if (__r == 0) // k < __hint[-1] 386 __last = __first + (*__hint - _M_cont.begin()); 387 if constexpr (_Multi) 388 { 389 if (__s == 0) // hint[0] < k 390 // Insert before the leftmost equivalent key. 391 __it = std::lower_bound(__first, __last, __k, _M_comp); 392 else 393 // Insert after the rightmost equivalent key. 394 __it = std::upper_bound(std::make_reverse_iterator(__last), 395 std::make_reverse_iterator(__first), 396 __k, std::not_fn(_M_comp)).base(); 397 } 398 else 399 __it = std::lower_bound(__first, __last, __k, _M_comp); 400 } 401 402 if constexpr (!_Multi) 403 if (__it != _M_cont.end() && !_M_comp(__k, __it[0])) 404 return {__it, false}; 405 406 auto __guard = _M_make_clear_guard(); 407 __it = _M_cont.insert(__it, std::forward<decltype(__k)>(__k)); 408 __guard._M_disable(); 409 return {__it, true}; 410 } 411 412 template<typename... _Args> 413 pair<iterator, bool> 414 _M_try_emplace(optional<const_iterator> __hint) 415 { return _M_try_emplace(__hint, value_type()); } 416 417 template<typename... _Args> 418 requires is_constructible_v<value_type, _Args...> 419 __emplace_result_t 420 emplace(_Args&&... __args) 421 { 422 auto __r = _M_try_emplace(nullopt, std::forward<_Args>(__args)...); 423 if constexpr (_Multi) 424 return __r.first; 425 else 426 return __r; 427 } 428 429 template<typename... _Args> 430 iterator 431 emplace_hint(const_iterator __position, _Args&&... __args) 432 { return _M_try_emplace(__position, std::forward<_Args>(__args)...).first; } 433 434 __emplace_result_t 435 insert(const value_type& __x) 436 { return emplace(__x); } 437 438 __emplace_result_t 439 insert(value_type&& __x) 440 { return emplace(std::move(__x)); } 441 442 iterator 443 insert(const_iterator __position, const value_type& __x) 444 { return emplace_hint(__position, __x); } 445 446 iterator 447 insert(const_iterator __position, value_type&& __x) 448 { return emplace_hint(__position, std::move(__x)); } 449 450 template<typename _Arg> 451 requires is_constructible_v<value_type, _Arg> 452 __emplace_result_t 453 insert(_Arg&& __x) 454 { return emplace(std::forward<_Arg>(__x)); } 455 456 template<typename _Arg> 457 requires is_constructible_v<value_type, _Arg> 458 iterator 459 insert(const_iterator __position, _Arg&& __x) 460 { return emplace_hint(__position, std::forward<_Arg>(__x)); } 461 462 template<__has_input_iter_cat _InputIterator> 463 void 464 insert(_InputIterator __first, _InputIterator __last) 465 { 466 auto __guard = _M_make_clear_guard(); 467 auto __it = _M_cont.insert(_M_cont.end(), __first, __last); 468 std::sort(__it, _M_cont.end(), _M_comp); 469 std::inplace_merge(_M_cont.begin(), __it, _M_cont.end(), _M_comp); 470 if constexpr (!_Multi) 471 _M_unique(); 472 __guard._M_disable(); 473 } 474 475 template<__has_input_iter_cat _InputIterator> 476 void 477 insert(__sorted_t, _InputIterator __first, _InputIterator __last) 478 { 479 auto __guard = _M_make_clear_guard(); 480 auto __it = _M_cont.insert(_M_cont.end(), __first, __last); 481 std::inplace_merge(_M_cont.begin(), __it, _M_cont.end(), _M_comp); 482 if constexpr (!_Multi) 483 _M_unique(); 484 __guard._M_disable(); 485 } 486 487 template<__detail::__container_compatible_range<value_type> _Rg> 488 void 489 insert_range(_Rg&& __rg) 490 { 491 auto __guard = _M_make_clear_guard(); 492 typename container_type::iterator __it; 493 if constexpr (requires { _M_cont.insert_range(_M_cont.end(), __rg); }) 494 __it = _M_cont.insert_range(_M_cont.end(), __rg); 495 else if constexpr (ranges::common_range<_Rg> 496 && __has_input_iter_cat<ranges::iterator_t<_Rg>>) 497 __it = _M_cont.insert(_M_cont.end(), ranges::begin(__rg), ranges::end(__rg)); 498 else 499 { 500 size_type __n = size(); 501 auto __first = ranges::begin(__rg); 502 auto __last = ranges::end(__rg); 503 for (; __first != __last; ++__first) 504 _M_cont.emplace_back(*__first); 505 __it = _M_cont.begin() + __n; 506 } 507 std::sort(__it, _M_cont.end(), _M_comp); 508 std::inplace_merge(_M_cont.begin(), __it, _M_cont.end(), _M_comp); 509 if constexpr (!_Multi) 510 _M_unique(); 511 __guard._M_disable(); 512 } 513 514 void 515 insert(initializer_list<value_type> __il) 516 { insert(__il.begin(), __il.end()); } 517 518 void 519 insert(__sorted_t __s, initializer_list<value_type> __il) 520 { insert(__s, __il.begin(), __il.end()); } 521 522 container_type 523 extract() && 524 { 525 auto __guard = _M_make_clear_guard(); 526 return std::move(_M_cont); 527 } 528 529 void 530 replace(container_type&& __cont) 531 { 532 _GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(__cont, _M_comp)); 533 auto __guard = _M_make_clear_guard(); 534 _M_cont = std::move(__cont); 535 __guard._M_disable(); 536 } 537 538 iterator 539 erase(const_iterator __position) 540 { return _M_cont.erase(__position); } 541 542 size_type 543 erase(const key_type& __x) 544 { return erase<const key_type&>(__x); } 545 546 template<typename _Key2> 547 requires same_as<remove_cvref_t<_Key2>, _Key> 548 || (__transparent_comparator<_Compare> 549 && !is_convertible_v<_Key2, iterator> 550 && !is_convertible_v<_Key2, const_iterator>) 551 size_type 552 erase(_Key2&& __x) 553 { 554 auto [__first, __last] = equal_range(std::forward<_Key2>(__x)); 555 auto __n = __last - __first; 556 erase(__first, __last); 557 return __n; 558 } 559 560 iterator 561 erase(const_iterator __first, const_iterator __last) 562 { return _M_cont.erase(__first, __last); } 563 564 void 565 swap(_Derived& __x) noexcept 566 { 567 using std::swap; 568 swap(_M_cont, __x._M_cont); 569 swap(_M_comp, __x._M_comp); 570 } 571 572 void 573 clear() noexcept 574 { _M_cont.clear(); } 575 576 // observers 577 [[nodiscard]] 578 key_compare 579 key_comp() const 580 { return _M_comp; } 581 582 [[nodiscard]] 583 value_compare 584 value_comp() const 585 { return _M_comp; } 586 587 // set operations 588 [[nodiscard]] 589 iterator 590 find(const key_type& __x) 591 { return find<key_type>(__x); } 592 593 [[nodiscard]] 594 const_iterator 595 find(const key_type& __x) const 596 { return find<key_type>(__x); } 597 598 template<typename _Key2> 599 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> 600 [[nodiscard]] 601 iterator 602 find(const _Key2& __x) 603 { 604 auto __it = lower_bound(__x); 605 if (__it != end() && !_M_comp(__x, *__it)) 606 return __it; 607 else 608 return end(); 609 } 610 611 template<typename _Key2> 612 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> 613 [[nodiscard]] 614 const_iterator 615 find(const _Key2& __x) const 616 { 617 auto __it = lower_bound(__x); 618 if (__it != cend() && !_M_comp(__x, *__it)) 619 return __it; 620 else 621 return cend(); 622 } 623 624 [[nodiscard]] 625 size_type 626 count(const key_type& __x) const 627 { return count<key_type>(__x); } 628 629 template<typename _Key2> 630 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> 631 [[nodiscard]] 632 size_type 633 count(const _Key2& __x) const 634 { 635 if constexpr (!_Multi) 636 return contains<_Key2>(__x); 637 else 638 { 639 auto [__first, __last] = equal_range(__x); 640 return __last - __first; 641 } 642 } 643 644 [[nodiscard]] 645 bool 646 contains(const key_type& __x) const 647 { return contains<key_type>(__x); } 648 649 template<typename _Key2> 650 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> 651 [[nodiscard]] 652 bool 653 contains(const _Key2& __x) const 654 { return find(__x) != cend(); } 655 656 [[nodiscard]] 657 iterator 658 lower_bound(const key_type& __x) 659 { return lower_bound<key_type>(__x); } 660 661 [[nodiscard]] 662 const_iterator 663 lower_bound(const key_type& __x) const 664 { return lower_bound<key_type>(__x); } 665 666 template<typename _Key2> 667 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> 668 [[nodiscard]] 669 iterator 670 lower_bound(const _Key2& __x) 671 { return std::lower_bound(begin(), end(), __x, _M_comp); } 672 673 template<typename _Key2> 674 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> 675 [[nodiscard]] 676 const_iterator 677 lower_bound(const _Key2& __x) const 678 { return std::lower_bound(begin(), end(), __x, _M_comp); } 679 680 [[nodiscard]] 681 iterator 682 upper_bound(const key_type& __x) 683 { return upper_bound<key_type>(__x); } 684 685 [[nodiscard]] 686 const_iterator 687 upper_bound(const key_type& __x) const 688 { return upper_bound<key_type>(__x); } 689 690 template<typename _Key2> 691 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> 692 [[nodiscard]] 693 iterator 694 upper_bound(const _Key2& __x) 695 { return std::upper_bound(begin(), end(), __x, _M_comp); } 696 697 template<typename _Key2> 698 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> 699 [[nodiscard]] 700 const_iterator 701 upper_bound(const _Key2& __x) const 702 { return std::upper_bound(begin(), end(), __x, _M_comp); } 703 704 [[nodiscard]] 705 pair<iterator, iterator> 706 equal_range(const key_type& __x) 707 { return equal_range<key_type>(__x); } 708 709 [[nodiscard]] 710 pair<const_iterator, const_iterator> 711 equal_range(const key_type& __x) const 712 { return equal_range<key_type>(__x); } 713 714 template<typename _Key2> 715 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> 716 [[nodiscard]] 717 pair<iterator, iterator> 718 equal_range(const _Key2& __x) 719 { return std::equal_range(begin(), end(), __x, _M_comp); } 720 721 template<typename _Key2> 722 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> 723 [[nodiscard]] 724 pair<const_iterator, const_iterator> 725 equal_range(const _Key2& __x) const 726 { return std::equal_range(begin(), end(), __x, _M_comp); } 727 728 [[nodiscard]] 729 friend bool 730 operator==(const _Derived& __x, const _Derived& __y) 731 { return std::equal(__x.begin(), __x.end(), __y.begin(), __y.end()); } 732 733 template<typename _Up = value_type> 734 [[nodiscard]] 735 friend __detail::__synth3way_t<_Up> 736 operator<=>(const _Derived& __x, const _Derived& __y) 737 { 738 return std::lexicographical_compare_three_way(__x.begin(), __x.end(), 739 __y.begin(), __y.end(), 740 __detail::__synth3way); 741 } 742 743 friend void 744 swap(_Derived& __x, _Derived& __y) noexcept 745 { return __x.swap(__y); } 746 747 template<typename _Predicate> 748 size_type 749 _M_erase_if(_Predicate __pred) 750 { 751 auto __guard = _M_make_clear_guard(); 752 auto __first = _M_cont.begin(); 753 auto __last = _M_cont.end(); 754 __first = std::remove_if(__first, __last, __pred); 755 auto __n = __last - __first; 756 erase(__first, __last); 757 __guard._M_disable(); 758 return __n; 759 } 760 761 private: 762 container_type _M_cont; 763 [[no_unique_address]] _Compare _M_comp; 764 765 void 766 _M_sort_uniq() 767 { 768 std::sort(_M_cont.begin(), _M_cont.end(), _M_comp); 769 if constexpr (!_Multi) 770 _M_unique(); 771 } 772 773 void 774 _M_unique() requires (!_Multi) 775 { 776 struct __key_equiv 777 { 778 __key_equiv(key_compare __c) : _M_comp(__c) { } 779 780 bool 781 operator()(const_reference __x, const_reference __y) const 782 { return !_M_comp(__x, __y) && !_M_comp(__y, __x); } 783 784 [[no_unique_address]] key_compare _M_comp; 785 }; 786 787 auto __first = _M_cont.begin(); 788 auto __last = _M_cont.end(); 789 __first = std::unique(__first, __last, __key_equiv(_M_comp)); 790 _M_cont.erase(__first, __last); 791 } 792 }; 793 794 /* Class template flat_set - container adaptor 795 * 796 * @ingroup 797 */ 798 template<typename _Key, typename _Compare = less<_Key>, 799 typename _KeyContainer = vector<_Key>> 800 class flat_set 801 : private _Flat_set_impl<_Key, _Compare, _KeyContainer, false> 802 { 803 using _Impl = _Flat_set_impl<_Key, _Compare, _KeyContainer, false>; 804 friend _Impl; 805 806 public: 807 // types 808 using typename _Impl::key_type; 809 using typename _Impl::value_type; 810 using typename _Impl::key_compare; 811 using typename _Impl::reference; 812 using typename _Impl::const_reference; 813 using typename _Impl::size_type; 814 using typename _Impl::difference_type; 815 using typename _Impl::iterator; 816 using typename _Impl::const_iterator; 817 using typename _Impl::reverse_iterator; 818 using typename _Impl::const_reverse_iterator; 819 using typename _Impl::container_type; 820 using typename _Impl::value_compare; 821 822 // constructors 823 using _Impl::_Impl; 824 825 // iterators 826 using _Impl::begin; 827 using _Impl::end; 828 using _Impl::rbegin; 829 using _Impl::rend; 830 831 using _Impl::cbegin; 832 using _Impl::cend; 833 using _Impl::crbegin; 834 using _Impl::crend; 835 836 // capacity 837 using _Impl::empty; 838 using _Impl::size; 839 using _Impl::max_size; 840 841 // modifiers 842 using _Impl::emplace; 843 using _Impl::emplace_hint; 844 using _Impl::insert; 845 using _Impl::insert_range; 846 using _Impl::extract; 847 using _Impl::replace; 848 using _Impl::erase; 849 using _Impl::swap; 850 using _Impl::clear; 851 852 // observers 853 using _Impl::key_comp; 854 using _Impl::value_comp; 855 856 // set operations 857 using _Impl::find; 858 using _Impl::count; 859 using _Impl::contains; 860 using _Impl::lower_bound; 861 using _Impl::upper_bound; 862 using _Impl::equal_range; 863 864 using _Impl::_M_erase_if; 865 }; 866 867 template<typename _KeyContainer, 868 __not_allocator_like _Compare = less<typename _KeyContainer::value_type>> 869 flat_set(_KeyContainer, _Compare = _Compare()) 870 -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>; 871 872 template<typename _KeyContainer, __allocator_for<_KeyContainer> _Alloc> 873 flat_set(_KeyContainer, _Alloc) 874 -> flat_set<typename _KeyContainer::value_type, 875 less<typename _KeyContainer::value_type>, _KeyContainer>; 876 877 template<typename _KeyContainer, __not_allocator_like _Compare, 878 __allocator_for<_KeyContainer> _Alloc> 879 flat_set(_KeyContainer, _Compare, _Alloc) 880 -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>; 881 882 template<typename _KeyContainer, 883 __not_allocator_like _Compare = less<typename _KeyContainer::value_type>> 884 flat_set(sorted_unique_t, _KeyContainer, _Compare = _Compare()) 885 -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>; 886 887 template<typename _KeyContainer, __allocator_for<_KeyContainer> _Alloc> 888 flat_set(sorted_unique_t, _KeyContainer, _Alloc) 889 -> flat_set<typename _KeyContainer::value_type, 890 less<typename _KeyContainer::value_type>, _KeyContainer>; 891 892 template<typename _KeyContainer, __not_allocator_like _Compare, 893 __allocator_for<_KeyContainer> _Alloc> 894 flat_set(sorted_unique_t, _KeyContainer, _Compare, _Alloc) 895 -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>; 896 897 template<__has_input_iter_cat _InputIterator, 898 __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>> 899 flat_set(_InputIterator, _InputIterator, _Compare = _Compare()) 900 -> flat_set<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>; 901 902 template<__has_input_iter_cat _InputIterator, 903 __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>> 904 flat_set(sorted_unique_t, _InputIterator, _InputIterator, _Compare = _Compare()) 905 -> flat_set<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>; 906 907 template<ranges::input_range _Rg, 908 __not_allocator_like _Compare = less<ranges::range_value_t<_Rg>>, 909 __allocator_like _Alloc = allocator<ranges::range_value_t<_Rg>>> 910 flat_set(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc()) 911 -> flat_set<ranges::range_value_t<_Rg>, _Compare, 912 vector<ranges::range_value_t<_Rg>, 913 __alloc_rebind<_Alloc, ranges::range_value_t<_Rg>>>>; 914 915 template<ranges::input_range _Rg, __allocator_like _Alloc> 916 flat_set(from_range_t, _Rg&&, _Alloc) 917 -> flat_set<ranges::range_value_t<_Rg>, less<ranges::range_value_t<_Rg>>, 918 vector<ranges::range_value_t<_Rg>, 919 __alloc_rebind<_Alloc, ranges::range_value_t<_Rg>>>>; 920 921 template<typename _Key, __not_allocator_like _Compare = less<_Key>> 922 flat_set(initializer_list<_Key>, _Compare = _Compare()) 923 -> flat_set<_Key, _Compare>; 924 925 template<typename _Key, __not_allocator_like _Compare = less<_Key>> 926 flat_set(sorted_unique_t, initializer_list<_Key>, _Compare = _Compare()) 927 -> flat_set<_Key, _Compare>; 928 929 template<typename _Key, typename _Compare, 930 typename _KeyContainer, typename _Alloc> 931 struct uses_allocator<flat_set<_Key, _Compare, _KeyContainer>, _Alloc> 932 : bool_constant<uses_allocator_v<_KeyContainer, _Alloc>> 933 { }; 934 935 template<typename _Key, typename _Compare, typename _KeyContainer, 936 typename _Predicate> 937 typename flat_set<_Key, _Compare, _KeyContainer>::size_type 938 erase_if(flat_set<_Key, _Compare, _KeyContainer>& __c, _Predicate __pred) 939 { return __c._M_erase_if(std::move(__pred)); } 940 941 /* Class template flat_multiset - container adaptor 942 * 943 * @ingroup 944 */ 945 template<typename _Key, typename _Compare = less<_Key>, 946 typename _KeyContainer = vector<_Key>> 947 class flat_multiset 948 : private _Flat_set_impl<_Key, _Compare, _KeyContainer, true> 949 { 950 using _Impl = _Flat_set_impl<_Key, _Compare, _KeyContainer, true>; 951 friend _Impl; 952 953 public: 954 // types 955 using typename _Impl::key_type; 956 using typename _Impl::value_type; 957 using typename _Impl::key_compare; 958 using typename _Impl::reference; 959 using typename _Impl::const_reference; 960 using typename _Impl::size_type; 961 using typename _Impl::difference_type; 962 using typename _Impl::iterator; 963 using typename _Impl::const_iterator; 964 using typename _Impl::reverse_iterator; 965 using typename _Impl::const_reverse_iterator; 966 using typename _Impl::container_type; 967 using typename _Impl::value_compare; 968 969 // constructors 970 using _Impl::_Impl; 971 972 // iterators 973 using _Impl::begin; 974 using _Impl::end; 975 using _Impl::rbegin; 976 using _Impl::rend; 977 978 using _Impl::cbegin; 979 using _Impl::cend; 980 using _Impl::crbegin; 981 using _Impl::crend; 982 983 // capacity 984 using _Impl::empty; 985 using _Impl::size; 986 using _Impl::max_size; 987 988 // modifiers 989 using _Impl::emplace; 990 using _Impl::emplace_hint; 991 using _Impl::insert; 992 using _Impl::insert_range; 993 using _Impl::extract; 994 using _Impl::replace; 995 using _Impl::erase; 996 using _Impl::swap; 997 using _Impl::clear; 998 999 // observers 1000 using _Impl::key_comp; 1001 using _Impl::value_comp; 1002 1003 // set operations 1004 using _Impl::find; 1005 using _Impl::count; 1006 using _Impl::contains; 1007 using _Impl::lower_bound; 1008 using _Impl::upper_bound; 1009 using _Impl::equal_range; 1010 1011 using _Impl::_M_erase_if; 1012 }; 1013 1014 template<typename _KeyContainer, 1015 __not_allocator_like _Compare = less<typename _KeyContainer::value_type>> 1016 flat_multiset(_KeyContainer, _Compare = _Compare()) 1017 -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>; 1018 1019 template<typename _KeyContainer, __allocator_for<_KeyContainer> _Alloc> 1020 flat_multiset(_KeyContainer, _Alloc) 1021 -> flat_multiset<typename _KeyContainer::value_type, 1022 less<typename _KeyContainer::value_type>, _KeyContainer>; 1023 1024 template<typename _KeyContainer, __not_allocator_like _Compare, 1025 __allocator_for<_KeyContainer> _Alloc> 1026 flat_multiset(_KeyContainer, _Compare, _Alloc) 1027 -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>; 1028 1029 template<typename _KeyContainer, 1030 __not_allocator_like _Compare = less<typename _KeyContainer::value_type>> 1031 flat_multiset(sorted_equivalent_t, _KeyContainer, _Compare = _Compare()) 1032 -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>; 1033 1034 template<typename _KeyContainer, __allocator_for<_KeyContainer> _Alloc> 1035 flat_multiset(sorted_equivalent_t, _KeyContainer, _Alloc) 1036 -> flat_multiset<typename _KeyContainer::value_type, 1037 less<typename _KeyContainer::value_type>, _KeyContainer>; 1038 1039 template<typename _KeyContainer, __not_allocator_like _Compare, 1040 __allocator_for<_KeyContainer> _Alloc> 1041 flat_multiset(sorted_equivalent_t, _KeyContainer, _Compare, _Alloc) 1042 -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>; 1043 1044 template<__has_input_iter_cat _InputIterator, 1045 __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>> 1046 flat_multiset(_InputIterator, _InputIterator, _Compare = _Compare()) 1047 -> flat_multiset<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>; 1048 1049 template<__has_input_iter_cat _InputIterator, 1050 __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>> 1051 flat_multiset(sorted_equivalent_t, _InputIterator, _InputIterator, _Compare = _Compare()) 1052 -> flat_multiset<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>; 1053 1054 template<ranges::input_range _Rg, 1055 __not_allocator_like _Compare = less<ranges::range_value_t<_Rg>>, 1056 __allocator_like _Alloc = allocator<ranges::range_value_t<_Rg>>> 1057 flat_multiset(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc()) 1058 -> flat_multiset<ranges::range_value_t<_Rg>, _Compare, 1059 vector<ranges::range_value_t<_Rg>, 1060 __alloc_rebind<_Alloc, ranges::range_value_t<_Rg>>>>; 1061 1062 template<ranges::input_range _Rg, __allocator_like _Alloc> 1063 flat_multiset(from_range_t, _Rg&&, _Alloc) 1064 -> flat_multiset<ranges::range_value_t<_Rg>, less<ranges::range_value_t<_Rg>>, 1065 vector<ranges::range_value_t<_Rg>, 1066 __alloc_rebind<_Alloc, ranges::range_value_t<_Rg>>>>; 1067 1068 template<typename _Key, __not_allocator_like _Compare = less<_Key>> 1069 flat_multiset(initializer_list<_Key>, _Compare = _Compare()) 1070 -> flat_multiset<_Key, _Compare>; 1071 1072 template<typename _Key, __not_allocator_like _Compare = less<_Key>> 1073 flat_multiset(sorted_equivalent_t, initializer_list<_Key>, _Compare = _Compare()) 1074 -> flat_multiset<_Key, _Compare>; 1075 1076 template<typename _Key, typename _Compare, 1077 typename _KeyContainer, typename _Alloc> 1078 struct uses_allocator<flat_multiset<_Key, _Compare, _KeyContainer>, _Alloc> 1079 : bool_constant<uses_allocator_v<_KeyContainer, _Alloc>> 1080 { }; 1081 1082 template<typename _Key, typename _Compare, typename _KeyContainer, 1083 typename _Predicate> 1084 typename flat_multiset<_Key, _Compare, _KeyContainer>::size_type 1085 erase_if(flat_multiset<_Key, _Compare, _KeyContainer>& __c, _Predicate __pred) 1086 { return __c._M_erase_if(std::move(__pred)); } 1087 1088 _GLIBCXX_END_NAMESPACE_VERSION 1089 } // namespace std 1090 #endif // __cpp_lib_flat_set 1091 #endif // _GLIBCXX_FLAT_SET
