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