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