1 // Map 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_map.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_MAP_H 57 #define _STL_MAP_H 1 58 59 #include <bits/functexcept.h> 60 #include <bits/concept_check.h> 61 #if __cplusplus >= 201103L 62 #include <initializer_list> 63 #include <tuple> 64 #endif 65 66 namespace std _GLIBCXX_VISIBILITY(default) 67 { 68 _GLIBCXX_BEGIN_NAMESPACE_VERSION 69 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 70 71 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 72 class multimap; 73 74 /** 75 * @brief A standard container made up of (key,value) pairs, which can be 76 * retrieved based on a key, in logarithmic time. 77 * 78 * @ingroup associative_containers 79 * 80 * @tparam _Key Type of key objects. 81 * @tparam _Tp Type of mapped objects. 82 * @tparam _Compare Comparison function object type, defaults to less<_Key>. 83 * @tparam _Alloc Allocator type, defaults to 84 * allocator<pair<const _Key, _Tp>. 85 * 86 * Meets the requirements of a <a href="tables.html#65">container</a>, a 87 * <a href="tables.html#66">reversible container</a>, and an 88 * <a href="tables.html#69">associative container</a> (using unique keys). 89 * For a @c map<Key,T> the key_type is Key, the mapped_type is T, and the 90 * value_type is std::pair<const Key,T>. 91 * 92 * Maps support bidirectional iterators. 93 * 94 * The private tree data is declared exactly the same way for map and 95 * multimap; the distinction is made entirely in how the tree functions are 96 * called (*_unique versus *_equal, same as the standard). 97 */ 98 template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>, 99 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 100 class map 101 { 102 public: 103 typedef _Key key_type; 104 typedef _Tp mapped_type; 105 typedef std::pair<const _Key, _Tp> value_type; 106 typedef _Compare key_compare; 107 typedef _Alloc allocator_type; 108 109 private: 110 #ifdef _GLIBCXX_CONCEPT_CHECKS 111 // concept requirements 112 typedef typename _Alloc::value_type _Alloc_value_type; 113 # if __cplusplus < 201103L 114 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 115 # endif 116 __glibcxx_class_requires4(_Compare, bool, _Key, _Key, 117 _BinaryFunctionConcept) 118 __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept) 119 #endif 120 121 #if __cplusplus >= 201103L 122 #if __cplusplus > 201703L || defined __STRICT_ANSI__ 123 static_assert(is_same<typename _Alloc::value_type, value_type>::value, 124 "std::map must have the same value_type as its allocator"); 125 #endif 126 #endif 127 128 public: 129 #pragma GCC diagnostic push 130 #pragma GCC diagnostic ignored "-Wdeprecated-declarations" 131 class value_compare 132 : public std::binary_function<value_type, value_type, bool> 133 { 134 friend class map<_Key, _Tp, _Compare, _Alloc>; 135 protected: 136 _Compare comp; 137 138 value_compare(_Compare __c) 139 : comp(__c) { } 140 141 public: 142 bool operator()(const value_type& __x, const value_type& __y) const 143 { return comp(__x.first, __y.first); } 144 }; 145 #pragma GCC diagnostic pop 146 147 private: 148 /// This turns a red-black tree into a [multi]map. 149 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 150 rebind<value_type>::other _Pair_alloc_type; 151 152 typedef _Rb_tree<key_type, value_type, _Select1st<value_type>, 153 key_compare, _Pair_alloc_type> _Rep_type; 154 155 /// The actual tree structure. 156 _Rep_type _M_t; 157 158 typedef __gnu_cxx::__alloc_traits<_Pair_alloc_type> _Alloc_traits; 159 160 #if __cplusplus >= 201703L 161 template<typename _Up, typename _Vp = remove_reference_t<_Up>> 162 static constexpr bool __usable_key 163 = __or_v<is_same<const _Vp, const _Key>, 164 __and_<is_scalar<_Vp>, is_scalar<_Key>>>; 165 #endif 166 167 public: 168 // many of these are specified differently in ISO, but the following are 169 // "functionally equivalent" 170 typedef typename _Alloc_traits::pointer pointer; 171 typedef typename _Alloc_traits::const_pointer const_pointer; 172 typedef typename _Alloc_traits::reference reference; 173 typedef typename _Alloc_traits::const_reference const_reference; 174 typedef typename _Rep_type::iterator iterator; 175 typedef typename _Rep_type::const_iterator const_iterator; 176 typedef typename _Rep_type::size_type size_type; 177 typedef typename _Rep_type::difference_type difference_type; 178 typedef typename _Rep_type::reverse_iterator reverse_iterator; 179 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 180 181 #if __cplusplus > 201402L 182 using node_type = typename _Rep_type::node_type; 183 using insert_return_type = typename _Rep_type::insert_return_type; 184 #endif 185 186 // [23.3.1.1] construct/copy/destroy 187 // (get_allocator() is also listed in this section) 188 189 /** 190 * @brief Default constructor creates no elements. 191 */ 192 #if __cplusplus < 201103L 193 map() : _M_t() { } 194 #else 195 map() = default; 196 #endif 197 198 /** 199 * @brief Creates a %map with no elements. 200 * @param __comp A comparison object. 201 * @param __a An allocator object. 202 */ 203 explicit 204 map(const _Compare& __comp, 205 const allocator_type& __a = allocator_type()) 206 : _M_t(__comp, _Pair_alloc_type(__a)) { } 207 208 /** 209 * @brief %Map copy constructor. 210 * 211 * Whether the allocator is copied depends on the allocator traits. 212 */ 213 #if __cplusplus < 201103L 214 map(const map& __x) 215 : _M_t(__x._M_t) { } 216 #else 217 map(const map&) = default; 218 219 /** 220 * @brief %Map move constructor. 221 * 222 * The newly-created %map contains the exact contents of the moved 223 * instance. The moved instance is a valid, but unspecified, %map. 224 */ 225 map(map&&) = default; 226 227 /** 228 * @brief Builds a %map from an initializer_list. 229 * @param __l An initializer_list. 230 * @param __comp A comparison object. 231 * @param __a An allocator object. 232 * 233 * Create a %map consisting of copies of the elements in the 234 * initializer_list @a __l. 235 * This is linear in N if the range is already sorted, and NlogN 236 * otherwise (where N is @a __l.size()). 237 */ 238 map(initializer_list<value_type> __l, 239 const _Compare& __comp = _Compare(), 240 const allocator_type& __a = allocator_type()) 241 : _M_t(__comp, _Pair_alloc_type(__a)) 242 { _M_t._M_insert_range_unique(__l.begin(), __l.end()); } 243 244 /// Allocator-extended default constructor. 245 explicit 246 map(const allocator_type& __a) 247 : _M_t(_Pair_alloc_type(__a)) { } 248 249 /// Allocator-extended copy constructor. 250 map(const map& __m, const __type_identity_t<allocator_type>& __a) 251 : _M_t(__m._M_t, _Pair_alloc_type(__a)) { } 252 253 /// Allocator-extended move constructor. 254 map(map&& __m, const __type_identity_t<allocator_type>& __a) 255 noexcept(is_nothrow_copy_constructible<_Compare>::value 256 && _Alloc_traits::_S_always_equal()) 257 : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { } 258 259 /// Allocator-extended initialier-list constructor. 260 map(initializer_list<value_type> __l, const allocator_type& __a) 261 : _M_t(_Pair_alloc_type(__a)) 262 { _M_t._M_insert_range_unique(__l.begin(), __l.end()); } 263 264 /// Allocator-extended range constructor. 265 template<typename _InputIterator> 266 map(_InputIterator __first, _InputIterator __last, 267 const allocator_type& __a) 268 : _M_t(_Pair_alloc_type(__a)) 269 { _M_t._M_insert_range_unique(__first, __last); } 270 #endif 271 272 /** 273 * @brief Builds a %map from a range. 274 * @param __first An input iterator. 275 * @param __last An input iterator. 276 * 277 * Create a %map consisting of copies of the elements from 278 * [__first,__last). This is linear in N if the range is 279 * already sorted, and NlogN otherwise (where N is 280 * distance(__first,__last)). 281 */ 282 template<typename _InputIterator> 283 map(_InputIterator __first, _InputIterator __last) 284 : _M_t() 285 { _M_t._M_insert_range_unique(__first, __last); } 286 287 /** 288 * @brief Builds a %map from a range. 289 * @param __first An input iterator. 290 * @param __last An input iterator. 291 * @param __comp A comparison functor. 292 * @param __a An allocator object. 293 * 294 * Create a %map consisting of copies of the elements from 295 * [__first,__last). This is linear in N if the range is 296 * already sorted, and NlogN otherwise (where N is 297 * distance(__first,__last)). 298 */ 299 template<typename _InputIterator> 300 map(_InputIterator __first, _InputIterator __last, 301 const _Compare& __comp, 302 const allocator_type& __a = allocator_type()) 303 : _M_t(__comp, _Pair_alloc_type(__a)) 304 { _M_t._M_insert_range_unique(__first, __last); } 305 306 #if __cplusplus >= 201103L 307 /** 308 * The dtor only erases the elements, and note that if the elements 309 * themselves are pointers, the pointed-to memory is not touched in any 310 * way. Managing the pointer is the user's responsibility. 311 */ 312 ~map() = default; 313 #endif 314 315 /** 316 * @brief %Map assignment operator. 317 * 318 * Whether the allocator is copied depends on the allocator traits. 319 */ 320 #if __cplusplus < 201103L 321 map& 322 operator=(const map& __x) 323 { 324 _M_t = __x._M_t; 325 return *this; 326 } 327 #else 328 map& 329 operator=(const map&) = default; 330 331 /// Move assignment operator. 332 map& 333 operator=(map&&) = default; 334 335 /** 336 * @brief %Map list assignment operator. 337 * @param __l An initializer_list. 338 * 339 * This function fills a %map with copies of the elements in the 340 * initializer list @a __l. 341 * 342 * Note that the assignment completely changes the %map and 343 * that the resulting %map's size is the same as the number 344 * of elements assigned. 345 */ 346 map& 347 operator=(initializer_list<value_type> __l) 348 { 349 _M_t._M_assign_unique(__l.begin(), __l.end()); 350 return *this; 351 } 352 #endif 353 354 /// Get a copy of the memory allocation object. 355 allocator_type 356 get_allocator() const _GLIBCXX_NOEXCEPT 357 { return allocator_type(_M_t.get_allocator()); } 358 359 // iterators 360 /** 361 * Returns a read/write iterator that points to the first pair in the 362 * %map. 363 * Iteration is done in ascending order according to the keys. 364 */ 365 iterator 366 begin() _GLIBCXX_NOEXCEPT 367 { return _M_t.begin(); } 368 369 /** 370 * Returns a read-only (constant) iterator that points to the first pair 371 * in the %map. Iteration is done in ascending order according to the 372 * keys. 373 */ 374 const_iterator 375 begin() const _GLIBCXX_NOEXCEPT 376 { return _M_t.begin(); } 377 378 /** 379 * Returns a read/write iterator that points one past the last 380 * pair in the %map. Iteration is done in ascending order 381 * according to the keys. 382 */ 383 iterator 384 end() _GLIBCXX_NOEXCEPT 385 { return _M_t.end(); } 386 387 /** 388 * Returns a read-only (constant) iterator that points one past the last 389 * pair in the %map. Iteration is done in ascending order according to 390 * the keys. 391 */ 392 const_iterator 393 end() const _GLIBCXX_NOEXCEPT 394 { return _M_t.end(); } 395 396 /** 397 * Returns a read/write reverse iterator that points to the last pair in 398 * the %map. Iteration is done in descending order according to the 399 * keys. 400 */ 401 reverse_iterator 402 rbegin() _GLIBCXX_NOEXCEPT 403 { return _M_t.rbegin(); } 404 405 /** 406 * Returns a read-only (constant) reverse iterator that points to the 407 * last pair in the %map. Iteration is done in descending order 408 * according to the keys. 409 */ 410 const_reverse_iterator 411 rbegin() const _GLIBCXX_NOEXCEPT 412 { return _M_t.rbegin(); } 413 414 /** 415 * Returns a read/write reverse iterator that points to one before the 416 * first pair in the %map. Iteration is done in descending order 417 * according to the keys. 418 */ 419 reverse_iterator 420 rend() _GLIBCXX_NOEXCEPT 421 { return _M_t.rend(); } 422 423 /** 424 * Returns a read-only (constant) reverse iterator that points to one 425 * before the first pair in the %map. Iteration is done in descending 426 * order according to the keys. 427 */ 428 const_reverse_iterator 429 rend() const _GLIBCXX_NOEXCEPT 430 { return _M_t.rend(); } 431 432 #if __cplusplus >= 201103L 433 /** 434 * Returns a read-only (constant) iterator that points to the first pair 435 * in the %map. Iteration is done in ascending order according to the 436 * keys. 437 */ 438 const_iterator 439 cbegin() const noexcept 440 { return _M_t.begin(); } 441 442 /** 443 * Returns a read-only (constant) iterator that points one past the last 444 * pair in the %map. Iteration is done in ascending order according to 445 * the keys. 446 */ 447 const_iterator 448 cend() const noexcept 449 { return _M_t.end(); } 450 451 /** 452 * Returns a read-only (constant) reverse iterator that points to the 453 * last pair in the %map. Iteration is done in descending order 454 * according to the keys. 455 */ 456 const_reverse_iterator 457 crbegin() const noexcept 458 { return _M_t.rbegin(); } 459 460 /** 461 * Returns a read-only (constant) reverse iterator that points to one 462 * before the first pair in the %map. Iteration is done in descending 463 * order according to the keys. 464 */ 465 const_reverse_iterator 466 crend() const noexcept 467 { return _M_t.rend(); } 468 #endif 469 470 // capacity 471 /** Returns true if the %map is empty. (Thus begin() would equal 472 * end().) 473 */ 474 _GLIBCXX_NODISCARD bool 475 empty() const _GLIBCXX_NOEXCEPT 476 { return _M_t.empty(); } 477 478 /** Returns the size of the %map. */ 479 size_type 480 size() const _GLIBCXX_NOEXCEPT 481 { return _M_t.size(); } 482 483 /** Returns the maximum size of the %map. */ 484 size_type 485 max_size() const _GLIBCXX_NOEXCEPT 486 { return _M_t.max_size(); } 487 488 // [23.3.1.2] element access 489 /** 490 * @brief Subscript ( @c [] ) access to %map data. 491 * @param __k The key for which data should be retrieved. 492 * @return A reference to the data of the (key,data) %pair. 493 * 494 * Allows for easy lookup with the subscript ( @c [] ) 495 * operator. Returns data associated with the key specified in 496 * subscript. If the key does not exist, a pair with that key 497 * is created using default values, which is then returned. 498 * 499 * Lookup requires logarithmic time. 500 */ 501 mapped_type& 502 operator[](const key_type& __k) 503 { 504 // concept requirements 505 __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>) 506 507 iterator __i = lower_bound(__k); 508 // __i->first is greater than or equivalent to __k. 509 if (__i == end() || key_comp()(__k, (*__i).first)) 510 #if __cplusplus >= 201103L 511 __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct, 512 std::tuple<const key_type&>(__k), 513 std::tuple<>()); 514 #else 515 __i = insert(__i, value_type(__k, mapped_type())); 516 #endif 517 return (*__i).second; 518 } 519 520 #if __cplusplus >= 201103L 521 mapped_type& 522 operator[](key_type&& __k) 523 { 524 // concept requirements 525 __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>) 526 527 iterator __i = lower_bound(__k); 528 // __i->first is greater than or equivalent to __k. 529 if (__i == end() || key_comp()(__k, (*__i).first)) 530 __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct, 531 std::forward_as_tuple(std::move(__k)), 532 std::tuple<>()); 533 return (*__i).second; 534 } 535 #endif 536 537 // _GLIBCXX_RESOLVE_LIB_DEFECTS 538 // DR 464. Suggestion for new member functions in standard containers. 539 /** 540 * @brief Access to %map data. 541 * @param __k The key for which data should be retrieved. 542 * @return A reference to the data whose key is equivalent to @a __k, if 543 * such a data is present in the %map. 544 * @throw std::out_of_range If no such data is present. 545 */ 546 mapped_type& 547 at(const key_type& __k) 548 { 549 iterator __i = lower_bound(__k); 550 if (__i == end() || key_comp()(__k, (*__i).first)) 551 __throw_out_of_range(__N("map::at")); 552 return (*__i).second; 553 } 554 555 const mapped_type& 556 at(const key_type& __k) const 557 { 558 const_iterator __i = lower_bound(__k); 559 if (__i == end() || key_comp()(__k, (*__i).first)) 560 __throw_out_of_range(__N("map::at")); 561 return (*__i).second; 562 } 563 564 // modifiers 565 #if __cplusplus >= 201103L 566 /** 567 * @brief Attempts to build and insert a std::pair into the %map. 568 * 569 * @param __args Arguments used to generate a new pair instance (see 570 * std::piecewise_contruct for passing arguments to each 571 * part of the pair constructor). 572 * 573 * @return A pair, of which the first element is an iterator that points 574 * to the possibly inserted pair, and the second is a bool that 575 * is true if the pair was actually inserted. 576 * 577 * This function attempts to build and insert a (key, value) %pair into 578 * the %map. 579 * A %map relies on unique keys and thus a %pair is only inserted if its 580 * first element (the key) is not already present in the %map. 581 * 582 * Insertion requires logarithmic time. 583 */ 584 template<typename... _Args> 585 std::pair<iterator, bool> 586 emplace(_Args&&... __args) 587 { 588 #if __cplusplus >= 201703L 589 if constexpr (sizeof...(_Args) == 2) 590 if constexpr (is_same_v<allocator_type, allocator<value_type>>) 591 { 592 auto&& [__a, __v] = pair<_Args&...>(__args...); 593 if constexpr (__usable_key<decltype(__a)>) 594 { 595 const key_type& __k = __a; 596 iterator __i = lower_bound(__k); 597 if (__i == end() || key_comp()(__k, (*__i).first)) 598 { 599 __i = emplace_hint(__i, std::forward<_Args>(__args)...); 600 return {__i, true}; 601 } 602 return {__i, false}; 603 } 604 } 605 #endif 606 return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); 607 } 608 609 /** 610 * @brief Attempts to build and insert a std::pair into the %map. 611 * 612 * @param __pos An iterator that serves as a hint as to where the pair 613 * should be inserted. 614 * @param __args Arguments used to generate a new pair instance (see 615 * std::piecewise_contruct for passing arguments to each 616 * part of the pair constructor). 617 * @return An iterator that points to the element with key of the 618 * std::pair built from @a __args (may or may not be that 619 * std::pair). 620 * 621 * This function is not concerned about whether the insertion took place, 622 * and thus does not return a boolean like the single-argument emplace() 623 * does. 624 * Note that the first parameter is only a hint and can potentially 625 * improve the performance of the insertion process. A bad hint would 626 * cause no gains in efficiency. 627 * 628 * See 629 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 630 * for more on @a hinting. 631 * 632 * Insertion requires logarithmic time (if the hint is not taken). 633 */ 634 template<typename... _Args> 635 iterator 636 emplace_hint(const_iterator __pos, _Args&&... __args) 637 { 638 return _M_t._M_emplace_hint_unique(__pos, 639 std::forward<_Args>(__args)...); 640 } 641 #endif 642 643 #if __cplusplus > 201402L 644 /// Extract a node. 645 node_type 646 extract(const_iterator __pos) 647 { 648 __glibcxx_assert(__pos != end()); 649 return _M_t.extract(__pos); 650 } 651 652 /// Extract a node. 653 node_type 654 extract(const key_type& __x) 655 { return _M_t.extract(__x); } 656 657 /// Re-insert an extracted node. 658 insert_return_type 659 insert(node_type&& __nh) 660 { return _M_t._M_reinsert_node_unique(std::move(__nh)); } 661 662 /// Re-insert an extracted node. 663 iterator 664 insert(const_iterator __hint, node_type&& __nh) 665 { return _M_t._M_reinsert_node_hint_unique(__hint, std::move(__nh)); } 666 667 template<typename, typename> 668 friend struct std::_Rb_tree_merge_helper; 669 670 template<typename _Cmp2> 671 void 672 merge(map<_Key, _Tp, _Cmp2, _Alloc>& __source) 673 { 674 using _Merge_helper = _Rb_tree_merge_helper<map, _Cmp2>; 675 _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source)); 676 } 677 678 template<typename _Cmp2> 679 void 680 merge(map<_Key, _Tp, _Cmp2, _Alloc>&& __source) 681 { merge(__source); } 682 683 template<typename _Cmp2> 684 void 685 merge(multimap<_Key, _Tp, _Cmp2, _Alloc>& __source) 686 { 687 using _Merge_helper = _Rb_tree_merge_helper<map, _Cmp2>; 688 _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source)); 689 } 690 691 template<typename _Cmp2> 692 void 693 merge(multimap<_Key, _Tp, _Cmp2, _Alloc>&& __source) 694 { merge(__source); } 695 #endif // C++17 696 697 #if __cplusplus > 201402L 698 #define __cpp_lib_map_try_emplace 201411L 699 /** 700 * @brief Attempts to build and insert a std::pair into the %map. 701 * 702 * @param __k Key to use for finding a possibly existing pair in 703 * the map. 704 * @param __args Arguments used to generate the .second for a new pair 705 * instance. 706 * 707 * @return A pair, of which the first element is an iterator that points 708 * to the possibly inserted pair, and the second is a bool that 709 * is true if the pair was actually inserted. 710 * 711 * This function attempts to build and insert a (key, value) %pair into 712 * the %map. 713 * A %map relies on unique keys and thus a %pair is only inserted if its 714 * first element (the key) is not already present in the %map. 715 * If a %pair is not inserted, this function has no effect. 716 * 717 * Insertion requires logarithmic time. 718 */ 719 template <typename... _Args> 720 pair<iterator, bool> 721 try_emplace(const key_type& __k, _Args&&... __args) 722 { 723 iterator __i = lower_bound(__k); 724 if (__i == end() || key_comp()(__k, (*__i).first)) 725 { 726 __i = emplace_hint(__i, std::piecewise_construct, 727 std::forward_as_tuple(__k), 728 std::forward_as_tuple( 729 std::forward<_Args>(__args)...)); 730 return {__i, true}; 731 } 732 return {__i, false}; 733 } 734 735 // move-capable overload 736 template <typename... _Args> 737 pair<iterator, bool> 738 try_emplace(key_type&& __k, _Args&&... __args) 739 { 740 iterator __i = lower_bound(__k); 741 if (__i == end() || key_comp()(__k, (*__i).first)) 742 { 743 __i = emplace_hint(__i, std::piecewise_construct, 744 std::forward_as_tuple(std::move(__k)), 745 std::forward_as_tuple( 746 std::forward<_Args>(__args)...)); 747 return {__i, true}; 748 } 749 return {__i, false}; 750 } 751 752 /** 753 * @brief Attempts to build and insert a std::pair into the %map. 754 * 755 * @param __hint An iterator that serves as a hint as to where the 756 * pair should be inserted. 757 * @param __k Key to use for finding a possibly existing pair in 758 * the map. 759 * @param __args Arguments used to generate the .second for a new pair 760 * instance. 761 * @return An iterator that points to the element with key of the 762 * std::pair built from @a __args (may or may not be that 763 * std::pair). 764 * 765 * This function is not concerned about whether the insertion took place, 766 * and thus does not return a boolean like the single-argument 767 * try_emplace() does. However, if insertion did not take place, 768 * this function has no effect. 769 * Note that the first parameter is only a hint and can potentially 770 * improve the performance of the insertion process. A bad hint would 771 * cause no gains in efficiency. 772 * 773 * See 774 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 775 * for more on @a hinting. 776 * 777 * Insertion requires logarithmic time (if the hint is not taken). 778 */ 779 template <typename... _Args> 780 iterator 781 try_emplace(const_iterator __hint, const key_type& __k, 782 _Args&&... __args) 783 { 784 iterator __i; 785 auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k); 786 if (__true_hint.second) 787 __i = emplace_hint(iterator(__true_hint.second), 788 std::piecewise_construct, 789 std::forward_as_tuple(__k), 790 std::forward_as_tuple( 791 std::forward<_Args>(__args)...)); 792 else 793 __i = iterator(__true_hint.first); 794 return __i; 795 } 796 797 // move-capable overload 798 template <typename... _Args> 799 iterator 800 try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args) 801 { 802 iterator __i; 803 auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k); 804 if (__true_hint.second) 805 __i = emplace_hint(iterator(__true_hint.second), 806 std::piecewise_construct, 807 std::forward_as_tuple(std::move(__k)), 808 std::forward_as_tuple( 809 std::forward<_Args>(__args)...)); 810 else 811 __i = iterator(__true_hint.first); 812 return __i; 813 } 814 #endif 815 816 /** 817 * @brief Attempts to insert a std::pair into the %map. 818 * @param __x Pair to be inserted (see std::make_pair for easy 819 * creation of pairs). 820 * 821 * @return A pair, of which the first element is an iterator that 822 * points to the possibly inserted pair, and the second is 823 * a bool that is true if the pair was actually inserted. 824 * 825 * This function attempts to insert a (key, value) %pair into the %map. 826 * A %map relies on unique keys and thus a %pair is only inserted if its 827 * first element (the key) is not already present in the %map. 828 * 829 * Insertion requires logarithmic time. 830 * @{ 831 */ 832 std::pair<iterator, bool> 833 insert(const value_type& __x) 834 { return _M_t._M_insert_unique(__x); } 835 836 #if __cplusplus >= 201103L 837 // _GLIBCXX_RESOLVE_LIB_DEFECTS 838 // 2354. Unnecessary copying when inserting into maps with braced-init 839 std::pair<iterator, bool> 840 insert(value_type&& __x) 841 { return _M_t._M_insert_unique(std::move(__x)); } 842 843 template<typename _Pair> 844 __enable_if_t<is_constructible<value_type, _Pair>::value, 845 pair<iterator, bool>> 846 insert(_Pair&& __x) 847 { 848 #if __cplusplus >= 201703L 849 using _P2 = remove_reference_t<_Pair>; 850 if constexpr (__is_pair<_P2>) 851 if constexpr (is_same_v<allocator_type, allocator<value_type>>) 852 if constexpr (__usable_key<typename _P2::first_type>) 853 { 854 const key_type& __k = __x.first; 855 iterator __i = lower_bound(__k); 856 if (__i == end() || key_comp()(__k, (*__i).first)) 857 { 858 __i = emplace_hint(__i, std::forward<_Pair>(__x)); 859 return {__i, true}; 860 } 861 return {__i, false}; 862 } 863 #endif 864 return _M_t._M_emplace_unique(std::forward<_Pair>(__x)); 865 } 866 #endif 867 /// @} 868 869 #if __cplusplus >= 201103L 870 /** 871 * @brief Attempts to insert a list of std::pairs into the %map. 872 * @param __list A std::initializer_list<value_type> of pairs to be 873 * inserted. 874 * 875 * Complexity similar to that of the range constructor. 876 */ 877 void 878 insert(std::initializer_list<value_type> __list) 879 { insert(__list.begin(), __list.end()); } 880 #endif 881 882 /** 883 * @brief Attempts to insert a std::pair into the %map. 884 * @param __position An iterator that serves as a hint as to where the 885 * pair should be inserted. 886 * @param __x Pair to be inserted (see std::make_pair for easy creation 887 * of pairs). 888 * @return An iterator that points to the element with key of 889 * @a __x (may or may not be the %pair passed in). 890 * 891 892 * This function is not concerned about whether the insertion 893 * took place, and thus does not return a boolean like the 894 * single-argument insert() does. Note that the first 895 * parameter is only a hint and can potentially improve the 896 * performance of the insertion process. A bad hint would 897 * cause no gains in efficiency. 898 * 899 * See 900 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 901 * for more on @a hinting. 902 * 903 * Insertion requires logarithmic time (if the hint is not taken). 904 * @{ 905 */ 906 iterator 907 #if __cplusplus >= 201103L 908 insert(const_iterator __position, const value_type& __x) 909 #else 910 insert(iterator __position, const value_type& __x) 911 #endif 912 { return _M_t._M_insert_unique_(__position, __x); } 913 914 #if __cplusplus >= 201103L 915 // _GLIBCXX_RESOLVE_LIB_DEFECTS 916 // 2354. Unnecessary copying when inserting into maps with braced-init 917 iterator 918 insert(const_iterator __position, value_type&& __x) 919 { return _M_t._M_insert_unique_(__position, std::move(__x)); } 920 921 template<typename _Pair> 922 __enable_if_t<is_constructible<value_type, _Pair>::value, iterator> 923 insert(const_iterator __position, _Pair&& __x) 924 { 925 return _M_t._M_emplace_hint_unique(__position, 926 std::forward<_Pair>(__x)); 927 } 928 #endif 929 /// @} 930 931 /** 932 * @brief Template function that attempts to insert a range of elements. 933 * @param __first Iterator pointing to the start of the range to be 934 * inserted. 935 * @param __last Iterator pointing to the end of the range. 936 * 937 * Complexity similar to that of the range constructor. 938 */ 939 template<typename _InputIterator> 940 void 941 insert(_InputIterator __first, _InputIterator __last) 942 { _M_t._M_insert_range_unique(__first, __last); } 943 944 #if __cplusplus > 201402L 945 /** 946 * @brief Attempts to insert or assign a std::pair into the %map. 947 * @param __k Key to use for finding a possibly existing pair in 948 * the map. 949 * @param __obj Argument used to generate the .second for a pair 950 * instance. 951 * 952 * @return A pair, of which the first element is an iterator that 953 * points to the possibly inserted pair, and the second is 954 * a bool that is true if the pair was actually inserted. 955 * 956 * This function attempts to insert a (key, value) %pair into the %map. 957 * A %map relies on unique keys and thus a %pair is only inserted if its 958 * first element (the key) is not already present in the %map. 959 * If the %pair was already in the %map, the .second of the %pair 960 * is assigned from __obj. 961 * 962 * Insertion requires logarithmic time. 963 */ 964 template <typename _Obj> 965 pair<iterator, bool> 966 insert_or_assign(const key_type& __k, _Obj&& __obj) 967 { 968 iterator __i = lower_bound(__k); 969 if (__i == end() || key_comp()(__k, (*__i).first)) 970 { 971 __i = emplace_hint(__i, std::piecewise_construct, 972 std::forward_as_tuple(__k), 973 std::forward_as_tuple( 974 std::forward<_Obj>(__obj))); 975 return {__i, true}; 976 } 977 (*__i).second = std::forward<_Obj>(__obj); 978 return {__i, false}; 979 } 980 981 // move-capable overload 982 template <typename _Obj> 983 pair<iterator, bool> 984 insert_or_assign(key_type&& __k, _Obj&& __obj) 985 { 986 iterator __i = lower_bound(__k); 987 if (__i == end() || key_comp()(__k, (*__i).first)) 988 { 989 __i = emplace_hint(__i, std::piecewise_construct, 990 std::forward_as_tuple(std::move(__k)), 991 std::forward_as_tuple( 992 std::forward<_Obj>(__obj))); 993 return {__i, true}; 994 } 995 (*__i).second = std::forward<_Obj>(__obj); 996 return {__i, false}; 997 } 998 999 /** 1000 * @brief Attempts to insert or assign a std::pair into the %map. 1001 * @param __hint An iterator that serves as a hint as to where the 1002 * pair should be inserted. 1003 * @param __k Key to use for finding a possibly existing pair in 1004 * the map. 1005 * @param __obj Argument used to generate the .second for a pair 1006 * instance. 1007 * 1008 * @return An iterator that points to the element with key of 1009 * @a __x (may or may not be the %pair passed in). 1010 * 1011 * This function attempts to insert a (key, value) %pair into the %map. 1012 * A %map relies on unique keys and thus a %pair is only inserted if its 1013 * first element (the key) is not already present in the %map. 1014 * If the %pair was already in the %map, the .second of the %pair 1015 * is assigned from __obj. 1016 * 1017 * Insertion requires logarithmic time. 1018 */ 1019 template <typename _Obj> 1020 iterator 1021 insert_or_assign(const_iterator __hint, 1022 const key_type& __k, _Obj&& __obj) 1023 { 1024 iterator __i; 1025 auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k); 1026 if (__true_hint.second) 1027 { 1028 return emplace_hint(iterator(__true_hint.second), 1029 std::piecewise_construct, 1030 std::forward_as_tuple(__k), 1031 std::forward_as_tuple( 1032 std::forward<_Obj>(__obj))); 1033 } 1034 __i = iterator(__true_hint.first); 1035 (*__i).second = std::forward<_Obj>(__obj); 1036 return __i; 1037 } 1038 1039 // move-capable overload 1040 template <typename _Obj> 1041 iterator 1042 insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj) 1043 { 1044 iterator __i; 1045 auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k); 1046 if (__true_hint.second) 1047 { 1048 return emplace_hint(iterator(__true_hint.second), 1049 std::piecewise_construct, 1050 std::forward_as_tuple(std::move(__k)), 1051 std::forward_as_tuple( 1052 std::forward<_Obj>(__obj))); 1053 } 1054 __i = iterator(__true_hint.first); 1055 (*__i).second = std::forward<_Obj>(__obj); 1056 return __i; 1057 } 1058 #endif 1059 1060 #if __cplusplus >= 201103L 1061 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1062 // DR 130. Associative erase should return an iterator. 1063 /** 1064 * @brief Erases an element from a %map. 1065 * @param __position An iterator pointing to the element to be erased. 1066 * @return An iterator pointing to the element immediately following 1067 * @a position prior to the element being erased. If no such 1068 * element exists, end() is returned. 1069 * 1070 * This function erases an element, pointed to by the given 1071 * iterator, from a %map. Note that this function only erases 1072 * the element, and that if the element is itself a pointer, 1073 * the pointed-to memory is not touched in any way. Managing 1074 * the pointer is the user's responsibility. 1075 * 1076 * @{ 1077 */ 1078 iterator 1079 erase(const_iterator __position) 1080 { return _M_t.erase(__position); } 1081 1082 // LWG 2059 1083 _GLIBCXX_ABI_TAG_CXX11 1084 iterator 1085 erase(iterator __position) 1086 { return _M_t.erase(__position); } 1087 /// @} 1088 #else 1089 /** 1090 * @brief Erases an element from a %map. 1091 * @param __position An iterator pointing to the element to be erased. 1092 * 1093 * This function erases an element, pointed to by the given 1094 * iterator, from a %map. Note that this function only erases 1095 * the element, and that if the element is itself a pointer, 1096 * the pointed-to memory is not touched in any way. Managing 1097 * the pointer is the user's responsibility. 1098 */ 1099 void 1100 erase(iterator __position) 1101 { _M_t.erase(__position); } 1102 #endif 1103 1104 /** 1105 * @brief Erases elements according to the provided key. 1106 * @param __x Key of element to be erased. 1107 * @return The number of elements erased. 1108 * 1109 * This function erases all the elements located by the given key from 1110 * a %map. 1111 * Note that this function only erases the element, and that if 1112 * the element is itself a pointer, the pointed-to memory is not touched 1113 * in any way. Managing the pointer is the user's responsibility. 1114 */ 1115 size_type 1116 erase(const key_type& __x) 1117 { return _M_t.erase(__x); } 1118 1119 #if __cplusplus >= 201103L 1120 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1121 // DR 130. Associative erase should return an iterator. 1122 /** 1123 * @brief Erases a [first,last) range of elements from a %map. 1124 * @param __first Iterator pointing to the start of the range to be 1125 * erased. 1126 * @param __last Iterator pointing to the end of the range to 1127 * be erased. 1128 * @return The iterator @a __last. 1129 * 1130 * This function erases a sequence of elements from a %map. 1131 * Note that this function only erases the element, and that if 1132 * the element is itself a pointer, the pointed-to memory is not touched 1133 * in any way. Managing the pointer is the user's responsibility. 1134 */ 1135 iterator 1136 erase(const_iterator __first, const_iterator __last) 1137 { return _M_t.erase(__first, __last); } 1138 #else 1139 /** 1140 * @brief Erases a [__first,__last) range of elements from a %map. 1141 * @param __first Iterator pointing to the start of the range to be 1142 * erased. 1143 * @param __last Iterator pointing to the end of the range to 1144 * be erased. 1145 * 1146 * This function erases a sequence of elements from a %map. 1147 * Note that this function only erases the element, and that if 1148 * the element is itself a pointer, the pointed-to memory is not touched 1149 * in any way. Managing the pointer is the user's responsibility. 1150 */ 1151 void 1152 erase(iterator __first, iterator __last) 1153 { _M_t.erase(__first, __last); } 1154 #endif 1155 1156 /** 1157 * @brief Swaps data with another %map. 1158 * @param __x A %map of the same element and allocator types. 1159 * 1160 * This exchanges the elements between two maps in constant 1161 * time. (It is only swapping a pointer, an integer, and an 1162 * instance of the @c Compare type (which itself is often 1163 * stateless and empty), so it should be quite fast.) Note 1164 * that the global std::swap() function is specialized such 1165 * that std::swap(m1,m2) will feed to this function. 1166 * 1167 * Whether the allocators are swapped depends on the allocator traits. 1168 */ 1169 void 1170 swap(map& __x) 1171 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value) 1172 { _M_t.swap(__x._M_t); } 1173 1174 /** 1175 * Erases all elements in a %map. Note that this function only 1176 * erases the elements, and that if the elements themselves are 1177 * pointers, the pointed-to memory is not touched in any way. 1178 * Managing the pointer is the user's responsibility. 1179 */ 1180 void 1181 clear() _GLIBCXX_NOEXCEPT 1182 { _M_t.clear(); } 1183 1184 // observers 1185 /** 1186 * Returns the key comparison object out of which the %map was 1187 * constructed. 1188 */ 1189 key_compare 1190 key_comp() const 1191 { return _M_t.key_comp(); } 1192 1193 /** 1194 * Returns a value comparison object, built from the key comparison 1195 * object out of which the %map was constructed. 1196 */ 1197 value_compare 1198 value_comp() const 1199 { return value_compare(_M_t.key_comp()); } 1200 1201 // [23.3.1.3] map operations 1202 1203 ///@{ 1204 /** 1205 * @brief Tries to locate an element in a %map. 1206 * @param __x Key of (key, value) %pair to be located. 1207 * @return Iterator pointing to sought-after element, or end() if not 1208 * found. 1209 * 1210 * This function takes a key and tries to locate the element with which 1211 * the key matches. If successful the function returns an iterator 1212 * pointing to the sought after %pair. If unsuccessful it returns the 1213 * past-the-end ( @c end() ) iterator. 1214 */ 1215 1216 iterator 1217 find(const key_type& __x) 1218 { return _M_t.find(__x); } 1219 1220 #if __cplusplus > 201103L 1221 template<typename _Kt> 1222 auto 1223 find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x)) 1224 { return _M_t._M_find_tr(__x); } 1225 #endif 1226 ///@} 1227 1228 ///@{ 1229 /** 1230 * @brief Tries to locate an element in a %map. 1231 * @param __x Key of (key, value) %pair to be located. 1232 * @return Read-only (constant) iterator pointing to sought-after 1233 * element, or end() if not found. 1234 * 1235 * This function takes a key and tries to locate the element with which 1236 * the key matches. If successful the function returns a constant 1237 * iterator pointing to the sought after %pair. If unsuccessful it 1238 * returns the past-the-end ( @c end() ) iterator. 1239 */ 1240 1241 const_iterator 1242 find(const key_type& __x) const 1243 { return _M_t.find(__x); } 1244 1245 #if __cplusplus > 201103L 1246 template<typename _Kt> 1247 auto 1248 find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x)) 1249 { return _M_t._M_find_tr(__x); } 1250 #endif 1251 ///@} 1252 1253 ///@{ 1254 /** 1255 * @brief Finds the number of elements with given key. 1256 * @param __x Key of (key, value) pairs to be located. 1257 * @return Number of elements with specified key. 1258 * 1259 * This function only makes sense for multimaps; for map the result will 1260 * either be 0 (not present) or 1 (present). 1261 */ 1262 size_type 1263 count(const key_type& __x) const 1264 { return _M_t.find(__x) == _M_t.end() ? 0 : 1; } 1265 1266 #if __cplusplus > 201103L 1267 template<typename _Kt> 1268 auto 1269 count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x)) 1270 { return _M_t._M_count_tr(__x); } 1271 #endif 1272 ///@} 1273 1274 #if __cplusplus > 201703L 1275 ///@{ 1276 /** 1277 * @brief Finds whether an element with the given key exists. 1278 * @param __x Key of (key, value) pairs to be located. 1279 * @return True if there is an element with the specified key. 1280 */ 1281 bool 1282 contains(const key_type& __x) const 1283 { return _M_t.find(__x) != _M_t.end(); } 1284 1285 template<typename _Kt> 1286 auto 1287 contains(const _Kt& __x) const 1288 -> decltype(_M_t._M_find_tr(__x), void(), true) 1289 { return _M_t._M_find_tr(__x) != _M_t.end(); } 1290 ///@} 1291 #endif 1292 1293 ///@{ 1294 /** 1295 * @brief Finds the beginning of a subsequence matching given key. 1296 * @param __x Key of (key, value) pair to be located. 1297 * @return Iterator pointing to first element equal to or greater 1298 * than key, or end(). 1299 * 1300 * This function returns the first element of a subsequence of elements 1301 * that matches the given key. If unsuccessful it returns an iterator 1302 * pointing to the first element that has a greater value than given key 1303 * or end() if no such element exists. 1304 */ 1305 iterator 1306 lower_bound(const key_type& __x) 1307 { return _M_t.lower_bound(__x); } 1308 1309 #if __cplusplus > 201103L 1310 template<typename _Kt> 1311 auto 1312 lower_bound(const _Kt& __x) 1313 -> decltype(iterator(_M_t._M_lower_bound_tr(__x))) 1314 { return iterator(_M_t._M_lower_bound_tr(__x)); } 1315 #endif 1316 ///@} 1317 1318 ///@{ 1319 /** 1320 * @brief Finds the beginning of a subsequence matching given key. 1321 * @param __x Key of (key, value) pair to be located. 1322 * @return Read-only (constant) iterator pointing to first element 1323 * equal to or greater than key, or end(). 1324 * 1325 * This function returns the first element of a subsequence of elements 1326 * that matches the given key. If unsuccessful it returns an iterator 1327 * pointing to the first element that has a greater value than given key 1328 * or end() if no such element exists. 1329 */ 1330 const_iterator 1331 lower_bound(const key_type& __x) const 1332 { return _M_t.lower_bound(__x); } 1333 1334 #if __cplusplus > 201103L 1335 template<typename _Kt> 1336 auto 1337 lower_bound(const _Kt& __x) const 1338 -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x))) 1339 { return const_iterator(_M_t._M_lower_bound_tr(__x)); } 1340 #endif 1341 ///@} 1342 1343 ///@{ 1344 /** 1345 * @brief Finds the end of a subsequence matching given key. 1346 * @param __x Key of (key, value) pair to be located. 1347 * @return Iterator pointing to the first element 1348 * greater than key, or end(). 1349 */ 1350 iterator 1351 upper_bound(const key_type& __x) 1352 { return _M_t.upper_bound(__x); } 1353 1354 #if __cplusplus > 201103L 1355 template<typename _Kt> 1356 auto 1357 upper_bound(const _Kt& __x) 1358 -> decltype(iterator(_M_t._M_upper_bound_tr(__x))) 1359 { return iterator(_M_t._M_upper_bound_tr(__x)); } 1360 #endif 1361 ///@} 1362 1363 ///@{ 1364 /** 1365 * @brief Finds the end of a subsequence matching given key. 1366 * @param __x Key of (key, value) pair to be located. 1367 * @return Read-only (constant) iterator pointing to first iterator 1368 * greater than key, or end(). 1369 */ 1370 const_iterator 1371 upper_bound(const key_type& __x) const 1372 { return _M_t.upper_bound(__x); } 1373 1374 #if __cplusplus > 201103L 1375 template<typename _Kt> 1376 auto 1377 upper_bound(const _Kt& __x) const 1378 -> decltype(const_iterator(_M_t._M_upper_bound_tr(__x))) 1379 { return const_iterator(_M_t._M_upper_bound_tr(__x)); } 1380 #endif 1381 ///@} 1382 1383 ///@{ 1384 /** 1385 * @brief Finds a subsequence matching given key. 1386 * @param __x Key of (key, value) pairs to be located. 1387 * @return Pair of iterators that possibly points to the subsequence 1388 * matching given key. 1389 * 1390 * This function is equivalent to 1391 * @code 1392 * std::make_pair(c.lower_bound(val), 1393 * c.upper_bound(val)) 1394 * @endcode 1395 * (but is faster than making the calls separately). 1396 * 1397 * This function probably only makes sense for multimaps. 1398 */ 1399 std::pair<iterator, iterator> 1400 equal_range(const key_type& __x) 1401 { return _M_t.equal_range(__x); } 1402 1403 #if __cplusplus > 201103L 1404 template<typename _Kt> 1405 auto 1406 equal_range(const _Kt& __x) 1407 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x))) 1408 { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); } 1409 #endif 1410 ///@} 1411 1412 ///@{ 1413 /** 1414 * @brief Finds a subsequence matching given key. 1415 * @param __x Key of (key, value) pairs to be located. 1416 * @return Pair of read-only (constant) iterators that possibly points 1417 * to the subsequence matching given key. 1418 * 1419 * This function is equivalent to 1420 * @code 1421 * std::make_pair(c.lower_bound(val), 1422 * c.upper_bound(val)) 1423 * @endcode 1424 * (but is faster than making the calls separately). 1425 * 1426 * This function probably only makes sense for multimaps. 1427 */ 1428 std::pair<const_iterator, const_iterator> 1429 equal_range(const key_type& __x) const 1430 { return _M_t.equal_range(__x); } 1431 1432 #if __cplusplus > 201103L 1433 template<typename _Kt> 1434 auto 1435 equal_range(const _Kt& __x) const 1436 -> decltype(pair<const_iterator, const_iterator>( 1437 _M_t._M_equal_range_tr(__x))) 1438 { 1439 return pair<const_iterator, const_iterator>( 1440 _M_t._M_equal_range_tr(__x)); 1441 } 1442 #endif 1443 ///@} 1444 1445 template<typename _K1, typename _T1, typename _C1, typename _A1> 1446 friend bool 1447 operator==(const map<_K1, _T1, _C1, _A1>&, 1448 const map<_K1, _T1, _C1, _A1>&); 1449 1450 #if __cpp_lib_three_way_comparison 1451 template<typename _K1, typename _T1, typename _C1, typename _A1> 1452 friend __detail::__synth3way_t<pair<const _K1, _T1>> 1453 operator<=>(const map<_K1, _T1, _C1, _A1>&, 1454 const map<_K1, _T1, _C1, _A1>&); 1455 #else 1456 template<typename _K1, typename _T1, typename _C1, typename _A1> 1457 friend bool 1458 operator<(const map<_K1, _T1, _C1, _A1>&, 1459 const map<_K1, _T1, _C1, _A1>&); 1460 #endif 1461 }; 1462 1463 1464 #if __cpp_deduction_guides >= 201606 1465 1466 template<typename _InputIterator, 1467 typename _Compare = less<__iter_key_t<_InputIterator>>, 1468 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>, 1469 typename = _RequireInputIter<_InputIterator>, 1470 typename = _RequireNotAllocator<_Compare>, 1471 typename = _RequireAllocator<_Allocator>> 1472 map(_InputIterator, _InputIterator, 1473 _Compare = _Compare(), _Allocator = _Allocator()) 1474 -> map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, 1475 _Compare, _Allocator>; 1476 1477 template<typename _Key, typename _Tp, typename _Compare = less<_Key>, 1478 typename _Allocator = allocator<pair<const _Key, _Tp>>, 1479 typename = _RequireNotAllocator<_Compare>, 1480 typename = _RequireAllocator<_Allocator>> 1481 map(initializer_list<pair<_Key, _Tp>>, 1482 _Compare = _Compare(), _Allocator = _Allocator()) 1483 -> map<_Key, _Tp, _Compare, _Allocator>; 1484 1485 template <typename _InputIterator, typename _Allocator, 1486 typename = _RequireInputIter<_InputIterator>, 1487 typename = _RequireAllocator<_Allocator>> 1488 map(_InputIterator, _InputIterator, _Allocator) 1489 -> map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, 1490 less<__iter_key_t<_InputIterator>>, _Allocator>; 1491 1492 template<typename _Key, typename _Tp, typename _Allocator, 1493 typename = _RequireAllocator<_Allocator>> 1494 map(initializer_list<pair<_Key, _Tp>>, _Allocator) 1495 -> map<_Key, _Tp, less<_Key>, _Allocator>; 1496 1497 #endif // deduction guides 1498 1499 /** 1500 * @brief Map equality comparison. 1501 * @param __x A %map. 1502 * @param __y A %map of the same type as @a x. 1503 * @return True iff the size and elements of the maps are equal. 1504 * 1505 * This is an equivalence relation. It is linear in the size of the 1506 * maps. Maps are considered equivalent if their sizes are equal, 1507 * and if corresponding elements compare equal. 1508 */ 1509 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 1510 inline bool 1511 operator==(const map<_Key, _Tp, _Compare, _Alloc>& __x, 1512 const map<_Key, _Tp, _Compare, _Alloc>& __y) 1513 { return __x._M_t == __y._M_t; } 1514 1515 #if __cpp_lib_three_way_comparison 1516 /** 1517 * @brief Map ordering relation. 1518 * @param __x A `map`. 1519 * @param __y A `map` of the same type as `x`. 1520 * @return A value indicating whether `__x` is less than, equal to, 1521 * greater than, or incomparable with `__y`. 1522 * 1523 * This is a total ordering relation. It is linear in the size of the 1524 * maps. The elements must be comparable with @c <. 1525 * 1526 * See `std::lexicographical_compare_three_way()` for how the determination 1527 * is made. This operator is used to synthesize relational operators like 1528 * `<` and `>=` etc. 1529 */ 1530 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 1531 inline __detail::__synth3way_t<pair<const _Key, _Tp>> 1532 operator<=>(const map<_Key, _Tp, _Compare, _Alloc>& __x, 1533 const map<_Key, _Tp, _Compare, _Alloc>& __y) 1534 { return __x._M_t <=> __y._M_t; } 1535 #else 1536 /** 1537 * @brief Map ordering relation. 1538 * @param __x A %map. 1539 * @param __y A %map of the same type as @a x. 1540 * @return True iff @a x is lexicographically less than @a y. 1541 * 1542 * This is a total ordering relation. It is linear in the size of the 1543 * maps. The elements must be comparable with @c <. 1544 * 1545 * See std::lexicographical_compare() for how the determination is made. 1546 */ 1547 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 1548 inline bool 1549 operator<(const map<_Key, _Tp, _Compare, _Alloc>& __x, 1550 const map<_Key, _Tp, _Compare, _Alloc>& __y) 1551 { return __x._M_t < __y._M_t; } 1552 1553 /// Based on operator== 1554 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 1555 inline bool 1556 operator!=(const map<_Key, _Tp, _Compare, _Alloc>& __x, 1557 const map<_Key, _Tp, _Compare, _Alloc>& __y) 1558 { return !(__x == __y); } 1559 1560 /// Based on operator< 1561 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 1562 inline bool 1563 operator>(const map<_Key, _Tp, _Compare, _Alloc>& __x, 1564 const map<_Key, _Tp, _Compare, _Alloc>& __y) 1565 { return __y < __x; } 1566 1567 /// Based on operator< 1568 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 1569 inline bool 1570 operator<=(const map<_Key, _Tp, _Compare, _Alloc>& __x, 1571 const map<_Key, _Tp, _Compare, _Alloc>& __y) 1572 { return !(__y < __x); } 1573 1574 /// Based on operator< 1575 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 1576 inline bool 1577 operator>=(const map<_Key, _Tp, _Compare, _Alloc>& __x, 1578 const map<_Key, _Tp, _Compare, _Alloc>& __y) 1579 { return !(__x < __y); } 1580 #endif // three-way comparison 1581 1582 /// See std::map::swap(). 1583 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 1584 inline void 1585 swap(map<_Key, _Tp, _Compare, _Alloc>& __x, 1586 map<_Key, _Tp, _Compare, _Alloc>& __y) 1587 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y))) 1588 { __x.swap(__y); } 1589 1590 _GLIBCXX_END_NAMESPACE_CONTAINER 1591 1592 #if __cplusplus > 201402L 1593 // Allow std::map access to internals of compatible maps. 1594 template<typename _Key, typename _Val, typename _Cmp1, typename _Alloc, 1595 typename _Cmp2> 1596 struct 1597 _Rb_tree_merge_helper<_GLIBCXX_STD_C::map<_Key, _Val, _Cmp1, _Alloc>, 1598 _Cmp2> 1599 { 1600 private: 1601 friend class _GLIBCXX_STD_C::map<_Key, _Val, _Cmp1, _Alloc>; 1602 1603 static auto& 1604 _S_get_tree(_GLIBCXX_STD_C::map<_Key, _Val, _Cmp2, _Alloc>& __map) 1605 { return __map._M_t; } 1606 1607 static auto& 1608 _S_get_tree(_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp2, _Alloc>& __map) 1609 { return __map._M_t; } 1610 }; 1611 #endif // C++17 1612 1613 _GLIBCXX_END_NAMESPACE_VERSION 1614 } // namespace std 1615 1616 #endif /* _STL_MAP_H */ 1617