1// -*- C++ -*- 2//===----------------------------- map ------------------------------------===// 3// 4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5// See https://llvm.org/LICENSE.txt for license information. 6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef _LIBCPP_MAP 11#define _LIBCPP_MAP 12 13/* 14 15 map synopsis 16 17namespace std 18{ 19 20template <class Key, class T, class Compare = less<Key>, 21 class Allocator = allocator<pair<const Key, T>>> 22class map 23{ 24public: 25 // types: 26 typedef Key key_type; 27 typedef T mapped_type; 28 typedef pair<const key_type, mapped_type> value_type; 29 typedef Compare key_compare; 30 typedef Allocator allocator_type; 31 typedef typename allocator_type::reference reference; 32 typedef typename allocator_type::const_reference const_reference; 33 typedef typename allocator_type::pointer pointer; 34 typedef typename allocator_type::const_pointer const_pointer; 35 typedef typename allocator_type::size_type size_type; 36 typedef typename allocator_type::difference_type difference_type; 37 38 typedef implementation-defined iterator; 39 typedef implementation-defined const_iterator; 40 typedef std::reverse_iterator<iterator> reverse_iterator; 41 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 42 typedef unspecified node_type; // C++17 43 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17 44 45 class value_compare 46 { 47 friend class map; 48 protected: 49 key_compare comp; 50 51 value_compare(key_compare c); 52 public: 53 typedef bool result_type; // deprecated in C++17, removed in C++20 54 typedef value_type first_argument_type; // deprecated in C++17, removed in C++20 55 typedef value_type second_argument_type; // deprecated in C++17, removed in C++20 56 bool operator()(const value_type& x, const value_type& y) const; 57 }; 58 59 // construct/copy/destroy: 60 map() 61 noexcept( 62 is_nothrow_default_constructible<allocator_type>::value && 63 is_nothrow_default_constructible<key_compare>::value && 64 is_nothrow_copy_constructible<key_compare>::value); 65 explicit map(const key_compare& comp); 66 map(const key_compare& comp, const allocator_type& a); 67 template <class InputIterator> 68 map(InputIterator first, InputIterator last, 69 const key_compare& comp = key_compare()); 70 template <class InputIterator> 71 map(InputIterator first, InputIterator last, 72 const key_compare& comp, const allocator_type& a); 73 map(const map& m); 74 map(map&& m) 75 noexcept( 76 is_nothrow_move_constructible<allocator_type>::value && 77 is_nothrow_move_constructible<key_compare>::value); 78 explicit map(const allocator_type& a); 79 map(const map& m, const allocator_type& a); 80 map(map&& m, const allocator_type& a); 81 map(initializer_list<value_type> il, const key_compare& comp = key_compare()); 82 map(initializer_list<value_type> il, const key_compare& comp, const allocator_type& a); 83 template <class InputIterator> 84 map(InputIterator first, InputIterator last, const allocator_type& a) 85 : map(first, last, Compare(), a) {} // C++14 86 map(initializer_list<value_type> il, const allocator_type& a) 87 : map(il, Compare(), a) {} // C++14 88 ~map(); 89 90 map& operator=(const map& m); 91 map& operator=(map&& m) 92 noexcept( 93 allocator_type::propagate_on_container_move_assignment::value && 94 is_nothrow_move_assignable<allocator_type>::value && 95 is_nothrow_move_assignable<key_compare>::value); 96 map& operator=(initializer_list<value_type> il); 97 98 // iterators: 99 iterator begin() noexcept; 100 const_iterator begin() const noexcept; 101 iterator end() noexcept; 102 const_iterator end() const noexcept; 103 104 reverse_iterator rbegin() noexcept; 105 const_reverse_iterator rbegin() const noexcept; 106 reverse_iterator rend() noexcept; 107 const_reverse_iterator rend() const noexcept; 108 109 const_iterator cbegin() const noexcept; 110 const_iterator cend() const noexcept; 111 const_reverse_iterator crbegin() const noexcept; 112 const_reverse_iterator crend() const noexcept; 113 114 // capacity: 115 bool empty() const noexcept; 116 size_type size() const noexcept; 117 size_type max_size() const noexcept; 118 119 // element access: 120 mapped_type& operator[](const key_type& k); 121 mapped_type& operator[](key_type&& k); 122 123 mapped_type& at(const key_type& k); 124 const mapped_type& at(const key_type& k) const; 125 126 // modifiers: 127 template <class... Args> 128 pair<iterator, bool> emplace(Args&&... args); 129 template <class... Args> 130 iterator emplace_hint(const_iterator position, Args&&... args); 131 pair<iterator, bool> insert(const value_type& v); 132 pair<iterator, bool> insert( value_type&& v); // C++17 133 template <class P> 134 pair<iterator, bool> insert(P&& p); 135 iterator insert(const_iterator position, const value_type& v); 136 iterator insert(const_iterator position, value_type&& v); // C++17 137 template <class P> 138 iterator insert(const_iterator position, P&& p); 139 template <class InputIterator> 140 void insert(InputIterator first, InputIterator last); 141 void insert(initializer_list<value_type> il); 142 143 node_type extract(const_iterator position); // C++17 144 node_type extract(const key_type& x); // C++17 145 insert_return_type insert(node_type&& nh); // C++17 146 iterator insert(const_iterator hint, node_type&& nh); // C++17 147 148 template <class... Args> 149 pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17 150 template <class... Args> 151 pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17 152 template <class... Args> 153 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17 154 template <class... Args> 155 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17 156 template <class M> 157 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17 158 template <class M> 159 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17 160 template <class M> 161 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17 162 template <class M> 163 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17 164 165 iterator erase(const_iterator position); 166 iterator erase(iterator position); // C++14 167 size_type erase(const key_type& k); 168 iterator erase(const_iterator first, const_iterator last); 169 void clear() noexcept; 170 171 template<class C2> 172 void merge(map<Key, T, C2, Allocator>& source); // C++17 173 template<class C2> 174 void merge(map<Key, T, C2, Allocator>&& source); // C++17 175 template<class C2> 176 void merge(multimap<Key, T, C2, Allocator>& source); // C++17 177 template<class C2> 178 void merge(multimap<Key, T, C2, Allocator>&& source); // C++17 179 180 void swap(map& m) 181 noexcept(allocator_traits<allocator_type>::is_always_equal::value && 182 is_nothrow_swappable<key_compare>::value); // C++17 183 184 // observers: 185 allocator_type get_allocator() const noexcept; 186 key_compare key_comp() const; 187 value_compare value_comp() const; 188 189 // map operations: 190 iterator find(const key_type& k); 191 const_iterator find(const key_type& k) const; 192 template<typename K> 193 iterator find(const K& x); // C++14 194 template<typename K> 195 const_iterator find(const K& x) const; // C++14 196 197 template<typename K> 198 size_type count(const K& x) const; // C++14 199 size_type count(const key_type& k) const; 200 201 bool contains(const key_type& x) const; // C++20 202 template<class K> bool contains(const K& x) const; // C++20 203 204 iterator lower_bound(const key_type& k); 205 const_iterator lower_bound(const key_type& k) const; 206 template<typename K> 207 iterator lower_bound(const K& x); // C++14 208 template<typename K> 209 const_iterator lower_bound(const K& x) const; // C++14 210 211 iterator upper_bound(const key_type& k); 212 const_iterator upper_bound(const key_type& k) const; 213 template<typename K> 214 iterator upper_bound(const K& x); // C++14 215 template<typename K> 216 const_iterator upper_bound(const K& x) const; // C++14 217 218 pair<iterator,iterator> equal_range(const key_type& k); 219 pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 220 template<typename K> 221 pair<iterator,iterator> equal_range(const K& x); // C++14 222 template<typename K> 223 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14 224}; 225 226template <class Key, class T, class Compare, class Allocator> 227bool 228operator==(const map<Key, T, Compare, Allocator>& x, 229 const map<Key, T, Compare, Allocator>& y); 230 231template <class Key, class T, class Compare, class Allocator> 232bool 233operator< (const map<Key, T, Compare, Allocator>& x, 234 const map<Key, T, Compare, Allocator>& y); 235 236template <class Key, class T, class Compare, class Allocator> 237bool 238operator!=(const map<Key, T, Compare, Allocator>& x, 239 const map<Key, T, Compare, Allocator>& y); 240 241template <class Key, class T, class Compare, class Allocator> 242bool 243operator> (const map<Key, T, Compare, Allocator>& x, 244 const map<Key, T, Compare, Allocator>& y); 245 246template <class Key, class T, class Compare, class Allocator> 247bool 248operator>=(const map<Key, T, Compare, Allocator>& x, 249 const map<Key, T, Compare, Allocator>& y); 250 251template <class Key, class T, class Compare, class Allocator> 252bool 253operator<=(const map<Key, T, Compare, Allocator>& x, 254 const map<Key, T, Compare, Allocator>& y); 255 256// specialized algorithms: 257template <class Key, class T, class Compare, class Allocator> 258void 259swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y) 260 noexcept(noexcept(x.swap(y))); 261 262template <class Key, class T, class Compare, class Allocator, class Predicate> 263typename map<Key, T, Compare, Allocator>::size_type 264erase_if(map<Key, T, Compare, Allocator>& c, Predicate pred); // C++20 265 266 267template <class Key, class T, class Compare = less<Key>, 268 class Allocator = allocator<pair<const Key, T>>> 269class multimap 270{ 271public: 272 // types: 273 typedef Key key_type; 274 typedef T mapped_type; 275 typedef pair<const key_type,mapped_type> value_type; 276 typedef Compare key_compare; 277 typedef Allocator allocator_type; 278 typedef typename allocator_type::reference reference; 279 typedef typename allocator_type::const_reference const_reference; 280 typedef typename allocator_type::size_type size_type; 281 typedef typename allocator_type::difference_type difference_type; 282 typedef typename allocator_type::pointer pointer; 283 typedef typename allocator_type::const_pointer const_pointer; 284 285 typedef implementation-defined iterator; 286 typedef implementation-defined const_iterator; 287 typedef std::reverse_iterator<iterator> reverse_iterator; 288 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 289 typedef unspecified node_type; // C++17 290 291 class value_compare 292 { 293 friend class multimap; 294 protected: 295 key_compare comp; 296 value_compare(key_compare c); 297 public: 298 typedef bool result_type; // deprecated in C++17, removed in C++20 299 typedef value_type first_argument_type; // deprecated in C++17, removed in C++20 300 typedef value_type second_argument_type; // deprecated in C++17, removed in C++20 301 bool operator()(const value_type& x, const value_type& y) const; 302 }; 303 304 // construct/copy/destroy: 305 multimap() 306 noexcept( 307 is_nothrow_default_constructible<allocator_type>::value && 308 is_nothrow_default_constructible<key_compare>::value && 309 is_nothrow_copy_constructible<key_compare>::value); 310 explicit multimap(const key_compare& comp); 311 multimap(const key_compare& comp, const allocator_type& a); 312 template <class InputIterator> 313 multimap(InputIterator first, InputIterator last, const key_compare& comp); 314 template <class InputIterator> 315 multimap(InputIterator first, InputIterator last, const key_compare& comp, 316 const allocator_type& a); 317 multimap(const multimap& m); 318 multimap(multimap&& m) 319 noexcept( 320 is_nothrow_move_constructible<allocator_type>::value && 321 is_nothrow_move_constructible<key_compare>::value); 322 explicit multimap(const allocator_type& a); 323 multimap(const multimap& m, const allocator_type& a); 324 multimap(multimap&& m, const allocator_type& a); 325 multimap(initializer_list<value_type> il, const key_compare& comp = key_compare()); 326 multimap(initializer_list<value_type> il, const key_compare& comp, 327 const allocator_type& a); 328 template <class InputIterator> 329 multimap(InputIterator first, InputIterator last, const allocator_type& a) 330 : multimap(first, last, Compare(), a) {} // C++14 331 multimap(initializer_list<value_type> il, const allocator_type& a) 332 : multimap(il, Compare(), a) {} // C++14 333 ~multimap(); 334 335 multimap& operator=(const multimap& m); 336 multimap& operator=(multimap&& m) 337 noexcept( 338 allocator_type::propagate_on_container_move_assignment::value && 339 is_nothrow_move_assignable<allocator_type>::value && 340 is_nothrow_move_assignable<key_compare>::value); 341 multimap& operator=(initializer_list<value_type> il); 342 343 // iterators: 344 iterator begin() noexcept; 345 const_iterator begin() const noexcept; 346 iterator end() noexcept; 347 const_iterator end() const noexcept; 348 349 reverse_iterator rbegin() noexcept; 350 const_reverse_iterator rbegin() const noexcept; 351 reverse_iterator rend() noexcept; 352 const_reverse_iterator rend() const noexcept; 353 354 const_iterator cbegin() const noexcept; 355 const_iterator cend() const noexcept; 356 const_reverse_iterator crbegin() const noexcept; 357 const_reverse_iterator crend() const noexcept; 358 359 // capacity: 360 bool empty() const noexcept; 361 size_type size() const noexcept; 362 size_type max_size() const noexcept; 363 364 // modifiers: 365 template <class... Args> 366 iterator emplace(Args&&... args); 367 template <class... Args> 368 iterator emplace_hint(const_iterator position, Args&&... args); 369 iterator insert(const value_type& v); 370 iterator insert( value_type&& v); // C++17 371 template <class P> 372 iterator insert(P&& p); 373 iterator insert(const_iterator position, const value_type& v); 374 iterator insert(const_iterator position, value_type&& v); // C++17 375 template <class P> 376 iterator insert(const_iterator position, P&& p); 377 template <class InputIterator> 378 void insert(InputIterator first, InputIterator last); 379 void insert(initializer_list<value_type> il); 380 381 node_type extract(const_iterator position); // C++17 382 node_type extract(const key_type& x); // C++17 383 iterator insert(node_type&& nh); // C++17 384 iterator insert(const_iterator hint, node_type&& nh); // C++17 385 386 iterator erase(const_iterator position); 387 iterator erase(iterator position); // C++14 388 size_type erase(const key_type& k); 389 iterator erase(const_iterator first, const_iterator last); 390 void clear() noexcept; 391 392 template<class C2> 393 void merge(multimap<Key, T, C2, Allocator>& source); // C++17 394 template<class C2> 395 void merge(multimap<Key, T, C2, Allocator>&& source); // C++17 396 template<class C2> 397 void merge(map<Key, T, C2, Allocator>& source); // C++17 398 template<class C2> 399 void merge(map<Key, T, C2, Allocator>&& source); // C++17 400 401 void swap(multimap& m) 402 noexcept(allocator_traits<allocator_type>::is_always_equal::value && 403 is_nothrow_swappable<key_compare>::value); // C++17 404 405 // observers: 406 allocator_type get_allocator() const noexcept; 407 key_compare key_comp() const; 408 value_compare value_comp() const; 409 410 // map operations: 411 iterator find(const key_type& k); 412 const_iterator find(const key_type& k) const; 413 template<typename K> 414 iterator find(const K& x); // C++14 415 template<typename K> 416 const_iterator find(const K& x) const; // C++14 417 418 template<typename K> 419 size_type count(const K& x) const; // C++14 420 size_type count(const key_type& k) const; 421 422 bool contains(const key_type& x) const; // C++20 423 template<class K> bool contains(const K& x) const; // C++20 424 425 iterator lower_bound(const key_type& k); 426 const_iterator lower_bound(const key_type& k) const; 427 template<typename K> 428 iterator lower_bound(const K& x); // C++14 429 template<typename K> 430 const_iterator lower_bound(const K& x) const; // C++14 431 432 iterator upper_bound(const key_type& k); 433 const_iterator upper_bound(const key_type& k) const; 434 template<typename K> 435 iterator upper_bound(const K& x); // C++14 436 template<typename K> 437 const_iterator upper_bound(const K& x) const; // C++14 438 439 pair<iterator,iterator> equal_range(const key_type& k); 440 pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 441 template<typename K> 442 pair<iterator,iterator> equal_range(const K& x); // C++14 443 template<typename K> 444 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14 445}; 446 447template <class Key, class T, class Compare, class Allocator> 448bool 449operator==(const multimap<Key, T, Compare, Allocator>& x, 450 const multimap<Key, T, Compare, Allocator>& y); 451 452template <class Key, class T, class Compare, class Allocator> 453bool 454operator< (const multimap<Key, T, Compare, Allocator>& x, 455 const multimap<Key, T, Compare, Allocator>& y); 456 457template <class Key, class T, class Compare, class Allocator> 458bool 459operator!=(const multimap<Key, T, Compare, Allocator>& x, 460 const multimap<Key, T, Compare, Allocator>& y); 461 462template <class Key, class T, class Compare, class Allocator> 463bool 464operator> (const multimap<Key, T, Compare, Allocator>& x, 465 const multimap<Key, T, Compare, Allocator>& y); 466 467template <class Key, class T, class Compare, class Allocator> 468bool 469operator>=(const multimap<Key, T, Compare, Allocator>& x, 470 const multimap<Key, T, Compare, Allocator>& y); 471 472template <class Key, class T, class Compare, class Allocator> 473bool 474operator<=(const multimap<Key, T, Compare, Allocator>& x, 475 const multimap<Key, T, Compare, Allocator>& y); 476 477// specialized algorithms: 478template <class Key, class T, class Compare, class Allocator> 479void 480swap(multimap<Key, T, Compare, Allocator>& x, 481 multimap<Key, T, Compare, Allocator>& y) 482 noexcept(noexcept(x.swap(y))); 483 484template <class Key, class T, class Compare, class Allocator, class Predicate> 485typename multimap<Key, T, Compare, Allocator>::size_type 486erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred); // C++20 487 488} // std 489 490*/ 491 492#include <__config> 493#include <__debug> 494#include <__node_handle> 495#include <__tree> 496#include <compare> 497#include <functional> 498#include <initializer_list> 499#include <iterator> // __libcpp_erase_if_container 500#include <memory> 501#include <type_traits> 502#include <utility> 503#include <version> 504 505#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 506#pragma GCC system_header 507#endif 508 509_LIBCPP_BEGIN_NAMESPACE_STD 510 511template <class _Key, class _CP, class _Compare, 512 bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value> 513class __map_value_compare 514 : private _Compare 515{ 516public: 517 _LIBCPP_INLINE_VISIBILITY 518 __map_value_compare() 519 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value) 520 : _Compare() {} 521 _LIBCPP_INLINE_VISIBILITY 522 __map_value_compare(_Compare c) 523 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value) 524 : _Compare(c) {} 525 _LIBCPP_INLINE_VISIBILITY 526 const _Compare& key_comp() const _NOEXCEPT {return *this;} 527 _LIBCPP_INLINE_VISIBILITY 528 bool operator()(const _CP& __x, const _CP& __y) const 529 {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y.__get_value().first);} 530 _LIBCPP_INLINE_VISIBILITY 531 bool operator()(const _CP& __x, const _Key& __y) const 532 {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y);} 533 _LIBCPP_INLINE_VISIBILITY 534 bool operator()(const _Key& __x, const _CP& __y) const 535 {return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);} 536 void swap(__map_value_compare&__y) 537 _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value) 538 { 539 using _VSTD::swap; 540 swap(static_cast<_Compare&>(*this), static_cast<_Compare&>(__y)); 541 } 542 543#if _LIBCPP_STD_VER > 11 544 template <typename _K2> 545 _LIBCPP_INLINE_VISIBILITY 546 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type 547 operator () ( const _K2& __x, const _CP& __y ) const 548 {return static_cast<const _Compare&>(*this) (__x, __y.__get_value().first);} 549 550 template <typename _K2> 551 _LIBCPP_INLINE_VISIBILITY 552 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type 553 operator () (const _CP& __x, const _K2& __y) const 554 {return static_cast<const _Compare&>(*this) (__x.__get_value().first, __y);} 555#endif 556}; 557 558template <class _Key, class _CP, class _Compare> 559class __map_value_compare<_Key, _CP, _Compare, false> 560{ 561 _Compare comp; 562 563public: 564 _LIBCPP_INLINE_VISIBILITY 565 __map_value_compare() 566 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value) 567 : comp() {} 568 _LIBCPP_INLINE_VISIBILITY 569 __map_value_compare(_Compare c) 570 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value) 571 : comp(c) {} 572 _LIBCPP_INLINE_VISIBILITY 573 const _Compare& key_comp() const _NOEXCEPT {return comp;} 574 575 _LIBCPP_INLINE_VISIBILITY 576 bool operator()(const _CP& __x, const _CP& __y) const 577 {return comp(__x.__get_value().first, __y.__get_value().first);} 578 _LIBCPP_INLINE_VISIBILITY 579 bool operator()(const _CP& __x, const _Key& __y) const 580 {return comp(__x.__get_value().first, __y);} 581 _LIBCPP_INLINE_VISIBILITY 582 bool operator()(const _Key& __x, const _CP& __y) const 583 {return comp(__x, __y.__get_value().first);} 584 void swap(__map_value_compare&__y) 585 _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value) 586 { 587 using _VSTD::swap; 588 swap(comp, __y.comp); 589 } 590 591#if _LIBCPP_STD_VER > 11 592 template <typename _K2> 593 _LIBCPP_INLINE_VISIBILITY 594 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type 595 operator () ( const _K2& __x, const _CP& __y ) const 596 {return comp (__x, __y.__get_value().first);} 597 598 template <typename _K2> 599 _LIBCPP_INLINE_VISIBILITY 600 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type 601 operator () (const _CP& __x, const _K2& __y) const 602 {return comp (__x.__get_value().first, __y);} 603#endif 604}; 605 606template <class _Key, class _CP, class _Compare, bool __b> 607inline _LIBCPP_INLINE_VISIBILITY 608void 609swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x, 610 __map_value_compare<_Key, _CP, _Compare, __b>& __y) 611 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 612{ 613 __x.swap(__y); 614} 615 616template <class _Allocator> 617class __map_node_destructor 618{ 619 typedef _Allocator allocator_type; 620 typedef allocator_traits<allocator_type> __alloc_traits; 621 622public: 623 typedef typename __alloc_traits::pointer pointer; 624 625private: 626 allocator_type& __na_; 627 628 __map_node_destructor& operator=(const __map_node_destructor&); 629 630public: 631 bool __first_constructed; 632 bool __second_constructed; 633 634 _LIBCPP_INLINE_VISIBILITY 635 explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT 636 : __na_(__na), 637 __first_constructed(false), 638 __second_constructed(false) 639 {} 640 641#ifndef _LIBCPP_CXX03_LANG 642 _LIBCPP_INLINE_VISIBILITY 643 __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT 644 : __na_(__x.__na_), 645 __first_constructed(__x.__value_constructed), 646 __second_constructed(__x.__value_constructed) 647 { 648 __x.__value_constructed = false; 649 } 650#endif // _LIBCPP_CXX03_LANG 651 652 _LIBCPP_INLINE_VISIBILITY 653 void operator()(pointer __p) _NOEXCEPT 654 { 655 if (__second_constructed) 656 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().second)); 657 if (__first_constructed) 658 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().first)); 659 if (__p) 660 __alloc_traits::deallocate(__na_, __p, 1); 661 } 662}; 663 664template <class _Key, class _Tp, class _Compare, class _Allocator> 665 class map; 666template <class _Key, class _Tp, class _Compare, class _Allocator> 667 class multimap; 668template <class _TreeIterator> class __map_const_iterator; 669 670#ifndef _LIBCPP_CXX03_LANG 671 672template <class _Key, class _Tp> 673struct _LIBCPP_STANDALONE_DEBUG __value_type 674{ 675 typedef _Key key_type; 676 typedef _Tp mapped_type; 677 typedef pair<const key_type, mapped_type> value_type; 678 typedef pair<key_type&, mapped_type&> __nc_ref_pair_type; 679 typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type; 680 681private: 682 value_type __cc; 683 684public: 685 _LIBCPP_INLINE_VISIBILITY 686 value_type& __get_value() 687 { 688#if _LIBCPP_STD_VER > 14 689 return *_VSTD::launder(_VSTD::addressof(__cc)); 690#else 691 return __cc; 692#endif 693 } 694 695 _LIBCPP_INLINE_VISIBILITY 696 const value_type& __get_value() const 697 { 698#if _LIBCPP_STD_VER > 14 699 return *_VSTD::launder(_VSTD::addressof(__cc)); 700#else 701 return __cc; 702#endif 703 } 704 705 _LIBCPP_INLINE_VISIBILITY 706 __nc_ref_pair_type __ref() 707 { 708 value_type& __v = __get_value(); 709 return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second); 710 } 711 712 _LIBCPP_INLINE_VISIBILITY 713 __nc_rref_pair_type __move() 714 { 715 value_type& __v = __get_value(); 716 return __nc_rref_pair_type( 717 _VSTD::move(const_cast<key_type&>(__v.first)), 718 _VSTD::move(__v.second)); 719 } 720 721 _LIBCPP_INLINE_VISIBILITY 722 __value_type& operator=(const __value_type& __v) 723 { 724 __ref() = __v.__get_value(); 725 return *this; 726 } 727 728 _LIBCPP_INLINE_VISIBILITY 729 __value_type& operator=(__value_type&& __v) 730 { 731 __ref() = __v.__move(); 732 return *this; 733 } 734 735 template <class _ValueTp, 736 class = typename enable_if< 737 __is_same_uncvref<_ValueTp, value_type>::value 738 >::type 739 > 740 _LIBCPP_INLINE_VISIBILITY 741 __value_type& operator=(_ValueTp&& __v) 742 { 743 __ref() = _VSTD::forward<_ValueTp>(__v); 744 return *this; 745 } 746 747private: 748 __value_type() _LIBCPP_EQUAL_DELETE; 749 ~__value_type() _LIBCPP_EQUAL_DELETE; 750 __value_type(const __value_type& __v) _LIBCPP_EQUAL_DELETE; 751 __value_type(__value_type&& __v) _LIBCPP_EQUAL_DELETE; 752}; 753 754#else 755 756template <class _Key, class _Tp> 757struct __value_type 758{ 759 typedef _Key key_type; 760 typedef _Tp mapped_type; 761 typedef pair<const key_type, mapped_type> value_type; 762 763private: 764 value_type __cc; 765 766public: 767 _LIBCPP_INLINE_VISIBILITY 768 value_type& __get_value() { return __cc; } 769 _LIBCPP_INLINE_VISIBILITY 770 const value_type& __get_value() const { return __cc; } 771 772private: 773 __value_type(); 774 __value_type(__value_type const&); 775 __value_type& operator=(__value_type const&); 776 ~__value_type(); 777}; 778 779#endif // _LIBCPP_CXX03_LANG 780 781template <class _Tp> 782struct __extract_key_value_types; 783 784template <class _Key, class _Tp> 785struct __extract_key_value_types<__value_type<_Key, _Tp> > 786{ 787 typedef _Key const __key_type; 788 typedef _Tp __mapped_type; 789}; 790 791template <class _TreeIterator> 792class _LIBCPP_TEMPLATE_VIS __map_iterator 793{ 794 typedef typename _TreeIterator::_NodeTypes _NodeTypes; 795 typedef typename _TreeIterator::__pointer_traits __pointer_traits; 796 797 _TreeIterator __i_; 798 799public: 800 typedef bidirectional_iterator_tag iterator_category; 801 typedef typename _NodeTypes::__map_value_type value_type; 802 typedef typename _TreeIterator::difference_type difference_type; 803 typedef value_type& reference; 804 typedef typename _NodeTypes::__map_value_type_pointer pointer; 805 806 _LIBCPP_INLINE_VISIBILITY 807 __map_iterator() _NOEXCEPT {} 808 809 _LIBCPP_INLINE_VISIBILITY 810 __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {} 811 812 _LIBCPP_INLINE_VISIBILITY 813 reference operator*() const {return __i_->__get_value();} 814 _LIBCPP_INLINE_VISIBILITY 815 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());} 816 817 _LIBCPP_INLINE_VISIBILITY 818 __map_iterator& operator++() {++__i_; return *this;} 819 _LIBCPP_INLINE_VISIBILITY 820 __map_iterator operator++(int) 821 { 822 __map_iterator __t(*this); 823 ++(*this); 824 return __t; 825 } 826 827 _LIBCPP_INLINE_VISIBILITY 828 __map_iterator& operator--() {--__i_; return *this;} 829 _LIBCPP_INLINE_VISIBILITY 830 __map_iterator operator--(int) 831 { 832 __map_iterator __t(*this); 833 --(*this); 834 return __t; 835 } 836 837 friend _LIBCPP_INLINE_VISIBILITY 838 bool operator==(const __map_iterator& __x, const __map_iterator& __y) 839 {return __x.__i_ == __y.__i_;} 840 friend 841 _LIBCPP_INLINE_VISIBILITY 842 bool operator!=(const __map_iterator& __x, const __map_iterator& __y) 843 {return __x.__i_ != __y.__i_;} 844 845 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map; 846 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap; 847 template <class> friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator; 848}; 849 850template <class _TreeIterator> 851class _LIBCPP_TEMPLATE_VIS __map_const_iterator 852{ 853 typedef typename _TreeIterator::_NodeTypes _NodeTypes; 854 typedef typename _TreeIterator::__pointer_traits __pointer_traits; 855 856 _TreeIterator __i_; 857 858public: 859 typedef bidirectional_iterator_tag iterator_category; 860 typedef typename _NodeTypes::__map_value_type value_type; 861 typedef typename _TreeIterator::difference_type difference_type; 862 typedef const value_type& reference; 863 typedef typename _NodeTypes::__const_map_value_type_pointer pointer; 864 865 _LIBCPP_INLINE_VISIBILITY 866 __map_const_iterator() _NOEXCEPT {} 867 868 _LIBCPP_INLINE_VISIBILITY 869 __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {} 870 _LIBCPP_INLINE_VISIBILITY 871 __map_const_iterator(__map_iterator< 872 typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT 873 : __i_(__i.__i_) {} 874 875 _LIBCPP_INLINE_VISIBILITY 876 reference operator*() const {return __i_->__get_value();} 877 _LIBCPP_INLINE_VISIBILITY 878 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());} 879 880 _LIBCPP_INLINE_VISIBILITY 881 __map_const_iterator& operator++() {++__i_; return *this;} 882 _LIBCPP_INLINE_VISIBILITY 883 __map_const_iterator operator++(int) 884 { 885 __map_const_iterator __t(*this); 886 ++(*this); 887 return __t; 888 } 889 890 _LIBCPP_INLINE_VISIBILITY 891 __map_const_iterator& operator--() {--__i_; return *this;} 892 _LIBCPP_INLINE_VISIBILITY 893 __map_const_iterator operator--(int) 894 { 895 __map_const_iterator __t(*this); 896 --(*this); 897 return __t; 898 } 899 900 friend _LIBCPP_INLINE_VISIBILITY 901 bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y) 902 {return __x.__i_ == __y.__i_;} 903 friend _LIBCPP_INLINE_VISIBILITY 904 bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y) 905 {return __x.__i_ != __y.__i_;} 906 907 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map; 908 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap; 909 template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator; 910}; 911 912template <class _Key, class _Tp, class _Compare = less<_Key>, 913 class _Allocator = allocator<pair<const _Key, _Tp> > > 914class _LIBCPP_TEMPLATE_VIS map 915{ 916public: 917 // types: 918 typedef _Key key_type; 919 typedef _Tp mapped_type; 920 typedef pair<const key_type, mapped_type> value_type; 921 typedef __identity_t<_Compare> key_compare; 922 typedef __identity_t<_Allocator> allocator_type; 923 typedef value_type& reference; 924 typedef const value_type& const_reference; 925 926 static_assert((is_same<typename allocator_type::value_type, value_type>::value), 927 "Allocator::value_type must be same type as value_type"); 928 929_LIBCPP_SUPPRESS_DEPRECATED_PUSH 930 class _LIBCPP_TEMPLATE_VIS value_compare 931#if defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) 932 : public binary_function<value_type, value_type, bool> 933#endif 934 { 935_LIBCPP_SUPPRESS_DEPRECATED_POP 936 friend class map; 937 protected: 938 key_compare comp; 939 940 _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {} 941 public: 942#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) 943 _LIBCPP_DEPRECATED_IN_CXX17 typedef bool result_type; 944 _LIBCPP_DEPRECATED_IN_CXX17 typedef value_type first_argument_type; 945 _LIBCPP_DEPRECATED_IN_CXX17 typedef value_type second_argument_type; 946#endif 947 _LIBCPP_INLINE_VISIBILITY 948 bool operator()(const value_type& __x, const value_type& __y) const 949 {return comp(__x.first, __y.first);} 950 }; 951 952private: 953 954 typedef _VSTD::__value_type<key_type, mapped_type> __value_type; 955 typedef __map_value_compare<key_type, __value_type, key_compare> __vc; 956 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, 957 __value_type>::type __allocator_type; 958 typedef __tree<__value_type, __vc, __allocator_type> __base; 959 typedef typename __base::__node_traits __node_traits; 960 typedef allocator_traits<allocator_type> __alloc_traits; 961 962 __base __tree_; 963 964public: 965 typedef typename __alloc_traits::pointer pointer; 966 typedef typename __alloc_traits::const_pointer const_pointer; 967 typedef typename __alloc_traits::size_type size_type; 968 typedef typename __alloc_traits::difference_type difference_type; 969 typedef __map_iterator<typename __base::iterator> iterator; 970 typedef __map_const_iterator<typename __base::const_iterator> const_iterator; 971 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 972 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 973 974#if _LIBCPP_STD_VER > 14 975 typedef __map_node_handle<typename __base::__node, allocator_type> node_type; 976 typedef __insert_return_type<iterator, node_type> insert_return_type; 977#endif 978 979 template <class _Key2, class _Value2, class _Comp2, class _Alloc2> 980 friend class _LIBCPP_TEMPLATE_VIS map; 981 template <class _Key2, class _Value2, class _Comp2, class _Alloc2> 982 friend class _LIBCPP_TEMPLATE_VIS multimap; 983 984 _LIBCPP_INLINE_VISIBILITY 985 map() 986 _NOEXCEPT_( 987 is_nothrow_default_constructible<allocator_type>::value && 988 is_nothrow_default_constructible<key_compare>::value && 989 is_nothrow_copy_constructible<key_compare>::value) 990 : __tree_(__vc(key_compare())) {} 991 992 _LIBCPP_INLINE_VISIBILITY 993 explicit map(const key_compare& __comp) 994 _NOEXCEPT_( 995 is_nothrow_default_constructible<allocator_type>::value && 996 is_nothrow_copy_constructible<key_compare>::value) 997 : __tree_(__vc(__comp)) {} 998 999 _LIBCPP_INLINE_VISIBILITY 1000 explicit map(const key_compare& __comp, const allocator_type& __a) 1001 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {} 1002 1003 template <class _InputIterator> 1004 _LIBCPP_INLINE_VISIBILITY 1005 map(_InputIterator __f, _InputIterator __l, 1006 const key_compare& __comp = key_compare()) 1007 : __tree_(__vc(__comp)) 1008 { 1009 insert(__f, __l); 1010 } 1011 1012 template <class _InputIterator> 1013 _LIBCPP_INLINE_VISIBILITY 1014 map(_InputIterator __f, _InputIterator __l, 1015 const key_compare& __comp, const allocator_type& __a) 1016 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) 1017 { 1018 insert(__f, __l); 1019 } 1020 1021#if _LIBCPP_STD_VER > 11 1022 template <class _InputIterator> 1023 _LIBCPP_INLINE_VISIBILITY 1024 map(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 1025 : map(__f, __l, key_compare(), __a) {} 1026#endif 1027 1028 _LIBCPP_INLINE_VISIBILITY 1029 map(const map& __m) 1030 : __tree_(__m.__tree_) 1031 { 1032 insert(__m.begin(), __m.end()); 1033 } 1034 1035 _LIBCPP_INLINE_VISIBILITY 1036 map& operator=(const map& __m) 1037 { 1038#ifndef _LIBCPP_CXX03_LANG 1039 __tree_ = __m.__tree_; 1040#else 1041 if (this != &__m) { 1042 __tree_.clear(); 1043 __tree_.value_comp() = __m.__tree_.value_comp(); 1044 __tree_.__copy_assign_alloc(__m.__tree_); 1045 insert(__m.begin(), __m.end()); 1046 } 1047#endif 1048 return *this; 1049 } 1050 1051#ifndef _LIBCPP_CXX03_LANG 1052 1053 _LIBCPP_INLINE_VISIBILITY 1054 map(map&& __m) 1055 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 1056 : __tree_(_VSTD::move(__m.__tree_)) 1057 { 1058 } 1059 1060 map(map&& __m, const allocator_type& __a); 1061 1062 _LIBCPP_INLINE_VISIBILITY 1063 map& operator=(map&& __m) 1064 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 1065 { 1066 __tree_ = _VSTD::move(__m.__tree_); 1067 return *this; 1068 } 1069 1070 _LIBCPP_INLINE_VISIBILITY 1071 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare()) 1072 : __tree_(__vc(__comp)) 1073 { 1074 insert(__il.begin(), __il.end()); 1075 } 1076 1077 _LIBCPP_INLINE_VISIBILITY 1078 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a) 1079 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) 1080 { 1081 insert(__il.begin(), __il.end()); 1082 } 1083 1084#if _LIBCPP_STD_VER > 11 1085 _LIBCPP_INLINE_VISIBILITY 1086 map(initializer_list<value_type> __il, const allocator_type& __a) 1087 : map(__il, key_compare(), __a) {} 1088#endif 1089 1090 _LIBCPP_INLINE_VISIBILITY 1091 map& operator=(initializer_list<value_type> __il) 1092 { 1093 __tree_.__assign_unique(__il.begin(), __il.end()); 1094 return *this; 1095 } 1096 1097#endif // _LIBCPP_CXX03_LANG 1098 1099 _LIBCPP_INLINE_VISIBILITY 1100 explicit map(const allocator_type& __a) 1101 : __tree_(typename __base::allocator_type(__a)) 1102 { 1103 } 1104 1105 _LIBCPP_INLINE_VISIBILITY 1106 map(const map& __m, const allocator_type& __a) 1107 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) 1108 { 1109 insert(__m.begin(), __m.end()); 1110 } 1111 1112 _LIBCPP_INLINE_VISIBILITY 1113 ~map() { 1114 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); 1115 } 1116 1117 _LIBCPP_INLINE_VISIBILITY 1118 iterator begin() _NOEXCEPT {return __tree_.begin();} 1119 _LIBCPP_INLINE_VISIBILITY 1120 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 1121 _LIBCPP_INLINE_VISIBILITY 1122 iterator end() _NOEXCEPT {return __tree_.end();} 1123 _LIBCPP_INLINE_VISIBILITY 1124 const_iterator end() const _NOEXCEPT {return __tree_.end();} 1125 1126 _LIBCPP_INLINE_VISIBILITY 1127 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());} 1128 _LIBCPP_INLINE_VISIBILITY 1129 const_reverse_iterator rbegin() const _NOEXCEPT 1130 {return const_reverse_iterator(end());} 1131 _LIBCPP_INLINE_VISIBILITY 1132 reverse_iterator rend() _NOEXCEPT 1133 {return reverse_iterator(begin());} 1134 _LIBCPP_INLINE_VISIBILITY 1135 const_reverse_iterator rend() const _NOEXCEPT 1136 {return const_reverse_iterator(begin());} 1137 1138 _LIBCPP_INLINE_VISIBILITY 1139 const_iterator cbegin() const _NOEXCEPT {return begin();} 1140 _LIBCPP_INLINE_VISIBILITY 1141 const_iterator cend() const _NOEXCEPT {return end();} 1142 _LIBCPP_INLINE_VISIBILITY 1143 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 1144 _LIBCPP_INLINE_VISIBILITY 1145 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 1146 1147 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 1148 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 1149 _LIBCPP_INLINE_VISIBILITY 1150 size_type size() const _NOEXCEPT {return __tree_.size();} 1151 _LIBCPP_INLINE_VISIBILITY 1152 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 1153 1154 mapped_type& operator[](const key_type& __k); 1155#ifndef _LIBCPP_CXX03_LANG 1156 mapped_type& operator[](key_type&& __k); 1157#endif 1158 1159 mapped_type& at(const key_type& __k); 1160 const mapped_type& at(const key_type& __k) const; 1161 1162 _LIBCPP_INLINE_VISIBILITY 1163 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());} 1164 _LIBCPP_INLINE_VISIBILITY 1165 key_compare key_comp() const {return __tree_.value_comp().key_comp();} 1166 _LIBCPP_INLINE_VISIBILITY 1167 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());} 1168 1169#ifndef _LIBCPP_CXX03_LANG 1170 template <class ..._Args> 1171 _LIBCPP_INLINE_VISIBILITY 1172 pair<iterator, bool> emplace(_Args&& ...__args) { 1173 return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...); 1174 } 1175 1176 template <class ..._Args> 1177 _LIBCPP_INLINE_VISIBILITY 1178 iterator emplace_hint(const_iterator __p, _Args&& ...__args) { 1179 return __tree_.__emplace_hint_unique(__p.__i_, _VSTD::forward<_Args>(__args)...); 1180 } 1181 1182 template <class _Pp, 1183 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1184 _LIBCPP_INLINE_VISIBILITY 1185 pair<iterator, bool> insert(_Pp&& __p) 1186 {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));} 1187 1188 template <class _Pp, 1189 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1190 _LIBCPP_INLINE_VISIBILITY 1191 iterator insert(const_iterator __pos, _Pp&& __p) 1192 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));} 1193 1194#endif // _LIBCPP_CXX03_LANG 1195 1196 _LIBCPP_INLINE_VISIBILITY 1197 pair<iterator, bool> 1198 insert(const value_type& __v) {return __tree_.__insert_unique(__v);} 1199 1200 _LIBCPP_INLINE_VISIBILITY 1201 iterator 1202 insert(const_iterator __p, const value_type& __v) 1203 {return __tree_.__insert_unique(__p.__i_, __v);} 1204 1205#ifndef _LIBCPP_CXX03_LANG 1206 _LIBCPP_INLINE_VISIBILITY 1207 pair<iterator, bool> 1208 insert(value_type&& __v) {return __tree_.__insert_unique(_VSTD::move(__v));} 1209 1210 _LIBCPP_INLINE_VISIBILITY 1211 iterator insert(const_iterator __p, value_type&& __v) 1212 {return __tree_.__insert_unique(__p.__i_, _VSTD::move(__v));} 1213 1214 _LIBCPP_INLINE_VISIBILITY 1215 void insert(initializer_list<value_type> __il) 1216 {insert(__il.begin(), __il.end());} 1217#endif 1218 1219 template <class _InputIterator> 1220 _LIBCPP_INLINE_VISIBILITY 1221 void insert(_InputIterator __f, _InputIterator __l) 1222 { 1223 for (const_iterator __e = cend(); __f != __l; ++__f) 1224 insert(__e.__i_, *__f); 1225 } 1226 1227#if _LIBCPP_STD_VER > 14 1228 1229 template <class... _Args> 1230 _LIBCPP_INLINE_VISIBILITY 1231 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) 1232 { 1233 return __tree_.__emplace_unique_key_args(__k, 1234 _VSTD::piecewise_construct, 1235 _VSTD::forward_as_tuple(__k), 1236 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); 1237 } 1238 1239 template <class... _Args> 1240 _LIBCPP_INLINE_VISIBILITY 1241 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) 1242 { 1243 return __tree_.__emplace_unique_key_args(__k, 1244 _VSTD::piecewise_construct, 1245 _VSTD::forward_as_tuple(_VSTD::move(__k)), 1246 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); 1247 } 1248 1249 template <class... _Args> 1250 _LIBCPP_INLINE_VISIBILITY 1251 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args) 1252 { 1253 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, 1254 _VSTD::piecewise_construct, 1255 _VSTD::forward_as_tuple(__k), 1256 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)).first; 1257 } 1258 1259 template <class... _Args> 1260 _LIBCPP_INLINE_VISIBILITY 1261 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) 1262 { 1263 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, 1264 _VSTD::piecewise_construct, 1265 _VSTD::forward_as_tuple(_VSTD::move(__k)), 1266 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)).first; 1267 } 1268 1269 template <class _Vp> 1270 _LIBCPP_INLINE_VISIBILITY 1271 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) 1272 { 1273 iterator __p = lower_bound(__k); 1274 if ( __p != end() && !key_comp()(__k, __p->first)) 1275 { 1276 __p->second = _VSTD::forward<_Vp>(__v); 1277 return _VSTD::make_pair(__p, false); 1278 } 1279 return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true); 1280 } 1281 1282 template <class _Vp> 1283 _LIBCPP_INLINE_VISIBILITY 1284 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) 1285 { 1286 iterator __p = lower_bound(__k); 1287 if ( __p != end() && !key_comp()(__k, __p->first)) 1288 { 1289 __p->second = _VSTD::forward<_Vp>(__v); 1290 return _VSTD::make_pair(__p, false); 1291 } 1292 return _VSTD::make_pair(emplace_hint(__p, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)), true); 1293 } 1294 1295 template <class _Vp> 1296 _LIBCPP_INLINE_VISIBILITY iterator insert_or_assign(const_iterator __h, 1297 const key_type& __k, 1298 _Vp&& __v) { 1299 auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args( 1300 __h.__i_, __k, __k, _VSTD::forward<_Vp>(__v)); 1301 1302 if (!__inserted) 1303 __r->__get_value().second = _VSTD::forward<_Vp>(__v); 1304 1305 return __r; 1306 } 1307 1308 template <class _Vp> 1309 _LIBCPP_INLINE_VISIBILITY iterator insert_or_assign(const_iterator __h, 1310 key_type&& __k, 1311 _Vp&& __v) { 1312 auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args( 1313 __h.__i_, __k, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)); 1314 1315 if (!__inserted) 1316 __r->__get_value().second = _VSTD::forward<_Vp>(__v); 1317 1318 return __r; 1319 } 1320 1321#endif // _LIBCPP_STD_VER > 14 1322 1323 _LIBCPP_INLINE_VISIBILITY 1324 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);} 1325 _LIBCPP_INLINE_VISIBILITY 1326 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);} 1327 _LIBCPP_INLINE_VISIBILITY 1328 size_type erase(const key_type& __k) 1329 {return __tree_.__erase_unique(__k);} 1330 _LIBCPP_INLINE_VISIBILITY 1331 iterator erase(const_iterator __f, const_iterator __l) 1332 {return __tree_.erase(__f.__i_, __l.__i_);} 1333 _LIBCPP_INLINE_VISIBILITY 1334 void clear() _NOEXCEPT {__tree_.clear();} 1335 1336#if _LIBCPP_STD_VER > 14 1337 _LIBCPP_INLINE_VISIBILITY 1338 insert_return_type insert(node_type&& __nh) 1339 { 1340 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1341 "node_type with incompatible allocator passed to map::insert()"); 1342 return __tree_.template __node_handle_insert_unique< 1343 node_type, insert_return_type>(_VSTD::move(__nh)); 1344 } 1345 _LIBCPP_INLINE_VISIBILITY 1346 iterator insert(const_iterator __hint, node_type&& __nh) 1347 { 1348 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1349 "node_type with incompatible allocator passed to map::insert()"); 1350 return __tree_.template __node_handle_insert_unique<node_type>( 1351 __hint.__i_, _VSTD::move(__nh)); 1352 } 1353 _LIBCPP_INLINE_VISIBILITY 1354 node_type extract(key_type const& __key) 1355 { 1356 return __tree_.template __node_handle_extract<node_type>(__key); 1357 } 1358 _LIBCPP_INLINE_VISIBILITY 1359 node_type extract(const_iterator __it) 1360 { 1361 return __tree_.template __node_handle_extract<node_type>(__it.__i_); 1362 } 1363 template <class _Compare2> 1364 _LIBCPP_INLINE_VISIBILITY 1365 void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source) 1366 { 1367 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1368 "merging container with incompatible allocator"); 1369 __tree_.__node_handle_merge_unique(__source.__tree_); 1370 } 1371 template <class _Compare2> 1372 _LIBCPP_INLINE_VISIBILITY 1373 void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source) 1374 { 1375 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1376 "merging container with incompatible allocator"); 1377 __tree_.__node_handle_merge_unique(__source.__tree_); 1378 } 1379 template <class _Compare2> 1380 _LIBCPP_INLINE_VISIBILITY 1381 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source) 1382 { 1383 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1384 "merging container with incompatible allocator"); 1385 __tree_.__node_handle_merge_unique(__source.__tree_); 1386 } 1387 template <class _Compare2> 1388 _LIBCPP_INLINE_VISIBILITY 1389 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source) 1390 { 1391 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1392 "merging container with incompatible allocator"); 1393 __tree_.__node_handle_merge_unique(__source.__tree_); 1394 } 1395#endif 1396 1397 _LIBCPP_INLINE_VISIBILITY 1398 void swap(map& __m) 1399 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 1400 {__tree_.swap(__m.__tree_);} 1401 1402 _LIBCPP_INLINE_VISIBILITY 1403 iterator find(const key_type& __k) {return __tree_.find(__k);} 1404 _LIBCPP_INLINE_VISIBILITY 1405 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 1406#if _LIBCPP_STD_VER > 11 1407 template <typename _K2> 1408 _LIBCPP_INLINE_VISIBILITY 1409 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 1410 find(const _K2& __k) {return __tree_.find(__k);} 1411 template <typename _K2> 1412 _LIBCPP_INLINE_VISIBILITY 1413 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 1414 find(const _K2& __k) const {return __tree_.find(__k);} 1415#endif 1416 1417 _LIBCPP_INLINE_VISIBILITY 1418 size_type count(const key_type& __k) const 1419 {return __tree_.__count_unique(__k);} 1420#if _LIBCPP_STD_VER > 11 1421 template <typename _K2> 1422 _LIBCPP_INLINE_VISIBILITY 1423 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 1424 count(const _K2& __k) const {return __tree_.__count_multi(__k);} 1425#endif 1426 1427#if _LIBCPP_STD_VER > 17 1428 _LIBCPP_INLINE_VISIBILITY 1429 bool contains(const key_type& __k) const {return find(__k) != end();} 1430 template <typename _K2> 1431 _LIBCPP_INLINE_VISIBILITY 1432 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type 1433 contains(const _K2& __k) const { return find(__k) != end(); } 1434#endif // _LIBCPP_STD_VER > 17 1435 1436 _LIBCPP_INLINE_VISIBILITY 1437 iterator lower_bound(const key_type& __k) 1438 {return __tree_.lower_bound(__k);} 1439 _LIBCPP_INLINE_VISIBILITY 1440 const_iterator lower_bound(const key_type& __k) const 1441 {return __tree_.lower_bound(__k);} 1442#if _LIBCPP_STD_VER > 11 1443 template <typename _K2> 1444 _LIBCPP_INLINE_VISIBILITY 1445 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 1446 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 1447 1448 template <typename _K2> 1449 _LIBCPP_INLINE_VISIBILITY 1450 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 1451 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 1452#endif 1453 1454 _LIBCPP_INLINE_VISIBILITY 1455 iterator upper_bound(const key_type& __k) 1456 {return __tree_.upper_bound(__k);} 1457 _LIBCPP_INLINE_VISIBILITY 1458 const_iterator upper_bound(const key_type& __k) const 1459 {return __tree_.upper_bound(__k);} 1460#if _LIBCPP_STD_VER > 11 1461 template <typename _K2> 1462 _LIBCPP_INLINE_VISIBILITY 1463 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 1464 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 1465 template <typename _K2> 1466 _LIBCPP_INLINE_VISIBILITY 1467 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 1468 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 1469#endif 1470 1471 _LIBCPP_INLINE_VISIBILITY 1472 pair<iterator,iterator> equal_range(const key_type& __k) 1473 {return __tree_.__equal_range_unique(__k);} 1474 _LIBCPP_INLINE_VISIBILITY 1475 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 1476 {return __tree_.__equal_range_unique(__k);} 1477#if _LIBCPP_STD_VER > 11 1478 template <typename _K2> 1479 _LIBCPP_INLINE_VISIBILITY 1480 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 1481 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 1482 template <typename _K2> 1483 _LIBCPP_INLINE_VISIBILITY 1484 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 1485 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 1486#endif 1487 1488private: 1489 typedef typename __base::__node __node; 1490 typedef typename __base::__node_allocator __node_allocator; 1491 typedef typename __base::__node_pointer __node_pointer; 1492 typedef typename __base::__node_base_pointer __node_base_pointer; 1493 typedef typename __base::__parent_pointer __parent_pointer; 1494 1495 typedef __map_node_destructor<__node_allocator> _Dp; 1496 typedef unique_ptr<__node, _Dp> __node_holder; 1497 1498#ifdef _LIBCPP_CXX03_LANG 1499 __node_holder __construct_node_with_key(const key_type& __k); 1500#endif 1501}; 1502 1503#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES 1504template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>, 1505 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, 1506 class = _EnableIf<!__is_allocator<_Compare>::value, void>, 1507 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 1508map(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) 1509 -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>; 1510 1511template<class _Key, class _Tp, class _Compare = less<remove_const_t<_Key>>, 1512 class _Allocator = allocator<pair<const _Key, _Tp>>, 1513 class = _EnableIf<!__is_allocator<_Compare>::value, void>, 1514 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 1515map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator()) 1516 -> map<remove_const_t<_Key>, _Tp, _Compare, _Allocator>; 1517 1518template<class _InputIterator, class _Allocator, 1519 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 1520map(_InputIterator, _InputIterator, _Allocator) 1521 -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, 1522 less<__iter_key_type<_InputIterator>>, _Allocator>; 1523 1524template<class _Key, class _Tp, class _Allocator, 1525 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 1526map(initializer_list<pair<_Key, _Tp>>, _Allocator) 1527 -> map<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>; 1528#endif 1529 1530#ifndef _LIBCPP_CXX03_LANG 1531template <class _Key, class _Tp, class _Compare, class _Allocator> 1532map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a) 1533 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a)) 1534{ 1535 if (__a != __m.get_allocator()) 1536 { 1537 const_iterator __e = cend(); 1538 while (!__m.empty()) 1539 __tree_.__insert_unique(__e.__i_, 1540 __m.__tree_.remove(__m.begin().__i_)->__value_.__move()); 1541 } 1542} 1543 1544template <class _Key, class _Tp, class _Compare, class _Allocator> 1545_Tp& 1546map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) 1547{ 1548 return __tree_.__emplace_unique_key_args(__k, 1549 _VSTD::piecewise_construct, 1550 _VSTD::forward_as_tuple(__k), 1551 _VSTD::forward_as_tuple()).first->__get_value().second; 1552} 1553 1554template <class _Key, class _Tp, class _Compare, class _Allocator> 1555_Tp& 1556map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k) 1557{ 1558 return __tree_.__emplace_unique_key_args(__k, 1559 _VSTD::piecewise_construct, 1560 _VSTD::forward_as_tuple(_VSTD::move(__k)), 1561 _VSTD::forward_as_tuple()).first->__get_value().second; 1562} 1563 1564#else // _LIBCPP_CXX03_LANG 1565 1566template <class _Key, class _Tp, class _Compare, class _Allocator> 1567typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder 1568map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k) 1569{ 1570 __node_allocator& __na = __tree_.__node_alloc(); 1571 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1572 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().first), __k); 1573 __h.get_deleter().__first_constructed = true; 1574 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().second)); 1575 __h.get_deleter().__second_constructed = true; 1576 return __h; 1577} 1578 1579template <class _Key, class _Tp, class _Compare, class _Allocator> 1580_Tp& 1581map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) 1582{ 1583 __parent_pointer __parent; 1584 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k); 1585 __node_pointer __r = static_cast<__node_pointer>(__child); 1586 if (__child == nullptr) 1587 { 1588 __node_holder __h = __construct_node_with_key(__k); 1589 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1590 __r = __h.release(); 1591 } 1592 return __r->__value_.__get_value().second; 1593} 1594 1595#endif // _LIBCPP_CXX03_LANG 1596 1597template <class _Key, class _Tp, class _Compare, class _Allocator> 1598_Tp& 1599map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) 1600{ 1601 __parent_pointer __parent; 1602 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k); 1603 if (__child == nullptr) 1604 __throw_out_of_range("map::at: key not found"); 1605 return static_cast<__node_pointer>(__child)->__value_.__get_value().second; 1606} 1607 1608template <class _Key, class _Tp, class _Compare, class _Allocator> 1609const _Tp& 1610map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const 1611{ 1612 __parent_pointer __parent; 1613 __node_base_pointer __child = __tree_.__find_equal(__parent, __k); 1614 if (__child == nullptr) 1615 __throw_out_of_range("map::at: key not found"); 1616 return static_cast<__node_pointer>(__child)->__value_.__get_value().second; 1617} 1618 1619 1620template <class _Key, class _Tp, class _Compare, class _Allocator> 1621inline _LIBCPP_INLINE_VISIBILITY 1622bool 1623operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1624 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1625{ 1626 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 1627} 1628 1629template <class _Key, class _Tp, class _Compare, class _Allocator> 1630inline _LIBCPP_INLINE_VISIBILITY 1631bool 1632operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x, 1633 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1634{ 1635 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 1636} 1637 1638template <class _Key, class _Tp, class _Compare, class _Allocator> 1639inline _LIBCPP_INLINE_VISIBILITY 1640bool 1641operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1642 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1643{ 1644 return !(__x == __y); 1645} 1646 1647template <class _Key, class _Tp, class _Compare, class _Allocator> 1648inline _LIBCPP_INLINE_VISIBILITY 1649bool 1650operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x, 1651 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1652{ 1653 return __y < __x; 1654} 1655 1656template <class _Key, class _Tp, class _Compare, class _Allocator> 1657inline _LIBCPP_INLINE_VISIBILITY 1658bool 1659operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1660 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1661{ 1662 return !(__x < __y); 1663} 1664 1665template <class _Key, class _Tp, class _Compare, class _Allocator> 1666inline _LIBCPP_INLINE_VISIBILITY 1667bool 1668operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1669 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1670{ 1671 return !(__y < __x); 1672} 1673 1674template <class _Key, class _Tp, class _Compare, class _Allocator> 1675inline _LIBCPP_INLINE_VISIBILITY 1676void 1677swap(map<_Key, _Tp, _Compare, _Allocator>& __x, 1678 map<_Key, _Tp, _Compare, _Allocator>& __y) 1679 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1680{ 1681 __x.swap(__y); 1682} 1683 1684#if _LIBCPP_STD_VER > 17 1685template <class _Key, class _Tp, class _Compare, class _Allocator, 1686 class _Predicate> 1687inline _LIBCPP_INLINE_VISIBILITY 1688 typename map<_Key, _Tp, _Compare, _Allocator>::size_type 1689 erase_if(map<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) { 1690 return _VSTD::__libcpp_erase_if_container(__c, __pred); 1691} 1692#endif 1693 1694 1695template <class _Key, class _Tp, class _Compare = less<_Key>, 1696 class _Allocator = allocator<pair<const _Key, _Tp> > > 1697class _LIBCPP_TEMPLATE_VIS multimap 1698{ 1699public: 1700 // types: 1701 typedef _Key key_type; 1702 typedef _Tp mapped_type; 1703 typedef pair<const key_type, mapped_type> value_type; 1704 typedef __identity_t<_Compare> key_compare; 1705 typedef __identity_t<_Allocator> allocator_type; 1706 typedef value_type& reference; 1707 typedef const value_type& const_reference; 1708 1709 static_assert((is_same<typename allocator_type::value_type, value_type>::value), 1710 "Allocator::value_type must be same type as value_type"); 1711 1712_LIBCPP_SUPPRESS_DEPRECATED_PUSH 1713 class _LIBCPP_TEMPLATE_VIS value_compare 1714#if defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) 1715 : public binary_function<value_type, value_type, bool> 1716#endif 1717 { 1718_LIBCPP_SUPPRESS_DEPRECATED_POP 1719 friend class multimap; 1720 protected: 1721 key_compare comp; 1722 1723 _LIBCPP_INLINE_VISIBILITY 1724 value_compare(key_compare c) : comp(c) {} 1725 public: 1726#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) 1727 _LIBCPP_DEPRECATED_IN_CXX17 typedef bool result_type; 1728 _LIBCPP_DEPRECATED_IN_CXX17 typedef value_type first_argument_type; 1729 _LIBCPP_DEPRECATED_IN_CXX17 typedef value_type second_argument_type; 1730#endif 1731 _LIBCPP_INLINE_VISIBILITY 1732 bool operator()(const value_type& __x, const value_type& __y) const 1733 {return comp(__x.first, __y.first);} 1734 }; 1735 1736private: 1737 1738 typedef _VSTD::__value_type<key_type, mapped_type> __value_type; 1739 typedef __map_value_compare<key_type, __value_type, key_compare> __vc; 1740 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, 1741 __value_type>::type __allocator_type; 1742 typedef __tree<__value_type, __vc, __allocator_type> __base; 1743 typedef typename __base::__node_traits __node_traits; 1744 typedef allocator_traits<allocator_type> __alloc_traits; 1745 1746 __base __tree_; 1747 1748public: 1749 typedef typename __alloc_traits::pointer pointer; 1750 typedef typename __alloc_traits::const_pointer const_pointer; 1751 typedef typename __alloc_traits::size_type size_type; 1752 typedef typename __alloc_traits::difference_type difference_type; 1753 typedef __map_iterator<typename __base::iterator> iterator; 1754 typedef __map_const_iterator<typename __base::const_iterator> const_iterator; 1755 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 1756 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 1757 1758#if _LIBCPP_STD_VER > 14 1759 typedef __map_node_handle<typename __base::__node, allocator_type> node_type; 1760#endif 1761 1762 template <class _Key2, class _Value2, class _Comp2, class _Alloc2> 1763 friend class _LIBCPP_TEMPLATE_VIS map; 1764 template <class _Key2, class _Value2, class _Comp2, class _Alloc2> 1765 friend class _LIBCPP_TEMPLATE_VIS multimap; 1766 1767 _LIBCPP_INLINE_VISIBILITY 1768 multimap() 1769 _NOEXCEPT_( 1770 is_nothrow_default_constructible<allocator_type>::value && 1771 is_nothrow_default_constructible<key_compare>::value && 1772 is_nothrow_copy_constructible<key_compare>::value) 1773 : __tree_(__vc(key_compare())) {} 1774 1775 _LIBCPP_INLINE_VISIBILITY 1776 explicit multimap(const key_compare& __comp) 1777 _NOEXCEPT_( 1778 is_nothrow_default_constructible<allocator_type>::value && 1779 is_nothrow_copy_constructible<key_compare>::value) 1780 : __tree_(__vc(__comp)) {} 1781 1782 _LIBCPP_INLINE_VISIBILITY 1783 explicit multimap(const key_compare& __comp, const allocator_type& __a) 1784 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {} 1785 1786 template <class _InputIterator> 1787 _LIBCPP_INLINE_VISIBILITY 1788 multimap(_InputIterator __f, _InputIterator __l, 1789 const key_compare& __comp = key_compare()) 1790 : __tree_(__vc(__comp)) 1791 { 1792 insert(__f, __l); 1793 } 1794 1795 template <class _InputIterator> 1796 _LIBCPP_INLINE_VISIBILITY 1797 multimap(_InputIterator __f, _InputIterator __l, 1798 const key_compare& __comp, const allocator_type& __a) 1799 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) 1800 { 1801 insert(__f, __l); 1802 } 1803 1804#if _LIBCPP_STD_VER > 11 1805 template <class _InputIterator> 1806 _LIBCPP_INLINE_VISIBILITY 1807 multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 1808 : multimap(__f, __l, key_compare(), __a) {} 1809#endif 1810 1811 _LIBCPP_INLINE_VISIBILITY 1812 multimap(const multimap& __m) 1813 : __tree_(__m.__tree_.value_comp(), 1814 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc())) 1815 { 1816 insert(__m.begin(), __m.end()); 1817 } 1818 1819 _LIBCPP_INLINE_VISIBILITY 1820 multimap& operator=(const multimap& __m) 1821 { 1822#ifndef _LIBCPP_CXX03_LANG 1823 __tree_ = __m.__tree_; 1824#else 1825 if (this != &__m) { 1826 __tree_.clear(); 1827 __tree_.value_comp() = __m.__tree_.value_comp(); 1828 __tree_.__copy_assign_alloc(__m.__tree_); 1829 insert(__m.begin(), __m.end()); 1830 } 1831#endif 1832 return *this; 1833 } 1834 1835#ifndef _LIBCPP_CXX03_LANG 1836 1837 _LIBCPP_INLINE_VISIBILITY 1838 multimap(multimap&& __m) 1839 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 1840 : __tree_(_VSTD::move(__m.__tree_)) 1841 { 1842 } 1843 1844 multimap(multimap&& __m, const allocator_type& __a); 1845 1846 _LIBCPP_INLINE_VISIBILITY 1847 multimap& operator=(multimap&& __m) 1848 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 1849 { 1850 __tree_ = _VSTD::move(__m.__tree_); 1851 return *this; 1852 } 1853 1854 _LIBCPP_INLINE_VISIBILITY 1855 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare()) 1856 : __tree_(__vc(__comp)) 1857 { 1858 insert(__il.begin(), __il.end()); 1859 } 1860 1861 _LIBCPP_INLINE_VISIBILITY 1862 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a) 1863 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) 1864 { 1865 insert(__il.begin(), __il.end()); 1866 } 1867 1868#if _LIBCPP_STD_VER > 11 1869 _LIBCPP_INLINE_VISIBILITY 1870 multimap(initializer_list<value_type> __il, const allocator_type& __a) 1871 : multimap(__il, key_compare(), __a) {} 1872#endif 1873 1874 _LIBCPP_INLINE_VISIBILITY 1875 multimap& operator=(initializer_list<value_type> __il) 1876 { 1877 __tree_.__assign_multi(__il.begin(), __il.end()); 1878 return *this; 1879 } 1880 1881#endif // _LIBCPP_CXX03_LANG 1882 1883 _LIBCPP_INLINE_VISIBILITY 1884 explicit multimap(const allocator_type& __a) 1885 : __tree_(typename __base::allocator_type(__a)) 1886 { 1887 } 1888 1889 _LIBCPP_INLINE_VISIBILITY 1890 multimap(const multimap& __m, const allocator_type& __a) 1891 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) 1892 { 1893 insert(__m.begin(), __m.end()); 1894 } 1895 1896 _LIBCPP_INLINE_VISIBILITY 1897 ~multimap() { 1898 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); 1899 } 1900 1901 _LIBCPP_INLINE_VISIBILITY 1902 iterator begin() _NOEXCEPT {return __tree_.begin();} 1903 _LIBCPP_INLINE_VISIBILITY 1904 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 1905 _LIBCPP_INLINE_VISIBILITY 1906 iterator end() _NOEXCEPT {return __tree_.end();} 1907 _LIBCPP_INLINE_VISIBILITY 1908 const_iterator end() const _NOEXCEPT {return __tree_.end();} 1909 1910 _LIBCPP_INLINE_VISIBILITY 1911 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());} 1912 _LIBCPP_INLINE_VISIBILITY 1913 const_reverse_iterator rbegin() const _NOEXCEPT 1914 {return const_reverse_iterator(end());} 1915 _LIBCPP_INLINE_VISIBILITY 1916 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());} 1917 _LIBCPP_INLINE_VISIBILITY 1918 const_reverse_iterator rend() const _NOEXCEPT 1919 {return const_reverse_iterator(begin());} 1920 1921 _LIBCPP_INLINE_VISIBILITY 1922 const_iterator cbegin() const _NOEXCEPT {return begin();} 1923 _LIBCPP_INLINE_VISIBILITY 1924 const_iterator cend() const _NOEXCEPT {return end();} 1925 _LIBCPP_INLINE_VISIBILITY 1926 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 1927 _LIBCPP_INLINE_VISIBILITY 1928 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 1929 1930 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 1931 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 1932 _LIBCPP_INLINE_VISIBILITY 1933 size_type size() const _NOEXCEPT {return __tree_.size();} 1934 _LIBCPP_INLINE_VISIBILITY 1935 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 1936 1937 _LIBCPP_INLINE_VISIBILITY 1938 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());} 1939 _LIBCPP_INLINE_VISIBILITY 1940 key_compare key_comp() const {return __tree_.value_comp().key_comp();} 1941 _LIBCPP_INLINE_VISIBILITY 1942 value_compare value_comp() const 1943 {return value_compare(__tree_.value_comp().key_comp());} 1944 1945#ifndef _LIBCPP_CXX03_LANG 1946 1947 template <class ..._Args> 1948 _LIBCPP_INLINE_VISIBILITY 1949 iterator emplace(_Args&& ...__args) { 1950 return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...); 1951 } 1952 1953 template <class ..._Args> 1954 _LIBCPP_INLINE_VISIBILITY 1955 iterator emplace_hint(const_iterator __p, _Args&& ...__args) { 1956 return __tree_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...); 1957 } 1958 1959 template <class _Pp, 1960 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1961 _LIBCPP_INLINE_VISIBILITY 1962 iterator insert(_Pp&& __p) 1963 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));} 1964 1965 template <class _Pp, 1966 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1967 _LIBCPP_INLINE_VISIBILITY 1968 iterator insert(const_iterator __pos, _Pp&& __p) 1969 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));} 1970 1971 _LIBCPP_INLINE_VISIBILITY 1972 iterator insert(value_type&& __v) 1973 {return __tree_.__insert_multi(_VSTD::move(__v));} 1974 1975 _LIBCPP_INLINE_VISIBILITY 1976 iterator insert(const_iterator __p, value_type&& __v) 1977 {return __tree_.__insert_multi(__p.__i_, _VSTD::move(__v));} 1978 1979 1980 _LIBCPP_INLINE_VISIBILITY 1981 void insert(initializer_list<value_type> __il) 1982 {insert(__il.begin(), __il.end());} 1983 1984#endif // _LIBCPP_CXX03_LANG 1985 1986 _LIBCPP_INLINE_VISIBILITY 1987 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);} 1988 1989 _LIBCPP_INLINE_VISIBILITY 1990 iterator insert(const_iterator __p, const value_type& __v) 1991 {return __tree_.__insert_multi(__p.__i_, __v);} 1992 1993 template <class _InputIterator> 1994 _LIBCPP_INLINE_VISIBILITY 1995 void insert(_InputIterator __f, _InputIterator __l) 1996 { 1997 for (const_iterator __e = cend(); __f != __l; ++__f) 1998 __tree_.__insert_multi(__e.__i_, *__f); 1999 } 2000 2001 _LIBCPP_INLINE_VISIBILITY 2002 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);} 2003 _LIBCPP_INLINE_VISIBILITY 2004 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);} 2005 _LIBCPP_INLINE_VISIBILITY 2006 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} 2007 _LIBCPP_INLINE_VISIBILITY 2008 iterator erase(const_iterator __f, const_iterator __l) 2009 {return __tree_.erase(__f.__i_, __l.__i_);} 2010 2011#if _LIBCPP_STD_VER > 14 2012 _LIBCPP_INLINE_VISIBILITY 2013 iterator insert(node_type&& __nh) 2014 { 2015 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 2016 "node_type with incompatible allocator passed to multimap::insert()"); 2017 return __tree_.template __node_handle_insert_multi<node_type>( 2018 _VSTD::move(__nh)); 2019 } 2020 _LIBCPP_INLINE_VISIBILITY 2021 iterator insert(const_iterator __hint, node_type&& __nh) 2022 { 2023 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 2024 "node_type with incompatible allocator passed to multimap::insert()"); 2025 return __tree_.template __node_handle_insert_multi<node_type>( 2026 __hint.__i_, _VSTD::move(__nh)); 2027 } 2028 _LIBCPP_INLINE_VISIBILITY 2029 node_type extract(key_type const& __key) 2030 { 2031 return __tree_.template __node_handle_extract<node_type>(__key); 2032 } 2033 _LIBCPP_INLINE_VISIBILITY 2034 node_type extract(const_iterator __it) 2035 { 2036 return __tree_.template __node_handle_extract<node_type>( 2037 __it.__i_); 2038 } 2039 template <class _Compare2> 2040 _LIBCPP_INLINE_VISIBILITY 2041 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source) 2042 { 2043 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 2044 "merging container with incompatible allocator"); 2045 return __tree_.__node_handle_merge_multi(__source.__tree_); 2046 } 2047 template <class _Compare2> 2048 _LIBCPP_INLINE_VISIBILITY 2049 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source) 2050 { 2051 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 2052 "merging container with incompatible allocator"); 2053 return __tree_.__node_handle_merge_multi(__source.__tree_); 2054 } 2055 template <class _Compare2> 2056 _LIBCPP_INLINE_VISIBILITY 2057 void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source) 2058 { 2059 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 2060 "merging container with incompatible allocator"); 2061 return __tree_.__node_handle_merge_multi(__source.__tree_); 2062 } 2063 template <class _Compare2> 2064 _LIBCPP_INLINE_VISIBILITY 2065 void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source) 2066 { 2067 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 2068 "merging container with incompatible allocator"); 2069 return __tree_.__node_handle_merge_multi(__source.__tree_); 2070 } 2071#endif 2072 2073 _LIBCPP_INLINE_VISIBILITY 2074 void clear() _NOEXCEPT {__tree_.clear();} 2075 2076 _LIBCPP_INLINE_VISIBILITY 2077 void swap(multimap& __m) 2078 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 2079 {__tree_.swap(__m.__tree_);} 2080 2081 _LIBCPP_INLINE_VISIBILITY 2082 iterator find(const key_type& __k) {return __tree_.find(__k);} 2083 _LIBCPP_INLINE_VISIBILITY 2084 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 2085#if _LIBCPP_STD_VER > 11 2086 template <typename _K2> 2087 _LIBCPP_INLINE_VISIBILITY 2088 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 2089 find(const _K2& __k) {return __tree_.find(__k);} 2090 template <typename _K2> 2091 _LIBCPP_INLINE_VISIBILITY 2092 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 2093 find(const _K2& __k) const {return __tree_.find(__k);} 2094#endif 2095 2096 _LIBCPP_INLINE_VISIBILITY 2097 size_type count(const key_type& __k) const 2098 {return __tree_.__count_multi(__k);} 2099#if _LIBCPP_STD_VER > 11 2100 template <typename _K2> 2101 _LIBCPP_INLINE_VISIBILITY 2102 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 2103 count(const _K2& __k) const {return __tree_.__count_multi(__k);} 2104#endif 2105 2106#if _LIBCPP_STD_VER > 17 2107 _LIBCPP_INLINE_VISIBILITY 2108 bool contains(const key_type& __k) const {return find(__k) != end();} 2109 template <typename _K2> 2110 _LIBCPP_INLINE_VISIBILITY 2111 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type 2112 contains(const _K2& __k) const { return find(__k) != end(); } 2113#endif // _LIBCPP_STD_VER > 17 2114 2115 _LIBCPP_INLINE_VISIBILITY 2116 iterator lower_bound(const key_type& __k) 2117 {return __tree_.lower_bound(__k);} 2118 _LIBCPP_INLINE_VISIBILITY 2119 const_iterator lower_bound(const key_type& __k) const 2120 {return __tree_.lower_bound(__k);} 2121#if _LIBCPP_STD_VER > 11 2122 template <typename _K2> 2123 _LIBCPP_INLINE_VISIBILITY 2124 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 2125 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 2126 2127 template <typename _K2> 2128 _LIBCPP_INLINE_VISIBILITY 2129 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 2130 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 2131#endif 2132 2133 _LIBCPP_INLINE_VISIBILITY 2134 iterator upper_bound(const key_type& __k) 2135 {return __tree_.upper_bound(__k);} 2136 _LIBCPP_INLINE_VISIBILITY 2137 const_iterator upper_bound(const key_type& __k) const 2138 {return __tree_.upper_bound(__k);} 2139#if _LIBCPP_STD_VER > 11 2140 template <typename _K2> 2141 _LIBCPP_INLINE_VISIBILITY 2142 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 2143 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 2144 template <typename _K2> 2145 _LIBCPP_INLINE_VISIBILITY 2146 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 2147 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 2148#endif 2149 2150 _LIBCPP_INLINE_VISIBILITY 2151 pair<iterator,iterator> equal_range(const key_type& __k) 2152 {return __tree_.__equal_range_multi(__k);} 2153 _LIBCPP_INLINE_VISIBILITY 2154 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 2155 {return __tree_.__equal_range_multi(__k);} 2156#if _LIBCPP_STD_VER > 11 2157 template <typename _K2> 2158 _LIBCPP_INLINE_VISIBILITY 2159 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 2160 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 2161 template <typename _K2> 2162 _LIBCPP_INLINE_VISIBILITY 2163 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 2164 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 2165#endif 2166 2167private: 2168 typedef typename __base::__node __node; 2169 typedef typename __base::__node_allocator __node_allocator; 2170 typedef typename __base::__node_pointer __node_pointer; 2171 2172 typedef __map_node_destructor<__node_allocator> _Dp; 2173 typedef unique_ptr<__node, _Dp> __node_holder; 2174}; 2175 2176#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES 2177template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>, 2178 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, 2179 class = _EnableIf<!__is_allocator<_Compare>::value, void>, 2180 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 2181multimap(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) 2182 -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>; 2183 2184template<class _Key, class _Tp, class _Compare = less<remove_const_t<_Key>>, 2185 class _Allocator = allocator<pair<const _Key, _Tp>>, 2186 class = _EnableIf<!__is_allocator<_Compare>::value, void>, 2187 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 2188multimap(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator()) 2189 -> multimap<remove_const_t<_Key>, _Tp, _Compare, _Allocator>; 2190 2191template<class _InputIterator, class _Allocator, 2192 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 2193multimap(_InputIterator, _InputIterator, _Allocator) 2194 -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, 2195 less<__iter_key_type<_InputIterator>>, _Allocator>; 2196 2197template<class _Key, class _Tp, class _Allocator, 2198 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 2199multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) 2200 -> multimap<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>; 2201#endif 2202 2203#ifndef _LIBCPP_CXX03_LANG 2204template <class _Key, class _Tp, class _Compare, class _Allocator> 2205multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a) 2206 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a)) 2207{ 2208 if (__a != __m.get_allocator()) 2209 { 2210 const_iterator __e = cend(); 2211 while (!__m.empty()) 2212 __tree_.__insert_multi(__e.__i_, 2213 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__move())); 2214 } 2215} 2216#endif 2217 2218template <class _Key, class _Tp, class _Compare, class _Allocator> 2219inline _LIBCPP_INLINE_VISIBILITY 2220bool 2221operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2222 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2223{ 2224 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 2225} 2226 2227template <class _Key, class _Tp, class _Compare, class _Allocator> 2228inline _LIBCPP_INLINE_VISIBILITY 2229bool 2230operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2231 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2232{ 2233 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 2234} 2235 2236template <class _Key, class _Tp, class _Compare, class _Allocator> 2237inline _LIBCPP_INLINE_VISIBILITY 2238bool 2239operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2240 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2241{ 2242 return !(__x == __y); 2243} 2244 2245template <class _Key, class _Tp, class _Compare, class _Allocator> 2246inline _LIBCPP_INLINE_VISIBILITY 2247bool 2248operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2249 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2250{ 2251 return __y < __x; 2252} 2253 2254template <class _Key, class _Tp, class _Compare, class _Allocator> 2255inline _LIBCPP_INLINE_VISIBILITY 2256bool 2257operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2258 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2259{ 2260 return !(__x < __y); 2261} 2262 2263template <class _Key, class _Tp, class _Compare, class _Allocator> 2264inline _LIBCPP_INLINE_VISIBILITY 2265bool 2266operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2267 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2268{ 2269 return !(__y < __x); 2270} 2271 2272template <class _Key, class _Tp, class _Compare, class _Allocator> 2273inline _LIBCPP_INLINE_VISIBILITY 2274void 2275swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2276 multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2277 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2278{ 2279 __x.swap(__y); 2280} 2281 2282#if _LIBCPP_STD_VER > 17 2283template <class _Key, class _Tp, class _Compare, class _Allocator, 2284 class _Predicate> 2285inline _LIBCPP_INLINE_VISIBILITY 2286 typename multimap<_Key, _Tp, _Compare, _Allocator>::size_type 2287 erase_if(multimap<_Key, _Tp, _Compare, _Allocator>& __c, 2288 _Predicate __pred) { 2289 return _VSTD::__libcpp_erase_if_container(__c, __pred); 2290} 2291#endif 2292 2293_LIBCPP_END_NAMESPACE_STD 2294 2295#endif // _LIBCPP_MAP 2296