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