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 <__functional/is_transparent.h> 495#include <__node_handle> 496#include <__tree> 497#include <__utility/forward.h> 498#include <compare> 499#include <functional> 500#include <initializer_list> 501#include <iterator> // __libcpp_erase_if_container 502#include <memory> 503#include <type_traits> 504#include <utility> 505#include <version> 506 507#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 508#pragma GCC system_header 509#endif 510 511_LIBCPP_BEGIN_NAMESPACE_STD 512 513template <class _Key, class _CP, class _Compare, 514 bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value> 515class __map_value_compare 516 : private _Compare 517{ 518public: 519 _LIBCPP_INLINE_VISIBILITY 520 __map_value_compare() 521 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value) 522 : _Compare() {} 523 _LIBCPP_INLINE_VISIBILITY 524 __map_value_compare(_Compare c) 525 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value) 526 : _Compare(c) {} 527 _LIBCPP_INLINE_VISIBILITY 528 const _Compare& key_comp() const _NOEXCEPT {return *this;} 529 _LIBCPP_INLINE_VISIBILITY 530 bool operator()(const _CP& __x, const _CP& __y) const 531 {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y.__get_value().first);} 532 _LIBCPP_INLINE_VISIBILITY 533 bool operator()(const _CP& __x, const _Key& __y) const 534 {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y);} 535 _LIBCPP_INLINE_VISIBILITY 536 bool operator()(const _Key& __x, const _CP& __y) const 537 {return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);} 538 void swap(__map_value_compare& __y) 539 _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value) 540 { 541 using _VSTD::swap; 542 swap(static_cast<_Compare&>(*this), static_cast<_Compare&>(__y)); 543 } 544 545#if _LIBCPP_STD_VER > 11 546 template <typename _K2> 547 _LIBCPP_INLINE_VISIBILITY 548 bool operator()(const _K2& __x, const _CP& __y) const 549 {return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);} 550 551 template <typename _K2> 552 _LIBCPP_INLINE_VISIBILITY 553 bool 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 bool operator()(const _K2& __x, const _CP& __y) const 595 {return comp(__x, __y.__get_value().first);} 596 597 template <typename _K2> 598 _LIBCPP_INLINE_VISIBILITY 599 bool operator()(const _CP& __x, const _K2& __y) const 600 {return comp(__x.__get_value().first, __y);} 601#endif 602}; 603 604template <class _Key, class _CP, class _Compare, bool __b> 605inline _LIBCPP_INLINE_VISIBILITY 606void 607swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x, 608 __map_value_compare<_Key, _CP, _Compare, __b>& __y) 609 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 610{ 611 __x.swap(__y); 612} 613 614template <class _Allocator> 615class __map_node_destructor 616{ 617 typedef _Allocator allocator_type; 618 typedef allocator_traits<allocator_type> __alloc_traits; 619 620public: 621 typedef typename __alloc_traits::pointer pointer; 622 623private: 624 allocator_type& __na_; 625 626 __map_node_destructor& operator=(const __map_node_destructor&); 627 628public: 629 bool __first_constructed; 630 bool __second_constructed; 631 632 _LIBCPP_INLINE_VISIBILITY 633 explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT 634 : __na_(__na), 635 __first_constructed(false), 636 __second_constructed(false) 637 {} 638 639#ifndef _LIBCPP_CXX03_LANG 640 _LIBCPP_INLINE_VISIBILITY 641 __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT 642 : __na_(__x.__na_), 643 __first_constructed(__x.__value_constructed), 644 __second_constructed(__x.__value_constructed) 645 { 646 __x.__value_constructed = false; 647 } 648#endif // _LIBCPP_CXX03_LANG 649 650 _LIBCPP_INLINE_VISIBILITY 651 void operator()(pointer __p) _NOEXCEPT 652 { 653 if (__second_constructed) 654 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().second)); 655 if (__first_constructed) 656 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().first)); 657 if (__p) 658 __alloc_traits::deallocate(__na_, __p, 1); 659 } 660}; 661 662template <class _Key, class _Tp, class _Compare, class _Allocator> 663 class map; 664template <class _Key, class _Tp, class _Compare, class _Allocator> 665 class multimap; 666template <class _TreeIterator> class __map_const_iterator; 667 668#ifndef _LIBCPP_CXX03_LANG 669 670template <class _Key, class _Tp> 671struct _LIBCPP_STANDALONE_DEBUG __value_type 672{ 673 typedef _Key key_type; 674 typedef _Tp mapped_type; 675 typedef pair<const key_type, mapped_type> value_type; 676 typedef pair<key_type&, mapped_type&> __nc_ref_pair_type; 677 typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type; 678 679private: 680 value_type __cc; 681 682public: 683 _LIBCPP_INLINE_VISIBILITY 684 value_type& __get_value() 685 { 686#if _LIBCPP_STD_VER > 14 687 return *_VSTD::launder(_VSTD::addressof(__cc)); 688#else 689 return __cc; 690#endif 691 } 692 693 _LIBCPP_INLINE_VISIBILITY 694 const value_type& __get_value() const 695 { 696#if _LIBCPP_STD_VER > 14 697 return *_VSTD::launder(_VSTD::addressof(__cc)); 698#else 699 return __cc; 700#endif 701 } 702 703 _LIBCPP_INLINE_VISIBILITY 704 __nc_ref_pair_type __ref() 705 { 706 value_type& __v = __get_value(); 707 return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second); 708 } 709 710 _LIBCPP_INLINE_VISIBILITY 711 __nc_rref_pair_type __move() 712 { 713 value_type& __v = __get_value(); 714 return __nc_rref_pair_type( 715 _VSTD::move(const_cast<key_type&>(__v.first)), 716 _VSTD::move(__v.second)); 717 } 718 719 _LIBCPP_INLINE_VISIBILITY 720 __value_type& operator=(const __value_type& __v) 721 { 722 __ref() = __v.__get_value(); 723 return *this; 724 } 725 726 _LIBCPP_INLINE_VISIBILITY 727 __value_type& operator=(__value_type&& __v) 728 { 729 __ref() = __v.__move(); 730 return *this; 731 } 732 733 template <class _ValueTp, 734 class = typename enable_if< 735 __is_same_uncvref<_ValueTp, value_type>::value 736 >::type 737 > 738 _LIBCPP_INLINE_VISIBILITY 739 __value_type& operator=(_ValueTp&& __v) 740 { 741 __ref() = _VSTD::forward<_ValueTp>(__v); 742 return *this; 743 } 744 745private: 746 __value_type() = delete; 747 ~__value_type() = delete; 748 __value_type(const __value_type&) = delete; 749 __value_type(__value_type&&) = delete; 750}; 751 752#else 753 754template <class _Key, class _Tp> 755struct __value_type 756{ 757 typedef _Key key_type; 758 typedef _Tp mapped_type; 759 typedef pair<const key_type, mapped_type> value_type; 760 761private: 762 value_type __cc; 763 764public: 765 _LIBCPP_INLINE_VISIBILITY 766 value_type& __get_value() { return __cc; } 767 _LIBCPP_INLINE_VISIBILITY 768 const value_type& __get_value() const { return __cc; } 769 770private: 771 __value_type(); 772 __value_type(__value_type const&); 773 __value_type& operator=(__value_type const&); 774 ~__value_type(); 775}; 776 777#endif // _LIBCPP_CXX03_LANG 778 779template <class _Tp> 780struct __extract_key_value_types; 781 782template <class _Key, class _Tp> 783struct __extract_key_value_types<__value_type<_Key, _Tp> > 784{ 785 typedef _Key const __key_type; 786 typedef _Tp __mapped_type; 787}; 788 789template <class _TreeIterator> 790class _LIBCPP_TEMPLATE_VIS __map_iterator 791{ 792 typedef typename _TreeIterator::_NodeTypes _NodeTypes; 793 typedef typename _TreeIterator::__pointer_traits __pointer_traits; 794 795 _TreeIterator __i_; 796 797public: 798 typedef bidirectional_iterator_tag iterator_category; 799 typedef typename _NodeTypes::__map_value_type value_type; 800 typedef typename _TreeIterator::difference_type difference_type; 801 typedef value_type& reference; 802 typedef typename _NodeTypes::__map_value_type_pointer pointer; 803 804 _LIBCPP_INLINE_VISIBILITY 805 __map_iterator() _NOEXCEPT {} 806 807 _LIBCPP_INLINE_VISIBILITY 808 __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {} 809 810 _LIBCPP_INLINE_VISIBILITY 811 reference operator*() const {return __i_->__get_value();} 812 _LIBCPP_INLINE_VISIBILITY 813 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());} 814 815 _LIBCPP_INLINE_VISIBILITY 816 __map_iterator& operator++() {++__i_; return *this;} 817 _LIBCPP_INLINE_VISIBILITY 818 __map_iterator operator++(int) 819 { 820 __map_iterator __t(*this); 821 ++(*this); 822 return __t; 823 } 824 825 _LIBCPP_INLINE_VISIBILITY 826 __map_iterator& operator--() {--__i_; return *this;} 827 _LIBCPP_INLINE_VISIBILITY 828 __map_iterator operator--(int) 829 { 830 __map_iterator __t(*this); 831 --(*this); 832 return __t; 833 } 834 835 friend _LIBCPP_INLINE_VISIBILITY 836 bool operator==(const __map_iterator& __x, const __map_iterator& __y) 837 {return __x.__i_ == __y.__i_;} 838 friend 839 _LIBCPP_INLINE_VISIBILITY 840 bool operator!=(const __map_iterator& __x, const __map_iterator& __y) 841 {return __x.__i_ != __y.__i_;} 842 843 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map; 844 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap; 845 template <class> friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator; 846}; 847 848template <class _TreeIterator> 849class _LIBCPP_TEMPLATE_VIS __map_const_iterator 850{ 851 typedef typename _TreeIterator::_NodeTypes _NodeTypes; 852 typedef typename _TreeIterator::__pointer_traits __pointer_traits; 853 854 _TreeIterator __i_; 855 856public: 857 typedef bidirectional_iterator_tag iterator_category; 858 typedef typename _NodeTypes::__map_value_type value_type; 859 typedef typename _TreeIterator::difference_type difference_type; 860 typedef const value_type& reference; 861 typedef typename _NodeTypes::__const_map_value_type_pointer pointer; 862 863 _LIBCPP_INLINE_VISIBILITY 864 __map_const_iterator() _NOEXCEPT {} 865 866 _LIBCPP_INLINE_VISIBILITY 867 __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {} 868 _LIBCPP_INLINE_VISIBILITY 869 __map_const_iterator(__map_iterator< 870 typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT 871 : __i_(__i.__i_) {} 872 873 _LIBCPP_INLINE_VISIBILITY 874 reference operator*() const {return __i_->__get_value();} 875 _LIBCPP_INLINE_VISIBILITY 876 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());} 877 878 _LIBCPP_INLINE_VISIBILITY 879 __map_const_iterator& operator++() {++__i_; return *this;} 880 _LIBCPP_INLINE_VISIBILITY 881 __map_const_iterator operator++(int) 882 { 883 __map_const_iterator __t(*this); 884 ++(*this); 885 return __t; 886 } 887 888 _LIBCPP_INLINE_VISIBILITY 889 __map_const_iterator& operator--() {--__i_; return *this;} 890 _LIBCPP_INLINE_VISIBILITY 891 __map_const_iterator operator--(int) 892 { 893 __map_const_iterator __t(*this); 894 --(*this); 895 return __t; 896 } 897 898 friend _LIBCPP_INLINE_VISIBILITY 899 bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y) 900 {return __x.__i_ == __y.__i_;} 901 friend _LIBCPP_INLINE_VISIBILITY 902 bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y) 903 {return __x.__i_ != __y.__i_;} 904 905 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map; 906 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap; 907 template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator; 908}; 909 910template <class _Key, class _Tp, class _Compare = less<_Key>, 911 class _Allocator = allocator<pair<const _Key, _Tp> > > 912class _LIBCPP_TEMPLATE_VIS map 913{ 914public: 915 // types: 916 typedef _Key key_type; 917 typedef _Tp mapped_type; 918 typedef pair<const key_type, mapped_type> value_type; 919 typedef __identity_t<_Compare> key_compare; 920 typedef __identity_t<_Allocator> allocator_type; 921 typedef value_type& reference; 922 typedef const value_type& const_reference; 923 924 static_assert((is_same<typename allocator_type::value_type, value_type>::value), 925 "Allocator::value_type must be same type as value_type"); 926 927_LIBCPP_SUPPRESS_DEPRECATED_PUSH 928 class _LIBCPP_TEMPLATE_VIS value_compare 929#if defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) 930 : public binary_function<value_type, value_type, bool> 931#endif 932 { 933_LIBCPP_SUPPRESS_DEPRECATED_POP 934 friend class map; 935 protected: 936 key_compare comp; 937 938 _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {} 939 public: 940#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) 941 _LIBCPP_DEPRECATED_IN_CXX17 typedef bool result_type; 942 _LIBCPP_DEPRECATED_IN_CXX17 typedef value_type first_argument_type; 943 _LIBCPP_DEPRECATED_IN_CXX17 typedef value_type second_argument_type; 944#endif 945 _LIBCPP_INLINE_VISIBILITY 946 bool operator()(const value_type& __x, const value_type& __y) const 947 {return comp(__x.first, __y.first);} 948 }; 949 950private: 951 952 typedef _VSTD::__value_type<key_type, mapped_type> __value_type; 953 typedef __map_value_compare<key_type, __value_type, key_compare> __vc; 954 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, 955 __value_type>::type __allocator_type; 956 typedef __tree<__value_type, __vc, __allocator_type> __base; 957 typedef typename __base::__node_traits __node_traits; 958 typedef allocator_traits<allocator_type> __alloc_traits; 959 960 __base __tree_; 961 962public: 963 typedef typename __alloc_traits::pointer pointer; 964 typedef typename __alloc_traits::const_pointer const_pointer; 965 typedef typename __alloc_traits::size_type size_type; 966 typedef typename __alloc_traits::difference_type difference_type; 967 typedef __map_iterator<typename __base::iterator> iterator; 968 typedef __map_const_iterator<typename __base::const_iterator> const_iterator; 969 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 970 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 971 972#if _LIBCPP_STD_VER > 14 973 typedef __map_node_handle<typename __base::__node, allocator_type> node_type; 974 typedef __insert_return_type<iterator, node_type> insert_return_type; 975#endif 976 977 template <class _Key2, class _Value2, class _Comp2, class _Alloc2> 978 friend class _LIBCPP_TEMPLATE_VIS map; 979 template <class _Key2, class _Value2, class _Comp2, class _Alloc2> 980 friend class _LIBCPP_TEMPLATE_VIS multimap; 981 982 _LIBCPP_INLINE_VISIBILITY 983 map() 984 _NOEXCEPT_( 985 is_nothrow_default_constructible<allocator_type>::value && 986 is_nothrow_default_constructible<key_compare>::value && 987 is_nothrow_copy_constructible<key_compare>::value) 988 : __tree_(__vc(key_compare())) {} 989 990 _LIBCPP_INLINE_VISIBILITY 991 explicit map(const key_compare& __comp) 992 _NOEXCEPT_( 993 is_nothrow_default_constructible<allocator_type>::value && 994 is_nothrow_copy_constructible<key_compare>::value) 995 : __tree_(__vc(__comp)) {} 996 997 _LIBCPP_INLINE_VISIBILITY 998 explicit map(const key_compare& __comp, const allocator_type& __a) 999 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {} 1000 1001 template <class _InputIterator> 1002 _LIBCPP_INLINE_VISIBILITY 1003 map(_InputIterator __f, _InputIterator __l, 1004 const key_compare& __comp = key_compare()) 1005 : __tree_(__vc(__comp)) 1006 { 1007 insert(__f, __l); 1008 } 1009 1010 template <class _InputIterator> 1011 _LIBCPP_INLINE_VISIBILITY 1012 map(_InputIterator __f, _InputIterator __l, 1013 const key_compare& __comp, const allocator_type& __a) 1014 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) 1015 { 1016 insert(__f, __l); 1017 } 1018 1019#if _LIBCPP_STD_VER > 11 1020 template <class _InputIterator> 1021 _LIBCPP_INLINE_VISIBILITY 1022 map(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 1023 : map(__f, __l, key_compare(), __a) {} 1024#endif 1025 1026 _LIBCPP_INLINE_VISIBILITY 1027 map(const map& __m) 1028 : __tree_(__m.__tree_) 1029 { 1030 insert(__m.begin(), __m.end()); 1031 } 1032 1033 _LIBCPP_INLINE_VISIBILITY 1034 map& operator=(const map& __m) 1035 { 1036#ifndef _LIBCPP_CXX03_LANG 1037 __tree_ = __m.__tree_; 1038#else 1039 if (this != &__m) { 1040 __tree_.clear(); 1041 __tree_.value_comp() = __m.__tree_.value_comp(); 1042 __tree_.__copy_assign_alloc(__m.__tree_); 1043 insert(__m.begin(), __m.end()); 1044 } 1045#endif 1046 return *this; 1047 } 1048 1049#ifndef _LIBCPP_CXX03_LANG 1050 1051 _LIBCPP_INLINE_VISIBILITY 1052 map(map&& __m) 1053 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 1054 : __tree_(_VSTD::move(__m.__tree_)) 1055 { 1056 } 1057 1058 map(map&& __m, const allocator_type& __a); 1059 1060 _LIBCPP_INLINE_VISIBILITY 1061 map& operator=(map&& __m) 1062 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 1063 { 1064 __tree_ = _VSTD::move(__m.__tree_); 1065 return *this; 1066 } 1067 1068 _LIBCPP_INLINE_VISIBILITY 1069 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare()) 1070 : __tree_(__vc(__comp)) 1071 { 1072 insert(__il.begin(), __il.end()); 1073 } 1074 1075 _LIBCPP_INLINE_VISIBILITY 1076 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a) 1077 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) 1078 { 1079 insert(__il.begin(), __il.end()); 1080 } 1081 1082#if _LIBCPP_STD_VER > 11 1083 _LIBCPP_INLINE_VISIBILITY 1084 map(initializer_list<value_type> __il, const allocator_type& __a) 1085 : map(__il, key_compare(), __a) {} 1086#endif 1087 1088 _LIBCPP_INLINE_VISIBILITY 1089 map& operator=(initializer_list<value_type> __il) 1090 { 1091 __tree_.__assign_unique(__il.begin(), __il.end()); 1092 return *this; 1093 } 1094 1095#endif // _LIBCPP_CXX03_LANG 1096 1097 _LIBCPP_INLINE_VISIBILITY 1098 explicit map(const allocator_type& __a) 1099 : __tree_(typename __base::allocator_type(__a)) 1100 { 1101 } 1102 1103 _LIBCPP_INLINE_VISIBILITY 1104 map(const map& __m, const allocator_type& __a) 1105 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) 1106 { 1107 insert(__m.begin(), __m.end()); 1108 } 1109 1110 _LIBCPP_INLINE_VISIBILITY 1111 ~map() { 1112 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); 1113 } 1114 1115 _LIBCPP_INLINE_VISIBILITY 1116 iterator begin() _NOEXCEPT {return __tree_.begin();} 1117 _LIBCPP_INLINE_VISIBILITY 1118 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 1119 _LIBCPP_INLINE_VISIBILITY 1120 iterator end() _NOEXCEPT {return __tree_.end();} 1121 _LIBCPP_INLINE_VISIBILITY 1122 const_iterator end() const _NOEXCEPT {return __tree_.end();} 1123 1124 _LIBCPP_INLINE_VISIBILITY 1125 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());} 1126 _LIBCPP_INLINE_VISIBILITY 1127 const_reverse_iterator rbegin() const _NOEXCEPT 1128 {return const_reverse_iterator(end());} 1129 _LIBCPP_INLINE_VISIBILITY 1130 reverse_iterator rend() _NOEXCEPT 1131 {return reverse_iterator(begin());} 1132 _LIBCPP_INLINE_VISIBILITY 1133 const_reverse_iterator rend() const _NOEXCEPT 1134 {return const_reverse_iterator(begin());} 1135 1136 _LIBCPP_INLINE_VISIBILITY 1137 const_iterator cbegin() const _NOEXCEPT {return begin();} 1138 _LIBCPP_INLINE_VISIBILITY 1139 const_iterator cend() const _NOEXCEPT {return end();} 1140 _LIBCPP_INLINE_VISIBILITY 1141 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 1142 _LIBCPP_INLINE_VISIBILITY 1143 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 1144 1145 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 1146 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 1147 _LIBCPP_INLINE_VISIBILITY 1148 size_type size() const _NOEXCEPT {return __tree_.size();} 1149 _LIBCPP_INLINE_VISIBILITY 1150 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 1151 1152 mapped_type& operator[](const key_type& __k); 1153#ifndef _LIBCPP_CXX03_LANG 1154 mapped_type& operator[](key_type&& __k); 1155#endif 1156 1157 mapped_type& at(const key_type& __k); 1158 const mapped_type& at(const key_type& __k) const; 1159 1160 _LIBCPP_INLINE_VISIBILITY 1161 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());} 1162 _LIBCPP_INLINE_VISIBILITY 1163 key_compare key_comp() const {return __tree_.value_comp().key_comp();} 1164 _LIBCPP_INLINE_VISIBILITY 1165 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());} 1166 1167#ifndef _LIBCPP_CXX03_LANG 1168 template <class ..._Args> 1169 _LIBCPP_INLINE_VISIBILITY 1170 pair<iterator, bool> emplace(_Args&& ...__args) { 1171 return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...); 1172 } 1173 1174 template <class ..._Args> 1175 _LIBCPP_INLINE_VISIBILITY 1176 iterator emplace_hint(const_iterator __p, _Args&& ...__args) { 1177 return __tree_.__emplace_hint_unique(__p.__i_, _VSTD::forward<_Args>(__args)...); 1178 } 1179 1180 template <class _Pp, 1181 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1182 _LIBCPP_INLINE_VISIBILITY 1183 pair<iterator, bool> insert(_Pp&& __p) 1184 {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));} 1185 1186 template <class _Pp, 1187 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1188 _LIBCPP_INLINE_VISIBILITY 1189 iterator insert(const_iterator __pos, _Pp&& __p) 1190 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));} 1191 1192#endif // _LIBCPP_CXX03_LANG 1193 1194 _LIBCPP_INLINE_VISIBILITY 1195 pair<iterator, bool> 1196 insert(const value_type& __v) {return __tree_.__insert_unique(__v);} 1197 1198 _LIBCPP_INLINE_VISIBILITY 1199 iterator 1200 insert(const_iterator __p, const value_type& __v) 1201 {return __tree_.__insert_unique(__p.__i_, __v);} 1202 1203#ifndef _LIBCPP_CXX03_LANG 1204 _LIBCPP_INLINE_VISIBILITY 1205 pair<iterator, bool> 1206 insert(value_type&& __v) {return __tree_.__insert_unique(_VSTD::move(__v));} 1207 1208 _LIBCPP_INLINE_VISIBILITY 1209 iterator insert(const_iterator __p, value_type&& __v) 1210 {return __tree_.__insert_unique(__p.__i_, _VSTD::move(__v));} 1211 1212 _LIBCPP_INLINE_VISIBILITY 1213 void insert(initializer_list<value_type> __il) 1214 {insert(__il.begin(), __il.end());} 1215#endif 1216 1217 template <class _InputIterator> 1218 _LIBCPP_INLINE_VISIBILITY 1219 void insert(_InputIterator __f, _InputIterator __l) 1220 { 1221 for (const_iterator __e = cend(); __f != __l; ++__f) 1222 insert(__e.__i_, *__f); 1223 } 1224 1225#if _LIBCPP_STD_VER > 14 1226 1227 template <class... _Args> 1228 _LIBCPP_INLINE_VISIBILITY 1229 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) 1230 { 1231 return __tree_.__emplace_unique_key_args(__k, 1232 _VSTD::piecewise_construct, 1233 _VSTD::forward_as_tuple(__k), 1234 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); 1235 } 1236 1237 template <class... _Args> 1238 _LIBCPP_INLINE_VISIBILITY 1239 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) 1240 { 1241 return __tree_.__emplace_unique_key_args(__k, 1242 _VSTD::piecewise_construct, 1243 _VSTD::forward_as_tuple(_VSTD::move(__k)), 1244 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); 1245 } 1246 1247 template <class... _Args> 1248 _LIBCPP_INLINE_VISIBILITY 1249 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args) 1250 { 1251 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, 1252 _VSTD::piecewise_construct, 1253 _VSTD::forward_as_tuple(__k), 1254 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)).first; 1255 } 1256 1257 template <class... _Args> 1258 _LIBCPP_INLINE_VISIBILITY 1259 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) 1260 { 1261 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, 1262 _VSTD::piecewise_construct, 1263 _VSTD::forward_as_tuple(_VSTD::move(__k)), 1264 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)).first; 1265 } 1266 1267 template <class _Vp> 1268 _LIBCPP_INLINE_VISIBILITY 1269 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) 1270 { 1271 iterator __p = lower_bound(__k); 1272 if ( __p != end() && !key_comp()(__k, __p->first)) 1273 { 1274 __p->second = _VSTD::forward<_Vp>(__v); 1275 return _VSTD::make_pair(__p, false); 1276 } 1277 return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true); 1278 } 1279 1280 template <class _Vp> 1281 _LIBCPP_INLINE_VISIBILITY 1282 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) 1283 { 1284 iterator __p = lower_bound(__k); 1285 if ( __p != end() && !key_comp()(__k, __p->first)) 1286 { 1287 __p->second = _VSTD::forward<_Vp>(__v); 1288 return _VSTD::make_pair(__p, false); 1289 } 1290 return _VSTD::make_pair(emplace_hint(__p, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)), true); 1291 } 1292 1293 template <class _Vp> 1294 _LIBCPP_INLINE_VISIBILITY iterator insert_or_assign(const_iterator __h, 1295 const key_type& __k, 1296 _Vp&& __v) { 1297 auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args( 1298 __h.__i_, __k, __k, _VSTD::forward<_Vp>(__v)); 1299 1300 if (!__inserted) 1301 __r->__get_value().second = _VSTD::forward<_Vp>(__v); 1302 1303 return __r; 1304 } 1305 1306 template <class _Vp> 1307 _LIBCPP_INLINE_VISIBILITY iterator insert_or_assign(const_iterator __h, 1308 key_type&& __k, 1309 _Vp&& __v) { 1310 auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args( 1311 __h.__i_, __k, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)); 1312 1313 if (!__inserted) 1314 __r->__get_value().second = _VSTD::forward<_Vp>(__v); 1315 1316 return __r; 1317 } 1318 1319#endif // _LIBCPP_STD_VER > 14 1320 1321 _LIBCPP_INLINE_VISIBILITY 1322 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);} 1323 _LIBCPP_INLINE_VISIBILITY 1324 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);} 1325 _LIBCPP_INLINE_VISIBILITY 1326 size_type erase(const key_type& __k) 1327 {return __tree_.__erase_unique(__k);} 1328 _LIBCPP_INLINE_VISIBILITY 1329 iterator erase(const_iterator __f, const_iterator __l) 1330 {return __tree_.erase(__f.__i_, __l.__i_);} 1331 _LIBCPP_INLINE_VISIBILITY 1332 void clear() _NOEXCEPT {__tree_.clear();} 1333 1334#if _LIBCPP_STD_VER > 14 1335 _LIBCPP_INLINE_VISIBILITY 1336 insert_return_type insert(node_type&& __nh) 1337 { 1338 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1339 "node_type with incompatible allocator passed to map::insert()"); 1340 return __tree_.template __node_handle_insert_unique< 1341 node_type, insert_return_type>(_VSTD::move(__nh)); 1342 } 1343 _LIBCPP_INLINE_VISIBILITY 1344 iterator insert(const_iterator __hint, node_type&& __nh) 1345 { 1346 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1347 "node_type with incompatible allocator passed to map::insert()"); 1348 return __tree_.template __node_handle_insert_unique<node_type>( 1349 __hint.__i_, _VSTD::move(__nh)); 1350 } 1351 _LIBCPP_INLINE_VISIBILITY 1352 node_type extract(key_type const& __key) 1353 { 1354 return __tree_.template __node_handle_extract<node_type>(__key); 1355 } 1356 _LIBCPP_INLINE_VISIBILITY 1357 node_type extract(const_iterator __it) 1358 { 1359 return __tree_.template __node_handle_extract<node_type>(__it.__i_); 1360 } 1361 template <class _Compare2> 1362 _LIBCPP_INLINE_VISIBILITY 1363 void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source) 1364 { 1365 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1366 "merging container with incompatible allocator"); 1367 __tree_.__node_handle_merge_unique(__source.__tree_); 1368 } 1369 template <class _Compare2> 1370 _LIBCPP_INLINE_VISIBILITY 1371 void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source) 1372 { 1373 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1374 "merging container with incompatible allocator"); 1375 __tree_.__node_handle_merge_unique(__source.__tree_); 1376 } 1377 template <class _Compare2> 1378 _LIBCPP_INLINE_VISIBILITY 1379 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source) 1380 { 1381 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1382 "merging container with incompatible allocator"); 1383 __tree_.__node_handle_merge_unique(__source.__tree_); 1384 } 1385 template <class _Compare2> 1386 _LIBCPP_INLINE_VISIBILITY 1387 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source) 1388 { 1389 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1390 "merging container with incompatible allocator"); 1391 __tree_.__node_handle_merge_unique(__source.__tree_); 1392 } 1393#endif 1394 1395 _LIBCPP_INLINE_VISIBILITY 1396 void swap(map& __m) 1397 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 1398 {__tree_.swap(__m.__tree_);} 1399 1400 _LIBCPP_INLINE_VISIBILITY 1401 iterator find(const key_type& __k) {return __tree_.find(__k);} 1402 _LIBCPP_INLINE_VISIBILITY 1403 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 1404#if _LIBCPP_STD_VER > 11 1405 template <typename _K2> 1406 _LIBCPP_INLINE_VISIBILITY 1407 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 1408 find(const _K2& __k) {return __tree_.find(__k);} 1409 template <typename _K2> 1410 _LIBCPP_INLINE_VISIBILITY 1411 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 1412 find(const _K2& __k) const {return __tree_.find(__k);} 1413#endif 1414 1415 _LIBCPP_INLINE_VISIBILITY 1416 size_type count(const key_type& __k) const 1417 {return __tree_.__count_unique(__k);} 1418#if _LIBCPP_STD_VER > 11 1419 template <typename _K2> 1420 _LIBCPP_INLINE_VISIBILITY 1421 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 1422 count(const _K2& __k) const {return __tree_.__count_multi(__k);} 1423#endif 1424 1425#if _LIBCPP_STD_VER > 17 1426 _LIBCPP_INLINE_VISIBILITY 1427 bool contains(const key_type& __k) const {return find(__k) != end();} 1428 template <typename _K2> 1429 _LIBCPP_INLINE_VISIBILITY 1430 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type 1431 contains(const _K2& __k) const { return find(__k) != end(); } 1432#endif // _LIBCPP_STD_VER > 17 1433 1434 _LIBCPP_INLINE_VISIBILITY 1435 iterator lower_bound(const key_type& __k) 1436 {return __tree_.lower_bound(__k);} 1437 _LIBCPP_INLINE_VISIBILITY 1438 const_iterator lower_bound(const key_type& __k) const 1439 {return __tree_.lower_bound(__k);} 1440#if _LIBCPP_STD_VER > 11 1441 template <typename _K2> 1442 _LIBCPP_INLINE_VISIBILITY 1443 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 1444 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 1445 1446 template <typename _K2> 1447 _LIBCPP_INLINE_VISIBILITY 1448 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 1449 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 1450#endif 1451 1452 _LIBCPP_INLINE_VISIBILITY 1453 iterator upper_bound(const key_type& __k) 1454 {return __tree_.upper_bound(__k);} 1455 _LIBCPP_INLINE_VISIBILITY 1456 const_iterator upper_bound(const key_type& __k) const 1457 {return __tree_.upper_bound(__k);} 1458#if _LIBCPP_STD_VER > 11 1459 template <typename _K2> 1460 _LIBCPP_INLINE_VISIBILITY 1461 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 1462 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 1463 template <typename _K2> 1464 _LIBCPP_INLINE_VISIBILITY 1465 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 1466 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 1467#endif 1468 1469 _LIBCPP_INLINE_VISIBILITY 1470 pair<iterator,iterator> equal_range(const key_type& __k) 1471 {return __tree_.__equal_range_unique(__k);} 1472 _LIBCPP_INLINE_VISIBILITY 1473 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 1474 {return __tree_.__equal_range_unique(__k);} 1475#if _LIBCPP_STD_VER > 11 1476 template <typename _K2> 1477 _LIBCPP_INLINE_VISIBILITY 1478 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 1479 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 1480 template <typename _K2> 1481 _LIBCPP_INLINE_VISIBILITY 1482 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 1483 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 1484#endif 1485 1486private: 1487 typedef typename __base::__node __node; 1488 typedef typename __base::__node_allocator __node_allocator; 1489 typedef typename __base::__node_pointer __node_pointer; 1490 typedef typename __base::__node_base_pointer __node_base_pointer; 1491 typedef typename __base::__parent_pointer __parent_pointer; 1492 1493 typedef __map_node_destructor<__node_allocator> _Dp; 1494 typedef unique_ptr<__node, _Dp> __node_holder; 1495 1496#ifdef _LIBCPP_CXX03_LANG 1497 __node_holder __construct_node_with_key(const key_type& __k); 1498#endif 1499}; 1500 1501#if _LIBCPP_STD_VER >= 17 1502template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>, 1503 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, 1504 class = enable_if_t<!__is_allocator<_Compare>::value, void>, 1505 class = enable_if_t<__is_allocator<_Allocator>::value, void>> 1506map(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) 1507 -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>; 1508 1509template<class _Key, class _Tp, class _Compare = less<remove_const_t<_Key>>, 1510 class _Allocator = allocator<pair<const _Key, _Tp>>, 1511 class = enable_if_t<!__is_allocator<_Compare>::value, void>, 1512 class = enable_if_t<__is_allocator<_Allocator>::value, void>> 1513map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator()) 1514 -> map<remove_const_t<_Key>, _Tp, _Compare, _Allocator>; 1515 1516template<class _InputIterator, class _Allocator, 1517 class = enable_if_t<__is_allocator<_Allocator>::value, void>> 1518map(_InputIterator, _InputIterator, _Allocator) 1519 -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, 1520 less<__iter_key_type<_InputIterator>>, _Allocator>; 1521 1522template<class _Key, class _Tp, class _Allocator, 1523 class = enable_if_t<__is_allocator<_Allocator>::value, void>> 1524map(initializer_list<pair<_Key, _Tp>>, _Allocator) 1525 -> map<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>; 1526#endif 1527 1528#ifndef _LIBCPP_CXX03_LANG 1529template <class _Key, class _Tp, class _Compare, class _Allocator> 1530map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a) 1531 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a)) 1532{ 1533 if (__a != __m.get_allocator()) 1534 { 1535 const_iterator __e = cend(); 1536 while (!__m.empty()) 1537 __tree_.__insert_unique(__e.__i_, 1538 __m.__tree_.remove(__m.begin().__i_)->__value_.__move()); 1539 } 1540} 1541 1542template <class _Key, class _Tp, class _Compare, class _Allocator> 1543_Tp& 1544map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) 1545{ 1546 return __tree_.__emplace_unique_key_args(__k, 1547 _VSTD::piecewise_construct, 1548 _VSTD::forward_as_tuple(__k), 1549 _VSTD::forward_as_tuple()).first->__get_value().second; 1550} 1551 1552template <class _Key, class _Tp, class _Compare, class _Allocator> 1553_Tp& 1554map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k) 1555{ 1556 return __tree_.__emplace_unique_key_args(__k, 1557 _VSTD::piecewise_construct, 1558 _VSTD::forward_as_tuple(_VSTD::move(__k)), 1559 _VSTD::forward_as_tuple()).first->__get_value().second; 1560} 1561 1562#else // _LIBCPP_CXX03_LANG 1563 1564template <class _Key, class _Tp, class _Compare, class _Allocator> 1565typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder 1566map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k) 1567{ 1568 __node_allocator& __na = __tree_.__node_alloc(); 1569 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1570 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().first), __k); 1571 __h.get_deleter().__first_constructed = true; 1572 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().second)); 1573 __h.get_deleter().__second_constructed = true; 1574 return __h; 1575} 1576 1577template <class _Key, class _Tp, class _Compare, class _Allocator> 1578_Tp& 1579map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) 1580{ 1581 __parent_pointer __parent; 1582 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k); 1583 __node_pointer __r = static_cast<__node_pointer>(__child); 1584 if (__child == nullptr) 1585 { 1586 __node_holder __h = __construct_node_with_key(__k); 1587 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1588 __r = __h.release(); 1589 } 1590 return __r->__value_.__get_value().second; 1591} 1592 1593#endif // _LIBCPP_CXX03_LANG 1594 1595template <class _Key, class _Tp, class _Compare, class _Allocator> 1596_Tp& 1597map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) 1598{ 1599 __parent_pointer __parent; 1600 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k); 1601 if (__child == nullptr) 1602 __throw_out_of_range("map::at: key not found"); 1603 return static_cast<__node_pointer>(__child)->__value_.__get_value().second; 1604} 1605 1606template <class _Key, class _Tp, class _Compare, class _Allocator> 1607const _Tp& 1608map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const 1609{ 1610 __parent_pointer __parent; 1611 __node_base_pointer __child = __tree_.__find_equal(__parent, __k); 1612 if (__child == nullptr) 1613 __throw_out_of_range("map::at: key not found"); 1614 return static_cast<__node_pointer>(__child)->__value_.__get_value().second; 1615} 1616 1617 1618template <class _Key, class _Tp, class _Compare, class _Allocator> 1619inline _LIBCPP_INLINE_VISIBILITY 1620bool 1621operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1622 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1623{ 1624 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 1625} 1626 1627template <class _Key, class _Tp, class _Compare, class _Allocator> 1628inline _LIBCPP_INLINE_VISIBILITY 1629bool 1630operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x, 1631 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1632{ 1633 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 1634} 1635 1636template <class _Key, class _Tp, class _Compare, class _Allocator> 1637inline _LIBCPP_INLINE_VISIBILITY 1638bool 1639operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1640 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1641{ 1642 return !(__x == __y); 1643} 1644 1645template <class _Key, class _Tp, class _Compare, class _Allocator> 1646inline _LIBCPP_INLINE_VISIBILITY 1647bool 1648operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x, 1649 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1650{ 1651 return __y < __x; 1652} 1653 1654template <class _Key, class _Tp, class _Compare, class _Allocator> 1655inline _LIBCPP_INLINE_VISIBILITY 1656bool 1657operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1658 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1659{ 1660 return !(__x < __y); 1661} 1662 1663template <class _Key, class _Tp, class _Compare, class _Allocator> 1664inline _LIBCPP_INLINE_VISIBILITY 1665bool 1666operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1667 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1668{ 1669 return !(__y < __x); 1670} 1671 1672template <class _Key, class _Tp, class _Compare, class _Allocator> 1673inline _LIBCPP_INLINE_VISIBILITY 1674void 1675swap(map<_Key, _Tp, _Compare, _Allocator>& __x, 1676 map<_Key, _Tp, _Compare, _Allocator>& __y) 1677 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1678{ 1679 __x.swap(__y); 1680} 1681 1682#if _LIBCPP_STD_VER > 17 1683template <class _Key, class _Tp, class _Compare, class _Allocator, 1684 class _Predicate> 1685inline _LIBCPP_INLINE_VISIBILITY 1686 typename map<_Key, _Tp, _Compare, _Allocator>::size_type 1687 erase_if(map<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) { 1688 return _VSTD::__libcpp_erase_if_container(__c, __pred); 1689} 1690#endif 1691 1692 1693template <class _Key, class _Tp, class _Compare = less<_Key>, 1694 class _Allocator = allocator<pair<const _Key, _Tp> > > 1695class _LIBCPP_TEMPLATE_VIS multimap 1696{ 1697public: 1698 // types: 1699 typedef _Key key_type; 1700 typedef _Tp mapped_type; 1701 typedef pair<const key_type, mapped_type> value_type; 1702 typedef __identity_t<_Compare> key_compare; 1703 typedef __identity_t<_Allocator> allocator_type; 1704 typedef value_type& reference; 1705 typedef const value_type& const_reference; 1706 1707 static_assert((is_same<typename allocator_type::value_type, value_type>::value), 1708 "Allocator::value_type must be same type as value_type"); 1709 1710_LIBCPP_SUPPRESS_DEPRECATED_PUSH 1711 class _LIBCPP_TEMPLATE_VIS value_compare 1712#if defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) 1713 : public binary_function<value_type, value_type, bool> 1714#endif 1715 { 1716_LIBCPP_SUPPRESS_DEPRECATED_POP 1717 friend class multimap; 1718 protected: 1719 key_compare comp; 1720 1721 _LIBCPP_INLINE_VISIBILITY 1722 value_compare(key_compare c) : comp(c) {} 1723 public: 1724#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS) 1725 _LIBCPP_DEPRECATED_IN_CXX17 typedef bool result_type; 1726 _LIBCPP_DEPRECATED_IN_CXX17 typedef value_type first_argument_type; 1727 _LIBCPP_DEPRECATED_IN_CXX17 typedef value_type second_argument_type; 1728#endif 1729 _LIBCPP_INLINE_VISIBILITY 1730 bool operator()(const value_type& __x, const value_type& __y) const 1731 {return comp(__x.first, __y.first);} 1732 }; 1733 1734private: 1735 1736 typedef _VSTD::__value_type<key_type, mapped_type> __value_type; 1737 typedef __map_value_compare<key_type, __value_type, key_compare> __vc; 1738 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, 1739 __value_type>::type __allocator_type; 1740 typedef __tree<__value_type, __vc, __allocator_type> __base; 1741 typedef typename __base::__node_traits __node_traits; 1742 typedef allocator_traits<allocator_type> __alloc_traits; 1743 1744 __base __tree_; 1745 1746public: 1747 typedef typename __alloc_traits::pointer pointer; 1748 typedef typename __alloc_traits::const_pointer const_pointer; 1749 typedef typename __alloc_traits::size_type size_type; 1750 typedef typename __alloc_traits::difference_type difference_type; 1751 typedef __map_iterator<typename __base::iterator> iterator; 1752 typedef __map_const_iterator<typename __base::const_iterator> const_iterator; 1753 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 1754 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 1755 1756#if _LIBCPP_STD_VER > 14 1757 typedef __map_node_handle<typename __base::__node, allocator_type> node_type; 1758#endif 1759 1760 template <class _Key2, class _Value2, class _Comp2, class _Alloc2> 1761 friend class _LIBCPP_TEMPLATE_VIS map; 1762 template <class _Key2, class _Value2, class _Comp2, class _Alloc2> 1763 friend class _LIBCPP_TEMPLATE_VIS multimap; 1764 1765 _LIBCPP_INLINE_VISIBILITY 1766 multimap() 1767 _NOEXCEPT_( 1768 is_nothrow_default_constructible<allocator_type>::value && 1769 is_nothrow_default_constructible<key_compare>::value && 1770 is_nothrow_copy_constructible<key_compare>::value) 1771 : __tree_(__vc(key_compare())) {} 1772 1773 _LIBCPP_INLINE_VISIBILITY 1774 explicit multimap(const key_compare& __comp) 1775 _NOEXCEPT_( 1776 is_nothrow_default_constructible<allocator_type>::value && 1777 is_nothrow_copy_constructible<key_compare>::value) 1778 : __tree_(__vc(__comp)) {} 1779 1780 _LIBCPP_INLINE_VISIBILITY 1781 explicit multimap(const key_compare& __comp, const allocator_type& __a) 1782 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {} 1783 1784 template <class _InputIterator> 1785 _LIBCPP_INLINE_VISIBILITY 1786 multimap(_InputIterator __f, _InputIterator __l, 1787 const key_compare& __comp = key_compare()) 1788 : __tree_(__vc(__comp)) 1789 { 1790 insert(__f, __l); 1791 } 1792 1793 template <class _InputIterator> 1794 _LIBCPP_INLINE_VISIBILITY 1795 multimap(_InputIterator __f, _InputIterator __l, 1796 const key_compare& __comp, const allocator_type& __a) 1797 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) 1798 { 1799 insert(__f, __l); 1800 } 1801 1802#if _LIBCPP_STD_VER > 11 1803 template <class _InputIterator> 1804 _LIBCPP_INLINE_VISIBILITY 1805 multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 1806 : multimap(__f, __l, key_compare(), __a) {} 1807#endif 1808 1809 _LIBCPP_INLINE_VISIBILITY 1810 multimap(const multimap& __m) 1811 : __tree_(__m.__tree_.value_comp(), 1812 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc())) 1813 { 1814 insert(__m.begin(), __m.end()); 1815 } 1816 1817 _LIBCPP_INLINE_VISIBILITY 1818 multimap& operator=(const multimap& __m) 1819 { 1820#ifndef _LIBCPP_CXX03_LANG 1821 __tree_ = __m.__tree_; 1822#else 1823 if (this != &__m) { 1824 __tree_.clear(); 1825 __tree_.value_comp() = __m.__tree_.value_comp(); 1826 __tree_.__copy_assign_alloc(__m.__tree_); 1827 insert(__m.begin(), __m.end()); 1828 } 1829#endif 1830 return *this; 1831 } 1832 1833#ifndef _LIBCPP_CXX03_LANG 1834 1835 _LIBCPP_INLINE_VISIBILITY 1836 multimap(multimap&& __m) 1837 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 1838 : __tree_(_VSTD::move(__m.__tree_)) 1839 { 1840 } 1841 1842 multimap(multimap&& __m, const allocator_type& __a); 1843 1844 _LIBCPP_INLINE_VISIBILITY 1845 multimap& operator=(multimap&& __m) 1846 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 1847 { 1848 __tree_ = _VSTD::move(__m.__tree_); 1849 return *this; 1850 } 1851 1852 _LIBCPP_INLINE_VISIBILITY 1853 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare()) 1854 : __tree_(__vc(__comp)) 1855 { 1856 insert(__il.begin(), __il.end()); 1857 } 1858 1859 _LIBCPP_INLINE_VISIBILITY 1860 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a) 1861 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) 1862 { 1863 insert(__il.begin(), __il.end()); 1864 } 1865 1866#if _LIBCPP_STD_VER > 11 1867 _LIBCPP_INLINE_VISIBILITY 1868 multimap(initializer_list<value_type> __il, const allocator_type& __a) 1869 : multimap(__il, key_compare(), __a) {} 1870#endif 1871 1872 _LIBCPP_INLINE_VISIBILITY 1873 multimap& operator=(initializer_list<value_type> __il) 1874 { 1875 __tree_.__assign_multi(__il.begin(), __il.end()); 1876 return *this; 1877 } 1878 1879#endif // _LIBCPP_CXX03_LANG 1880 1881 _LIBCPP_INLINE_VISIBILITY 1882 explicit multimap(const allocator_type& __a) 1883 : __tree_(typename __base::allocator_type(__a)) 1884 { 1885 } 1886 1887 _LIBCPP_INLINE_VISIBILITY 1888 multimap(const multimap& __m, const allocator_type& __a) 1889 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) 1890 { 1891 insert(__m.begin(), __m.end()); 1892 } 1893 1894 _LIBCPP_INLINE_VISIBILITY 1895 ~multimap() { 1896 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); 1897 } 1898 1899 _LIBCPP_INLINE_VISIBILITY 1900 iterator begin() _NOEXCEPT {return __tree_.begin();} 1901 _LIBCPP_INLINE_VISIBILITY 1902 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 1903 _LIBCPP_INLINE_VISIBILITY 1904 iterator end() _NOEXCEPT {return __tree_.end();} 1905 _LIBCPP_INLINE_VISIBILITY 1906 const_iterator end() const _NOEXCEPT {return __tree_.end();} 1907 1908 _LIBCPP_INLINE_VISIBILITY 1909 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());} 1910 _LIBCPP_INLINE_VISIBILITY 1911 const_reverse_iterator rbegin() const _NOEXCEPT 1912 {return const_reverse_iterator(end());} 1913 _LIBCPP_INLINE_VISIBILITY 1914 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());} 1915 _LIBCPP_INLINE_VISIBILITY 1916 const_reverse_iterator rend() const _NOEXCEPT 1917 {return const_reverse_iterator(begin());} 1918 1919 _LIBCPP_INLINE_VISIBILITY 1920 const_iterator cbegin() const _NOEXCEPT {return begin();} 1921 _LIBCPP_INLINE_VISIBILITY 1922 const_iterator cend() const _NOEXCEPT {return end();} 1923 _LIBCPP_INLINE_VISIBILITY 1924 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 1925 _LIBCPP_INLINE_VISIBILITY 1926 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 1927 1928 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 1929 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 1930 _LIBCPP_INLINE_VISIBILITY 1931 size_type size() const _NOEXCEPT {return __tree_.size();} 1932 _LIBCPP_INLINE_VISIBILITY 1933 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 1934 1935 _LIBCPP_INLINE_VISIBILITY 1936 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());} 1937 _LIBCPP_INLINE_VISIBILITY 1938 key_compare key_comp() const {return __tree_.value_comp().key_comp();} 1939 _LIBCPP_INLINE_VISIBILITY 1940 value_compare value_comp() const 1941 {return value_compare(__tree_.value_comp().key_comp());} 1942 1943#ifndef _LIBCPP_CXX03_LANG 1944 1945 template <class ..._Args> 1946 _LIBCPP_INLINE_VISIBILITY 1947 iterator emplace(_Args&& ...__args) { 1948 return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...); 1949 } 1950 1951 template <class ..._Args> 1952 _LIBCPP_INLINE_VISIBILITY 1953 iterator emplace_hint(const_iterator __p, _Args&& ...__args) { 1954 return __tree_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...); 1955 } 1956 1957 template <class _Pp, 1958 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1959 _LIBCPP_INLINE_VISIBILITY 1960 iterator insert(_Pp&& __p) 1961 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));} 1962 1963 template <class _Pp, 1964 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1965 _LIBCPP_INLINE_VISIBILITY 1966 iterator insert(const_iterator __pos, _Pp&& __p) 1967 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));} 1968 1969 _LIBCPP_INLINE_VISIBILITY 1970 iterator insert(value_type&& __v) 1971 {return __tree_.__insert_multi(_VSTD::move(__v));} 1972 1973 _LIBCPP_INLINE_VISIBILITY 1974 iterator insert(const_iterator __p, value_type&& __v) 1975 {return __tree_.__insert_multi(__p.__i_, _VSTD::move(__v));} 1976 1977 1978 _LIBCPP_INLINE_VISIBILITY 1979 void insert(initializer_list<value_type> __il) 1980 {insert(__il.begin(), __il.end());} 1981 1982#endif // _LIBCPP_CXX03_LANG 1983 1984 _LIBCPP_INLINE_VISIBILITY 1985 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);} 1986 1987 _LIBCPP_INLINE_VISIBILITY 1988 iterator insert(const_iterator __p, const value_type& __v) 1989 {return __tree_.__insert_multi(__p.__i_, __v);} 1990 1991 template <class _InputIterator> 1992 _LIBCPP_INLINE_VISIBILITY 1993 void insert(_InputIterator __f, _InputIterator __l) 1994 { 1995 for (const_iterator __e = cend(); __f != __l; ++__f) 1996 __tree_.__insert_multi(__e.__i_, *__f); 1997 } 1998 1999 _LIBCPP_INLINE_VISIBILITY 2000 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);} 2001 _LIBCPP_INLINE_VISIBILITY 2002 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);} 2003 _LIBCPP_INLINE_VISIBILITY 2004 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} 2005 _LIBCPP_INLINE_VISIBILITY 2006 iterator erase(const_iterator __f, const_iterator __l) 2007 {return __tree_.erase(__f.__i_, __l.__i_);} 2008 2009#if _LIBCPP_STD_VER > 14 2010 _LIBCPP_INLINE_VISIBILITY 2011 iterator insert(node_type&& __nh) 2012 { 2013 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 2014 "node_type with incompatible allocator passed to multimap::insert()"); 2015 return __tree_.template __node_handle_insert_multi<node_type>( 2016 _VSTD::move(__nh)); 2017 } 2018 _LIBCPP_INLINE_VISIBILITY 2019 iterator insert(const_iterator __hint, node_type&& __nh) 2020 { 2021 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 2022 "node_type with incompatible allocator passed to multimap::insert()"); 2023 return __tree_.template __node_handle_insert_multi<node_type>( 2024 __hint.__i_, _VSTD::move(__nh)); 2025 } 2026 _LIBCPP_INLINE_VISIBILITY 2027 node_type extract(key_type const& __key) 2028 { 2029 return __tree_.template __node_handle_extract<node_type>(__key); 2030 } 2031 _LIBCPP_INLINE_VISIBILITY 2032 node_type extract(const_iterator __it) 2033 { 2034 return __tree_.template __node_handle_extract<node_type>( 2035 __it.__i_); 2036 } 2037 template <class _Compare2> 2038 _LIBCPP_INLINE_VISIBILITY 2039 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source) 2040 { 2041 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 2042 "merging container with incompatible allocator"); 2043 return __tree_.__node_handle_merge_multi(__source.__tree_); 2044 } 2045 template <class _Compare2> 2046 _LIBCPP_INLINE_VISIBILITY 2047 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source) 2048 { 2049 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 2050 "merging container with incompatible allocator"); 2051 return __tree_.__node_handle_merge_multi(__source.__tree_); 2052 } 2053 template <class _Compare2> 2054 _LIBCPP_INLINE_VISIBILITY 2055 void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source) 2056 { 2057 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 2058 "merging container with incompatible allocator"); 2059 return __tree_.__node_handle_merge_multi(__source.__tree_); 2060 } 2061 template <class _Compare2> 2062 _LIBCPP_INLINE_VISIBILITY 2063 void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source) 2064 { 2065 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 2066 "merging container with incompatible allocator"); 2067 return __tree_.__node_handle_merge_multi(__source.__tree_); 2068 } 2069#endif 2070 2071 _LIBCPP_INLINE_VISIBILITY 2072 void clear() _NOEXCEPT {__tree_.clear();} 2073 2074 _LIBCPP_INLINE_VISIBILITY 2075 void swap(multimap& __m) 2076 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 2077 {__tree_.swap(__m.__tree_);} 2078 2079 _LIBCPP_INLINE_VISIBILITY 2080 iterator find(const key_type& __k) {return __tree_.find(__k);} 2081 _LIBCPP_INLINE_VISIBILITY 2082 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 2083#if _LIBCPP_STD_VER > 11 2084 template <typename _K2> 2085 _LIBCPP_INLINE_VISIBILITY 2086 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 2087 find(const _K2& __k) {return __tree_.find(__k);} 2088 template <typename _K2> 2089 _LIBCPP_INLINE_VISIBILITY 2090 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 2091 find(const _K2& __k) const {return __tree_.find(__k);} 2092#endif 2093 2094 _LIBCPP_INLINE_VISIBILITY 2095 size_type count(const key_type& __k) const 2096 {return __tree_.__count_multi(__k);} 2097#if _LIBCPP_STD_VER > 11 2098 template <typename _K2> 2099 _LIBCPP_INLINE_VISIBILITY 2100 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 2101 count(const _K2& __k) const {return __tree_.__count_multi(__k);} 2102#endif 2103 2104#if _LIBCPP_STD_VER > 17 2105 _LIBCPP_INLINE_VISIBILITY 2106 bool contains(const key_type& __k) const {return find(__k) != end();} 2107 template <typename _K2> 2108 _LIBCPP_INLINE_VISIBILITY 2109 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type 2110 contains(const _K2& __k) const { return find(__k) != end(); } 2111#endif // _LIBCPP_STD_VER > 17 2112 2113 _LIBCPP_INLINE_VISIBILITY 2114 iterator lower_bound(const key_type& __k) 2115 {return __tree_.lower_bound(__k);} 2116 _LIBCPP_INLINE_VISIBILITY 2117 const_iterator lower_bound(const key_type& __k) const 2118 {return __tree_.lower_bound(__k);} 2119#if _LIBCPP_STD_VER > 11 2120 template <typename _K2> 2121 _LIBCPP_INLINE_VISIBILITY 2122 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 2123 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 2124 2125 template <typename _K2> 2126 _LIBCPP_INLINE_VISIBILITY 2127 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 2128 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 2129#endif 2130 2131 _LIBCPP_INLINE_VISIBILITY 2132 iterator upper_bound(const key_type& __k) 2133 {return __tree_.upper_bound(__k);} 2134 _LIBCPP_INLINE_VISIBILITY 2135 const_iterator upper_bound(const key_type& __k) const 2136 {return __tree_.upper_bound(__k);} 2137#if _LIBCPP_STD_VER > 11 2138 template <typename _K2> 2139 _LIBCPP_INLINE_VISIBILITY 2140 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 2141 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 2142 template <typename _K2> 2143 _LIBCPP_INLINE_VISIBILITY 2144 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 2145 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 2146#endif 2147 2148 _LIBCPP_INLINE_VISIBILITY 2149 pair<iterator,iterator> equal_range(const key_type& __k) 2150 {return __tree_.__equal_range_multi(__k);} 2151 _LIBCPP_INLINE_VISIBILITY 2152 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 2153 {return __tree_.__equal_range_multi(__k);} 2154#if _LIBCPP_STD_VER > 11 2155 template <typename _K2> 2156 _LIBCPP_INLINE_VISIBILITY 2157 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 2158 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 2159 template <typename _K2> 2160 _LIBCPP_INLINE_VISIBILITY 2161 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 2162 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 2163#endif 2164 2165private: 2166 typedef typename __base::__node __node; 2167 typedef typename __base::__node_allocator __node_allocator; 2168 typedef typename __base::__node_pointer __node_pointer; 2169 2170 typedef __map_node_destructor<__node_allocator> _Dp; 2171 typedef unique_ptr<__node, _Dp> __node_holder; 2172}; 2173 2174#if _LIBCPP_STD_VER >= 17 2175template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>, 2176 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, 2177 class = enable_if_t<!__is_allocator<_Compare>::value, void>, 2178 class = enable_if_t<__is_allocator<_Allocator>::value, void>> 2179multimap(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) 2180 -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>; 2181 2182template<class _Key, class _Tp, class _Compare = less<remove_const_t<_Key>>, 2183 class _Allocator = allocator<pair<const _Key, _Tp>>, 2184 class = enable_if_t<!__is_allocator<_Compare>::value, void>, 2185 class = enable_if_t<__is_allocator<_Allocator>::value, void>> 2186multimap(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator()) 2187 -> multimap<remove_const_t<_Key>, _Tp, _Compare, _Allocator>; 2188 2189template<class _InputIterator, class _Allocator, 2190 class = enable_if_t<__is_allocator<_Allocator>::value, void>> 2191multimap(_InputIterator, _InputIterator, _Allocator) 2192 -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, 2193 less<__iter_key_type<_InputIterator>>, _Allocator>; 2194 2195template<class _Key, class _Tp, class _Allocator, 2196 class = enable_if_t<__is_allocator<_Allocator>::value, void>> 2197multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) 2198 -> multimap<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>; 2199#endif 2200 2201#ifndef _LIBCPP_CXX03_LANG 2202template <class _Key, class _Tp, class _Compare, class _Allocator> 2203multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a) 2204 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a)) 2205{ 2206 if (__a != __m.get_allocator()) 2207 { 2208 const_iterator __e = cend(); 2209 while (!__m.empty()) 2210 __tree_.__insert_multi(__e.__i_, 2211 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__move())); 2212 } 2213} 2214#endif 2215 2216template <class _Key, class _Tp, class _Compare, class _Allocator> 2217inline _LIBCPP_INLINE_VISIBILITY 2218bool 2219operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2220 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2221{ 2222 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 2223} 2224 2225template <class _Key, class _Tp, class _Compare, class _Allocator> 2226inline _LIBCPP_INLINE_VISIBILITY 2227bool 2228operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2229 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2230{ 2231 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 2232} 2233 2234template <class _Key, class _Tp, class _Compare, class _Allocator> 2235inline _LIBCPP_INLINE_VISIBILITY 2236bool 2237operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2238 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2239{ 2240 return !(__x == __y); 2241} 2242 2243template <class _Key, class _Tp, class _Compare, class _Allocator> 2244inline _LIBCPP_INLINE_VISIBILITY 2245bool 2246operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2247 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2248{ 2249 return __y < __x; 2250} 2251 2252template <class _Key, class _Tp, class _Compare, class _Allocator> 2253inline _LIBCPP_INLINE_VISIBILITY 2254bool 2255operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2256 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2257{ 2258 return !(__x < __y); 2259} 2260 2261template <class _Key, class _Tp, class _Compare, class _Allocator> 2262inline _LIBCPP_INLINE_VISIBILITY 2263bool 2264operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2265 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2266{ 2267 return !(__y < __x); 2268} 2269 2270template <class _Key, class _Tp, class _Compare, class _Allocator> 2271inline _LIBCPP_INLINE_VISIBILITY 2272void 2273swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2274 multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2275 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2276{ 2277 __x.swap(__y); 2278} 2279 2280#if _LIBCPP_STD_VER > 17 2281template <class _Key, class _Tp, class _Compare, class _Allocator, 2282 class _Predicate> 2283inline _LIBCPP_INLINE_VISIBILITY 2284 typename multimap<_Key, _Tp, _Compare, _Allocator>::size_type 2285 erase_if(multimap<_Key, _Tp, _Compare, _Allocator>& __c, 2286 _Predicate __pred) { 2287 return _VSTD::__libcpp_erase_if_container(__c, __pred); 2288} 2289#endif 2290 2291_LIBCPP_END_NAMESPACE_STD 2292 2293#endif // _LIBCPP_MAP 2294