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 class _LIBCPP_TYPE_VIS_ONLY value_compare 844 : public binary_function<value_type, value_type, bool> 845 { 846 friend class map; 847 protected: 848 key_compare comp; 849 850 _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {} 851 public: 852 _LIBCPP_INLINE_VISIBILITY 853 bool operator()(const value_type& __x, const value_type& __y) const 854 {return comp(__x.first, __y.first);} 855 }; 856 857private: 858 859 typedef _VSTD::__value_type<key_type, mapped_type> __value_type; 860 typedef __map_value_compare<key_type, __value_type, key_compare> __vc; 861 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, 862 __value_type>::type __allocator_type; 863 typedef __tree<__value_type, __vc, __allocator_type> __base; 864 typedef typename __base::__node_traits __node_traits; 865 typedef allocator_traits<allocator_type> __alloc_traits; 866 867 __base __tree_; 868 869public: 870 typedef typename __alloc_traits::pointer pointer; 871 typedef typename __alloc_traits::const_pointer const_pointer; 872 typedef typename __alloc_traits::size_type size_type; 873 typedef typename __alloc_traits::difference_type difference_type; 874 typedef __map_iterator<typename __base::iterator> iterator; 875 typedef __map_const_iterator<typename __base::const_iterator> const_iterator; 876 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 877 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 878 879 _LIBCPP_INLINE_VISIBILITY 880 map() 881 _NOEXCEPT_( 882 is_nothrow_default_constructible<allocator_type>::value && 883 is_nothrow_default_constructible<key_compare>::value && 884 is_nothrow_copy_constructible<key_compare>::value) 885 : __tree_(__vc(key_compare())) {} 886 887 _LIBCPP_INLINE_VISIBILITY 888 explicit map(const key_compare& __comp) 889 _NOEXCEPT_( 890 is_nothrow_default_constructible<allocator_type>::value && 891 is_nothrow_copy_constructible<key_compare>::value) 892 : __tree_(__vc(__comp)) {} 893 894 _LIBCPP_INLINE_VISIBILITY 895 explicit map(const key_compare& __comp, const allocator_type& __a) 896 : __tree_(__vc(__comp), __a) {} 897 898 template <class _InputIterator> 899 _LIBCPP_INLINE_VISIBILITY 900 map(_InputIterator __f, _InputIterator __l, 901 const key_compare& __comp = key_compare()) 902 : __tree_(__vc(__comp)) 903 { 904 insert(__f, __l); 905 } 906 907 template <class _InputIterator> 908 _LIBCPP_INLINE_VISIBILITY 909 map(_InputIterator __f, _InputIterator __l, 910 const key_compare& __comp, const allocator_type& __a) 911 : __tree_(__vc(__comp), __a) 912 { 913 insert(__f, __l); 914 } 915 916#if _LIBCPP_STD_VER > 11 917 template <class _InputIterator> 918 _LIBCPP_INLINE_VISIBILITY 919 map(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 920 : map(__f, __l, key_compare(), __a) {} 921#endif 922 923 _LIBCPP_INLINE_VISIBILITY 924 map(const map& __m) 925 : __tree_(__m.__tree_) 926 { 927 insert(__m.begin(), __m.end()); 928 } 929 930 _LIBCPP_INLINE_VISIBILITY 931 map& operator=(const map& __m) 932 { 933#if __cplusplus >= 201103L 934 __tree_ = __m.__tree_; 935#else 936 if (this != &__m) { 937 __tree_.clear(); 938 __tree_.value_comp() = __m.__tree_.value_comp(); 939 __tree_.__copy_assign_alloc(__m.__tree_); 940 insert(__m.begin(), __m.end()); 941 } 942#endif 943 return *this; 944 } 945 946#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 947 948 _LIBCPP_INLINE_VISIBILITY 949 map(map&& __m) 950 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 951 : __tree_(_VSTD::move(__m.__tree_)) 952 { 953 } 954 955 map(map&& __m, const allocator_type& __a); 956 957 _LIBCPP_INLINE_VISIBILITY 958 map& operator=(map&& __m) 959 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 960 { 961 __tree_ = _VSTD::move(__m.__tree_); 962 return *this; 963 } 964 965#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 966 967#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 968 969 _LIBCPP_INLINE_VISIBILITY 970 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare()) 971 : __tree_(__vc(__comp)) 972 { 973 insert(__il.begin(), __il.end()); 974 } 975 976 _LIBCPP_INLINE_VISIBILITY 977 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a) 978 : __tree_(__vc(__comp), __a) 979 { 980 insert(__il.begin(), __il.end()); 981 } 982 983#if _LIBCPP_STD_VER > 11 984 _LIBCPP_INLINE_VISIBILITY 985 map(initializer_list<value_type> __il, const allocator_type& __a) 986 : map(__il, key_compare(), __a) {} 987#endif 988 989 _LIBCPP_INLINE_VISIBILITY 990 map& operator=(initializer_list<value_type> __il) 991 { 992 __tree_.__assign_unique(__il.begin(), __il.end()); 993 return *this; 994 } 995 996#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 997 998 _LIBCPP_INLINE_VISIBILITY 999 explicit map(const allocator_type& __a) 1000 : __tree_(__a) 1001 { 1002 } 1003 1004 _LIBCPP_INLINE_VISIBILITY 1005 map(const map& __m, const allocator_type& __a) 1006 : __tree_(__m.__tree_.value_comp(), __a) 1007 { 1008 insert(__m.begin(), __m.end()); 1009 } 1010 1011 _LIBCPP_INLINE_VISIBILITY 1012 iterator begin() _NOEXCEPT {return __tree_.begin();} 1013 _LIBCPP_INLINE_VISIBILITY 1014 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 1015 _LIBCPP_INLINE_VISIBILITY 1016 iterator end() _NOEXCEPT {return __tree_.end();} 1017 _LIBCPP_INLINE_VISIBILITY 1018 const_iterator end() const _NOEXCEPT {return __tree_.end();} 1019 1020 _LIBCPP_INLINE_VISIBILITY 1021 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());} 1022 _LIBCPP_INLINE_VISIBILITY 1023 const_reverse_iterator rbegin() const _NOEXCEPT 1024 {return const_reverse_iterator(end());} 1025 _LIBCPP_INLINE_VISIBILITY 1026 reverse_iterator rend() _NOEXCEPT 1027 {return reverse_iterator(begin());} 1028 _LIBCPP_INLINE_VISIBILITY 1029 const_reverse_iterator rend() const _NOEXCEPT 1030 {return const_reverse_iterator(begin());} 1031 1032 _LIBCPP_INLINE_VISIBILITY 1033 const_iterator cbegin() const _NOEXCEPT {return begin();} 1034 _LIBCPP_INLINE_VISIBILITY 1035 const_iterator cend() const _NOEXCEPT {return end();} 1036 _LIBCPP_INLINE_VISIBILITY 1037 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 1038 _LIBCPP_INLINE_VISIBILITY 1039 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 1040 1041 _LIBCPP_INLINE_VISIBILITY 1042 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 1043 _LIBCPP_INLINE_VISIBILITY 1044 size_type size() const _NOEXCEPT {return __tree_.size();} 1045 _LIBCPP_INLINE_VISIBILITY 1046 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 1047 1048 mapped_type& operator[](const key_type& __k); 1049#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1050 mapped_type& operator[](key_type&& __k); 1051#endif 1052 1053 mapped_type& at(const key_type& __k); 1054 const mapped_type& at(const key_type& __k) const; 1055 1056 _LIBCPP_INLINE_VISIBILITY 1057 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 1058 _LIBCPP_INLINE_VISIBILITY 1059 key_compare key_comp() const {return __tree_.value_comp().key_comp();} 1060 _LIBCPP_INLINE_VISIBILITY 1061 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());} 1062 1063#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1064#ifndef _LIBCPP_HAS_NO_VARIADICS 1065 1066 template <class ..._Args> 1067 pair<iterator, bool> 1068 emplace(_Args&& ...__args); 1069 1070 template <class ..._Args> 1071 iterator 1072 emplace_hint(const_iterator __p, _Args&& ...__args); 1073 1074#endif // _LIBCPP_HAS_NO_VARIADICS 1075 1076 template <class _Pp, 1077 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1078 _LIBCPP_INLINE_VISIBILITY 1079 pair<iterator, bool> insert(_Pp&& __p) 1080 {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));} 1081 1082 template <class _Pp, 1083 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1084 _LIBCPP_INLINE_VISIBILITY 1085 iterator insert(const_iterator __pos, _Pp&& __p) 1086 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));} 1087 1088#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1089 1090 _LIBCPP_INLINE_VISIBILITY 1091 pair<iterator, bool> 1092 insert(const value_type& __v) {return __tree_.__insert_unique(__v);} 1093 1094 _LIBCPP_INLINE_VISIBILITY 1095 iterator 1096 insert(const_iterator __p, const value_type& __v) 1097 {return __tree_.__insert_unique(__p.__i_, __v);} 1098 1099 template <class _InputIterator> 1100 _LIBCPP_INLINE_VISIBILITY 1101 void insert(_InputIterator __f, _InputIterator __l) 1102 { 1103 for (const_iterator __e = cend(); __f != __l; ++__f) 1104 insert(__e.__i_, *__f); 1105 } 1106 1107#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1108 1109 _LIBCPP_INLINE_VISIBILITY 1110 void insert(initializer_list<value_type> __il) 1111 {insert(__il.begin(), __il.end());} 1112 1113#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1114 1115#if _LIBCPP_STD_VER > 14 1116#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1117#ifndef _LIBCPP_HAS_NO_VARIADICS 1118 template <class... _Args> 1119 _LIBCPP_INLINE_VISIBILITY 1120 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) 1121 { 1122 iterator __p = lower_bound(__k); 1123 if ( __p != end() && !key_comp()(__k, __p->first)) 1124 return _VSTD::make_pair(__p, false); 1125 else 1126 return _VSTD::make_pair( 1127 emplace_hint(__p, 1128 _VSTD::piecewise_construct, _VSTD::forward_as_tuple(__k), 1129 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)), 1130 true); 1131 } 1132 1133 template <class... _Args> 1134 _LIBCPP_INLINE_VISIBILITY 1135 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) 1136 { 1137 iterator __p = lower_bound(__k); 1138 if ( __p != end() && !key_comp()(__k, __p->first)) 1139 return _VSTD::make_pair(__p, false); 1140 else 1141 return _VSTD::make_pair( 1142 emplace_hint(__p, 1143 _VSTD::piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)), 1144 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)), 1145 true); 1146 } 1147 1148 template <class... _Args> 1149 _LIBCPP_INLINE_VISIBILITY 1150 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args) 1151 { 1152 iterator __p = lower_bound(__k); 1153 if ( __p != end() && !key_comp()(__k, __p->first)) 1154 return __p; 1155 else 1156 return emplace_hint(__p, 1157 _VSTD::piecewise_construct, _VSTD::forward_as_tuple(__k), 1158 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); 1159 } 1160 1161 template <class... _Args> 1162 _LIBCPP_INLINE_VISIBILITY 1163 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) 1164 { 1165 iterator __p = lower_bound(__k); 1166 if ( __p != end() && !key_comp()(__k, __p->first)) 1167 return __p; 1168 else 1169 return emplace_hint(__p, 1170 _VSTD::piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)), 1171 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); 1172 } 1173 1174 template <class _Vp> 1175 _LIBCPP_INLINE_VISIBILITY 1176 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) 1177 { 1178 iterator __p = lower_bound(__k); 1179 if ( __p != end() && !key_comp()(__k, __p->first)) 1180 { 1181 __p->second = _VSTD::forward<_Vp>(__v); 1182 return _VSTD::make_pair(__p, false); 1183 } 1184 return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true); 1185 } 1186 1187 template <class _Vp> 1188 _LIBCPP_INLINE_VISIBILITY 1189 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) 1190 { 1191 iterator __p = lower_bound(__k); 1192 if ( __p != end() && !key_comp()(__k, __p->first)) 1193 { 1194 __p->second = _VSTD::forward<_Vp>(__v); 1195 return _VSTD::make_pair(__p, false); 1196 } 1197 return _VSTD::make_pair(emplace_hint(__p, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)), true); 1198 } 1199 1200 template <class _Vp> 1201 _LIBCPP_INLINE_VISIBILITY 1202 iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v) 1203 { 1204 iterator __p = lower_bound(__k); 1205 if ( __p != end() && !key_comp()(__k, __p->first)) 1206 { 1207 __p->second = _VSTD::forward<_Vp>(__v); 1208 return __p; 1209 } 1210 return emplace_hint(__h, __k, _VSTD::forward<_Vp>(__v)); 1211 } 1212 1213 template <class _Vp> 1214 _LIBCPP_INLINE_VISIBILITY 1215 iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v) 1216 { 1217 iterator __p = lower_bound(__k); 1218 if ( __p != end() && !key_comp()(__k, __p->first)) 1219 { 1220 __p->second = _VSTD::forward<_Vp>(__v); 1221 return __p; 1222 } 1223 return emplace_hint(__h, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)); 1224 } 1225#endif 1226#endif 1227#endif 1228 1229 _LIBCPP_INLINE_VISIBILITY 1230 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);} 1231 _LIBCPP_INLINE_VISIBILITY 1232 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);} 1233 _LIBCPP_INLINE_VISIBILITY 1234 size_type erase(const key_type& __k) 1235 {return __tree_.__erase_unique(__k);} 1236 _LIBCPP_INLINE_VISIBILITY 1237 iterator erase(const_iterator __f, const_iterator __l) 1238 {return __tree_.erase(__f.__i_, __l.__i_);} 1239 _LIBCPP_INLINE_VISIBILITY 1240 void clear() _NOEXCEPT {__tree_.clear();} 1241 1242 _LIBCPP_INLINE_VISIBILITY 1243 void swap(map& __m) 1244 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 1245 {__tree_.swap(__m.__tree_);} 1246 1247 _LIBCPP_INLINE_VISIBILITY 1248 iterator find(const key_type& __k) {return __tree_.find(__k);} 1249 _LIBCPP_INLINE_VISIBILITY 1250 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 1251#if _LIBCPP_STD_VER > 11 1252 template <typename _K2> 1253 _LIBCPP_INLINE_VISIBILITY 1254 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 1255 find(const _K2& __k) {return __tree_.find(__k);} 1256 template <typename _K2> 1257 _LIBCPP_INLINE_VISIBILITY 1258 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 1259 find(const _K2& __k) const {return __tree_.find(__k);} 1260#endif 1261 1262 _LIBCPP_INLINE_VISIBILITY 1263 size_type count(const key_type& __k) const 1264 {return __tree_.__count_unique(__k);} 1265#if _LIBCPP_STD_VER > 11 1266 template <typename _K2> 1267 _LIBCPP_INLINE_VISIBILITY 1268 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 1269 count(const _K2& __k) const {return __tree_.__count_unique(__k);} 1270#endif 1271 _LIBCPP_INLINE_VISIBILITY 1272 iterator lower_bound(const key_type& __k) 1273 {return __tree_.lower_bound(__k);} 1274 _LIBCPP_INLINE_VISIBILITY 1275 const_iterator lower_bound(const key_type& __k) const 1276 {return __tree_.lower_bound(__k);} 1277#if _LIBCPP_STD_VER > 11 1278 template <typename _K2> 1279 _LIBCPP_INLINE_VISIBILITY 1280 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 1281 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 1282 1283 template <typename _K2> 1284 _LIBCPP_INLINE_VISIBILITY 1285 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 1286 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 1287#endif 1288 1289 _LIBCPP_INLINE_VISIBILITY 1290 iterator upper_bound(const key_type& __k) 1291 {return __tree_.upper_bound(__k);} 1292 _LIBCPP_INLINE_VISIBILITY 1293 const_iterator upper_bound(const key_type& __k) const 1294 {return __tree_.upper_bound(__k);} 1295#if _LIBCPP_STD_VER > 11 1296 template <typename _K2> 1297 _LIBCPP_INLINE_VISIBILITY 1298 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 1299 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 1300 template <typename _K2> 1301 _LIBCPP_INLINE_VISIBILITY 1302 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 1303 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 1304#endif 1305 1306 _LIBCPP_INLINE_VISIBILITY 1307 pair<iterator,iterator> equal_range(const key_type& __k) 1308 {return __tree_.__equal_range_unique(__k);} 1309 _LIBCPP_INLINE_VISIBILITY 1310 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 1311 {return __tree_.__equal_range_unique(__k);} 1312#if _LIBCPP_STD_VER > 11 1313 template <typename _K2> 1314 _LIBCPP_INLINE_VISIBILITY 1315 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 1316 equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);} 1317 template <typename _K2> 1318 _LIBCPP_INLINE_VISIBILITY 1319 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 1320 equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);} 1321#endif 1322 1323private: 1324 typedef typename __base::__node __node; 1325 typedef typename __base::__node_allocator __node_allocator; 1326 typedef typename __base::__node_pointer __node_pointer; 1327 typedef typename __base::__node_const_pointer __node_const_pointer; 1328 typedef typename __base::__node_base_pointer __node_base_pointer; 1329 typedef typename __base::__node_base_const_pointer __node_base_const_pointer; 1330 typedef __map_node_destructor<__node_allocator> _Dp; 1331 typedef unique_ptr<__node, _Dp> __node_holder; 1332 1333#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1334 __node_holder __construct_node(); 1335 template <class _A0> 1336 __node_holder __construct_node(_A0&& __a0); 1337 __node_holder __construct_node_with_key(key_type&& __k); 1338#ifndef _LIBCPP_HAS_NO_VARIADICS 1339 template <class _A0, class _A1, class ..._Args> 1340 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); 1341#endif // _LIBCPP_HAS_NO_VARIADICS 1342#endif 1343 __node_holder __construct_node_with_key(const key_type& __k); 1344 1345 __node_base_pointer& 1346 __find_equal_key(__node_base_pointer& __parent, const key_type& __k); 1347 __node_base_const_pointer 1348 __find_equal_key(__node_base_const_pointer& __parent, const key_type& __k) const; 1349}; 1350 1351// Find place to insert if __k doesn't exist 1352// Set __parent to parent of null leaf 1353// Return reference to null leaf 1354// If __k exists, set parent to node of __k and return reference to node of __k 1355template <class _Key, class _Tp, class _Compare, class _Allocator> 1356typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_pointer& 1357map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_pointer& __parent, 1358 const key_type& __k) 1359{ 1360 __node_pointer __nd = __tree_.__root(); 1361 if (__nd != nullptr) 1362 { 1363 while (true) 1364 { 1365 if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first)) 1366 { 1367 if (__nd->__left_ != nullptr) 1368 __nd = static_cast<__node_pointer>(__nd->__left_); 1369 else 1370 { 1371 __parent = static_cast<__node_base_pointer>(__nd); 1372 return __parent->__left_; 1373 } 1374 } 1375 else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k)) 1376 { 1377 if (__nd->__right_ != nullptr) 1378 __nd = static_cast<__node_pointer>(__nd->__right_); 1379 else 1380 { 1381 __parent = static_cast<__node_base_pointer>(__nd); 1382 return __parent->__right_; 1383 } 1384 } 1385 else 1386 { 1387 __parent = static_cast<__node_base_pointer>(__nd); 1388 return __parent; 1389 } 1390 } 1391 } 1392 __parent = static_cast<__node_base_pointer>(__tree_.__end_node()); 1393 return __parent->__left_; 1394} 1395 1396// Find __k 1397// Set __parent to parent of null leaf and 1398// return reference to null leaf iv __k does not exist. 1399// If __k exists, set parent to node of __k and return reference to node of __k 1400template <class _Key, class _Tp, class _Compare, class _Allocator> 1401typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_const_pointer 1402map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_const_pointer& __parent, 1403 const key_type& __k) const 1404{ 1405 __node_const_pointer __nd = __tree_.__root(); 1406 if (__nd != nullptr) 1407 { 1408 while (true) 1409 { 1410 if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first)) 1411 { 1412 if (__nd->__left_ != nullptr) 1413 __nd = static_cast<__node_pointer>(__nd->__left_); 1414 else 1415 { 1416 __parent = static_cast<__node_base_pointer>(__nd); 1417 return const_cast<const __node_base_const_pointer&>(__parent->__left_); 1418 } 1419 } 1420 else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k)) 1421 { 1422 if (__nd->__right_ != nullptr) 1423 __nd = static_cast<__node_pointer>(__nd->__right_); 1424 else 1425 { 1426 __parent = static_cast<__node_base_pointer>(__nd); 1427 return const_cast<const __node_base_const_pointer&>(__parent->__right_); 1428 } 1429 } 1430 else 1431 { 1432 __parent = static_cast<__node_base_pointer>(__nd); 1433 return __parent; 1434 } 1435 } 1436 } 1437 __parent = static_cast<__node_base_pointer>(__tree_.__end_node()); 1438 return const_cast<const __node_base_const_pointer&>(__parent->__left_); 1439} 1440 1441#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1442 1443template <class _Key, class _Tp, class _Compare, class _Allocator> 1444map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a) 1445 : __tree_(_VSTD::move(__m.__tree_), __a) 1446{ 1447 if (__a != __m.get_allocator()) 1448 { 1449 const_iterator __e = cend(); 1450 while (!__m.empty()) 1451 __tree_.__insert_unique(__e.__i_, 1452 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_)); 1453 } 1454} 1455 1456template <class _Key, class _Tp, class _Compare, class _Allocator> 1457typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder 1458map<_Key, _Tp, _Compare, _Allocator>::__construct_node() 1459{ 1460 __node_allocator& __na = __tree_.__node_alloc(); 1461 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1462 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first)); 1463 __h.get_deleter().__first_constructed = true; 1464 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); 1465 __h.get_deleter().__second_constructed = true; 1466 return __h; 1467} 1468 1469template <class _Key, class _Tp, class _Compare, class _Allocator> 1470template <class _A0> 1471typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder 1472map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0) 1473{ 1474 __node_allocator& __na = __tree_.__node_alloc(); 1475 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1476 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0)); 1477 __h.get_deleter().__first_constructed = true; 1478 __h.get_deleter().__second_constructed = true; 1479 return __h; 1480} 1481 1482template <class _Key, class _Tp, class _Compare, class _Allocator> 1483typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder 1484map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(key_type&& __k) 1485{ 1486 __node_allocator& __na = __tree_.__node_alloc(); 1487 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1488 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k)); 1489 __h.get_deleter().__first_constructed = true; 1490 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); 1491 __h.get_deleter().__second_constructed = true; 1492 return __h; 1493} 1494 1495#ifndef _LIBCPP_HAS_NO_VARIADICS 1496 1497template <class _Key, class _Tp, class _Compare, class _Allocator> 1498template <class _A0, class _A1, class ..._Args> 1499typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder 1500map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args) 1501{ 1502 __node_allocator& __na = __tree_.__node_alloc(); 1503 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1504 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1505 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), 1506 _VSTD::forward<_Args>(__args)...); 1507 __h.get_deleter().__first_constructed = true; 1508 __h.get_deleter().__second_constructed = true; 1509 return __h; 1510} 1511 1512#endif // _LIBCPP_HAS_NO_VARIADICS 1513 1514#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1515 1516template <class _Key, class _Tp, class _Compare, class _Allocator> 1517typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder 1518map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k) 1519{ 1520 __node_allocator& __na = __tree_.__node_alloc(); 1521 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1522 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k); 1523 __h.get_deleter().__first_constructed = true; 1524 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); 1525 __h.get_deleter().__second_constructed = true; 1526 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03 1527} 1528 1529template <class _Key, class _Tp, class _Compare, class _Allocator> 1530_Tp& 1531map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) 1532{ 1533 __node_base_pointer __parent; 1534 __node_base_pointer& __child = __find_equal_key(__parent, __k); 1535 __node_pointer __r = static_cast<__node_pointer>(__child); 1536 if (__child == nullptr) 1537 { 1538 __node_holder __h = __construct_node_with_key(__k); 1539 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1540 __r = __h.release(); 1541 } 1542 return __r->__value_.__cc.second; 1543} 1544 1545#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1546 1547template <class _Key, class _Tp, class _Compare, class _Allocator> 1548_Tp& 1549map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k) 1550{ 1551 __node_base_pointer __parent; 1552 __node_base_pointer& __child = __find_equal_key(__parent, __k); 1553 __node_pointer __r = static_cast<__node_pointer>(__child); 1554 if (__child == nullptr) 1555 { 1556 __node_holder __h = __construct_node_with_key(_VSTD::move(__k)); 1557 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1558 __r = __h.release(); 1559 } 1560 return __r->__value_.__cc.second; 1561} 1562 1563#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1564 1565template <class _Key, class _Tp, class _Compare, class _Allocator> 1566_Tp& 1567map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) 1568{ 1569 __node_base_pointer __parent; 1570 __node_base_pointer& __child = __find_equal_key(__parent, __k); 1571#ifndef _LIBCPP_NO_EXCEPTIONS 1572 if (__child == nullptr) 1573 throw out_of_range("map::at: key not found"); 1574#endif // _LIBCPP_NO_EXCEPTIONS 1575 return static_cast<__node_pointer>(__child)->__value_.__cc.second; 1576} 1577 1578template <class _Key, class _Tp, class _Compare, class _Allocator> 1579const _Tp& 1580map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const 1581{ 1582 __node_base_const_pointer __parent; 1583 __node_base_const_pointer __child = __find_equal_key(__parent, __k); 1584#ifndef _LIBCPP_NO_EXCEPTIONS 1585 if (__child == nullptr) 1586 throw out_of_range("map::at: key not found"); 1587#endif // _LIBCPP_NO_EXCEPTIONS 1588 return static_cast<__node_const_pointer>(__child)->__value_.__cc.second; 1589} 1590 1591#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1592 1593template <class _Key, class _Tp, class _Compare, class _Allocator> 1594template <class ..._Args> 1595pair<typename map<_Key, _Tp, _Compare, _Allocator>::iterator, bool> 1596map<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args) 1597{ 1598 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1599 pair<iterator, bool> __r = __tree_.__node_insert_unique(__h.get()); 1600 if (__r.second) 1601 __h.release(); 1602 return __r; 1603} 1604 1605template <class _Key, class _Tp, class _Compare, class _Allocator> 1606template <class ..._Args> 1607typename map<_Key, _Tp, _Compare, _Allocator>::iterator 1608map<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p, 1609 _Args&& ...__args) 1610{ 1611 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1612 iterator __r = __tree_.__node_insert_unique(__p.__i_, __h.get()); 1613 if (__r.__i_.__ptr_ == __h.get()) 1614 __h.release(); 1615 return __r; 1616} 1617 1618#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1619 1620template <class _Key, class _Tp, class _Compare, class _Allocator> 1621inline _LIBCPP_INLINE_VISIBILITY 1622bool 1623operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1624 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1625{ 1626 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 1627} 1628 1629template <class _Key, class _Tp, class _Compare, class _Allocator> 1630inline _LIBCPP_INLINE_VISIBILITY 1631bool 1632operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x, 1633 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1634{ 1635 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 1636} 1637 1638template <class _Key, class _Tp, class _Compare, class _Allocator> 1639inline _LIBCPP_INLINE_VISIBILITY 1640bool 1641operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1642 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1643{ 1644 return !(__x == __y); 1645} 1646 1647template <class _Key, class _Tp, class _Compare, class _Allocator> 1648inline _LIBCPP_INLINE_VISIBILITY 1649bool 1650operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x, 1651 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1652{ 1653 return __y < __x; 1654} 1655 1656template <class _Key, class _Tp, class _Compare, class _Allocator> 1657inline _LIBCPP_INLINE_VISIBILITY 1658bool 1659operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1660 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1661{ 1662 return !(__x < __y); 1663} 1664 1665template <class _Key, class _Tp, class _Compare, class _Allocator> 1666inline _LIBCPP_INLINE_VISIBILITY 1667bool 1668operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1669 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1670{ 1671 return !(__y < __x); 1672} 1673 1674template <class _Key, class _Tp, class _Compare, class _Allocator> 1675inline _LIBCPP_INLINE_VISIBILITY 1676void 1677swap(map<_Key, _Tp, _Compare, _Allocator>& __x, 1678 map<_Key, _Tp, _Compare, _Allocator>& __y) 1679 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1680{ 1681 __x.swap(__y); 1682} 1683 1684template <class _Key, class _Tp, class _Compare = less<_Key>, 1685 class _Allocator = allocator<pair<const _Key, _Tp> > > 1686class _LIBCPP_TYPE_VIS_ONLY multimap 1687{ 1688public: 1689 // types: 1690 typedef _Key key_type; 1691 typedef _Tp mapped_type; 1692 typedef pair<const key_type, mapped_type> value_type; 1693 typedef pair<key_type, mapped_type> __nc_value_type; 1694 typedef _Compare key_compare; 1695 typedef _Allocator allocator_type; 1696 typedef value_type& reference; 1697 typedef const value_type& const_reference; 1698 1699 class _LIBCPP_TYPE_VIS_ONLY value_compare 1700 : public binary_function<value_type, value_type, bool> 1701 { 1702 friend class multimap; 1703 protected: 1704 key_compare comp; 1705 1706 _LIBCPP_INLINE_VISIBILITY 1707 value_compare(key_compare c) : comp(c) {} 1708 public: 1709 _LIBCPP_INLINE_VISIBILITY 1710 bool operator()(const value_type& __x, const value_type& __y) const 1711 {return comp(__x.first, __y.first);} 1712 }; 1713 1714private: 1715 1716 typedef _VSTD::__value_type<key_type, mapped_type> __value_type; 1717 typedef __map_value_compare<key_type, __value_type, key_compare> __vc; 1718 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, 1719 __value_type>::type __allocator_type; 1720 typedef __tree<__value_type, __vc, __allocator_type> __base; 1721 typedef typename __base::__node_traits __node_traits; 1722 typedef allocator_traits<allocator_type> __alloc_traits; 1723 1724 __base __tree_; 1725 1726public: 1727 typedef typename __alloc_traits::pointer pointer; 1728 typedef typename __alloc_traits::const_pointer const_pointer; 1729 typedef typename __alloc_traits::size_type size_type; 1730 typedef typename __alloc_traits::difference_type difference_type; 1731 typedef __map_iterator<typename __base::iterator> iterator; 1732 typedef __map_const_iterator<typename __base::const_iterator> const_iterator; 1733 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 1734 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 1735 1736 _LIBCPP_INLINE_VISIBILITY 1737 multimap() 1738 _NOEXCEPT_( 1739 is_nothrow_default_constructible<allocator_type>::value && 1740 is_nothrow_default_constructible<key_compare>::value && 1741 is_nothrow_copy_constructible<key_compare>::value) 1742 : __tree_(__vc(key_compare())) {} 1743 1744 _LIBCPP_INLINE_VISIBILITY 1745 explicit multimap(const key_compare& __comp) 1746 _NOEXCEPT_( 1747 is_nothrow_default_constructible<allocator_type>::value && 1748 is_nothrow_copy_constructible<key_compare>::value) 1749 : __tree_(__vc(__comp)) {} 1750 1751 _LIBCPP_INLINE_VISIBILITY 1752 explicit multimap(const key_compare& __comp, const allocator_type& __a) 1753 : __tree_(__vc(__comp), __a) {} 1754 1755 template <class _InputIterator> 1756 _LIBCPP_INLINE_VISIBILITY 1757 multimap(_InputIterator __f, _InputIterator __l, 1758 const key_compare& __comp = key_compare()) 1759 : __tree_(__vc(__comp)) 1760 { 1761 insert(__f, __l); 1762 } 1763 1764 template <class _InputIterator> 1765 _LIBCPP_INLINE_VISIBILITY 1766 multimap(_InputIterator __f, _InputIterator __l, 1767 const key_compare& __comp, const allocator_type& __a) 1768 : __tree_(__vc(__comp), __a) 1769 { 1770 insert(__f, __l); 1771 } 1772 1773#if _LIBCPP_STD_VER > 11 1774 template <class _InputIterator> 1775 _LIBCPP_INLINE_VISIBILITY 1776 multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 1777 : multimap(__f, __l, key_compare(), __a) {} 1778#endif 1779 1780 _LIBCPP_INLINE_VISIBILITY 1781 multimap(const multimap& __m) 1782 : __tree_(__m.__tree_.value_comp(), 1783 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc())) 1784 { 1785 insert(__m.begin(), __m.end()); 1786 } 1787 1788 _LIBCPP_INLINE_VISIBILITY 1789 multimap& operator=(const multimap& __m) 1790 { 1791#if __cplusplus >= 201103L 1792 __tree_ = __m.__tree_; 1793#else 1794 if (this != &__m) { 1795 __tree_.clear(); 1796 __tree_.value_comp() = __m.__tree_.value_comp(); 1797 __tree_.__copy_assign_alloc(__m.__tree_); 1798 insert(__m.begin(), __m.end()); 1799 } 1800#endif 1801 return *this; 1802 } 1803 1804#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1805 1806 _LIBCPP_INLINE_VISIBILITY 1807 multimap(multimap&& __m) 1808 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 1809 : __tree_(_VSTD::move(__m.__tree_)) 1810 { 1811 } 1812 1813 multimap(multimap&& __m, const allocator_type& __a); 1814 1815 _LIBCPP_INLINE_VISIBILITY 1816 multimap& operator=(multimap&& __m) 1817 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 1818 { 1819 __tree_ = _VSTD::move(__m.__tree_); 1820 return *this; 1821 } 1822 1823#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1824 1825#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1826 1827 _LIBCPP_INLINE_VISIBILITY 1828 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare()) 1829 : __tree_(__vc(__comp)) 1830 { 1831 insert(__il.begin(), __il.end()); 1832 } 1833 1834 _LIBCPP_INLINE_VISIBILITY 1835 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a) 1836 : __tree_(__vc(__comp), __a) 1837 { 1838 insert(__il.begin(), __il.end()); 1839 } 1840 1841#if _LIBCPP_STD_VER > 11 1842 _LIBCPP_INLINE_VISIBILITY 1843 multimap(initializer_list<value_type> __il, const allocator_type& __a) 1844 : multimap(__il, key_compare(), __a) {} 1845#endif 1846 1847 _LIBCPP_INLINE_VISIBILITY 1848 multimap& operator=(initializer_list<value_type> __il) 1849 { 1850 __tree_.__assign_multi(__il.begin(), __il.end()); 1851 return *this; 1852 } 1853 1854#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1855 1856 _LIBCPP_INLINE_VISIBILITY 1857 explicit multimap(const allocator_type& __a) 1858 : __tree_(__a) 1859 { 1860 } 1861 1862 _LIBCPP_INLINE_VISIBILITY 1863 multimap(const multimap& __m, const allocator_type& __a) 1864 : __tree_(__m.__tree_.value_comp(), __a) 1865 { 1866 insert(__m.begin(), __m.end()); 1867 } 1868 1869 _LIBCPP_INLINE_VISIBILITY 1870 iterator begin() _NOEXCEPT {return __tree_.begin();} 1871 _LIBCPP_INLINE_VISIBILITY 1872 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 1873 _LIBCPP_INLINE_VISIBILITY 1874 iterator end() _NOEXCEPT {return __tree_.end();} 1875 _LIBCPP_INLINE_VISIBILITY 1876 const_iterator end() const _NOEXCEPT {return __tree_.end();} 1877 1878 _LIBCPP_INLINE_VISIBILITY 1879 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());} 1880 _LIBCPP_INLINE_VISIBILITY 1881 const_reverse_iterator rbegin() const _NOEXCEPT 1882 {return const_reverse_iterator(end());} 1883 _LIBCPP_INLINE_VISIBILITY 1884 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());} 1885 _LIBCPP_INLINE_VISIBILITY 1886 const_reverse_iterator rend() const _NOEXCEPT 1887 {return const_reverse_iterator(begin());} 1888 1889 _LIBCPP_INLINE_VISIBILITY 1890 const_iterator cbegin() const _NOEXCEPT {return begin();} 1891 _LIBCPP_INLINE_VISIBILITY 1892 const_iterator cend() const _NOEXCEPT {return end();} 1893 _LIBCPP_INLINE_VISIBILITY 1894 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 1895 _LIBCPP_INLINE_VISIBILITY 1896 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 1897 1898 _LIBCPP_INLINE_VISIBILITY 1899 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 1900 _LIBCPP_INLINE_VISIBILITY 1901 size_type size() const _NOEXCEPT {return __tree_.size();} 1902 _LIBCPP_INLINE_VISIBILITY 1903 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 1904 1905 _LIBCPP_INLINE_VISIBILITY 1906 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 1907 _LIBCPP_INLINE_VISIBILITY 1908 key_compare key_comp() const {return __tree_.value_comp().key_comp();} 1909 _LIBCPP_INLINE_VISIBILITY 1910 value_compare value_comp() const 1911 {return value_compare(__tree_.value_comp().key_comp());} 1912 1913#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1914#ifndef _LIBCPP_HAS_NO_VARIADICS 1915 1916 template <class ..._Args> 1917 iterator 1918 emplace(_Args&& ...__args); 1919 1920 template <class ..._Args> 1921 iterator 1922 emplace_hint(const_iterator __p, _Args&& ...__args); 1923 1924#endif // _LIBCPP_HAS_NO_VARIADICS 1925 1926 template <class _Pp, 1927 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1928 _LIBCPP_INLINE_VISIBILITY 1929 iterator insert(_Pp&& __p) 1930 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));} 1931 1932 template <class _Pp, 1933 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1934 _LIBCPP_INLINE_VISIBILITY 1935 iterator insert(const_iterator __pos, _Pp&& __p) 1936 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));} 1937 1938#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1939 1940 _LIBCPP_INLINE_VISIBILITY 1941 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);} 1942 1943 _LIBCPP_INLINE_VISIBILITY 1944 iterator insert(const_iterator __p, const value_type& __v) 1945 {return __tree_.__insert_multi(__p.__i_, __v);} 1946 1947 template <class _InputIterator> 1948 _LIBCPP_INLINE_VISIBILITY 1949 void insert(_InputIterator __f, _InputIterator __l) 1950 { 1951 for (const_iterator __e = cend(); __f != __l; ++__f) 1952 __tree_.__insert_multi(__e.__i_, *__f); 1953 } 1954 1955#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1956 1957 _LIBCPP_INLINE_VISIBILITY 1958 void insert(initializer_list<value_type> __il) 1959 {insert(__il.begin(), __il.end());} 1960 1961#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1962 1963 _LIBCPP_INLINE_VISIBILITY 1964 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);} 1965 _LIBCPP_INLINE_VISIBILITY 1966 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);} 1967 _LIBCPP_INLINE_VISIBILITY 1968 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} 1969 _LIBCPP_INLINE_VISIBILITY 1970 iterator erase(const_iterator __f, const_iterator __l) 1971 {return __tree_.erase(__f.__i_, __l.__i_);} 1972 _LIBCPP_INLINE_VISIBILITY 1973 void clear() {__tree_.clear();} 1974 1975 _LIBCPP_INLINE_VISIBILITY 1976 void swap(multimap& __m) 1977 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 1978 {__tree_.swap(__m.__tree_);} 1979 1980 _LIBCPP_INLINE_VISIBILITY 1981 iterator find(const key_type& __k) {return __tree_.find(__k);} 1982 _LIBCPP_INLINE_VISIBILITY 1983 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 1984#if _LIBCPP_STD_VER > 11 1985 template <typename _K2> 1986 _LIBCPP_INLINE_VISIBILITY 1987 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 1988 find(const _K2& __k) {return __tree_.find(__k);} 1989 template <typename _K2> 1990 _LIBCPP_INLINE_VISIBILITY 1991 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 1992 find(const _K2& __k) const {return __tree_.find(__k);} 1993#endif 1994 1995 _LIBCPP_INLINE_VISIBILITY 1996 size_type count(const key_type& __k) const 1997 {return __tree_.__count_multi(__k);} 1998#if _LIBCPP_STD_VER > 11 1999 template <typename _K2> 2000 _LIBCPP_INLINE_VISIBILITY 2001 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 2002 count(const _K2& __k) const {return __tree_.__count_multi(__k);} 2003#endif 2004 _LIBCPP_INLINE_VISIBILITY 2005 iterator lower_bound(const key_type& __k) 2006 {return __tree_.lower_bound(__k);} 2007 _LIBCPP_INLINE_VISIBILITY 2008 const_iterator lower_bound(const key_type& __k) const 2009 {return __tree_.lower_bound(__k);} 2010#if _LIBCPP_STD_VER > 11 2011 template <typename _K2> 2012 _LIBCPP_INLINE_VISIBILITY 2013 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 2014 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 2015 2016 template <typename _K2> 2017 _LIBCPP_INLINE_VISIBILITY 2018 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 2019 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 2020#endif 2021 2022 _LIBCPP_INLINE_VISIBILITY 2023 iterator upper_bound(const key_type& __k) 2024 {return __tree_.upper_bound(__k);} 2025 _LIBCPP_INLINE_VISIBILITY 2026 const_iterator upper_bound(const key_type& __k) const 2027 {return __tree_.upper_bound(__k);} 2028#if _LIBCPP_STD_VER > 11 2029 template <typename _K2> 2030 _LIBCPP_INLINE_VISIBILITY 2031 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 2032 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 2033 template <typename _K2> 2034 _LIBCPP_INLINE_VISIBILITY 2035 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 2036 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 2037#endif 2038 2039 _LIBCPP_INLINE_VISIBILITY 2040 pair<iterator,iterator> equal_range(const key_type& __k) 2041 {return __tree_.__equal_range_multi(__k);} 2042 _LIBCPP_INLINE_VISIBILITY 2043 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 2044 {return __tree_.__equal_range_multi(__k);} 2045#if _LIBCPP_STD_VER > 11 2046 template <typename _K2> 2047 _LIBCPP_INLINE_VISIBILITY 2048 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 2049 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 2050 template <typename _K2> 2051 _LIBCPP_INLINE_VISIBILITY 2052 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 2053 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 2054#endif 2055 2056private: 2057 typedef typename __base::__node __node; 2058 typedef typename __base::__node_allocator __node_allocator; 2059 typedef typename __base::__node_pointer __node_pointer; 2060 typedef typename __base::__node_const_pointer __node_const_pointer; 2061 typedef __map_node_destructor<__node_allocator> _Dp; 2062 typedef unique_ptr<__node, _Dp> __node_holder; 2063 2064#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2065 __node_holder __construct_node(); 2066 template <class _A0> 2067 __node_holder 2068 __construct_node(_A0&& __a0); 2069#ifndef _LIBCPP_HAS_NO_VARIADICS 2070 template <class _A0, class _A1, class ..._Args> 2071 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); 2072#endif // _LIBCPP_HAS_NO_VARIADICS 2073#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2074}; 2075 2076#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2077 2078template <class _Key, class _Tp, class _Compare, class _Allocator> 2079multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a) 2080 : __tree_(_VSTD::move(__m.__tree_), __a) 2081{ 2082 if (__a != __m.get_allocator()) 2083 { 2084 const_iterator __e = cend(); 2085 while (!__m.empty()) 2086 __tree_.__insert_multi(__e.__i_, 2087 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_)); 2088 } 2089} 2090 2091template <class _Key, class _Tp, class _Compare, class _Allocator> 2092typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder 2093multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node() 2094{ 2095 __node_allocator& __na = __tree_.__node_alloc(); 2096 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2097 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first)); 2098 __h.get_deleter().__first_constructed = true; 2099 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); 2100 __h.get_deleter().__second_constructed = true; 2101 return __h; 2102} 2103 2104template <class _Key, class _Tp, class _Compare, class _Allocator> 2105template <class _A0> 2106typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder 2107multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0) 2108{ 2109 __node_allocator& __na = __tree_.__node_alloc(); 2110 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2111 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0)); 2112 __h.get_deleter().__first_constructed = true; 2113 __h.get_deleter().__second_constructed = true; 2114 return __h; 2115} 2116 2117#ifndef _LIBCPP_HAS_NO_VARIADICS 2118 2119template <class _Key, class _Tp, class _Compare, class _Allocator> 2120template <class _A0, class _A1, class ..._Args> 2121typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder 2122multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args) 2123{ 2124 __node_allocator& __na = __tree_.__node_alloc(); 2125 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2126 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 2127 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), 2128 _VSTD::forward<_Args>(__args)...); 2129 __h.get_deleter().__first_constructed = true; 2130 __h.get_deleter().__second_constructed = true; 2131 return __h; 2132} 2133 2134#endif // _LIBCPP_HAS_NO_VARIADICS 2135#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2136 2137#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 2138 2139template <class _Key, class _Tp, class _Compare, class _Allocator> 2140template <class ..._Args> 2141typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator 2142multimap<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args) 2143{ 2144 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2145 iterator __r = __tree_.__node_insert_multi(__h.get()); 2146 __h.release(); 2147 return __r; 2148} 2149 2150template <class _Key, class _Tp, class _Compare, class _Allocator> 2151template <class ..._Args> 2152typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator 2153multimap<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p, 2154 _Args&& ...__args) 2155{ 2156 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2157 iterator __r = __tree_.__node_insert_multi(__p.__i_, __h.get()); 2158 __h.release(); 2159 return __r; 2160} 2161 2162#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 2163 2164template <class _Key, class _Tp, class _Compare, class _Allocator> 2165inline _LIBCPP_INLINE_VISIBILITY 2166bool 2167operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2168 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2169{ 2170 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 2171} 2172 2173template <class _Key, class _Tp, class _Compare, class _Allocator> 2174inline _LIBCPP_INLINE_VISIBILITY 2175bool 2176operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2177 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2178{ 2179 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 2180} 2181 2182template <class _Key, class _Tp, class _Compare, class _Allocator> 2183inline _LIBCPP_INLINE_VISIBILITY 2184bool 2185operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2186 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2187{ 2188 return !(__x == __y); 2189} 2190 2191template <class _Key, class _Tp, class _Compare, class _Allocator> 2192inline _LIBCPP_INLINE_VISIBILITY 2193bool 2194operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2195 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2196{ 2197 return __y < __x; 2198} 2199 2200template <class _Key, class _Tp, class _Compare, class _Allocator> 2201inline _LIBCPP_INLINE_VISIBILITY 2202bool 2203operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2204 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2205{ 2206 return !(__x < __y); 2207} 2208 2209template <class _Key, class _Tp, class _Compare, class _Allocator> 2210inline _LIBCPP_INLINE_VISIBILITY 2211bool 2212operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2213 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2214{ 2215 return !(__y < __x); 2216} 2217 2218template <class _Key, class _Tp, class _Compare, class _Allocator> 2219inline _LIBCPP_INLINE_VISIBILITY 2220void 2221swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2222 multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2223 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2224{ 2225 __x.swap(__y); 2226} 2227 2228_LIBCPP_END_NAMESPACE_STD 2229 2230#endif // _LIBCPP_MAP 2231