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