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