1 // Multimap 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,1997 40 * Silicon Graphics Computer Systems, Inc. 41 * 42 * Permission to use, copy, modify, distribute and sell this software 43 * and its documentation for any purpose is hereby granted without fee, 44 * provided that the above copyright notice appear in all copies and 45 * that both that copyright notice and this permission notice appear 46 * in supporting documentation. Silicon Graphics makes no 47 * representations about the suitability of this software for any 48 * purpose. It is provided "as is" without express or implied warranty. 49 */ 50 51 /** @file bits/stl_multimap.h 52 * This is an internal header file, included by other library headers. 53 * Do not attempt to use it directly. @headername{map} 54 */ 55 56 #ifndef _STL_MULTIMAP_H 57 #define _STL_MULTIMAP_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 _Tp, typename _Compare, typename _Alloc> 70 class map; 71 72 /** 73 * @brief A standard container made up of (key,value) pairs, which can be 74 * retrieved based on a key, in logarithmic time. 75 * 76 * @ingroup associative_containers 77 * 78 * @tparam _Key Type of key objects. 79 * @tparam _Tp Type of mapped objects. 80 * @tparam _Compare Comparison function object type, defaults to less<_Key>. 81 * @tparam _Alloc Allocator type, defaults to 82 * allocator<pair<const _Key, _Tp>. 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 multimap<Key,T> the key_type is Key, the mapped_type 88 * is T, and the value_type is std::pair<const Key,T>. 89 * 90 * Multimaps support bidirectional iterators. 91 * 92 * The private tree data is declared exactly the same way for map and 93 * multimap; the distinction is made entirely in how the tree functions are 94 * called (*_unique versus *_equal, same as the standard). 95 */ 96 template <typename _Key, typename _Tp, 97 typename _Compare = std::less<_Key>, 98 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 99 class multimap 100 { 101 public: 102 typedef _Key key_type; 103 typedef _Tp mapped_type; 104 typedef std::pair<const _Key, _Tp> value_type; 105 typedef _Compare key_compare; 106 typedef _Alloc allocator_type; 107 108 private: 109 #ifdef _GLIBCXX_CONCEPT_CHECKS 110 // concept requirements 111 typedef typename _Alloc::value_type _Alloc_value_type; 112 # if __cplusplus < 201103L 113 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 114 # endif 115 __glibcxx_class_requires4(_Compare, bool, _Key, _Key, 116 _BinaryFunctionConcept) 117 __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept) 118 #endif 119 120 #if __cplusplus >= 201103L 121 #if __cplusplus > 201703L || defined __STRICT_ANSI__ 122 static_assert(is_same<typename _Alloc::value_type, value_type>::value, 123 "std::multimap must have the same value_type as its allocator"); 124 #endif 125 #endif 126 127 public: 128 #pragma GCC diagnostic push 129 #pragma GCC diagnostic ignored "-Wdeprecated-declarations" 130 class value_compare 131 : public std::binary_function<value_type, value_type, bool> 132 { 133 friend class multimap<_Key, _Tp, _Compare, _Alloc>; 134 protected: 135 _Compare comp; 136 137 value_compare(_Compare __c) 138 : comp(__c) { } 139 140 public: 141 bool operator()(const value_type& __x, const value_type& __y) const 142 { return comp(__x.first, __y.first); } 143 }; 144 #pragma GCC diagnostic pop 145 146 private: 147 /// This turns a red-black tree into a [multi]map. 148 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 149 rebind<value_type>::other _Pair_alloc_type; 150 151 typedef _Rb_tree<key_type, value_type, _Select1st<value_type>, 152 key_compare, _Pair_alloc_type> _Rep_type; 153 /// The actual tree structure. 154 _Rep_type _M_t; 155 156 typedef __gnu_cxx::__alloc_traits<_Pair_alloc_type> _Alloc_traits; 157 158 public: 159 // many of these are specified differently in ISO, but the following are 160 // "functionally equivalent" 161 typedef typename _Alloc_traits::pointer pointer; 162 typedef typename _Alloc_traits::const_pointer const_pointer; 163 typedef typename _Alloc_traits::reference reference; 164 typedef typename _Alloc_traits::const_reference const_reference; 165 typedef typename _Rep_type::iterator iterator; 166 typedef typename _Rep_type::const_iterator const_iterator; 167 typedef typename _Rep_type::size_type size_type; 168 typedef typename _Rep_type::difference_type difference_type; 169 typedef typename _Rep_type::reverse_iterator reverse_iterator; 170 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 171 172 #if __cplusplus > 201402L 173 using node_type = typename _Rep_type::node_type; 174 #endif 175 176 // [23.3.2] construct/copy/destroy 177 // (get_allocator() is also listed in this section) 178 179 /** 180 * @brief Default constructor creates no elements. 181 */ 182 #if __cplusplus < 201103L 183 multimap() : _M_t() { } 184 #else 185 multimap() = default; 186 #endif 187 188 /** 189 * @brief Creates a %multimap with no elements. 190 * @param __comp A comparison object. 191 * @param __a An allocator object. 192 */ 193 explicit 194 multimap(const _Compare& __comp, 195 const allocator_type& __a = allocator_type()) 196 : _M_t(__comp, _Pair_alloc_type(__a)) { } 197 198 /** 199 * @brief %Multimap copy constructor. 200 * 201 * Whether the allocator is copied depends on the allocator traits. 202 */ 203 #if __cplusplus < 201103L 204 multimap(const multimap& __x) 205 : _M_t(__x._M_t) { } 206 #else 207 multimap(const multimap&) = default; 208 209 /** 210 * @brief %Multimap move constructor. 211 * 212 * The newly-created %multimap contains the exact contents of the 213 * moved instance. The moved instance is a valid, but unspecified 214 * %multimap. 215 */ 216 multimap(multimap&&) = default; 217 218 /** 219 * @brief Builds a %multimap from an initializer_list. 220 * @param __l An initializer_list. 221 * @param __comp A comparison functor. 222 * @param __a An allocator object. 223 * 224 * Create a %multimap consisting of copies of the elements from 225 * the initializer_list. This is linear in N if the list is already 226 * sorted, and NlogN otherwise (where N is @a __l.size()). 227 */ 228 multimap(initializer_list<value_type> __l, 229 const _Compare& __comp = _Compare(), 230 const allocator_type& __a = allocator_type()) 231 : _M_t(__comp, _Pair_alloc_type(__a)) 232 { _M_t._M_insert_range_equal(__l.begin(), __l.end()); } 233 234 /// Allocator-extended default constructor. 235 explicit 236 multimap(const allocator_type& __a) 237 : _M_t(_Pair_alloc_type(__a)) { } 238 239 /// Allocator-extended copy constructor. 240 multimap(const multimap& __m, 241 const __type_identity_t<allocator_type>& __a) 242 : _M_t(__m._M_t, _Pair_alloc_type(__a)) { } 243 244 /// Allocator-extended move constructor. 245 multimap(multimap&& __m, const __type_identity_t<allocator_type>& __a) 246 noexcept(is_nothrow_copy_constructible<_Compare>::value 247 && _Alloc_traits::_S_always_equal()) 248 : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { } 249 250 /// Allocator-extended initialier-list constructor. 251 multimap(initializer_list<value_type> __l, const allocator_type& __a) 252 : _M_t(_Pair_alloc_type(__a)) 253 { _M_t._M_insert_range_equal(__l.begin(), __l.end()); } 254 255 /// Allocator-extended range constructor. 256 template<typename _InputIterator> 257 multimap(_InputIterator __first, _InputIterator __last, 258 const allocator_type& __a) 259 : _M_t(_Pair_alloc_type(__a)) 260 { _M_t._M_insert_range_equal(__first, __last); } 261 #endif 262 263 /** 264 * @brief Builds a %multimap from a range. 265 * @param __first An input iterator. 266 * @param __last An input iterator. 267 * 268 * Create a %multimap consisting of copies of the elements from 269 * [__first,__last). This is linear in N if the range is already sorted, 270 * and NlogN otherwise (where N is distance(__first,__last)). 271 */ 272 template<typename _InputIterator> 273 multimap(_InputIterator __first, _InputIterator __last) 274 : _M_t() 275 { _M_t._M_insert_range_equal(__first, __last); } 276 277 /** 278 * @brief Builds a %multimap from a range. 279 * @param __first An input iterator. 280 * @param __last An input iterator. 281 * @param __comp A comparison functor. 282 * @param __a An allocator object. 283 * 284 * Create a %multimap consisting of copies of the elements from 285 * [__first,__last). This is linear in N if the range is already sorted, 286 * and NlogN otherwise (where N is distance(__first,__last)). 287 */ 288 template<typename _InputIterator> 289 multimap(_InputIterator __first, _InputIterator __last, 290 const _Compare& __comp, 291 const allocator_type& __a = allocator_type()) 292 : _M_t(__comp, _Pair_alloc_type(__a)) 293 { _M_t._M_insert_range_equal(__first, __last); } 294 295 #if __cplusplus >= 201103L 296 /** 297 * The dtor only erases the elements, and note that if the elements 298 * themselves are pointers, the pointed-to memory is not touched in any 299 * way. Managing the pointer is the user's responsibility. 300 */ 301 ~multimap() = default; 302 #endif 303 304 /** 305 * @brief %Multimap assignment operator. 306 * 307 * Whether the allocator is copied depends on the allocator traits. 308 */ 309 #if __cplusplus < 201103L 310 multimap& 311 operator=(const multimap& __x) 312 { 313 _M_t = __x._M_t; 314 return *this; 315 } 316 #else 317 multimap& 318 operator=(const multimap&) = default; 319 320 /// Move assignment operator. 321 multimap& 322 operator=(multimap&&) = default; 323 324 /** 325 * @brief %Multimap list assignment operator. 326 * @param __l An initializer_list. 327 * 328 * This function fills a %multimap with copies of the elements 329 * in the initializer list @a __l. 330 * 331 * Note that the assignment completely changes the %multimap and 332 * that the resulting %multimap's size is the same as the number 333 * of elements assigned. 334 */ 335 multimap& 336 operator=(initializer_list<value_type> __l) 337 { 338 _M_t._M_assign_equal(__l.begin(), __l.end()); 339 return *this; 340 } 341 #endif 342 343 /// Get a copy of the memory allocation object. 344 allocator_type 345 get_allocator() const _GLIBCXX_NOEXCEPT 346 { return allocator_type(_M_t.get_allocator()); } 347 348 // iterators 349 /** 350 * Returns a read/write iterator that points to the first pair in the 351 * %multimap. Iteration is done in ascending order according to the 352 * keys. 353 */ 354 iterator 355 begin() _GLIBCXX_NOEXCEPT 356 { return _M_t.begin(); } 357 358 /** 359 * Returns a read-only (constant) iterator that points to the first pair 360 * in the %multimap. Iteration is done in ascending order according to 361 * the keys. 362 */ 363 const_iterator 364 begin() const _GLIBCXX_NOEXCEPT 365 { return _M_t.begin(); } 366 367 /** 368 * Returns a read/write iterator that points one past the last pair in 369 * the %multimap. Iteration is done in ascending order according to the 370 * keys. 371 */ 372 iterator 373 end() _GLIBCXX_NOEXCEPT 374 { return _M_t.end(); } 375 376 /** 377 * Returns a read-only (constant) iterator that points one past the last 378 * pair in the %multimap. Iteration is done in ascending order according 379 * to the keys. 380 */ 381 const_iterator 382 end() const _GLIBCXX_NOEXCEPT 383 { return _M_t.end(); } 384 385 /** 386 * Returns a read/write reverse iterator that points to the last pair in 387 * the %multimap. Iteration is done in descending order according to the 388 * keys. 389 */ 390 reverse_iterator 391 rbegin() _GLIBCXX_NOEXCEPT 392 { return _M_t.rbegin(); } 393 394 /** 395 * Returns a read-only (constant) reverse iterator that points to the 396 * last pair in the %multimap. Iteration is done in descending order 397 * according to the keys. 398 */ 399 const_reverse_iterator 400 rbegin() const _GLIBCXX_NOEXCEPT 401 { return _M_t.rbegin(); } 402 403 /** 404 * Returns a read/write reverse iterator that points to one before the 405 * first pair in the %multimap. Iteration is done in descending order 406 * according to the keys. 407 */ 408 reverse_iterator 409 rend() _GLIBCXX_NOEXCEPT 410 { return _M_t.rend(); } 411 412 /** 413 * Returns a read-only (constant) reverse iterator that points to one 414 * before the first pair in the %multimap. Iteration is done in 415 * descending order according to the keys. 416 */ 417 const_reverse_iterator 418 rend() const _GLIBCXX_NOEXCEPT 419 { return _M_t.rend(); } 420 421 #if __cplusplus >= 201103L 422 /** 423 * Returns a read-only (constant) iterator that points to the first pair 424 * in the %multimap. Iteration is done in ascending order according to 425 * the keys. 426 */ 427 const_iterator 428 cbegin() const noexcept 429 { return _M_t.begin(); } 430 431 /** 432 * Returns a read-only (constant) iterator that points one past the last 433 * pair in the %multimap. Iteration is done in ascending order according 434 * to the keys. 435 */ 436 const_iterator 437 cend() const noexcept 438 { return _M_t.end(); } 439 440 /** 441 * Returns a read-only (constant) reverse iterator that points to the 442 * last pair in the %multimap. Iteration is done in descending order 443 * according to the keys. 444 */ 445 const_reverse_iterator 446 crbegin() const noexcept 447 { return _M_t.rbegin(); } 448 449 /** 450 * Returns a read-only (constant) reverse iterator that points to one 451 * before the first pair in the %multimap. Iteration is done in 452 * descending order according to the keys. 453 */ 454 const_reverse_iterator 455 crend() const noexcept 456 { return _M_t.rend(); } 457 #endif 458 459 // capacity 460 /** Returns true if the %multimap is empty. */ 461 _GLIBCXX_NODISCARD bool 462 empty() const _GLIBCXX_NOEXCEPT 463 { return _M_t.empty(); } 464 465 /** Returns the size of the %multimap. */ 466 size_type 467 size() const _GLIBCXX_NOEXCEPT 468 { return _M_t.size(); } 469 470 /** Returns the maximum size of the %multimap. */ 471 size_type 472 max_size() const _GLIBCXX_NOEXCEPT 473 { return _M_t.max_size(); } 474 475 // modifiers 476 #if __cplusplus >= 201103L 477 /** 478 * @brief Build and insert a std::pair into the %multimap. 479 * 480 * @param __args Arguments used to generate a new pair instance (see 481 * std::piecewise_contruct for passing arguments to each 482 * part of the pair constructor). 483 * 484 * @return An iterator that points to the inserted (key,value) pair. 485 * 486 * This function builds and inserts a (key, value) %pair into the 487 * %multimap. 488 * Contrary to a std::map the %multimap does not rely on unique keys and 489 * thus multiple pairs with the same key can be inserted. 490 * 491 * Insertion requires logarithmic time. 492 */ 493 template<typename... _Args> 494 iterator 495 emplace(_Args&&... __args) 496 { return _M_t._M_emplace_equal(std::forward<_Args>(__args)...); } 497 498 /** 499 * @brief Builds and inserts a std::pair into the %multimap. 500 * 501 * @param __pos An iterator that serves as a hint as to where the pair 502 * should be inserted. 503 * @param __args Arguments used to generate a new pair instance (see 504 * std::piecewise_contruct for passing arguments to each 505 * part of the pair constructor). 506 * @return An iterator that points to the inserted (key,value) pair. 507 * 508 * This function inserts a (key, value) pair into the %multimap. 509 * Contrary to a std::map the %multimap does not rely on unique keys and 510 * thus multiple pairs with the same key can be inserted. 511 * Note that the first parameter is only a hint and can potentially 512 * improve the performance of the insertion process. A bad hint would 513 * cause no gains in efficiency. 514 * 515 * For more on @a hinting, see: 516 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 517 * 518 * Insertion requires logarithmic time (if the hint is not taken). 519 */ 520 template<typename... _Args> 521 iterator 522 emplace_hint(const_iterator __pos, _Args&&... __args) 523 { 524 return _M_t._M_emplace_hint_equal(__pos, 525 std::forward<_Args>(__args)...); 526 } 527 #endif 528 529 /** 530 * @brief Inserts a std::pair into the %multimap. 531 * @param __x Pair to be inserted (see std::make_pair for easy creation 532 * of pairs). 533 * @return An iterator that points to the inserted (key,value) pair. 534 * 535 * This function inserts a (key, value) pair into the %multimap. 536 * Contrary to a std::map the %multimap does not rely on unique keys and 537 * thus multiple pairs with the same key can be inserted. 538 * 539 * Insertion requires logarithmic time. 540 * @{ 541 */ 542 iterator 543 insert(const value_type& __x) 544 { return _M_t._M_insert_equal(__x); } 545 546 #if __cplusplus >= 201103L 547 // _GLIBCXX_RESOLVE_LIB_DEFECTS 548 // 2354. Unnecessary copying when inserting into maps with braced-init 549 iterator 550 insert(value_type&& __x) 551 { return _M_t._M_insert_equal(std::move(__x)); } 552 553 template<typename _Pair> 554 __enable_if_t<is_constructible<value_type, _Pair>::value, iterator> 555 insert(_Pair&& __x) 556 { return _M_t._M_emplace_equal(std::forward<_Pair>(__x)); } 557 #endif 558 /// @} 559 560 /** 561 * @brief Inserts a std::pair into the %multimap. 562 * @param __position An iterator that serves as a hint as to where the 563 * pair should be inserted. 564 * @param __x Pair to be inserted (see std::make_pair for easy creation 565 * of pairs). 566 * @return An iterator that points to the inserted (key,value) pair. 567 * 568 * This function inserts a (key, value) pair into the %multimap. 569 * Contrary to a std::map the %multimap does not rely on unique keys and 570 * thus multiple pairs with the same key can be inserted. 571 * Note that the first parameter is only a hint and can potentially 572 * improve the performance of the insertion process. A bad hint would 573 * cause no gains in efficiency. 574 * 575 * For more on @a hinting, see: 576 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 577 * 578 * Insertion requires logarithmic time (if the hint is not taken). 579 * @{ 580 */ 581 iterator 582 #if __cplusplus >= 201103L 583 insert(const_iterator __position, const value_type& __x) 584 #else 585 insert(iterator __position, const value_type& __x) 586 #endif 587 { return _M_t._M_insert_equal_(__position, __x); } 588 589 #if __cplusplus >= 201103L 590 // _GLIBCXX_RESOLVE_LIB_DEFECTS 591 // 2354. Unnecessary copying when inserting into maps with braced-init 592 iterator 593 insert(const_iterator __position, value_type&& __x) 594 { return _M_t._M_insert_equal_(__position, std::move(__x)); } 595 596 template<typename _Pair> 597 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator> 598 insert(const_iterator __position, _Pair&& __x) 599 { 600 return _M_t._M_emplace_hint_equal(__position, 601 std::forward<_Pair>(__x)); 602 } 603 #endif 604 /// @} 605 606 /** 607 * @brief A template function that attempts to insert a range 608 * of elements. 609 * @param __first Iterator pointing to the start of the range to be 610 * inserted. 611 * @param __last Iterator pointing to the end of the range. 612 * 613 * Complexity similar to that of the range constructor. 614 */ 615 template<typename _InputIterator> 616 void 617 insert(_InputIterator __first, _InputIterator __last) 618 { _M_t._M_insert_range_equal(__first, __last); } 619 620 #if __cplusplus >= 201103L 621 /** 622 * @brief Attempts to insert a list of std::pairs into the %multimap. 623 * @param __l A std::initializer_list<value_type> of pairs to be 624 * inserted. 625 * 626 * Complexity similar to that of the range constructor. 627 */ 628 void 629 insert(initializer_list<value_type> __l) 630 { this->insert(__l.begin(), __l.end()); } 631 #endif 632 633 #if __cplusplus > 201402L 634 /// Extract a node. 635 node_type 636 extract(const_iterator __pos) 637 { 638 __glibcxx_assert(__pos != end()); 639 return _M_t.extract(__pos); 640 } 641 642 /// Extract a node. 643 node_type 644 extract(const key_type& __x) 645 { return _M_t.extract(__x); } 646 647 /// Re-insert an extracted node. 648 iterator 649 insert(node_type&& __nh) 650 { return _M_t._M_reinsert_node_equal(std::move(__nh)); } 651 652 /// Re-insert an extracted node. 653 iterator 654 insert(const_iterator __hint, node_type&& __nh) 655 { return _M_t._M_reinsert_node_hint_equal(__hint, std::move(__nh)); } 656 657 template<typename, typename> 658 friend struct std::_Rb_tree_merge_helper; 659 660 template<typename _Cmp2> 661 void 662 merge(multimap<_Key, _Tp, _Cmp2, _Alloc>& __source) 663 { 664 using _Merge_helper = _Rb_tree_merge_helper<multimap, _Cmp2>; 665 _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source)); 666 } 667 668 template<typename _Cmp2> 669 void 670 merge(multimap<_Key, _Tp, _Cmp2, _Alloc>&& __source) 671 { merge(__source); } 672 673 template<typename _Cmp2> 674 void 675 merge(map<_Key, _Tp, _Cmp2, _Alloc>& __source) 676 { 677 using _Merge_helper = _Rb_tree_merge_helper<multimap, _Cmp2>; 678 _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source)); 679 } 680 681 template<typename _Cmp2> 682 void 683 merge(map<_Key, _Tp, _Cmp2, _Alloc>&& __source) 684 { merge(__source); } 685 #endif // C++17 686 687 #if __cplusplus >= 201103L 688 // _GLIBCXX_RESOLVE_LIB_DEFECTS 689 // DR 130. Associative erase should return an iterator. 690 /** 691 * @brief Erases an element from a %multimap. 692 * @param __position An iterator pointing to the element to be erased. 693 * @return An iterator pointing to the element immediately following 694 * @a position prior to the element being erased. If no such 695 * element exists, end() is returned. 696 * 697 * This function erases an element, pointed to by the given iterator, 698 * from a %multimap. Note that this function only erases the element, 699 * and that if the element is itself a pointer, the pointed-to memory is 700 * not touched in any way. Managing the pointer is the user's 701 * responsibility. 702 * 703 * @{ 704 */ 705 iterator 706 erase(const_iterator __position) 707 { return _M_t.erase(__position); } 708 709 // LWG 2059. 710 _GLIBCXX_ABI_TAG_CXX11 711 iterator 712 erase(iterator __position) 713 { return _M_t.erase(__position); } 714 /// @} 715 #else 716 /** 717 * @brief Erases an element from a %multimap. 718 * @param __position An iterator pointing to the element to be erased. 719 * 720 * This function erases an element, pointed to by the given iterator, 721 * from a %multimap. Note that this function only erases the element, 722 * and that if the element is itself a pointer, the pointed-to memory is 723 * not touched in any way. Managing the pointer is the user's 724 * responsibility. 725 */ 726 void 727 erase(iterator __position) 728 { _M_t.erase(__position); } 729 #endif 730 731 /** 732 * @brief Erases elements according to the provided key. 733 * @param __x Key of element to be erased. 734 * @return The number of elements erased. 735 * 736 * This function erases all elements located by the given key from a 737 * %multimap. 738 * Note that this function only erases the element, and that if 739 * the element is itself a pointer, the pointed-to memory is not touched 740 * in any way. Managing the pointer is the user's responsibility. 741 */ 742 size_type 743 erase(const key_type& __x) 744 { return _M_t.erase(__x); } 745 746 #if __cplusplus >= 201103L 747 // _GLIBCXX_RESOLVE_LIB_DEFECTS 748 // DR 130. Associative erase should return an iterator. 749 /** 750 * @brief Erases a [first,last) range of elements from a %multimap. 751 * @param __first Iterator pointing to the start of the range to be 752 * erased. 753 * @param __last Iterator pointing to the end of the range to be 754 * erased . 755 * @return The iterator @a __last. 756 * 757 * This function erases a sequence of elements from a %multimap. 758 * Note that this function only erases the elements, and that if 759 * the elements themselves are pointers, the pointed-to memory is not 760 * touched in any way. Managing the pointer is the user's 761 * responsibility. 762 */ 763 iterator 764 erase(const_iterator __first, const_iterator __last) 765 { return _M_t.erase(__first, __last); } 766 #else 767 // _GLIBCXX_RESOLVE_LIB_DEFECTS 768 // DR 130. Associative erase should return an iterator. 769 /** 770 * @brief Erases a [first,last) range of elements from a %multimap. 771 * @param __first Iterator pointing to the start of the range to be 772 * erased. 773 * @param __last Iterator pointing to the end of the range to 774 * be erased. 775 * 776 * This function erases a sequence of elements from a %multimap. 777 * Note that this function only erases the elements, and that if 778 * the elements themselves are pointers, the pointed-to memory is not 779 * touched in any way. Managing the pointer is the user's 780 * responsibility. 781 */ 782 void 783 erase(iterator __first, iterator __last) 784 { _M_t.erase(__first, __last); } 785 #endif 786 787 /** 788 * @brief Swaps data with another %multimap. 789 * @param __x A %multimap of the same element and allocator types. 790 * 791 * This exchanges the elements between two multimaps in constant time. 792 * (It is only swapping a pointer, an integer, and an instance of 793 * the @c Compare type (which itself is often stateless and empty), so it 794 * should be quite fast.) 795 * Note that the global std::swap() function is specialized such that 796 * std::swap(m1,m2) will feed to this function. 797 * 798 * Whether the allocators are swapped depends on the allocator traits. 799 */ 800 void 801 swap(multimap& __x) 802 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value) 803 { _M_t.swap(__x._M_t); } 804 805 /** 806 * Erases all elements in a %multimap. Note that this function only 807 * erases the elements, and that if the elements themselves are pointers, 808 * the pointed-to memory is not touched in any way. Managing the pointer 809 * is the user's responsibility. 810 */ 811 void 812 clear() _GLIBCXX_NOEXCEPT 813 { _M_t.clear(); } 814 815 // observers 816 /** 817 * Returns the key comparison object out of which the %multimap 818 * was constructed. 819 */ 820 key_compare 821 key_comp() const 822 { return _M_t.key_comp(); } 823 824 /** 825 * Returns a value comparison object, built from the key comparison 826 * object out of which the %multimap was constructed. 827 */ 828 value_compare 829 value_comp() const 830 { return value_compare(_M_t.key_comp()); } 831 832 // multimap operations 833 834 ///@{ 835 /** 836 * @brief Tries to locate an element in a %multimap. 837 * @param __x Key of (key, value) pair to be located. 838 * @return Iterator pointing to sought-after element, 839 * or end() if not found. 840 * 841 * This function takes a key and tries to locate the element with which 842 * the key matches. If successful the function returns an iterator 843 * pointing to the sought after %pair. If unsuccessful it returns the 844 * past-the-end ( @c end() ) iterator. 845 */ 846 iterator 847 find(const key_type& __x) 848 { return _M_t.find(__x); } 849 850 #if __cplusplus > 201103L 851 template<typename _Kt> 852 auto 853 find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x)) 854 { return _M_t._M_find_tr(__x); } 855 #endif 856 ///@} 857 858 ///@{ 859 /** 860 * @brief Tries to locate an element in a %multimap. 861 * @param __x Key of (key, value) pair to be located. 862 * @return Read-only (constant) iterator pointing to sought-after 863 * element, or end() if not found. 864 * 865 * This function takes a key and tries to locate the element with which 866 * the key matches. If successful the function returns a constant 867 * iterator pointing to the sought after %pair. If unsuccessful it 868 * returns the past-the-end ( @c end() ) iterator. 869 */ 870 const_iterator 871 find(const key_type& __x) const 872 { return _M_t.find(__x); } 873 874 #if __cplusplus > 201103L 875 template<typename _Kt> 876 auto 877 find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x)) 878 { return _M_t._M_find_tr(__x); } 879 #endif 880 ///@} 881 882 ///@{ 883 /** 884 * @brief Finds the number of elements with given key. 885 * @param __x Key of (key, value) pairs to be located. 886 * @return Number of elements with specified key. 887 */ 888 size_type 889 count(const key_type& __x) const 890 { return _M_t.count(__x); } 891 892 #if __cplusplus > 201103L 893 template<typename _Kt> 894 auto 895 count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x)) 896 { return _M_t._M_count_tr(__x); } 897 #endif 898 ///@} 899 900 #if __cplusplus > 201703L 901 ///@{ 902 /** 903 * @brief Finds whether an element with the given key exists. 904 * @param __x Key of (key, value) pairs to be located. 905 * @return True if there is any element with the specified key. 906 */ 907 bool 908 contains(const key_type& __x) const 909 { return _M_t.find(__x) != _M_t.end(); } 910 911 template<typename _Kt> 912 auto 913 contains(const _Kt& __x) const 914 -> decltype(_M_t._M_find_tr(__x), void(), true) 915 { return _M_t._M_find_tr(__x) != _M_t.end(); } 916 ///@} 917 #endif 918 919 ///@{ 920 /** 921 * @brief Finds the beginning of a subsequence matching given key. 922 * @param __x Key of (key, value) pair to be located. 923 * @return Iterator pointing to first element equal to or greater 924 * than key, or end(). 925 * 926 * This function returns the first element of a subsequence of elements 927 * that matches the given key. If unsuccessful it returns an iterator 928 * pointing to the first element that has a greater value than given key 929 * or end() if no such element exists. 930 */ 931 iterator 932 lower_bound(const key_type& __x) 933 { return _M_t.lower_bound(__x); } 934 935 #if __cplusplus > 201103L 936 template<typename _Kt> 937 auto 938 lower_bound(const _Kt& __x) 939 -> decltype(iterator(_M_t._M_lower_bound_tr(__x))) 940 { return iterator(_M_t._M_lower_bound_tr(__x)); } 941 #endif 942 ///@} 943 944 ///@{ 945 /** 946 * @brief Finds the beginning of a subsequence matching given key. 947 * @param __x Key of (key, value) pair to be located. 948 * @return Read-only (constant) iterator pointing to first element 949 * equal to or greater than key, or end(). 950 * 951 * This function returns the first element of a subsequence of 952 * elements that matches the given key. If unsuccessful the 953 * iterator will point to the next greatest element or, if no 954 * such greater element exists, to end(). 955 */ 956 const_iterator 957 lower_bound(const key_type& __x) const 958 { return _M_t.lower_bound(__x); } 959 960 #if __cplusplus > 201103L 961 template<typename _Kt> 962 auto 963 lower_bound(const _Kt& __x) const 964 -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x))) 965 { return const_iterator(_M_t._M_lower_bound_tr(__x)); } 966 #endif 967 ///@} 968 969 ///@{ 970 /** 971 * @brief Finds the end of a subsequence matching given key. 972 * @param __x Key of (key, value) pair to be located. 973 * @return Iterator pointing to the first element 974 * greater than key, or end(). 975 */ 976 iterator 977 upper_bound(const key_type& __x) 978 { return _M_t.upper_bound(__x); } 979 980 #if __cplusplus > 201103L 981 template<typename _Kt> 982 auto 983 upper_bound(const _Kt& __x) 984 -> decltype(iterator(_M_t._M_upper_bound_tr(__x))) 985 { return iterator(_M_t._M_upper_bound_tr(__x)); } 986 #endif 987 ///@} 988 989 ///@{ 990 /** 991 * @brief Finds the end of a subsequence matching given key. 992 * @param __x Key of (key, value) pair to be located. 993 * @return Read-only (constant) iterator pointing to first iterator 994 * greater than key, or end(). 995 */ 996 const_iterator 997 upper_bound(const key_type& __x) const 998 { return _M_t.upper_bound(__x); } 999 1000 #if __cplusplus > 201103L 1001 template<typename _Kt> 1002 auto 1003 upper_bound(const _Kt& __x) const 1004 -> decltype(const_iterator(_M_t._M_upper_bound_tr(__x))) 1005 { return const_iterator(_M_t._M_upper_bound_tr(__x)); } 1006 #endif 1007 ///@} 1008 1009 ///@{ 1010 /** 1011 * @brief Finds a subsequence matching given key. 1012 * @param __x Key of (key, value) pairs to be located. 1013 * @return Pair of iterators that possibly points to the subsequence 1014 * matching given key. 1015 * 1016 * This function is equivalent to 1017 * @code 1018 * std::make_pair(c.lower_bound(val), 1019 * c.upper_bound(val)) 1020 * @endcode 1021 * (but is faster than making the calls separately). 1022 */ 1023 std::pair<iterator, iterator> 1024 equal_range(const key_type& __x) 1025 { return _M_t.equal_range(__x); } 1026 1027 #if __cplusplus > 201103L 1028 template<typename _Kt> 1029 auto 1030 equal_range(const _Kt& __x) 1031 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x))) 1032 { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); } 1033 #endif 1034 ///@} 1035 1036 ///@{ 1037 /** 1038 * @brief Finds a subsequence matching given key. 1039 * @param __x Key of (key, value) pairs to be located. 1040 * @return Pair of read-only (constant) iterators that possibly points 1041 * to the subsequence matching given key. 1042 * 1043 * This function is equivalent to 1044 * @code 1045 * std::make_pair(c.lower_bound(val), 1046 * c.upper_bound(val)) 1047 * @endcode 1048 * (but is faster than making the calls separately). 1049 */ 1050 std::pair<const_iterator, const_iterator> 1051 equal_range(const key_type& __x) const 1052 { return _M_t.equal_range(__x); } 1053 1054 #if __cplusplus > 201103L 1055 template<typename _Kt> 1056 auto 1057 equal_range(const _Kt& __x) const 1058 -> decltype(pair<const_iterator, const_iterator>( 1059 _M_t._M_equal_range_tr(__x))) 1060 { 1061 return pair<const_iterator, const_iterator>( 1062 _M_t._M_equal_range_tr(__x)); 1063 } 1064 #endif 1065 ///@} 1066 1067 template<typename _K1, typename _T1, typename _C1, typename _A1> 1068 friend bool 1069 operator==(const multimap<_K1, _T1, _C1, _A1>&, 1070 const multimap<_K1, _T1, _C1, _A1>&); 1071 1072 #if __cpp_lib_three_way_comparison 1073 template<typename _K1, typename _T1, typename _C1, typename _A1> 1074 friend __detail::__synth3way_t<pair<const _K1, _T1>> 1075 operator<=>(const multimap<_K1, _T1, _C1, _A1>&, 1076 const multimap<_K1, _T1, _C1, _A1>&); 1077 #else 1078 template<typename _K1, typename _T1, typename _C1, typename _A1> 1079 friend bool 1080 operator<(const multimap<_K1, _T1, _C1, _A1>&, 1081 const multimap<_K1, _T1, _C1, _A1>&); 1082 #endif 1083 }; 1084 1085 #if __cpp_deduction_guides >= 201606 1086 1087 template<typename _InputIterator, 1088 typename _Compare = less<__iter_key_t<_InputIterator>>, 1089 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>, 1090 typename = _RequireInputIter<_InputIterator>, 1091 typename = _RequireNotAllocator<_Compare>, 1092 typename = _RequireAllocator<_Allocator>> 1093 multimap(_InputIterator, _InputIterator, 1094 _Compare = _Compare(), _Allocator = _Allocator()) 1095 -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, 1096 _Compare, _Allocator>; 1097 1098 template<typename _Key, typename _Tp, typename _Compare = less<_Key>, 1099 typename _Allocator = allocator<pair<const _Key, _Tp>>, 1100 typename = _RequireNotAllocator<_Compare>, 1101 typename = _RequireAllocator<_Allocator>> 1102 multimap(initializer_list<pair<_Key, _Tp>>, 1103 _Compare = _Compare(), _Allocator = _Allocator()) 1104 -> multimap<_Key, _Tp, _Compare, _Allocator>; 1105 1106 template<typename _InputIterator, typename _Allocator, 1107 typename = _RequireInputIter<_InputIterator>, 1108 typename = _RequireAllocator<_Allocator>> 1109 multimap(_InputIterator, _InputIterator, _Allocator) 1110 -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, 1111 less<__iter_key_t<_InputIterator>>, _Allocator>; 1112 1113 template<typename _Key, typename _Tp, typename _Allocator, 1114 typename = _RequireAllocator<_Allocator>> 1115 multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) 1116 -> multimap<_Key, _Tp, less<_Key>, _Allocator>; 1117 1118 #endif // deduction guides 1119 1120 /** 1121 * @brief Multimap equality comparison. 1122 * @param __x A %multimap. 1123 * @param __y A %multimap of the same type as @a __x. 1124 * @return True iff the size and elements of the maps are equal. 1125 * 1126 * This is an equivalence relation. It is linear in the size of the 1127 * multimaps. Multimaps are considered equivalent if their sizes are equal, 1128 * and if corresponding elements compare equal. 1129 */ 1130 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 1131 inline bool 1132 operator==(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 1133 const multimap<_Key, _Tp, _Compare, _Alloc>& __y) 1134 { return __x._M_t == __y._M_t; } 1135 1136 #if __cpp_lib_three_way_comparison 1137 /** 1138 * @brief Multimap ordering relation. 1139 * @param __x A `multimap`. 1140 * @param __y A `multimap` of the same type as `x`. 1141 * @return A value indicating whether `__x` is less than, equal to, 1142 * greater than, or incomparable with `__y`. 1143 * 1144 * This is a total ordering relation. It is linear in the size of the 1145 * maps. The elements must be comparable with @c <. 1146 * 1147 * See `std::lexicographical_compare_three_way()` for how the determination 1148 * is made. This operator is used to synthesize relational operators like 1149 * `<` and `>=` etc. 1150 */ 1151 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 1152 inline __detail::__synth3way_t<pair<const _Key, _Tp>> 1153 operator<=>(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 1154 const multimap<_Key, _Tp, _Compare, _Alloc>& __y) 1155 { return __x._M_t <=> __y._M_t; } 1156 #else 1157 /** 1158 * @brief Multimap ordering relation. 1159 * @param __x A %multimap. 1160 * @param __y A %multimap of the same type as @a __x. 1161 * @return True iff @a x is lexicographically less than @a y. 1162 * 1163 * This is a total ordering relation. It is linear in the size of the 1164 * multimaps. The elements must be comparable with @c <. 1165 * 1166 * See std::lexicographical_compare() for how the determination is made. 1167 */ 1168 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 1169 inline bool 1170 operator<(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 1171 const multimap<_Key, _Tp, _Compare, _Alloc>& __y) 1172 { return __x._M_t < __y._M_t; } 1173 1174 /// Based on operator== 1175 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 1176 inline bool 1177 operator!=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 1178 const multimap<_Key, _Tp, _Compare, _Alloc>& __y) 1179 { return !(__x == __y); } 1180 1181 /// Based on operator< 1182 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 1183 inline bool 1184 operator>(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 1185 const multimap<_Key, _Tp, _Compare, _Alloc>& __y) 1186 { return __y < __x; } 1187 1188 /// Based on operator< 1189 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 1190 inline bool 1191 operator<=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 1192 const multimap<_Key, _Tp, _Compare, _Alloc>& __y) 1193 { return !(__y < __x); } 1194 1195 /// Based on operator< 1196 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 1197 inline bool 1198 operator>=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 1199 const multimap<_Key, _Tp, _Compare, _Alloc>& __y) 1200 { return !(__x < __y); } 1201 #endif // three-way comparison 1202 1203 /// See std::multimap::swap(). 1204 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 1205 inline void 1206 swap(multimap<_Key, _Tp, _Compare, _Alloc>& __x, 1207 multimap<_Key, _Tp, _Compare, _Alloc>& __y) 1208 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y))) 1209 { __x.swap(__y); } 1210 1211 _GLIBCXX_END_NAMESPACE_CONTAINER 1212 1213 #if __cplusplus > 201402L 1214 // Allow std::multimap access to internals of compatible maps. 1215 template<typename _Key, typename _Val, typename _Cmp1, typename _Alloc, 1216 typename _Cmp2> 1217 struct 1218 _Rb_tree_merge_helper<_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp1, _Alloc>, 1219 _Cmp2> 1220 { 1221 private: 1222 friend class _GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp1, _Alloc>; 1223 1224 static auto& 1225 _S_get_tree(_GLIBCXX_STD_C::map<_Key, _Val, _Cmp2, _Alloc>& __map) 1226 { return __map._M_t; } 1227 1228 static auto& 1229 _S_get_tree(_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp2, _Alloc>& __map) 1230 { return __map._M_t; } 1231 }; 1232 #endif // C++17 1233 1234 _GLIBCXX_END_NAMESPACE_VERSION 1235 } // namespace std 1236 1237 #endif /* _STL_MULTIMAP_H */ 1238