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