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