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