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