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