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