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