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> 578#include <__config> 579#include <__functional/binary_function.h> 580#include <__functional/is_transparent.h> 581#include <__functional/operations.h> 582#include <__iterator/erase_if_container.h> 583#include <__iterator/iterator_traits.h> 584#include <__iterator/ranges_iterator_traits.h> 585#include <__iterator/reverse_iterator.h> 586#include <__memory/addressof.h> 587#include <__memory/allocator.h> 588#include <__memory_resource/polymorphic_allocator.h> 589#include <__node_handle> 590#include <__ranges/concepts.h> 591#include <__ranges/container_compatible_range.h> 592#include <__ranges/from_range.h> 593#include <__tree> 594#include <__type_traits/is_allocator.h> 595#include <__utility/forward.h> 596#include <__utility/piecewise_construct.h> 597#include <__utility/swap.h> 598#include <stdexcept> 599#include <tuple> 600#include <version> 601 602// standard-mandated includes 603 604// [iterator.range] 605#include <__iterator/access.h> 606#include <__iterator/data.h> 607#include <__iterator/empty.h> 608#include <__iterator/reverse_access.h> 609#include <__iterator/size.h> 610 611// [associative.map.syn] 612#include <compare> 613#include <initializer_list> 614 615#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 616# pragma GCC system_header 617#endif 618 619_LIBCPP_PUSH_MACROS 620#include <__undef_macros> 621 622_LIBCPP_BEGIN_NAMESPACE_STD 623 624template <class _Key, 625 class _CP, 626 class _Compare, 627 bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value> 628class __map_value_compare : private _Compare { 629public: 630 _LIBCPP_HIDE_FROM_ABI __map_value_compare() _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value) 631 : _Compare() {} 632 _LIBCPP_HIDE_FROM_ABI __map_value_compare(_Compare __c) _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value) 633 : _Compare(__c) {} 634 _LIBCPP_HIDE_FROM_ABI const _Compare& key_comp() const _NOEXCEPT { return *this; } 635 _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _CP& __y) const { 636 return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y.__get_value().first); 637 } 638 _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _Key& __y) const { 639 return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y); 640 } 641 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _CP& __y) const { 642 return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first); 643 } 644 _LIBCPP_HIDE_FROM_ABI void swap(__map_value_compare& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Compare>) { 645 using std::swap; 646 swap(static_cast<_Compare&>(*this), static_cast<_Compare&>(__y)); 647 } 648 649#if _LIBCPP_STD_VER >= 14 650 template <typename _K2> 651 _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _CP& __y) const { 652 return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first); 653 } 654 655 template <typename _K2> 656 _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _K2& __y) const { 657 return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y); 658 } 659#endif 660}; 661 662template <class _Key, class _CP, class _Compare> 663class __map_value_compare<_Key, _CP, _Compare, false> { 664 _Compare __comp_; 665 666public: 667 _LIBCPP_HIDE_FROM_ABI __map_value_compare() _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value) 668 : __comp_() {} 669 _LIBCPP_HIDE_FROM_ABI __map_value_compare(_Compare __c) _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value) 670 : __comp_(__c) {} 671 _LIBCPP_HIDE_FROM_ABI const _Compare& key_comp() const _NOEXCEPT { return __comp_; } 672 673 _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _CP& __y) const { 674 return __comp_(__x.__get_value().first, __y.__get_value().first); 675 } 676 _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _Key& __y) const { 677 return __comp_(__x.__get_value().first, __y); 678 } 679 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _CP& __y) const { 680 return __comp_(__x, __y.__get_value().first); 681 } 682 void swap(__map_value_compare& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Compare>) { 683 using std::swap; 684 swap(__comp_, __y.__comp_); 685 } 686 687#if _LIBCPP_STD_VER >= 14 688 template <typename _K2> 689 _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _CP& __y) const { 690 return __comp_(__x, __y.__get_value().first); 691 } 692 693 template <typename _K2> 694 _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _K2& __y) const { 695 return __comp_(__x.__get_value().first, __y); 696 } 697#endif 698}; 699 700template <class _Key, class _CP, class _Compare, bool __b> 701inline _LIBCPP_HIDE_FROM_ABI void 702swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x, __map_value_compare<_Key, _CP, _Compare, __b>& __y) 703 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 704 __x.swap(__y); 705} 706 707template <class _Allocator> 708class __map_node_destructor { 709 typedef _Allocator allocator_type; 710 typedef allocator_traits<allocator_type> __alloc_traits; 711 712public: 713 typedef typename __alloc_traits::pointer pointer; 714 715private: 716 allocator_type& __na_; 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 __map_node_destructor& operator=(const __map_node_destructor&) = delete; 737 738 _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT { 739 if (__second_constructed) 740 __alloc_traits::destroy(__na_, std::addressof(__p->__value_.__get_value().second)); 741 if (__first_constructed) 742 __alloc_traits::destroy(__na_, std::addressof(__p->__value_.__get_value().first)); 743 if (__p) 744 __alloc_traits::deallocate(__na_, __p, 1); 745 } 746}; 747 748template <class _Key, class _Tp, class _Compare, class _Allocator> 749class map; 750template <class _Key, class _Tp, class _Compare, class _Allocator> 751class multimap; 752template <class _TreeIterator> 753class __map_const_iterator; 754 755#ifndef _LIBCPP_CXX03_LANG 756 757template <class _Key, class _Tp> 758struct _LIBCPP_STANDALONE_DEBUG __value_type { 759 typedef _Key key_type; 760 typedef _Tp mapped_type; 761 typedef pair<const key_type, mapped_type> value_type; 762 typedef pair<key_type&, mapped_type&> __nc_ref_pair_type; 763 typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type; 764 765private: 766 value_type __cc_; 767 768public: 769 _LIBCPP_HIDE_FROM_ABI value_type& __get_value() { 770# if _LIBCPP_STD_VER >= 17 771 return *std::launder(std::addressof(__cc_)); 772# else 773 return __cc_; 774# endif 775 } 776 777 _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const { 778# if _LIBCPP_STD_VER >= 17 779 return *std::launder(std::addressof(__cc_)); 780# else 781 return __cc_; 782# endif 783 } 784 785 _LIBCPP_HIDE_FROM_ABI __nc_ref_pair_type __ref() { 786 value_type& __v = __get_value(); 787 return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second); 788 } 789 790 _LIBCPP_HIDE_FROM_ABI __nc_rref_pair_type __move() { 791 value_type& __v = __get_value(); 792 return __nc_rref_pair_type(std::move(const_cast<key_type&>(__v.first)), std::move(__v.second)); 793 } 794 795 _LIBCPP_HIDE_FROM_ABI __value_type& operator=(const __value_type& __v) { 796 __ref() = __v.__get_value(); 797 return *this; 798 } 799 800 _LIBCPP_HIDE_FROM_ABI __value_type& operator=(__value_type&& __v) { 801 __ref() = __v.__move(); 802 return *this; 803 } 804 805 template <class _ValueTp, __enable_if_t<__is_same_uncvref<_ValueTp, value_type>::value, int> = 0> 806 _LIBCPP_HIDE_FROM_ABI __value_type& operator=(_ValueTp&& __v) { 807 __ref() = std::forward<_ValueTp>(__v); 808 return *this; 809 } 810 811 __value_type() = delete; 812 ~__value_type() = delete; 813 __value_type(const __value_type&) = delete; 814 __value_type(__value_type&&) = delete; 815}; 816 817#else 818 819template <class _Key, class _Tp> 820struct __value_type { 821 typedef _Key key_type; 822 typedef _Tp mapped_type; 823 typedef pair<const key_type, mapped_type> value_type; 824 825private: 826 value_type __cc_; 827 828public: 829 _LIBCPP_HIDE_FROM_ABI value_type& __get_value() { return __cc_; } 830 _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const { return __cc_; } 831 832 __value_type() = delete; 833 __value_type(__value_type const&) = delete; 834 __value_type& operator=(__value_type const&) = delete; 835 ~__value_type() = delete; 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(__check_valid_allocator<allocator_type>::value, ""); 1001 1002 __base __tree_; 1003 1004public: 1005 typedef typename __alloc_traits::pointer pointer; 1006 typedef typename __alloc_traits::const_pointer const_pointer; 1007 typedef typename __alloc_traits::size_type size_type; 1008 typedef typename __alloc_traits::difference_type difference_type; 1009 typedef __map_iterator<typename __base::iterator> iterator; 1010 typedef __map_const_iterator<typename __base::const_iterator> const_iterator; 1011 typedef std::reverse_iterator<iterator> reverse_iterator; 1012 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 1013 1014#if _LIBCPP_STD_VER >= 17 1015 typedef __map_node_handle<typename __base::__node, allocator_type> node_type; 1016 typedef __insert_return_type<iterator, node_type> insert_return_type; 1017#endif 1018 1019 template <class _Key2, class _Value2, class _Comp2, class _Alloc2> 1020 friend class _LIBCPP_TEMPLATE_VIS map; 1021 template <class _Key2, class _Value2, class _Comp2, class _Alloc2> 1022 friend class _LIBCPP_TEMPLATE_VIS multimap; 1023 1024 _LIBCPP_HIDE_FROM_ABI map() _NOEXCEPT_( 1025 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&& 1026 is_nothrow_copy_constructible<key_compare>::value) 1027 : __tree_(__vc(key_compare())) {} 1028 1029 _LIBCPP_HIDE_FROM_ABI explicit map(const key_compare& __comp) _NOEXCEPT_( 1030 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value) 1031 : __tree_(__vc(__comp)) {} 1032 1033 _LIBCPP_HIDE_FROM_ABI explicit map(const key_compare& __comp, const allocator_type& __a) 1034 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {} 1035 1036 template <class _InputIterator> 1037 _LIBCPP_HIDE_FROM_ABI map(_InputIterator __f, _InputIterator __l, const key_compare& __comp = key_compare()) 1038 : __tree_(__vc(__comp)) { 1039 insert(__f, __l); 1040 } 1041 1042 template <class _InputIterator> 1043 _LIBCPP_HIDE_FROM_ABI 1044 map(_InputIterator __f, _InputIterator __l, const key_compare& __comp, const allocator_type& __a) 1045 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) { 1046 insert(__f, __l); 1047 } 1048 1049#if _LIBCPP_STD_VER >= 23 1050 template <_ContainerCompatibleRange<value_type> _Range> 1051 _LIBCPP_HIDE_FROM_ABI 1052 map(from_range_t, 1053 _Range&& __range, 1054 const key_compare& __comp = key_compare(), 1055 const allocator_type& __a = allocator_type()) 1056 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) { 1057 insert_range(std::forward<_Range>(__range)); 1058 } 1059#endif 1060 1061#if _LIBCPP_STD_VER >= 14 1062 template <class _InputIterator> 1063 _LIBCPP_HIDE_FROM_ABI map(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 1064 : map(__f, __l, key_compare(), __a) {} 1065#endif 1066 1067#if _LIBCPP_STD_VER >= 23 1068 template <_ContainerCompatibleRange<value_type> _Range> 1069 _LIBCPP_HIDE_FROM_ABI map(from_range_t, _Range&& __range, const allocator_type& __a) 1070 : map(from_range, std::forward<_Range>(__range), key_compare(), __a) {} 1071#endif 1072 1073 _LIBCPP_HIDE_FROM_ABI map(const map& __m) : __tree_(__m.__tree_) { insert(__m.begin(), __m.end()); } 1074 1075 _LIBCPP_HIDE_FROM_ABI map& operator=(const map& __m) { 1076#ifndef _LIBCPP_CXX03_LANG 1077 __tree_ = __m.__tree_; 1078#else 1079 if (this != std::addressof(__m)) { 1080 __tree_.clear(); 1081 __tree_.value_comp() = __m.__tree_.value_comp(); 1082 __tree_.__copy_assign_alloc(__m.__tree_); 1083 insert(__m.begin(), __m.end()); 1084 } 1085#endif 1086 return *this; 1087 } 1088 1089#ifndef _LIBCPP_CXX03_LANG 1090 1091 _LIBCPP_HIDE_FROM_ABI map(map&& __m) noexcept(is_nothrow_move_constructible<__base>::value) 1092 : __tree_(std::move(__m.__tree_)) {} 1093 1094 _LIBCPP_HIDE_FROM_ABI map(map&& __m, const allocator_type& __a); 1095 1096 _LIBCPP_HIDE_FROM_ABI map& operator=(map&& __m) noexcept(is_nothrow_move_assignable<__base>::value) { 1097 __tree_ = std::move(__m.__tree_); 1098 return *this; 1099 } 1100 1101 _LIBCPP_HIDE_FROM_ABI map(initializer_list<value_type> __il, const key_compare& __comp = key_compare()) 1102 : __tree_(__vc(__comp)) { 1103 insert(__il.begin(), __il.end()); 1104 } 1105 1106 _LIBCPP_HIDE_FROM_ABI map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a) 1107 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) { 1108 insert(__il.begin(), __il.end()); 1109 } 1110 1111# if _LIBCPP_STD_VER >= 14 1112 _LIBCPP_HIDE_FROM_ABI map(initializer_list<value_type> __il, const allocator_type& __a) 1113 : map(__il, key_compare(), __a) {} 1114# endif 1115 1116 _LIBCPP_HIDE_FROM_ABI map& operator=(initializer_list<value_type> __il) { 1117 __tree_.__assign_unique(__il.begin(), __il.end()); 1118 return *this; 1119 } 1120 1121#endif // _LIBCPP_CXX03_LANG 1122 1123 _LIBCPP_HIDE_FROM_ABI explicit map(const allocator_type& __a) : __tree_(typename __base::allocator_type(__a)) {} 1124 1125 _LIBCPP_HIDE_FROM_ABI map(const map& __m, const allocator_type& __a) 1126 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) { 1127 insert(__m.begin(), __m.end()); 1128 } 1129 1130 _LIBCPP_HIDE_FROM_ABI ~map() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); } 1131 1132 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); } 1133 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); } 1134 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); } 1135 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); } 1136 1137 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); } 1138 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); } 1139 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); } 1140 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); } 1141 1142 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); } 1143 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); } 1144 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); } 1145 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); } 1146 1147 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; } 1148 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); } 1149 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); } 1150 1151 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k); 1152#ifndef _LIBCPP_CXX03_LANG 1153 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](key_type&& __k); 1154#endif 1155 1156 _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __k); 1157 _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __k) const; 1158 1159 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(__tree_.__alloc()); } 1160 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp().key_comp(); } 1161 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return value_compare(__tree_.value_comp().key_comp()); } 1162 1163#ifndef _LIBCPP_CXX03_LANG 1164 template <class... _Args> 1165 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) { 1166 return __tree_.__emplace_unique(std::forward<_Args>(__args)...); 1167 } 1168 1169 template <class... _Args> 1170 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) { 1171 return __tree_.__emplace_hint_unique(__p.__i_, std::forward<_Args>(__args)...); 1172 } 1173 1174 template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0> 1175 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(_Pp&& __p) { 1176 return __tree_.__insert_unique(std::forward<_Pp>(__p)); 1177 } 1178 1179 template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0> 1180 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __pos, _Pp&& __p) { 1181 return __tree_.__insert_unique(__pos.__i_, std::forward<_Pp>(__p)); 1182 } 1183 1184#endif // _LIBCPP_CXX03_LANG 1185 1186 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__insert_unique(__v); } 1187 1188 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) { 1189 return __tree_.__insert_unique(__p.__i_, __v); 1190 } 1191 1192#ifndef _LIBCPP_CXX03_LANG 1193 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __v) { 1194 return __tree_.__insert_unique(std::move(__v)); 1195 } 1196 1197 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) { 1198 return __tree_.__insert_unique(__p.__i_, std::move(__v)); 1199 } 1200 1201 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); } 1202#endif 1203 1204 template <class _InputIterator> 1205 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) { 1206 for (const_iterator __e = cend(); __f != __l; ++__f) 1207 insert(__e.__i_, *__f); 1208 } 1209 1210#if _LIBCPP_STD_VER >= 23 1211 template <_ContainerCompatibleRange<value_type> _Range> 1212 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) { 1213 const_iterator __end = cend(); 1214 for (auto&& __element : __range) { 1215 insert(__end.__i_, std::forward<decltype(__element)>(__element)); 1216 } 1217 } 1218#endif 1219 1220#if _LIBCPP_STD_VER >= 17 1221 1222 template <class... _Args> 1223 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) { 1224 return __tree_.__emplace_unique_key_args( 1225 __k, 1226 std::piecewise_construct, 1227 std::forward_as_tuple(__k), 1228 std::forward_as_tuple(std::forward<_Args>(__args)...)); 1229 } 1230 1231 template <class... _Args> 1232 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) { 1233 return __tree_.__emplace_unique_key_args( 1234 __k, 1235 std::piecewise_construct, 1236 std::forward_as_tuple(std::move(__k)), 1237 std::forward_as_tuple(std::forward<_Args>(__args)...)); 1238 } 1239 1240 template <class... _Args> 1241 _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args) { 1242 return __tree_ 1243 .__emplace_hint_unique_key_args( 1244 __h.__i_, 1245 __k, 1246 std::piecewise_construct, 1247 std::forward_as_tuple(__k), 1248 std::forward_as_tuple(std::forward<_Args>(__args)...)) 1249 .first; 1250 } 1251 1252 template <class... _Args> 1253 _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) { 1254 return __tree_ 1255 .__emplace_hint_unique_key_args( 1256 __h.__i_, 1257 __k, 1258 std::piecewise_construct, 1259 std::forward_as_tuple(std::move(__k)), 1260 std::forward_as_tuple(std::forward<_Args>(__args)...)) 1261 .first; 1262 } 1263 1264 template <class _Vp> 1265 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) { 1266 iterator __p = lower_bound(__k); 1267 if (__p != end() && !key_comp()(__k, __p->first)) { 1268 __p->second = std::forward<_Vp>(__v); 1269 return std::make_pair(__p, false); 1270 } 1271 return std::make_pair(emplace_hint(__p, __k, std::forward<_Vp>(__v)), true); 1272 } 1273 1274 template <class _Vp> 1275 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) { 1276 iterator __p = lower_bound(__k); 1277 if (__p != end() && !key_comp()(__k, __p->first)) { 1278 __p->second = std::forward<_Vp>(__v); 1279 return std::make_pair(__p, false); 1280 } 1281 return std::make_pair(emplace_hint(__p, std::move(__k), std::forward<_Vp>(__v)), true); 1282 } 1283 1284 template <class _Vp> 1285 _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v) { 1286 auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, __k, std::forward<_Vp>(__v)); 1287 1288 if (!__inserted) 1289 __r->__get_value().second = std::forward<_Vp>(__v); 1290 1291 return __r; 1292 } 1293 1294 template <class _Vp> 1295 _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v) { 1296 auto [__r, __inserted] = 1297 __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, std::move(__k), std::forward<_Vp>(__v)); 1298 1299 if (!__inserted) 1300 __r->__get_value().second = std::forward<_Vp>(__v); 1301 1302 return __r; 1303 } 1304 1305#endif // _LIBCPP_STD_VER >= 17 1306 1307 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p.__i_); } 1308 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __tree_.erase(__p.__i_); } 1309 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_unique(__k); } 1310 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) { 1311 return __tree_.erase(__f.__i_, __l.__i_); 1312 } 1313 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); } 1314 1315#if _LIBCPP_STD_VER >= 17 1316 _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) { 1317 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 1318 "node_type with incompatible allocator passed to map::insert()"); 1319 return __tree_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh)); 1320 } 1321 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) { 1322 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 1323 "node_type with incompatible allocator passed to map::insert()"); 1324 return __tree_.template __node_handle_insert_unique<node_type>(__hint.__i_, std::move(__nh)); 1325 } 1326 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) { 1327 return __tree_.template __node_handle_extract<node_type>(__key); 1328 } 1329 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) { 1330 return __tree_.template __node_handle_extract<node_type>(__it.__i_); 1331 } 1332 template <class _Compare2> 1333 _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source) { 1334 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1335 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 1336 __tree_.__node_handle_merge_unique(__source.__tree_); 1337 } 1338 template <class _Compare2> 1339 _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source) { 1340 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1341 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 1342 __tree_.__node_handle_merge_unique(__source.__tree_); 1343 } 1344 template <class _Compare2> 1345 _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source) { 1346 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1347 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 1348 __tree_.__node_handle_merge_unique(__source.__tree_); 1349 } 1350 template <class _Compare2> 1351 _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source) { 1352 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1353 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 1354 __tree_.__node_handle_merge_unique(__source.__tree_); 1355 } 1356#endif 1357 1358 _LIBCPP_HIDE_FROM_ABI void swap(map& __m) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) { __tree_.swap(__m.__tree_); } 1359 1360 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); } 1361 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); } 1362#if _LIBCPP_STD_VER >= 14 1363 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0> 1364 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) { 1365 return __tree_.find(__k); 1366 } 1367 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0> 1368 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const { 1369 return __tree_.find(__k); 1370 } 1371#endif 1372 1373 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_unique(__k); } 1374#if _LIBCPP_STD_VER >= 14 1375 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0> 1376 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const { 1377 return __tree_.__count_multi(__k); 1378 } 1379#endif 1380 1381#if _LIBCPP_STD_VER >= 20 1382 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); } 1383 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0> 1384 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const { 1385 return find(__k) != end(); 1386 } 1387#endif // _LIBCPP_STD_VER >= 20 1388 1389 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); } 1390 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); } 1391#if _LIBCPP_STD_VER >= 14 1392 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0> 1393 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) { 1394 return __tree_.lower_bound(__k); 1395 } 1396 1397 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0> 1398 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const { 1399 return __tree_.lower_bound(__k); 1400 } 1401#endif 1402 1403 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); } 1404 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); } 1405#if _LIBCPP_STD_VER >= 14 1406 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0> 1407 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) { 1408 return __tree_.upper_bound(__k); 1409 } 1410 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0> 1411 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const { 1412 return __tree_.upper_bound(__k); 1413 } 1414#endif 1415 1416 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { 1417 return __tree_.__equal_range_unique(__k); 1418 } 1419 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 1420 return __tree_.__equal_range_unique(__k); 1421 } 1422#if _LIBCPP_STD_VER >= 14 1423 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0> 1424 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) { 1425 return __tree_.__equal_range_multi(__k); 1426 } 1427 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0> 1428 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const { 1429 return __tree_.__equal_range_multi(__k); 1430 } 1431#endif 1432 1433private: 1434 typedef typename __base::__node __node; 1435 typedef typename __base::__node_allocator __node_allocator; 1436 typedef typename __base::__node_pointer __node_pointer; 1437 typedef typename __base::__node_base_pointer __node_base_pointer; 1438 typedef typename __base::__parent_pointer __parent_pointer; 1439 1440 typedef __map_node_destructor<__node_allocator> _Dp; 1441 typedef unique_ptr<__node, _Dp> __node_holder; 1442 1443#ifdef _LIBCPP_CXX03_LANG 1444 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_with_key(const key_type& __k); 1445#endif 1446}; 1447 1448#if _LIBCPP_STD_VER >= 17 1449template <class _InputIterator, 1450 class _Compare = less<__iter_key_type<_InputIterator>>, 1451 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, 1452 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>, 1453 class = enable_if_t<!__is_allocator<_Compare>::value, void>, 1454 class = enable_if_t<__is_allocator<_Allocator>::value, void>> 1455map(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) 1456 -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>; 1457 1458# if _LIBCPP_STD_VER >= 23 1459template <ranges::input_range _Range, 1460 class _Compare = less<__range_key_type<_Range>>, 1461 class _Allocator = allocator<__range_to_alloc_type<_Range>>, 1462 class = enable_if_t<!__is_allocator<_Compare>::value, void>, 1463 class = enable_if_t<__is_allocator<_Allocator>::value, void>> 1464map(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator()) 1465 -> map<__range_key_type<_Range>, __range_mapped_type<_Range>, _Compare, _Allocator>; 1466# endif 1467 1468template <class _Key, 1469 class _Tp, 1470 class _Compare = less<remove_const_t<_Key>>, 1471 class _Allocator = allocator<pair<const _Key, _Tp>>, 1472 class = enable_if_t<!__is_allocator<_Compare>::value, void>, 1473 class = enable_if_t<__is_allocator<_Allocator>::value, void>> 1474map(initializer_list<pair<_Key, _Tp>>, 1475 _Compare = _Compare(), 1476 _Allocator = _Allocator()) -> map<remove_const_t<_Key>, _Tp, _Compare, _Allocator>; 1477 1478template <class _InputIterator, 1479 class _Allocator, 1480 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>, 1481 class = enable_if_t<__is_allocator<_Allocator>::value, void>> 1482map(_InputIterator, _InputIterator, _Allocator) 1483 -> map<__iter_key_type<_InputIterator>, 1484 __iter_mapped_type<_InputIterator>, 1485 less<__iter_key_type<_InputIterator>>, 1486 _Allocator>; 1487 1488# if _LIBCPP_STD_VER >= 23 1489template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>> 1490map(from_range_t, _Range&&, _Allocator) 1491 -> map<__range_key_type<_Range>, __range_mapped_type<_Range>, less<__range_key_type<_Range>>, _Allocator>; 1492# endif 1493 1494template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>> 1495map(initializer_list<pair<_Key, _Tp>>, 1496 _Allocator) -> map<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>; 1497#endif 1498 1499#ifndef _LIBCPP_CXX03_LANG 1500template <class _Key, class _Tp, class _Compare, class _Allocator> 1501map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a) 1502 : __tree_(std::move(__m.__tree_), typename __base::allocator_type(__a)) { 1503 if (__a != __m.get_allocator()) { 1504 const_iterator __e = cend(); 1505 while (!__m.empty()) 1506 __tree_.__insert_unique(__e.__i_, __m.__tree_.remove(__m.begin().__i_)->__value_.__move()); 1507 } 1508} 1509 1510template <class _Key, class _Tp, class _Compare, class _Allocator> 1511_Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) { 1512 return __tree_ 1513 .__emplace_unique_key_args(__k, std::piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple()) 1514 .first->__get_value() 1515 .second; 1516} 1517 1518template <class _Key, class _Tp, class _Compare, class _Allocator> 1519_Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k) { 1520 // TODO investigate this clang-tidy warning. 1521 // NOLINTBEGIN(bugprone-use-after-move) 1522 return __tree_ 1523 .__emplace_unique_key_args( 1524 __k, std::piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple()) 1525 .first->__get_value() 1526 .second; 1527 // NOLINTEND(bugprone-use-after-move) 1528} 1529 1530#else // _LIBCPP_CXX03_LANG 1531 1532template <class _Key, class _Tp, class _Compare, class _Allocator> 1533typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder 1534map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k) { 1535 __node_allocator& __na = __tree_.__node_alloc(); 1536 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1537 __node_traits::construct(__na, std::addressof(__h->__value_.__get_value().first), __k); 1538 __h.get_deleter().__first_constructed = true; 1539 __node_traits::construct(__na, std::addressof(__h->__value_.__get_value().second)); 1540 __h.get_deleter().__second_constructed = true; 1541 return __h; 1542} 1543 1544template <class _Key, class _Tp, class _Compare, class _Allocator> 1545_Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) { 1546 __parent_pointer __parent; 1547 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k); 1548 __node_pointer __r = static_cast<__node_pointer>(__child); 1549 if (__child == nullptr) { 1550 __node_holder __h = __construct_node_with_key(__k); 1551 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1552 __r = __h.release(); 1553 } 1554 return __r->__value_.__get_value().second; 1555} 1556 1557#endif // _LIBCPP_CXX03_LANG 1558 1559template <class _Key, class _Tp, class _Compare, class _Allocator> 1560_Tp& map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) { 1561 __parent_pointer __parent; 1562 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k); 1563 if (__child == nullptr) 1564 __throw_out_of_range("map::at: key not found"); 1565 return static_cast<__node_pointer>(__child)->__value_.__get_value().second; 1566} 1567 1568template <class _Key, class _Tp, class _Compare, class _Allocator> 1569const _Tp& map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const { 1570 __parent_pointer __parent; 1571 __node_base_pointer __child = __tree_.__find_equal(__parent, __k); 1572 if (__child == nullptr) 1573 __throw_out_of_range("map::at: key not found"); 1574 return static_cast<__node_pointer>(__child)->__value_.__get_value().second; 1575} 1576 1577template <class _Key, class _Tp, class _Compare, class _Allocator> 1578inline _LIBCPP_HIDE_FROM_ABI bool 1579operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) { 1580 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin()); 1581} 1582 1583#if _LIBCPP_STD_VER <= 17 1584 1585template <class _Key, class _Tp, class _Compare, class _Allocator> 1586inline _LIBCPP_HIDE_FROM_ABI bool 1587operator<(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) { 1588 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 1589} 1590 1591template <class _Key, class _Tp, class _Compare, class _Allocator> 1592inline _LIBCPP_HIDE_FROM_ABI bool 1593operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) { 1594 return !(__x == __y); 1595} 1596 1597template <class _Key, class _Tp, class _Compare, class _Allocator> 1598inline _LIBCPP_HIDE_FROM_ABI bool 1599operator>(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) { 1600 return __y < __x; 1601} 1602 1603template <class _Key, class _Tp, class _Compare, class _Allocator> 1604inline _LIBCPP_HIDE_FROM_ABI bool 1605operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) { 1606 return !(__x < __y); 1607} 1608 1609template <class _Key, class _Tp, class _Compare, class _Allocator> 1610inline _LIBCPP_HIDE_FROM_ABI bool 1611operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) { 1612 return !(__y < __x); 1613} 1614 1615#else // #if _LIBCPP_STD_VER <= 17 1616 1617template <class _Key, class _Tp, class _Compare, class _Allocator> 1618_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<pair<const _Key, _Tp>> 1619operator<=>(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) { 1620 return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way); 1621} 1622 1623#endif // #if _LIBCPP_STD_VER <= 17 1624 1625template <class _Key, class _Tp, class _Compare, class _Allocator> 1626inline _LIBCPP_HIDE_FROM_ABI void 1627swap(map<_Key, _Tp, _Compare, _Allocator>& __x, map<_Key, _Tp, _Compare, _Allocator>& __y) 1628 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 1629 __x.swap(__y); 1630} 1631 1632#if _LIBCPP_STD_VER >= 20 1633template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate> 1634inline _LIBCPP_HIDE_FROM_ABI typename map<_Key, _Tp, _Compare, _Allocator>::size_type 1635erase_if(map<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) { 1636 return std::__libcpp_erase_if_container(__c, __pred); 1637} 1638#endif 1639 1640template <class _Key, class _Tp, class _Compare = less<_Key>, class _Allocator = allocator<pair<const _Key, _Tp> > > 1641class _LIBCPP_TEMPLATE_VIS multimap { 1642public: 1643 // types: 1644 typedef _Key key_type; 1645 typedef _Tp mapped_type; 1646 typedef pair<const key_type, mapped_type> value_type; 1647 typedef __type_identity_t<_Compare> key_compare; 1648 typedef __type_identity_t<_Allocator> allocator_type; 1649 typedef value_type& reference; 1650 typedef const value_type& const_reference; 1651 1652 static_assert(__check_valid_allocator<allocator_type>::value, ""); 1653 static_assert(is_same<typename allocator_type::value_type, value_type>::value, 1654 "Allocator::value_type must be same type as value_type"); 1655 1656 class _LIBCPP_TEMPLATE_VIS value_compare : public __binary_function<value_type, value_type, bool> { 1657 friend class multimap; 1658 1659 protected: 1660 key_compare comp; 1661 1662 _LIBCPP_HIDE_FROM_ABI value_compare(key_compare __c) : comp(__c) {} 1663 1664 public: 1665 _LIBCPP_HIDE_FROM_ABI bool operator()(const value_type& __x, const value_type& __y) const { 1666 return comp(__x.first, __y.first); 1667 } 1668 }; 1669 1670private: 1671 typedef std::__value_type<key_type, mapped_type> __value_type; 1672 typedef __map_value_compare<key_type, __value_type, key_compare> __vc; 1673 typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type; 1674 typedef __tree<__value_type, __vc, __allocator_type> __base; 1675 typedef typename __base::__node_traits __node_traits; 1676 typedef allocator_traits<allocator_type> __alloc_traits; 1677 1678 __base __tree_; 1679 1680public: 1681 typedef typename __alloc_traits::pointer pointer; 1682 typedef typename __alloc_traits::const_pointer const_pointer; 1683 typedef typename __alloc_traits::size_type size_type; 1684 typedef typename __alloc_traits::difference_type difference_type; 1685 typedef __map_iterator<typename __base::iterator> iterator; 1686 typedef __map_const_iterator<typename __base::const_iterator> const_iterator; 1687 typedef std::reverse_iterator<iterator> reverse_iterator; 1688 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 1689 1690#if _LIBCPP_STD_VER >= 17 1691 typedef __map_node_handle<typename __base::__node, allocator_type> node_type; 1692#endif 1693 1694 template <class _Key2, class _Value2, class _Comp2, class _Alloc2> 1695 friend class _LIBCPP_TEMPLATE_VIS map; 1696 template <class _Key2, class _Value2, class _Comp2, class _Alloc2> 1697 friend class _LIBCPP_TEMPLATE_VIS multimap; 1698 1699 _LIBCPP_HIDE_FROM_ABI multimap() _NOEXCEPT_( 1700 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&& 1701 is_nothrow_copy_constructible<key_compare>::value) 1702 : __tree_(__vc(key_compare())) {} 1703 1704 _LIBCPP_HIDE_FROM_ABI explicit multimap(const key_compare& __comp) _NOEXCEPT_( 1705 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value) 1706 : __tree_(__vc(__comp)) {} 1707 1708 _LIBCPP_HIDE_FROM_ABI explicit multimap(const key_compare& __comp, const allocator_type& __a) 1709 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {} 1710 1711 template <class _InputIterator> 1712 _LIBCPP_HIDE_FROM_ABI multimap(_InputIterator __f, _InputIterator __l, const key_compare& __comp = key_compare()) 1713 : __tree_(__vc(__comp)) { 1714 insert(__f, __l); 1715 } 1716 1717 template <class _InputIterator> 1718 _LIBCPP_HIDE_FROM_ABI 1719 multimap(_InputIterator __f, _InputIterator __l, const key_compare& __comp, const allocator_type& __a) 1720 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) { 1721 insert(__f, __l); 1722 } 1723 1724#if _LIBCPP_STD_VER >= 23 1725 template <_ContainerCompatibleRange<value_type> _Range> 1726 _LIBCPP_HIDE_FROM_ABI 1727 multimap(from_range_t, 1728 _Range&& __range, 1729 const key_compare& __comp = key_compare(), 1730 const allocator_type& __a = allocator_type()) 1731 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) { 1732 insert_range(std::forward<_Range>(__range)); 1733 } 1734#endif 1735 1736#if _LIBCPP_STD_VER >= 14 1737 template <class _InputIterator> 1738 _LIBCPP_HIDE_FROM_ABI multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 1739 : multimap(__f, __l, key_compare(), __a) {} 1740#endif 1741 1742#if _LIBCPP_STD_VER >= 23 1743 template <_ContainerCompatibleRange<value_type> _Range> 1744 _LIBCPP_HIDE_FROM_ABI multimap(from_range_t, _Range&& __range, const allocator_type& __a) 1745 : multimap(from_range, std::forward<_Range>(__range), key_compare(), __a) {} 1746#endif 1747 1748 _LIBCPP_HIDE_FROM_ABI multimap(const multimap& __m) 1749 : __tree_(__m.__tree_.value_comp(), 1750 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc())) { 1751 insert(__m.begin(), __m.end()); 1752 } 1753 1754 _LIBCPP_HIDE_FROM_ABI multimap& operator=(const multimap& __m) { 1755#ifndef _LIBCPP_CXX03_LANG 1756 __tree_ = __m.__tree_; 1757#else 1758 if (this != std::addressof(__m)) { 1759 __tree_.clear(); 1760 __tree_.value_comp() = __m.__tree_.value_comp(); 1761 __tree_.__copy_assign_alloc(__m.__tree_); 1762 insert(__m.begin(), __m.end()); 1763 } 1764#endif 1765 return *this; 1766 } 1767 1768#ifndef _LIBCPP_CXX03_LANG 1769 1770 _LIBCPP_HIDE_FROM_ABI multimap(multimap&& __m) noexcept(is_nothrow_move_constructible<__base>::value) 1771 : __tree_(std::move(__m.__tree_)) {} 1772 1773 _LIBCPP_HIDE_FROM_ABI multimap(multimap&& __m, const allocator_type& __a); 1774 1775 _LIBCPP_HIDE_FROM_ABI multimap& operator=(multimap&& __m) noexcept(is_nothrow_move_assignable<__base>::value) { 1776 __tree_ = std::move(__m.__tree_); 1777 return *this; 1778 } 1779 1780 _LIBCPP_HIDE_FROM_ABI multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare()) 1781 : __tree_(__vc(__comp)) { 1782 insert(__il.begin(), __il.end()); 1783 } 1784 1785 _LIBCPP_HIDE_FROM_ABI 1786 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a) 1787 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) { 1788 insert(__il.begin(), __il.end()); 1789 } 1790 1791# if _LIBCPP_STD_VER >= 14 1792 _LIBCPP_HIDE_FROM_ABI multimap(initializer_list<value_type> __il, const allocator_type& __a) 1793 : multimap(__il, key_compare(), __a) {} 1794# endif 1795 1796 _LIBCPP_HIDE_FROM_ABI multimap& operator=(initializer_list<value_type> __il) { 1797 __tree_.__assign_multi(__il.begin(), __il.end()); 1798 return *this; 1799 } 1800 1801#endif // _LIBCPP_CXX03_LANG 1802 1803 _LIBCPP_HIDE_FROM_ABI explicit multimap(const allocator_type& __a) : __tree_(typename __base::allocator_type(__a)) {} 1804 1805 _LIBCPP_HIDE_FROM_ABI multimap(const multimap& __m, const allocator_type& __a) 1806 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) { 1807 insert(__m.begin(), __m.end()); 1808 } 1809 1810 _LIBCPP_HIDE_FROM_ABI ~multimap() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); } 1811 1812 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); } 1813 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); } 1814 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); } 1815 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); } 1816 1817 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); } 1818 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); } 1819 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); } 1820 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); } 1821 1822 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); } 1823 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); } 1824 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); } 1825 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); } 1826 1827 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; } 1828 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); } 1829 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); } 1830 1831 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(__tree_.__alloc()); } 1832 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp().key_comp(); } 1833 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return value_compare(__tree_.value_comp().key_comp()); } 1834 1835#ifndef _LIBCPP_CXX03_LANG 1836 1837 template <class... _Args> 1838 _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) { 1839 return __tree_.__emplace_multi(std::forward<_Args>(__args)...); 1840 } 1841 1842 template <class... _Args> 1843 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) { 1844 return __tree_.__emplace_hint_multi(__p.__i_, std::forward<_Args>(__args)...); 1845 } 1846 1847 template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0> 1848 _LIBCPP_HIDE_FROM_ABI iterator insert(_Pp&& __p) { 1849 return __tree_.__insert_multi(std::forward<_Pp>(__p)); 1850 } 1851 1852 template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0> 1853 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __pos, _Pp&& __p) { 1854 return __tree_.__insert_multi(__pos.__i_, std::forward<_Pp>(__p)); 1855 } 1856 1857 _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __v) { return __tree_.__insert_multi(std::move(__v)); } 1858 1859 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) { 1860 return __tree_.__insert_multi(__p.__i_, std::move(__v)); 1861 } 1862 1863 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); } 1864 1865#endif // _LIBCPP_CXX03_LANG 1866 1867 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __v) { return __tree_.__insert_multi(__v); } 1868 1869 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) { 1870 return __tree_.__insert_multi(__p.__i_, __v); 1871 } 1872 1873 template <class _InputIterator> 1874 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) { 1875 for (const_iterator __e = cend(); __f != __l; ++__f) 1876 __tree_.__insert_multi(__e.__i_, *__f); 1877 } 1878 1879#if _LIBCPP_STD_VER >= 23 1880 template <_ContainerCompatibleRange<value_type> _Range> 1881 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) { 1882 const_iterator __end = cend(); 1883 for (auto&& __element : __range) { 1884 __tree_.__insert_multi(__end.__i_, std::forward<decltype(__element)>(__element)); 1885 } 1886 } 1887#endif 1888 1889 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p.__i_); } 1890 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __tree_.erase(__p.__i_); } 1891 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_multi(__k); } 1892 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) { 1893 return __tree_.erase(__f.__i_, __l.__i_); 1894 } 1895 1896#if _LIBCPP_STD_VER >= 17 1897 _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) { 1898 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 1899 "node_type with incompatible allocator passed to multimap::insert()"); 1900 return __tree_.template __node_handle_insert_multi<node_type>(std::move(__nh)); 1901 } 1902 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) { 1903 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 1904 "node_type with incompatible allocator passed to multimap::insert()"); 1905 return __tree_.template __node_handle_insert_multi<node_type>(__hint.__i_, std::move(__nh)); 1906 } 1907 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) { 1908 return __tree_.template __node_handle_extract<node_type>(__key); 1909 } 1910 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) { 1911 return __tree_.template __node_handle_extract<node_type>(__it.__i_); 1912 } 1913 template <class _Compare2> 1914 _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source) { 1915 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1916 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 1917 return __tree_.__node_handle_merge_multi(__source.__tree_); 1918 } 1919 template <class _Compare2> 1920 _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source) { 1921 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1922 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 1923 return __tree_.__node_handle_merge_multi(__source.__tree_); 1924 } 1925 template <class _Compare2> 1926 _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source) { 1927 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1928 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 1929 return __tree_.__node_handle_merge_multi(__source.__tree_); 1930 } 1931 template <class _Compare2> 1932 _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source) { 1933 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1934 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 1935 return __tree_.__node_handle_merge_multi(__source.__tree_); 1936 } 1937#endif 1938 1939 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); } 1940 1941 _LIBCPP_HIDE_FROM_ABI void swap(multimap& __m) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) { 1942 __tree_.swap(__m.__tree_); 1943 } 1944 1945 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); } 1946 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); } 1947#if _LIBCPP_STD_VER >= 14 1948 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0> 1949 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) { 1950 return __tree_.find(__k); 1951 } 1952 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0> 1953 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const { 1954 return __tree_.find(__k); 1955 } 1956#endif 1957 1958 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_multi(__k); } 1959#if _LIBCPP_STD_VER >= 14 1960 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0> 1961 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const { 1962 return __tree_.__count_multi(__k); 1963 } 1964#endif 1965 1966#if _LIBCPP_STD_VER >= 20 1967 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); } 1968 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0> 1969 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const { 1970 return find(__k) != end(); 1971 } 1972#endif // _LIBCPP_STD_VER >= 20 1973 1974 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); } 1975 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); } 1976#if _LIBCPP_STD_VER >= 14 1977 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0> 1978 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) { 1979 return __tree_.lower_bound(__k); 1980 } 1981 1982 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0> 1983 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const { 1984 return __tree_.lower_bound(__k); 1985 } 1986#endif 1987 1988 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); } 1989 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); } 1990#if _LIBCPP_STD_VER >= 14 1991 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0> 1992 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) { 1993 return __tree_.upper_bound(__k); 1994 } 1995 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0> 1996 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const { 1997 return __tree_.upper_bound(__k); 1998 } 1999#endif 2000 2001 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { 2002 return __tree_.__equal_range_multi(__k); 2003 } 2004 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 2005 return __tree_.__equal_range_multi(__k); 2006 } 2007#if _LIBCPP_STD_VER >= 14 2008 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0> 2009 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) { 2010 return __tree_.__equal_range_multi(__k); 2011 } 2012 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0> 2013 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const { 2014 return __tree_.__equal_range_multi(__k); 2015 } 2016#endif 2017 2018private: 2019 typedef typename __base::__node __node; 2020 typedef typename __base::__node_allocator __node_allocator; 2021 typedef typename __base::__node_pointer __node_pointer; 2022 2023 typedef __map_node_destructor<__node_allocator> _Dp; 2024 typedef unique_ptr<__node, _Dp> __node_holder; 2025}; 2026 2027#if _LIBCPP_STD_VER >= 17 2028template <class _InputIterator, 2029 class _Compare = less<__iter_key_type<_InputIterator>>, 2030 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, 2031 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>, 2032 class = enable_if_t<!__is_allocator<_Compare>::value, void>, 2033 class = enable_if_t<__is_allocator<_Allocator>::value, void>> 2034multimap(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) 2035 -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>; 2036 2037# if _LIBCPP_STD_VER >= 23 2038template <ranges::input_range _Range, 2039 class _Compare = less<__range_key_type<_Range>>, 2040 class _Allocator = allocator<__range_to_alloc_type<_Range>>, 2041 class = enable_if_t<!__is_allocator<_Compare>::value, void>, 2042 class = enable_if_t<__is_allocator<_Allocator>::value, void>> 2043multimap(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator()) 2044 -> multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, _Compare, _Allocator>; 2045# endif 2046 2047template <class _Key, 2048 class _Tp, 2049 class _Compare = less<remove_const_t<_Key>>, 2050 class _Allocator = allocator<pair<const _Key, _Tp>>, 2051 class = enable_if_t<!__is_allocator<_Compare>::value, void>, 2052 class = enable_if_t<__is_allocator<_Allocator>::value, void>> 2053multimap(initializer_list<pair<_Key, _Tp>>, 2054 _Compare = _Compare(), 2055 _Allocator = _Allocator()) -> multimap<remove_const_t<_Key>, _Tp, _Compare, _Allocator>; 2056 2057template <class _InputIterator, 2058 class _Allocator, 2059 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>, 2060 class = enable_if_t<__is_allocator<_Allocator>::value, void>> 2061multimap(_InputIterator, _InputIterator, _Allocator) 2062 -> multimap<__iter_key_type<_InputIterator>, 2063 __iter_mapped_type<_InputIterator>, 2064 less<__iter_key_type<_InputIterator>>, 2065 _Allocator>; 2066 2067# if _LIBCPP_STD_VER >= 23 2068template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>> 2069multimap(from_range_t, _Range&&, _Allocator) 2070 -> multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, less<__range_key_type<_Range>>, _Allocator>; 2071# endif 2072 2073template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>> 2074multimap(initializer_list<pair<_Key, _Tp>>, 2075 _Allocator) -> multimap<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>; 2076#endif 2077 2078#ifndef _LIBCPP_CXX03_LANG 2079template <class _Key, class _Tp, class _Compare, class _Allocator> 2080multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a) 2081 : __tree_(std::move(__m.__tree_), typename __base::allocator_type(__a)) { 2082 if (__a != __m.get_allocator()) { 2083 const_iterator __e = cend(); 2084 while (!__m.empty()) 2085 __tree_.__insert_multi(__e.__i_, std::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__move())); 2086 } 2087} 2088#endif 2089 2090template <class _Key, class _Tp, class _Compare, class _Allocator> 2091inline _LIBCPP_HIDE_FROM_ABI bool 2092operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) { 2093 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin()); 2094} 2095 2096#if _LIBCPP_STD_VER <= 17 2097 2098template <class _Key, class _Tp, class _Compare, class _Allocator> 2099inline _LIBCPP_HIDE_FROM_ABI bool 2100operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) { 2101 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 2102} 2103 2104template <class _Key, class _Tp, class _Compare, class _Allocator> 2105inline _LIBCPP_HIDE_FROM_ABI bool 2106operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) { 2107 return !(__x == __y); 2108} 2109 2110template <class _Key, class _Tp, class _Compare, class _Allocator> 2111inline _LIBCPP_HIDE_FROM_ABI bool 2112operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) { 2113 return __y < __x; 2114} 2115 2116template <class _Key, class _Tp, class _Compare, class _Allocator> 2117inline _LIBCPP_HIDE_FROM_ABI bool 2118operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) { 2119 return !(__x < __y); 2120} 2121 2122template <class _Key, class _Tp, class _Compare, class _Allocator> 2123inline _LIBCPP_HIDE_FROM_ABI bool 2124operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) { 2125 return !(__y < __x); 2126} 2127 2128#else // #if _LIBCPP_STD_VER <= 17 2129 2130template <class _Key, class _Tp, class _Compare, class _Allocator> 2131_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<pair<const _Key, _Tp>> 2132operator<=>(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2133 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) { 2134 return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), __synth_three_way); 2135} 2136 2137#endif // #if _LIBCPP_STD_VER <= 17 2138 2139template <class _Key, class _Tp, class _Compare, class _Allocator> 2140inline _LIBCPP_HIDE_FROM_ABI void 2141swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x, multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2142 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 2143 __x.swap(__y); 2144} 2145 2146#if _LIBCPP_STD_VER >= 20 2147template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate> 2148inline _LIBCPP_HIDE_FROM_ABI typename multimap<_Key, _Tp, _Compare, _Allocator>::size_type 2149erase_if(multimap<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) { 2150 return std::__libcpp_erase_if_container(__c, __pred); 2151} 2152#endif 2153 2154_LIBCPP_END_NAMESPACE_STD 2155 2156#if _LIBCPP_STD_VER >= 17 2157_LIBCPP_BEGIN_NAMESPACE_STD 2158namespace pmr { 2159template <class _KeyT, class _ValueT, class _CompareT = std::less<_KeyT>> 2160using map _LIBCPP_AVAILABILITY_PMR = 2161 std::map<_KeyT, _ValueT, _CompareT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>; 2162 2163template <class _KeyT, class _ValueT, class _CompareT = std::less<_KeyT>> 2164using multimap _LIBCPP_AVAILABILITY_PMR = 2165 std::multimap<_KeyT, _ValueT, _CompareT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>; 2166} // namespace pmr 2167_LIBCPP_END_NAMESPACE_STD 2168#endif 2169 2170_LIBCPP_POP_MACROS 2171 2172#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 2173# include <concepts> 2174# include <cstdlib> 2175# include <functional> 2176# include <iterator> 2177# include <type_traits> 2178# include <utility> 2179#endif 2180 2181#endif // _LIBCPP_MAP 2182