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