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