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