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