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