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