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