Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/c++/15/bits/stl_set.h
1 // Set implementation -*- C++ -*- 2 3 // Copyright (C) 2001-2025 Free Software Foundation, Inc. 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 /* 26 * 27 * Copyright (c) 1994 28 * Hewlett-Packard Company 29 * 30 * Permission to use, copy, modify, distribute and sell this software 31 * and its documentation for any purpose is hereby granted without fee, 32 * provided that the above copyright notice appear in all copies and 33 * that both that copyright notice and this permission notice appear 34 * in supporting documentation. Hewlett-Packard Company makes no 35 * representations about the suitability of this software for any 36 * purpose. It is provided "as is" without express or implied warranty. 37 * 38 * 39 * Copyright (c) 1996,1997 40 * Silicon Graphics Computer Systems, Inc. 41 * 42 * Permission to use, copy, modify, distribute and sell this software 43 * and its documentation for any purpose is hereby granted without fee, 44 * provided that the above copyright notice appear in all copies and 45 * that both that copyright notice and this permission notice appear 46 * in supporting documentation. Silicon Graphics makes no 47 * representations about the suitability of this software for any 48 * purpose. It is provided "as is" without express or implied warranty. 49 */ 50 51 /** @file bits/stl_set.h 52 * This is an internal header file, included by other library headers. 53 * Do not attempt to use it directly. @headername{set} 54 */ 55 56 #ifndef _STL_SET_H 57 #define _STL_SET_H 1 58 59 #include <bits/concept_check.h> 60 #if __cplusplus >= 201103L 61 #include <initializer_list> 62 #endif 63 #if __glibcxx_containers_ranges // C++ >= 23 64 # include <bits/ranges_base.h> // ranges::begin, ranges::distance etc. 65 #endif 66 67 namespace std _GLIBCXX_VISIBILITY(default) 68 { 69 _GLIBCXX_BEGIN_NAMESPACE_VERSION 70 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 71 72 template<typename _Key, typename _Compare, typename _Alloc> 73 class multiset; 74 75 /** 76 * @brief A standard container made up of unique keys, which can be 77 * retrieved in logarithmic time. 78 * 79 * @ingroup associative_containers 80 * @headerfile set 81 * @since C++98 82 * 83 * @tparam _Key Type of key objects. 84 * @tparam _Compare Comparison function object type, defaults to less<_Key>. 85 * @tparam _Alloc Allocator type, defaults to allocator<_Key>. 86 * 87 * Meets the requirements of a <a href="tables.html#65">container</a>, a 88 * <a href="tables.html#66">reversible container</a>, and an 89 * <a href="tables.html#69">associative container</a> (using unique keys). 90 * 91 * Sets support bidirectional iterators. 92 * 93 * The private tree data is declared exactly the same way for set and 94 * multiset; the distinction is made entirely in how the tree functions are 95 * called (*_unique versus *_equal, same as the standard). 96 */ 97 template<typename _Key, typename _Compare = std::less<_Key>, 98 typename _Alloc = std::allocator<_Key> > 99 class set 100 { 101 #ifdef _GLIBCXX_CONCEPT_CHECKS 102 // concept requirements 103 typedef typename _Alloc::value_type _Alloc_value_type; 104 # if __cplusplus < 201103L 105 __glibcxx_class_requires(_Key, _SGIAssignableConcept) 106 # endif 107 __glibcxx_class_requires4(_Compare, bool, _Key, _Key, 108 _BinaryFunctionConcept) 109 __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept) 110 #endif 111 112 #if __cplusplus >= 201103L 113 static_assert(is_same<typename remove_cv<_Key>::type, _Key>::value, 114 "std::set must have a non-const, non-volatile value_type"); 115 # if __cplusplus > 201703L || defined __STRICT_ANSI__ 116 static_assert(is_same<typename _Alloc::value_type, _Key>::value, 117 "std::set must have the same value_type as its allocator"); 118 # endif 119 #endif 120 121 public: 122 // typedefs: 123 ///@{ 124 /// Public typedefs. 125 typedef _Key key_type; 126 typedef _Key value_type; 127 typedef _Compare key_compare; 128 typedef _Compare value_compare; 129 typedef _Alloc allocator_type; 130 ///@} 131 132 private: 133 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 134 rebind<_Key>::other _Key_alloc_type; 135 136 typedef _Rb_tree<key_type, value_type, _Identity<value_type>, 137 key_compare, _Key_alloc_type> _Rep_type; 138 _Rep_type _M_t; // Red-black tree representing set. 139 140 typedef __gnu_cxx::__alloc_traits<_Key_alloc_type> _Alloc_traits; 141 142 public: 143 ///@{ 144 /// Iterator-related typedefs. 145 typedef typename _Alloc_traits::pointer pointer; 146 typedef typename _Alloc_traits::const_pointer const_pointer; 147 typedef typename _Alloc_traits::reference reference; 148 typedef typename _Alloc_traits::const_reference const_reference; 149 // _GLIBCXX_RESOLVE_LIB_DEFECTS 150 // DR 103. set::iterator is required to be modifiable, 151 // but this allows modification of keys. 152 typedef typename _Rep_type::const_iterator iterator; 153 typedef typename _Rep_type::const_iterator const_iterator; 154 typedef typename _Rep_type::const_reverse_iterator reverse_iterator; 155 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 156 typedef typename _Rep_type::size_type size_type; 157 typedef typename _Rep_type::difference_type difference_type; 158 ///@} 159 160 #ifdef __glibcxx_node_extract // >= C++17 161 using node_type = typename _Rep_type::node_type; 162 using insert_return_type = typename _Rep_type::insert_return_type; 163 #endif 164 165 // allocation/deallocation 166 /** 167 * @brief Default constructor creates no elements. 168 */ 169 #if __cplusplus < 201103L 170 set() : _M_t() { } 171 #else 172 set() = default; 173 #endif 174 175 /** 176 * @brief Creates a %set with no elements. 177 * @param __comp Comparator to use. 178 * @param __a An allocator object. 179 */ 180 explicit 181 set(const _Compare& __comp, 182 const allocator_type& __a = allocator_type()) 183 : _M_t(__comp, _Key_alloc_type(__a)) { } 184 185 /** 186 * @brief Builds a %set from a range. 187 * @param __first An input iterator. 188 * @param __last An input iterator. 189 * 190 * Create a %set consisting of copies of the elements from 191 * [__first,__last). This is linear in N if the range is 192 * already sorted, and NlogN otherwise (where N is 193 * distance(__first,__last)). 194 */ 195 template<typename _InputIterator> 196 set(_InputIterator __first, _InputIterator __last) 197 : _M_t() 198 { _M_t._M_insert_range_unique(__first, __last); } 199 200 /** 201 * @brief Builds a %set from a range. 202 * @param __first An input iterator. 203 * @param __last An input iterator. 204 * @param __comp A comparison functor. 205 * @param __a An allocator object. 206 * 207 * Create a %set consisting of copies of the elements from 208 * [__first,__last). This is linear in N if the range is 209 * already sorted, and NlogN otherwise (where N is 210 * distance(__first,__last)). 211 */ 212 template<typename _InputIterator> 213 set(_InputIterator __first, _InputIterator __last, 214 const _Compare& __comp, 215 const allocator_type& __a = allocator_type()) 216 : _M_t(__comp, _Key_alloc_type(__a)) 217 { _M_t._M_insert_range_unique(__first, __last); } 218 219 /** 220 * @brief %Set copy constructor. 221 * 222 * Whether the allocator is copied depends on the allocator traits. 223 */ 224 #if __cplusplus < 201103L 225 set(const set& __x) 226 : _M_t(__x._M_t) { } 227 #else 228 set(const set&) = default; 229 230 /** 231 * @brief %Set move constructor 232 * 233 * The newly-created %set contains the exact contents of the moved 234 * instance. The moved instance is a valid, but unspecified, %set. 235 */ 236 set(set&&) = default; 237 238 /** 239 * @brief Builds a %set from an initializer_list. 240 * @param __l An initializer_list. 241 * @param __comp A comparison functor. 242 * @param __a An allocator object. 243 * 244 * Create a %set consisting of copies of the elements in the list. 245 * This is linear in N if the list is already sorted, and NlogN 246 * otherwise (where N is @a __l.size()). 247 */ 248 set(initializer_list<value_type> __l, 249 const _Compare& __comp = _Compare(), 250 const allocator_type& __a = allocator_type()) 251 : _M_t(__comp, _Key_alloc_type(__a)) 252 { _M_t._M_insert_range_unique(__l.begin(), __l.end()); } 253 254 /// Allocator-extended default constructor. 255 explicit 256 set(const allocator_type& __a) 257 : _M_t(_Key_alloc_type(__a)) { } 258 259 /// Allocator-extended copy constructor. 260 set(const set& __x, const __type_identity_t<allocator_type>& __a) 261 : _M_t(__x._M_t, _Key_alloc_type(__a)) { } 262 263 /// Allocator-extended move constructor. 264 set(set&& __x, const __type_identity_t<allocator_type>& __a) 265 noexcept(is_nothrow_copy_constructible<_Compare>::value 266 && _Alloc_traits::_S_always_equal()) 267 : _M_t(std::move(__x._M_t), _Key_alloc_type(__a)) { } 268 269 /// Allocator-extended initialier-list constructor. 270 set(initializer_list<value_type> __l, const allocator_type& __a) 271 : _M_t(_Key_alloc_type(__a)) 272 { _M_t._M_insert_range_unique(__l.begin(), __l.end()); } 273 274 /// Allocator-extended range constructor. 275 template<typename _InputIterator> 276 set(_InputIterator __first, _InputIterator __last, 277 const allocator_type& __a) 278 : _M_t(_Key_alloc_type(__a)) 279 { _M_t._M_insert_range_unique(__first, __last); } 280 281 #if __glibcxx_containers_ranges // C++ >= 23 282 /** 283 * @brief Builds a %set from a range. 284 * @since C++23 285 */ 286 template<__detail::__container_compatible_range<_Key> _Rg> 287 set(from_range_t, _Rg&& __rg, 288 const _Compare& __comp, 289 const _Alloc& __a = _Alloc()) 290 : _M_t(__comp, _Key_alloc_type(__a)) 291 { insert_range(std::forward<_Rg>(__rg)); } 292 293 /// Allocator-extended range constructor. 294 template<__detail::__container_compatible_range<_Key> _Rg> 295 set(from_range_t, _Rg&& __rg, const _Alloc& __a = _Alloc()) 296 : _M_t(_Key_alloc_type(__a)) 297 { insert_range(std::forward<_Rg>(__rg)); } 298 #endif 299 300 /** 301 * The dtor only erases the elements, and note that if the elements 302 * themselves are pointers, the pointed-to memory is not touched in any 303 * way. Managing the pointer is the user's responsibility. 304 */ 305 ~set() = default; 306 #endif 307 308 /** 309 * @brief %Set assignment operator. 310 * 311 * Whether the allocator is copied depends on the allocator traits. 312 */ 313 #if __cplusplus < 201103L 314 set& 315 operator=(const set& __x) 316 { 317 _M_t = __x._M_t; 318 return *this; 319 } 320 #else 321 set& 322 operator=(const set&) = default; 323 324 /// Move assignment operator. 325 set& 326 operator=(set&&) = default; 327 328 /** 329 * @brief %Set list assignment operator. 330 * @param __l An initializer_list. 331 * 332 * This function fills a %set with copies of the elements in the 333 * initializer list @a __l. 334 * 335 * Note that the assignment completely changes the %set and 336 * that the resulting %set's size is the same as the number 337 * of elements assigned. 338 */ 339 set& 340 operator=(initializer_list<value_type> __l) 341 { 342 _M_t._M_assign_unique(__l.begin(), __l.end()); 343 return *this; 344 } 345 #endif 346 347 // accessors: 348 349 /// Returns the comparison object with which the %set was constructed. 350 key_compare 351 key_comp() const 352 { return _M_t.key_comp(); } 353 /// Returns the comparison object with which the %set was constructed. 354 value_compare 355 value_comp() const 356 { return _M_t.key_comp(); } 357 /// Returns the allocator object with which the %set was constructed. 358 allocator_type 359 get_allocator() const _GLIBCXX_NOEXCEPT 360 { return allocator_type(_M_t.get_allocator()); } 361 362 /** 363 * Returns a read-only (constant) iterator that points to the first 364 * element in the %set. Iteration is done in ascending order according 365 * to the keys. 366 */ 367 iterator 368 begin() const _GLIBCXX_NOEXCEPT 369 { return _M_t.begin(); } 370 371 /** 372 * Returns a read-only (constant) iterator that points one past the last 373 * element in the %set. Iteration is done in ascending order according 374 * to the keys. 375 */ 376 iterator 377 end() const _GLIBCXX_NOEXCEPT 378 { return _M_t.end(); } 379 380 /** 381 * Returns a read-only (constant) iterator that points to the last 382 * element in the %set. Iteration is done in descending order according 383 * to the keys. 384 */ 385 reverse_iterator 386 rbegin() const _GLIBCXX_NOEXCEPT 387 { return _M_t.rbegin(); } 388 389 /** 390 * Returns a read-only (constant) reverse iterator that points to the 391 * last pair in the %set. Iteration is done in descending order 392 * according to the keys. 393 */ 394 reverse_iterator 395 rend() const _GLIBCXX_NOEXCEPT 396 { return _M_t.rend(); } 397 398 #if __cplusplus >= 201103L 399 /** 400 * Returns a read-only (constant) iterator that points to the first 401 * element in the %set. Iteration is done in ascending order according 402 * to the keys. 403 */ 404 iterator 405 cbegin() const noexcept 406 { return _M_t.begin(); } 407 408 /** 409 * Returns a read-only (constant) iterator that points one past the last 410 * element in the %set. Iteration is done in ascending order according 411 * to the keys. 412 */ 413 iterator 414 cend() const noexcept 415 { return _M_t.end(); } 416 417 /** 418 * Returns a read-only (constant) iterator that points to the last 419 * element in the %set. Iteration is done in descending order according 420 * to the keys. 421 */ 422 reverse_iterator 423 crbegin() const noexcept 424 { return _M_t.rbegin(); } 425 426 /** 427 * Returns a read-only (constant) reverse iterator that points to the 428 * last pair in the %set. Iteration is done in descending order 429 * according to the keys. 430 */ 431 reverse_iterator 432 crend() const noexcept 433 { return _M_t.rend(); } 434 #endif 435 436 /// Returns true if the %set is empty. 437 _GLIBCXX_NODISCARD bool 438 empty() const _GLIBCXX_NOEXCEPT 439 { return _M_t.empty(); } 440 441 /// Returns the size of the %set. 442 size_type 443 size() const _GLIBCXX_NOEXCEPT 444 { return _M_t.size(); } 445 446 /// Returns the maximum size of the %set. 447 size_type 448 max_size() const _GLIBCXX_NOEXCEPT 449 { return _M_t.max_size(); } 450 451 /** 452 * @brief Swaps data with another %set. 453 * @param __x A %set of the same element and allocator types. 454 * 455 * This exchanges the elements between two sets in constant 456 * time. (It is only swapping a pointer, an integer, and an 457 * instance of the @c Compare type (which itself is often 458 * stateless and empty), so it should be quite fast.) Note 459 * that the global std::swap() function is specialized such 460 * that std::swap(s1,s2) will feed to this function. 461 * 462 * Whether the allocators are swapped depends on the allocator traits. 463 */ 464 void 465 swap(set& __x) 466 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value) 467 { _M_t.swap(__x._M_t); } 468 469 // insert/erase 470 #if __cplusplus >= 201103L 471 /** 472 * @brief Attempts to build and insert an element into the %set. 473 * @param __args Arguments used to generate an element. 474 * @return A pair, of which the first element is an iterator that points 475 * to the possibly inserted element, and the second is a bool 476 * that is true if the element was actually inserted. 477 * 478 * This function attempts to build and insert an element into the %set. 479 * A %set relies on unique keys and thus an element is only inserted if 480 * it is not already present in the %set. 481 * 482 * Insertion requires logarithmic time. 483 */ 484 template<typename... _Args> 485 std::pair<iterator, bool> 486 emplace(_Args&&... __args) 487 { return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); } 488 489 /** 490 * @brief Attempts to insert an element into the %set. 491 * @param __pos An iterator that serves as a hint as to where the 492 * element should be inserted. 493 * @param __args Arguments used to generate the element to be 494 * inserted. 495 * @return An iterator that points to the element with key equivalent to 496 * the one generated from @a __args (may or may not be the 497 * element itself). 498 * 499 * This function is not concerned about whether the insertion took place, 500 * and thus does not return a boolean like the single-argument emplace() 501 * does. Note that the first parameter is only a hint and can 502 * potentially improve the performance of the insertion process. A bad 503 * hint would cause no gains in efficiency. 504 * 505 * For more on @a hinting, see: 506 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 507 * 508 * Insertion requires logarithmic time (if the hint is not taken). 509 */ 510 template<typename... _Args> 511 iterator 512 emplace_hint(const_iterator __pos, _Args&&... __args) 513 { 514 return _M_t._M_emplace_hint_unique(__pos, 515 std::forward<_Args>(__args)...); 516 } 517 #endif 518 519 /** 520 * @brief Attempts to insert an element into the %set. 521 * @param __x Element to be inserted. 522 * @return A pair, of which the first element is an iterator that points 523 * to the possibly inserted element, and the second is a bool 524 * that is true if the element was actually inserted. 525 * 526 * This function attempts to insert an element into the %set. A %set 527 * relies on unique keys and thus an element is only inserted if it is 528 * not already present in the %set. 529 * 530 * Insertion requires logarithmic time. 531 */ 532 std::pair<iterator, bool> 533 insert(const value_type& __x) 534 { 535 std::pair<typename _Rep_type::iterator, bool> __p = 536 _M_t._M_insert_unique(__x); 537 return std::pair<iterator, bool>(__p.first, __p.second); 538 } 539 540 #if __cplusplus >= 201103L 541 std::pair<iterator, bool> 542 insert(value_type&& __x) 543 { 544 std::pair<typename _Rep_type::iterator, bool> __p = 545 _M_t._M_insert_unique(std::move(__x)); 546 return std::pair<iterator, bool>(__p.first, __p.second); 547 } 548 #endif 549 550 /** 551 * @brief Attempts to insert an element into the %set. 552 * @param __position An iterator that serves as a hint as to where the 553 * element should be inserted. 554 * @param __x Element to be inserted. 555 * @return An iterator that points to the element with key of 556 * @a __x (may or may not be the element passed in). 557 * 558 * This function is not concerned about whether the insertion took place, 559 * and thus does not return a boolean like the single-argument insert() 560 * does. Note that the first parameter is only a hint and can 561 * potentially improve the performance of the insertion process. A bad 562 * hint would cause no gains in efficiency. 563 * 564 * For more on @a hinting, see: 565 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 566 * 567 * Insertion requires logarithmic time (if the hint is not taken). 568 */ 569 iterator 570 insert(const_iterator __position, const value_type& __x) 571 { return _M_t._M_insert_unique_(__position, __x); } 572 573 #if __cplusplus >= 201103L 574 iterator 575 insert(const_iterator __position, value_type&& __x) 576 { return _M_t._M_insert_unique_(__position, std::move(__x)); } 577 #endif 578 579 /** 580 * @brief A template function that attempts to insert a range 581 * of elements. 582 * @param __first Iterator pointing to the start of the range to be 583 * inserted. 584 * @param __last Iterator pointing to the end of the range. 585 * 586 * Complexity similar to that of the range constructor. 587 */ 588 template<typename _InputIterator> 589 void 590 insert(_InputIterator __first, _InputIterator __last) 591 { _M_t._M_insert_range_unique(__first, __last); } 592 593 #if __cplusplus >= 201103L 594 /** 595 * @brief Attempts to insert a list of elements into the %set. 596 * @param __l A std::initializer_list<value_type> of elements 597 * to be inserted. 598 * 599 * Complexity similar to that of the range constructor. 600 */ 601 void 602 insert(initializer_list<value_type> __l) 603 { this->insert(__l.begin(), __l.end()); } 604 #endif 605 606 #if __glibcxx_containers_ranges // C++ >= 23 607 /** 608 * @brief Inserts a range of elements. 609 * @since C++23 610 * @param __rg An input range of elements that can be converted to 611 * the set's value type. 612 */ 613 template<__detail::__container_compatible_range<_Key> _Rg> 614 void 615 insert_range(_Rg&& __rg) 616 { 617 auto __first = ranges::begin(__rg); 618 const auto __last = ranges::end(__rg); 619 using _Rv = remove_cvref_t<ranges::range_reference_t<_Rg>>; 620 for (; __first != __last; ++__first) 621 if constexpr (is_same_v<_Rv, _Key>) 622 _M_t._M_insert_unique(*__first); 623 else 624 _M_t._M_emplace_unique(*__first); 625 } 626 #endif 627 628 #ifdef __glibcxx_node_extract // >= C++17 629 /// Extract a node. 630 node_type 631 extract(const_iterator __pos) 632 { 633 __glibcxx_assert(__pos != end()); 634 return _M_t.extract(__pos); 635 } 636 637 /// Extract a node. 638 node_type 639 extract(const key_type& __x) 640 { return _M_t.extract(__x); } 641 642 /// Re-insert an extracted node. 643 insert_return_type 644 insert(node_type&& __nh) 645 { return _M_t._M_reinsert_node_unique(std::move(__nh)); } 646 647 /// Re-insert an extracted node. 648 iterator 649 insert(const_iterator __hint, node_type&& __nh) 650 { return _M_t._M_reinsert_node_hint_unique(__hint, std::move(__nh)); } 651 652 template<typename, typename> 653 friend struct std::_Rb_tree_merge_helper; 654 655 template<typename _Compare1> 656 void 657 merge(set<_Key, _Compare1, _Alloc>& __source) 658 { 659 using _Merge_helper = _Rb_tree_merge_helper<set, _Compare1>; 660 _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source)); 661 } 662 663 template<typename _Compare1> 664 void 665 merge(set<_Key, _Compare1, _Alloc>&& __source) 666 { merge(__source); } 667 668 template<typename _Compare1> 669 void 670 merge(multiset<_Key, _Compare1, _Alloc>& __source) 671 { 672 using _Merge_helper = _Rb_tree_merge_helper<set, _Compare1>; 673 _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source)); 674 } 675 676 template<typename _Compare1> 677 void 678 merge(multiset<_Key, _Compare1, _Alloc>&& __source) 679 { merge(__source); } 680 #endif // C++17 681 682 #if __cplusplus >= 201103L 683 // _GLIBCXX_RESOLVE_LIB_DEFECTS 684 // DR 130. Associative erase should return an iterator. 685 /** 686 * @brief Erases an element from a %set. 687 * @param __position An iterator pointing to the element to be erased. 688 * @return An iterator pointing to the element immediately following 689 * @a __position prior to the element being erased. If no such 690 * element exists, end() is returned. 691 * 692 * This function erases an element, pointed to by the given iterator, 693 * from a %set. Note that this function only erases the element, and 694 * that if the element is itself a pointer, the pointed-to memory is not 695 * touched in any way. Managing the pointer is the user's 696 * responsibility. 697 */ 698 _GLIBCXX_ABI_TAG_CXX11 699 iterator 700 erase(const_iterator __position) 701 { return _M_t.erase(__position); } 702 #else 703 /** 704 * @brief Erases an element from a %set. 705 * @param position An iterator pointing to the element to be erased. 706 * 707 * This function erases an element, pointed to by the given iterator, 708 * from a %set. Note that this function only erases the element, and 709 * that if the element is itself a pointer, the pointed-to memory is not 710 * touched in any way. Managing the pointer is the user's 711 * responsibility. 712 */ 713 void 714 erase(iterator __position) 715 { _M_t.erase(__position); } 716 #endif 717 718 /** 719 * @brief Erases elements according to the provided key. 720 * @param __x Key of element to be erased. 721 * @return The number of elements erased. 722 * 723 * This function erases all the elements located by the given key from 724 * a %set. 725 * Note that this function only erases the element, and that if 726 * the element is itself a pointer, the pointed-to memory is not touched 727 * in any way. Managing the pointer is the user's responsibility. 728 */ 729 size_type 730 erase(const key_type& __x) 731 { return _M_t.erase(__x); } 732 733 #if __cplusplus >= 201103L 734 // _GLIBCXX_RESOLVE_LIB_DEFECTS 735 // DR 130. Associative erase should return an iterator. 736 /** 737 * @brief Erases a [__first,__last) range of elements from a %set. 738 * @param __first Iterator pointing to the start of the range to be 739 * erased. 740 741 * @param __last Iterator pointing to the end of the range to 742 * be erased. 743 * @return The iterator @a __last. 744 * 745 * This function erases a sequence of elements from a %set. 746 * Note that this function only erases the element, and that if 747 * the element is itself a pointer, the pointed-to memory is not touched 748 * in any way. Managing the pointer is the user's responsibility. 749 */ 750 _GLIBCXX_ABI_TAG_CXX11 751 iterator 752 erase(const_iterator __first, const_iterator __last) 753 { return _M_t.erase(__first, __last); } 754 #else 755 /** 756 * @brief Erases a [first,last) range of elements from a %set. 757 * @param __first Iterator pointing to the start of the range to be 758 * erased. 759 * @param __last Iterator pointing to the end of the range to 760 * be erased. 761 * 762 * This function erases a sequence of elements from a %set. 763 * Note that this function only erases the element, and that if 764 * the element is itself a pointer, the pointed-to memory is not touched 765 * in any way. Managing the pointer is the user's responsibility. 766 */ 767 void 768 erase(iterator __first, iterator __last) 769 { _M_t.erase(__first, __last); } 770 #endif 771 772 /** 773 * Erases all elements in a %set. Note that this function only erases 774 * the elements, and that if the elements themselves are pointers, the 775 * pointed-to memory is not touched in any way. Managing the pointer is 776 * the user's responsibility. 777 */ 778 void 779 clear() _GLIBCXX_NOEXCEPT 780 { _M_t.clear(); } 781 782 // set operations: 783 784 ///@{ 785 /** 786 * @brief Finds the number of elements. 787 * @param __x Element to located. 788 * @return Number of elements with specified key. 789 * 790 * This function only makes sense for multisets; for set the result will 791 * either be 0 (not present) or 1 (present). 792 */ 793 size_type 794 count(const key_type& __x) const 795 { return _M_t.find(__x) == _M_t.end() ? 0 : 1; } 796 797 #if __cplusplus > 201103L 798 template<typename _Kt> 799 auto 800 count(const _Kt& __x) const 801 -> decltype(_M_t._M_count_tr(__x)) 802 { return _M_t._M_count_tr(__x); } 803 #endif 804 ///@} 805 806 #if __cplusplus > 201703L 807 ///@{ 808 /** 809 * @brief Finds whether an element with the given key exists. 810 * @param __x Key of elements to be located. 811 * @return True if there is an element with the specified key. 812 */ 813 bool 814 contains(const key_type& __x) const 815 { return _M_t.find(__x) != _M_t.end(); } 816 817 template<typename _Kt> 818 auto 819 contains(const _Kt& __x) const 820 -> decltype(_M_t._M_find_tr(__x), void(), true) 821 { return _M_t._M_find_tr(__x) != _M_t.end(); } 822 ///@} 823 #endif 824 825 // _GLIBCXX_RESOLVE_LIB_DEFECTS 826 // 214. set::find() missing const overload 827 ///@{ 828 /** 829 * @brief Tries to locate an element in a %set. 830 * @param __x Element to be located. 831 * @return Iterator pointing to sought-after element, or end() if not 832 * found. 833 * 834 * This function takes a key and tries to locate the element with which 835 * the key matches. If successful the function returns an iterator 836 * pointing to the sought after element. If unsuccessful it returns the 837 * past-the-end ( @c end() ) iterator. 838 */ 839 iterator 840 find(const key_type& __x) 841 { return _M_t.find(__x); } 842 843 const_iterator 844 find(const key_type& __x) const 845 { return _M_t.find(__x); } 846 847 #if __cplusplus > 201103L 848 template<typename _Kt> 849 auto 850 find(const _Kt& __x) 851 -> decltype(iterator{_M_t._M_find_tr(__x)}) 852 { return iterator{_M_t._M_find_tr(__x)}; } 853 854 template<typename _Kt> 855 auto 856 find(const _Kt& __x) const 857 -> decltype(const_iterator{_M_t._M_find_tr(__x)}) 858 { return const_iterator{_M_t._M_find_tr(__x)}; } 859 #endif 860 ///@} 861 862 ///@{ 863 /** 864 * @brief Finds the beginning of a subsequence matching given key. 865 * @param __x Key to be located. 866 * @return Iterator pointing to first element equal to or greater 867 * than key, or end(). 868 * 869 * This function returns the first element of a subsequence of elements 870 * that matches the given key. If unsuccessful it returns an iterator 871 * pointing to the first element that has a greater value than given key 872 * or end() if no such element exists. 873 */ 874 iterator 875 lower_bound(const key_type& __x) 876 { return _M_t.lower_bound(__x); } 877 878 const_iterator 879 lower_bound(const key_type& __x) const 880 { return _M_t.lower_bound(__x); } 881 882 #if __cplusplus > 201103L 883 template<typename _Kt> 884 auto 885 lower_bound(const _Kt& __x) 886 -> decltype(iterator(_M_t._M_lower_bound_tr(__x))) 887 { return iterator(_M_t._M_lower_bound_tr(__x)); } 888 889 template<typename _Kt> 890 auto 891 lower_bound(const _Kt& __x) const 892 -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x))) 893 { return const_iterator(_M_t._M_lower_bound_tr(__x)); } 894 #endif 895 ///@} 896 897 ///@{ 898 /** 899 * @brief Finds the end of a subsequence matching given key. 900 * @param __x Key to be located. 901 * @return Iterator pointing to the first element 902 * greater than key, or end(). 903 */ 904 iterator 905 upper_bound(const key_type& __x) 906 { return _M_t.upper_bound(__x); } 907 908 const_iterator 909 upper_bound(const key_type& __x) const 910 { return _M_t.upper_bound(__x); } 911 912 #if __cplusplus > 201103L 913 template<typename _Kt> 914 auto 915 upper_bound(const _Kt& __x) 916 -> decltype(iterator(_M_t._M_upper_bound_tr(__x))) 917 { return iterator(_M_t._M_upper_bound_tr(__x)); } 918 919 template<typename _Kt> 920 auto 921 upper_bound(const _Kt& __x) const 922 -> decltype(const_iterator(_M_t._M_upper_bound_tr(__x))) 923 { return const_iterator(_M_t._M_upper_bound_tr(__x)); } 924 #endif 925 ///@} 926 927 ///@{ 928 /** 929 * @brief Finds a subsequence matching given key. 930 * @param __x Key to be located. 931 * @return Pair of iterators that possibly points to the subsequence 932 * matching given key. 933 * 934 * This function is equivalent to 935 * @code 936 * std::make_pair(c.lower_bound(val), 937 * c.upper_bound(val)) 938 * @endcode 939 * (but is faster than making the calls separately). 940 * 941 * This function probably only makes sense for multisets. 942 */ 943 std::pair<iterator, iterator> 944 equal_range(const key_type& __x) 945 { return _M_t.equal_range(__x); } 946 947 std::pair<const_iterator, const_iterator> 948 equal_range(const key_type& __x) const 949 { return _M_t.equal_range(__x); } 950 951 #if __cplusplus > 201103L 952 template<typename _Kt> 953 auto 954 equal_range(const _Kt& __x) 955 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x))) 956 { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); } 957 958 template<typename _Kt> 959 auto 960 equal_range(const _Kt& __x) const 961 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x))) 962 { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); } 963 #endif 964 ///@} 965 966 template<typename _K1, typename _C1, typename _A1> 967 friend bool 968 operator==(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&); 969 970 #if __cpp_lib_three_way_comparison 971 template<typename _K1, typename _C1, typename _A1> 972 friend __detail::__synth3way_t<_K1> 973 operator<=>(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&); 974 #else 975 template<typename _K1, typename _C1, typename _A1> 976 friend bool 977 operator<(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&); 978 #endif 979 }; 980 981 #if __cpp_deduction_guides >= 201606 982 983 template<typename _InputIterator, 984 typename _Compare = 985 less<typename iterator_traits<_InputIterator>::value_type>, 986 typename _Allocator = 987 allocator<typename iterator_traits<_InputIterator>::value_type>, 988 typename = _RequireInputIter<_InputIterator>, 989 typename = _RequireNotAllocator<_Compare>, 990 typename = _RequireAllocator<_Allocator>> 991 set(_InputIterator, _InputIterator, 992 _Compare = _Compare(), _Allocator = _Allocator()) 993 -> set<typename iterator_traits<_InputIterator>::value_type, 994 _Compare, _Allocator>; 995 996 template<typename _Key, typename _Compare = less<_Key>, 997 typename _Allocator = allocator<_Key>, 998 typename = _RequireNotAllocator<_Compare>, 999 typename = _RequireAllocator<_Allocator>> 1000 set(initializer_list<_Key>, 1001 _Compare = _Compare(), _Allocator = _Allocator()) 1002 -> set<_Key, _Compare, _Allocator>; 1003 1004 template<typename _InputIterator, typename _Allocator, 1005 typename = _RequireInputIter<_InputIterator>, 1006 typename = _RequireAllocator<_Allocator>> 1007 set(_InputIterator, _InputIterator, _Allocator) 1008 -> set<typename iterator_traits<_InputIterator>::value_type, 1009 less<typename iterator_traits<_InputIterator>::value_type>, 1010 _Allocator>; 1011 1012 template<typename _Key, typename _Allocator, 1013 typename = _RequireAllocator<_Allocator>> 1014 set(initializer_list<_Key>, _Allocator) 1015 -> set<_Key, less<_Key>, _Allocator>; 1016 1017 #if __glibcxx_containers_ranges // C++ >= 23 1018 template<ranges::input_range _Rg, 1019 __not_allocator_like _Compare = less<ranges::range_value_t<_Rg>>, 1020 __allocator_like _Alloc = std::allocator<ranges::range_value_t<_Rg>>> 1021 set(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc()) 1022 -> set<ranges::range_value_t<_Rg>, _Compare, _Alloc>; 1023 1024 template<ranges::input_range _Rg, __allocator_like _Alloc> 1025 set(from_range_t, _Rg&&, _Alloc) 1026 -> set<ranges::range_value_t<_Rg>, less<ranges::range_value_t<_Rg>>, _Alloc>; 1027 #endif 1028 #endif // deduction guides 1029 1030 /** 1031 * @brief Set equality comparison. 1032 * @param __x A %set. 1033 * @param __y A %set of the same type as @a x. 1034 * @return True iff the size and elements of the sets are equal. 1035 * 1036 * This is an equivalence relation. It is linear in the size of the sets. 1037 * Sets are considered equivalent if their sizes are equal, and if 1038 * corresponding elements compare equal. 1039 */ 1040 template<typename _Key, typename _Compare, typename _Alloc> 1041 inline bool 1042 operator==(const set<_Key, _Compare, _Alloc>& __x, 1043 const set<_Key, _Compare, _Alloc>& __y) 1044 { return __x._M_t == __y._M_t; } 1045 1046 #if __cpp_lib_three_way_comparison 1047 /** 1048 * @brief Set ordering relation. 1049 * @param __x A `set`. 1050 * @param __y A `set` of the same type as `x`. 1051 * @return A value indicating whether `__x` is less than, equal to, 1052 * greater than, or incomparable with `__y`. 1053 * 1054 * This is a total ordering relation. It is linear in the size of the 1055 * maps. The elements must be comparable with @c <. 1056 * 1057 * See `std::lexicographical_compare_three_way()` for how the determination 1058 * is made. This operator is used to synthesize relational operators like 1059 * `<` and `>=` etc. 1060 */ 1061 template<typename _Key, typename _Compare, typename _Alloc> 1062 inline __detail::__synth3way_t<_Key> 1063 operator<=>(const set<_Key, _Compare, _Alloc>& __x, 1064 const set<_Key, _Compare, _Alloc>& __y) 1065 { return __x._M_t <=> __y._M_t; } 1066 #else 1067 /** 1068 * @brief Set ordering relation. 1069 * @param __x A %set. 1070 * @param __y A %set of the same type as @a x. 1071 * @return True iff @a __x is lexicographically less than @a __y. 1072 * 1073 * This is a total ordering relation. It is linear in the size of the 1074 * sets. The elements must be comparable with @c <. 1075 * 1076 * See std::lexicographical_compare() for how the determination is made. 1077 */ 1078 template<typename _Key, typename _Compare, typename _Alloc> 1079 inline bool 1080 operator<(const set<_Key, _Compare, _Alloc>& __x, 1081 const set<_Key, _Compare, _Alloc>& __y) 1082 { return __x._M_t < __y._M_t; } 1083 1084 /// Returns !(x == y). 1085 template<typename _Key, typename _Compare, typename _Alloc> 1086 inline bool 1087 operator!=(const set<_Key, _Compare, _Alloc>& __x, 1088 const set<_Key, _Compare, _Alloc>& __y) 1089 { return !(__x == __y); } 1090 1091 /// Returns y < x. 1092 template<typename _Key, typename _Compare, typename _Alloc> 1093 inline bool 1094 operator>(const set<_Key, _Compare, _Alloc>& __x, 1095 const set<_Key, _Compare, _Alloc>& __y) 1096 { return __y < __x; } 1097 1098 /// Returns !(y < x) 1099 template<typename _Key, typename _Compare, typename _Alloc> 1100 inline bool 1101 operator<=(const set<_Key, _Compare, _Alloc>& __x, 1102 const set<_Key, _Compare, _Alloc>& __y) 1103 { return !(__y < __x); } 1104 1105 /// Returns !(x < y) 1106 template<typename _Key, typename _Compare, typename _Alloc> 1107 inline bool 1108 operator>=(const set<_Key, _Compare, _Alloc>& __x, 1109 const set<_Key, _Compare, _Alloc>& __y) 1110 { return !(__x < __y); } 1111 #endif // three-way comparison 1112 1113 /// See std::set::swap(). 1114 template<typename _Key, typename _Compare, typename _Alloc> 1115 inline void 1116 swap(set<_Key, _Compare, _Alloc>& __x, set<_Key, _Compare, _Alloc>& __y) 1117 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y))) 1118 { __x.swap(__y); } 1119 1120 _GLIBCXX_END_NAMESPACE_CONTAINER 1121 1122 #if __cplusplus > 201402L 1123 // Allow std::set access to internals of compatible sets. 1124 template<typename _Val, typename _Cmp1, typename _Alloc, typename _Cmp2> 1125 struct 1126 _Rb_tree_merge_helper<_GLIBCXX_STD_C::set<_Val, _Cmp1, _Alloc>, _Cmp2> 1127 { 1128 private: 1129 friend class _GLIBCXX_STD_C::set<_Val, _Cmp1, _Alloc>; 1130 1131 static auto& 1132 _S_get_tree(_GLIBCXX_STD_C::set<_Val, _Cmp2, _Alloc>& __set) 1133 { return __set._M_t; } 1134 1135 static auto& 1136 _S_get_tree(_GLIBCXX_STD_C::multiset<_Val, _Cmp2, _Alloc>& __set) 1137 { return __set._M_t; } 1138 }; 1139 #endif // C++17 1140 1141 _GLIBCXX_END_NAMESPACE_VERSION 1142 } //namespace std 1143 #endif /* _STL_SET_H */
