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