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