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