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