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