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