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