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