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 size_type count(const key_type& k) const; 197 bool contains(const key_type& x) const; // C++20 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 size_type count(const key_type& k) const; 411 bool contains(const key_type& x) const; // C++20 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 1402#if _LIBCPP_STD_VER > 17 1403 _LIBCPP_INLINE_VISIBILITY 1404 bool contains(const key_type& __k) const {return find(__k) != end();} 1405#endif // _LIBCPP_STD_VER > 17 1406 1407 _LIBCPP_INLINE_VISIBILITY 1408 iterator lower_bound(const key_type& __k) 1409 {return __tree_.lower_bound(__k);} 1410 _LIBCPP_INLINE_VISIBILITY 1411 const_iterator lower_bound(const key_type& __k) const 1412 {return __tree_.lower_bound(__k);} 1413#if _LIBCPP_STD_VER > 11 1414 template <typename _K2> 1415 _LIBCPP_INLINE_VISIBILITY 1416 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 1417 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 1418 1419 template <typename _K2> 1420 _LIBCPP_INLINE_VISIBILITY 1421 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 1422 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 1423#endif 1424 1425 _LIBCPP_INLINE_VISIBILITY 1426 iterator upper_bound(const key_type& __k) 1427 {return __tree_.upper_bound(__k);} 1428 _LIBCPP_INLINE_VISIBILITY 1429 const_iterator upper_bound(const key_type& __k) const 1430 {return __tree_.upper_bound(__k);} 1431#if _LIBCPP_STD_VER > 11 1432 template <typename _K2> 1433 _LIBCPP_INLINE_VISIBILITY 1434 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 1435 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 1436 template <typename _K2> 1437 _LIBCPP_INLINE_VISIBILITY 1438 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 1439 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 1440#endif 1441 1442 _LIBCPP_INLINE_VISIBILITY 1443 pair<iterator,iterator> equal_range(const key_type& __k) 1444 {return __tree_.__equal_range_unique(__k);} 1445 _LIBCPP_INLINE_VISIBILITY 1446 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 1447 {return __tree_.__equal_range_unique(__k);} 1448#if _LIBCPP_STD_VER > 11 1449 template <typename _K2> 1450 _LIBCPP_INLINE_VISIBILITY 1451 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 1452 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 1453 template <typename _K2> 1454 _LIBCPP_INLINE_VISIBILITY 1455 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 1456 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 1457#endif 1458 1459private: 1460 typedef typename __base::__node __node; 1461 typedef typename __base::__node_allocator __node_allocator; 1462 typedef typename __base::__node_pointer __node_pointer; 1463 typedef typename __base::__node_base_pointer __node_base_pointer; 1464 typedef typename __base::__parent_pointer __parent_pointer; 1465 1466 typedef __map_node_destructor<__node_allocator> _Dp; 1467 typedef unique_ptr<__node, _Dp> __node_holder; 1468 1469#ifdef _LIBCPP_CXX03_LANG 1470 __node_holder __construct_node_with_key(const key_type& __k); 1471#endif 1472}; 1473 1474#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES 1475template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>, 1476 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, 1477 class = _EnableIf<!__is_allocator<_Compare>::value, void>, 1478 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 1479map(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) 1480 -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>; 1481 1482template<class _Key, class _Tp, class _Compare = less<remove_const_t<_Key>>, 1483 class _Allocator = allocator<pair<const _Key, _Tp>>, 1484 class = _EnableIf<!__is_allocator<_Compare>::value, void>, 1485 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 1486map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator()) 1487 -> map<remove_const_t<_Key>, _Tp, _Compare, _Allocator>; 1488 1489template<class _InputIterator, class _Allocator, 1490 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 1491map(_InputIterator, _InputIterator, _Allocator) 1492 -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, 1493 less<__iter_key_type<_InputIterator>>, _Allocator>; 1494 1495template<class _Key, class _Tp, class _Allocator, 1496 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 1497map(initializer_list<pair<_Key, _Tp>>, _Allocator) 1498 -> map<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>; 1499#endif 1500 1501#ifndef _LIBCPP_CXX03_LANG 1502template <class _Key, class _Tp, class _Compare, class _Allocator> 1503map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a) 1504 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a)) 1505{ 1506 if (__a != __m.get_allocator()) 1507 { 1508 const_iterator __e = cend(); 1509 while (!__m.empty()) 1510 __tree_.__insert_unique(__e.__i_, 1511 __m.__tree_.remove(__m.begin().__i_)->__value_.__move()); 1512 } 1513} 1514 1515template <class _Key, class _Tp, class _Compare, class _Allocator> 1516_Tp& 1517map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) 1518{ 1519 return __tree_.__emplace_unique_key_args(__k, 1520 _VSTD::piecewise_construct, 1521 _VSTD::forward_as_tuple(__k), 1522 _VSTD::forward_as_tuple()).first->__get_value().second; 1523} 1524 1525template <class _Key, class _Tp, class _Compare, class _Allocator> 1526_Tp& 1527map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k) 1528{ 1529 return __tree_.__emplace_unique_key_args(__k, 1530 _VSTD::piecewise_construct, 1531 _VSTD::forward_as_tuple(_VSTD::move(__k)), 1532 _VSTD::forward_as_tuple()).first->__get_value().second; 1533} 1534 1535#else // _LIBCPP_CXX03_LANG 1536 1537template <class _Key, class _Tp, class _Compare, class _Allocator> 1538typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder 1539map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k) 1540{ 1541 __node_allocator& __na = __tree_.__node_alloc(); 1542 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1543 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().first), __k); 1544 __h.get_deleter().__first_constructed = true; 1545 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().second)); 1546 __h.get_deleter().__second_constructed = true; 1547 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03 1548} 1549 1550template <class _Key, class _Tp, class _Compare, class _Allocator> 1551_Tp& 1552map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) 1553{ 1554 __parent_pointer __parent; 1555 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k); 1556 __node_pointer __r = static_cast<__node_pointer>(__child); 1557 if (__child == nullptr) 1558 { 1559 __node_holder __h = __construct_node_with_key(__k); 1560 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1561 __r = __h.release(); 1562 } 1563 return __r->__value_.__get_value().second; 1564} 1565 1566#endif // _LIBCPP_CXX03_LANG 1567 1568template <class _Key, class _Tp, class _Compare, class _Allocator> 1569_Tp& 1570map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) 1571{ 1572 __parent_pointer __parent; 1573 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k); 1574 if (__child == nullptr) 1575 __throw_out_of_range("map::at: key not found"); 1576 return static_cast<__node_pointer>(__child)->__value_.__get_value().second; 1577} 1578 1579template <class _Key, class _Tp, class _Compare, class _Allocator> 1580const _Tp& 1581map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const 1582{ 1583 __parent_pointer __parent; 1584 __node_base_pointer __child = __tree_.__find_equal(__parent, __k); 1585 if (__child == nullptr) 1586 __throw_out_of_range("map::at: key not found"); 1587 return static_cast<__node_pointer>(__child)->__value_.__get_value().second; 1588} 1589 1590 1591template <class _Key, class _Tp, class _Compare, class _Allocator> 1592inline _LIBCPP_INLINE_VISIBILITY 1593bool 1594operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1595 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1596{ 1597 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 1598} 1599 1600template <class _Key, class _Tp, class _Compare, class _Allocator> 1601inline _LIBCPP_INLINE_VISIBILITY 1602bool 1603operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x, 1604 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1605{ 1606 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 1607} 1608 1609template <class _Key, class _Tp, class _Compare, class _Allocator> 1610inline _LIBCPP_INLINE_VISIBILITY 1611bool 1612operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1613 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1614{ 1615 return !(__x == __y); 1616} 1617 1618template <class _Key, class _Tp, class _Compare, class _Allocator> 1619inline _LIBCPP_INLINE_VISIBILITY 1620bool 1621operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x, 1622 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1623{ 1624 return __y < __x; 1625} 1626 1627template <class _Key, class _Tp, class _Compare, class _Allocator> 1628inline _LIBCPP_INLINE_VISIBILITY 1629bool 1630operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1631 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1632{ 1633 return !(__x < __y); 1634} 1635 1636template <class _Key, class _Tp, class _Compare, class _Allocator> 1637inline _LIBCPP_INLINE_VISIBILITY 1638bool 1639operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1640 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1641{ 1642 return !(__y < __x); 1643} 1644 1645template <class _Key, class _Tp, class _Compare, class _Allocator> 1646inline _LIBCPP_INLINE_VISIBILITY 1647void 1648swap(map<_Key, _Tp, _Compare, _Allocator>& __x, 1649 map<_Key, _Tp, _Compare, _Allocator>& __y) 1650 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1651{ 1652 __x.swap(__y); 1653} 1654 1655#if _LIBCPP_STD_VER > 17 1656template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate> 1657inline _LIBCPP_INLINE_VISIBILITY 1658void erase_if(map<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) 1659{ __libcpp_erase_if_container(__c, __pred); } 1660#endif 1661 1662 1663template <class _Key, class _Tp, class _Compare = less<_Key>, 1664 class _Allocator = allocator<pair<const _Key, _Tp> > > 1665class _LIBCPP_TEMPLATE_VIS multimap 1666{ 1667public: 1668 // types: 1669 typedef _Key key_type; 1670 typedef _Tp mapped_type; 1671 typedef pair<const key_type, mapped_type> value_type; 1672 typedef typename __identity<_Compare>::type key_compare; 1673 typedef typename __identity<_Allocator>::type allocator_type; 1674 typedef value_type& reference; 1675 typedef const value_type& const_reference; 1676 1677 static_assert((is_same<typename allocator_type::value_type, value_type>::value), 1678 "Allocator::value_type must be same type as value_type"); 1679 1680 class _LIBCPP_TEMPLATE_VIS value_compare 1681 : public binary_function<value_type, value_type, bool> 1682 { 1683 friend class multimap; 1684 protected: 1685 key_compare comp; 1686 1687 _LIBCPP_INLINE_VISIBILITY 1688 value_compare(key_compare c) : comp(c) {} 1689 public: 1690 _LIBCPP_INLINE_VISIBILITY 1691 bool operator()(const value_type& __x, const value_type& __y) const 1692 {return comp(__x.first, __y.first);} 1693 }; 1694 1695private: 1696 1697 typedef _VSTD::__value_type<key_type, mapped_type> __value_type; 1698 typedef __map_value_compare<key_type, __value_type, key_compare> __vc; 1699 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, 1700 __value_type>::type __allocator_type; 1701 typedef __tree<__value_type, __vc, __allocator_type> __base; 1702 typedef typename __base::__node_traits __node_traits; 1703 typedef allocator_traits<allocator_type> __alloc_traits; 1704 1705 __base __tree_; 1706 1707public: 1708 typedef typename __alloc_traits::pointer pointer; 1709 typedef typename __alloc_traits::const_pointer const_pointer; 1710 typedef typename __alloc_traits::size_type size_type; 1711 typedef typename __alloc_traits::difference_type difference_type; 1712 typedef __map_iterator<typename __base::iterator> iterator; 1713 typedef __map_const_iterator<typename __base::const_iterator> const_iterator; 1714 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 1715 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 1716 1717#if _LIBCPP_STD_VER > 14 1718 typedef __map_node_handle<typename __base::__node, allocator_type> node_type; 1719#endif 1720 1721 template <class _Key2, class _Value2, class _Comp2, class _Alloc2> 1722 friend class _LIBCPP_TEMPLATE_VIS map; 1723 template <class _Key2, class _Value2, class _Comp2, class _Alloc2> 1724 friend class _LIBCPP_TEMPLATE_VIS multimap; 1725 1726 _LIBCPP_INLINE_VISIBILITY 1727 multimap() 1728 _NOEXCEPT_( 1729 is_nothrow_default_constructible<allocator_type>::value && 1730 is_nothrow_default_constructible<key_compare>::value && 1731 is_nothrow_copy_constructible<key_compare>::value) 1732 : __tree_(__vc(key_compare())) {} 1733 1734 _LIBCPP_INLINE_VISIBILITY 1735 explicit multimap(const key_compare& __comp) 1736 _NOEXCEPT_( 1737 is_nothrow_default_constructible<allocator_type>::value && 1738 is_nothrow_copy_constructible<key_compare>::value) 1739 : __tree_(__vc(__comp)) {} 1740 1741 _LIBCPP_INLINE_VISIBILITY 1742 explicit multimap(const key_compare& __comp, const allocator_type& __a) 1743 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {} 1744 1745 template <class _InputIterator> 1746 _LIBCPP_INLINE_VISIBILITY 1747 multimap(_InputIterator __f, _InputIterator __l, 1748 const key_compare& __comp = key_compare()) 1749 : __tree_(__vc(__comp)) 1750 { 1751 insert(__f, __l); 1752 } 1753 1754 template <class _InputIterator> 1755 _LIBCPP_INLINE_VISIBILITY 1756 multimap(_InputIterator __f, _InputIterator __l, 1757 const key_compare& __comp, const allocator_type& __a) 1758 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) 1759 { 1760 insert(__f, __l); 1761 } 1762 1763#if _LIBCPP_STD_VER > 11 1764 template <class _InputIterator> 1765 _LIBCPP_INLINE_VISIBILITY 1766 multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 1767 : multimap(__f, __l, key_compare(), __a) {} 1768#endif 1769 1770 _LIBCPP_INLINE_VISIBILITY 1771 multimap(const multimap& __m) 1772 : __tree_(__m.__tree_.value_comp(), 1773 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc())) 1774 { 1775 insert(__m.begin(), __m.end()); 1776 } 1777 1778 _LIBCPP_INLINE_VISIBILITY 1779 multimap& operator=(const multimap& __m) 1780 { 1781#ifndef _LIBCPP_CXX03_LANG 1782 __tree_ = __m.__tree_; 1783#else 1784 if (this != &__m) { 1785 __tree_.clear(); 1786 __tree_.value_comp() = __m.__tree_.value_comp(); 1787 __tree_.__copy_assign_alloc(__m.__tree_); 1788 insert(__m.begin(), __m.end()); 1789 } 1790#endif 1791 return *this; 1792 } 1793 1794#ifndef _LIBCPP_CXX03_LANG 1795 1796 _LIBCPP_INLINE_VISIBILITY 1797 multimap(multimap&& __m) 1798 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 1799 : __tree_(_VSTD::move(__m.__tree_)) 1800 { 1801 } 1802 1803 multimap(multimap&& __m, const allocator_type& __a); 1804 1805 _LIBCPP_INLINE_VISIBILITY 1806 multimap& operator=(multimap&& __m) 1807 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 1808 { 1809 __tree_ = _VSTD::move(__m.__tree_); 1810 return *this; 1811 } 1812 1813 _LIBCPP_INLINE_VISIBILITY 1814 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare()) 1815 : __tree_(__vc(__comp)) 1816 { 1817 insert(__il.begin(), __il.end()); 1818 } 1819 1820 _LIBCPP_INLINE_VISIBILITY 1821 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a) 1822 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) 1823 { 1824 insert(__il.begin(), __il.end()); 1825 } 1826 1827#if _LIBCPP_STD_VER > 11 1828 _LIBCPP_INLINE_VISIBILITY 1829 multimap(initializer_list<value_type> __il, const allocator_type& __a) 1830 : multimap(__il, key_compare(), __a) {} 1831#endif 1832 1833 _LIBCPP_INLINE_VISIBILITY 1834 multimap& operator=(initializer_list<value_type> __il) 1835 { 1836 __tree_.__assign_multi(__il.begin(), __il.end()); 1837 return *this; 1838 } 1839 1840#endif // _LIBCPP_CXX03_LANG 1841 1842 _LIBCPP_INLINE_VISIBILITY 1843 explicit multimap(const allocator_type& __a) 1844 : __tree_(typename __base::allocator_type(__a)) 1845 { 1846 } 1847 1848 _LIBCPP_INLINE_VISIBILITY 1849 multimap(const multimap& __m, const allocator_type& __a) 1850 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) 1851 { 1852 insert(__m.begin(), __m.end()); 1853 } 1854 1855 _LIBCPP_INLINE_VISIBILITY 1856 ~multimap() { 1857 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); 1858 } 1859 1860 _LIBCPP_INLINE_VISIBILITY 1861 iterator begin() _NOEXCEPT {return __tree_.begin();} 1862 _LIBCPP_INLINE_VISIBILITY 1863 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 1864 _LIBCPP_INLINE_VISIBILITY 1865 iterator end() _NOEXCEPT {return __tree_.end();} 1866 _LIBCPP_INLINE_VISIBILITY 1867 const_iterator end() const _NOEXCEPT {return __tree_.end();} 1868 1869 _LIBCPP_INLINE_VISIBILITY 1870 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());} 1871 _LIBCPP_INLINE_VISIBILITY 1872 const_reverse_iterator rbegin() const _NOEXCEPT 1873 {return const_reverse_iterator(end());} 1874 _LIBCPP_INLINE_VISIBILITY 1875 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());} 1876 _LIBCPP_INLINE_VISIBILITY 1877 const_reverse_iterator rend() const _NOEXCEPT 1878 {return const_reverse_iterator(begin());} 1879 1880 _LIBCPP_INLINE_VISIBILITY 1881 const_iterator cbegin() const _NOEXCEPT {return begin();} 1882 _LIBCPP_INLINE_VISIBILITY 1883 const_iterator cend() const _NOEXCEPT {return end();} 1884 _LIBCPP_INLINE_VISIBILITY 1885 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 1886 _LIBCPP_INLINE_VISIBILITY 1887 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 1888 1889 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 1890 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 1891 _LIBCPP_INLINE_VISIBILITY 1892 size_type size() const _NOEXCEPT {return __tree_.size();} 1893 _LIBCPP_INLINE_VISIBILITY 1894 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 1895 1896 _LIBCPP_INLINE_VISIBILITY 1897 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());} 1898 _LIBCPP_INLINE_VISIBILITY 1899 key_compare key_comp() const {return __tree_.value_comp().key_comp();} 1900 _LIBCPP_INLINE_VISIBILITY 1901 value_compare value_comp() const 1902 {return value_compare(__tree_.value_comp().key_comp());} 1903 1904#ifndef _LIBCPP_CXX03_LANG 1905 1906 template <class ..._Args> 1907 _LIBCPP_INLINE_VISIBILITY 1908 iterator emplace(_Args&& ...__args) { 1909 return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...); 1910 } 1911 1912 template <class ..._Args> 1913 _LIBCPP_INLINE_VISIBILITY 1914 iterator emplace_hint(const_iterator __p, _Args&& ...__args) { 1915 return __tree_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...); 1916 } 1917 1918 template <class _Pp, 1919 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1920 _LIBCPP_INLINE_VISIBILITY 1921 iterator insert(_Pp&& __p) 1922 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));} 1923 1924 template <class _Pp, 1925 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1926 _LIBCPP_INLINE_VISIBILITY 1927 iterator insert(const_iterator __pos, _Pp&& __p) 1928 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));} 1929 1930 _LIBCPP_INLINE_VISIBILITY 1931 iterator insert(value_type&& __v) 1932 {return __tree_.__insert_multi(_VSTD::move(__v));} 1933 1934 _LIBCPP_INLINE_VISIBILITY 1935 iterator insert(const_iterator __p, value_type&& __v) 1936 {return __tree_.__insert_multi(__p.__i_, _VSTD::move(__v));} 1937 1938 1939 _LIBCPP_INLINE_VISIBILITY 1940 void insert(initializer_list<value_type> __il) 1941 {insert(__il.begin(), __il.end());} 1942 1943#endif // _LIBCPP_CXX03_LANG 1944 1945 _LIBCPP_INLINE_VISIBILITY 1946 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);} 1947 1948 _LIBCPP_INLINE_VISIBILITY 1949 iterator insert(const_iterator __p, const value_type& __v) 1950 {return __tree_.__insert_multi(__p.__i_, __v);} 1951 1952 template <class _InputIterator> 1953 _LIBCPP_INLINE_VISIBILITY 1954 void insert(_InputIterator __f, _InputIterator __l) 1955 { 1956 for (const_iterator __e = cend(); __f != __l; ++__f) 1957 __tree_.__insert_multi(__e.__i_, *__f); 1958 } 1959 1960 _LIBCPP_INLINE_VISIBILITY 1961 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);} 1962 _LIBCPP_INLINE_VISIBILITY 1963 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);} 1964 _LIBCPP_INLINE_VISIBILITY 1965 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} 1966 _LIBCPP_INLINE_VISIBILITY 1967 iterator erase(const_iterator __f, const_iterator __l) 1968 {return __tree_.erase(__f.__i_, __l.__i_);} 1969 1970#if _LIBCPP_STD_VER > 14 1971 _LIBCPP_INLINE_VISIBILITY 1972 iterator insert(node_type&& __nh) 1973 { 1974 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1975 "node_type with incompatible allocator passed to multimap::insert()"); 1976 return __tree_.template __node_handle_insert_multi<node_type>( 1977 _VSTD::move(__nh)); 1978 } 1979 _LIBCPP_INLINE_VISIBILITY 1980 iterator insert(const_iterator __hint, node_type&& __nh) 1981 { 1982 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1983 "node_type with incompatible allocator passed to multimap::insert()"); 1984 return __tree_.template __node_handle_insert_multi<node_type>( 1985 __hint.__i_, _VSTD::move(__nh)); 1986 } 1987 _LIBCPP_INLINE_VISIBILITY 1988 node_type extract(key_type const& __key) 1989 { 1990 return __tree_.template __node_handle_extract<node_type>(__key); 1991 } 1992 _LIBCPP_INLINE_VISIBILITY 1993 node_type extract(const_iterator __it) 1994 { 1995 return __tree_.template __node_handle_extract<node_type>( 1996 __it.__i_); 1997 } 1998 template <class _Compare2> 1999 _LIBCPP_INLINE_VISIBILITY 2000 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source) 2001 { 2002 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 2003 "merging container with incompatible allocator"); 2004 return __tree_.__node_handle_merge_multi(__source.__tree_); 2005 } 2006 template <class _Compare2> 2007 _LIBCPP_INLINE_VISIBILITY 2008 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source) 2009 { 2010 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 2011 "merging container with incompatible allocator"); 2012 return __tree_.__node_handle_merge_multi(__source.__tree_); 2013 } 2014 template <class _Compare2> 2015 _LIBCPP_INLINE_VISIBILITY 2016 void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source) 2017 { 2018 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 2019 "merging container with incompatible allocator"); 2020 return __tree_.__node_handle_merge_multi(__source.__tree_); 2021 } 2022 template <class _Compare2> 2023 _LIBCPP_INLINE_VISIBILITY 2024 void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source) 2025 { 2026 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 2027 "merging container with incompatible allocator"); 2028 return __tree_.__node_handle_merge_multi(__source.__tree_); 2029 } 2030#endif 2031 2032 _LIBCPP_INLINE_VISIBILITY 2033 void clear() _NOEXCEPT {__tree_.clear();} 2034 2035 _LIBCPP_INLINE_VISIBILITY 2036 void swap(multimap& __m) 2037 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 2038 {__tree_.swap(__m.__tree_);} 2039 2040 _LIBCPP_INLINE_VISIBILITY 2041 iterator find(const key_type& __k) {return __tree_.find(__k);} 2042 _LIBCPP_INLINE_VISIBILITY 2043 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 2044#if _LIBCPP_STD_VER > 11 2045 template <typename _K2> 2046 _LIBCPP_INLINE_VISIBILITY 2047 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 2048 find(const _K2& __k) {return __tree_.find(__k);} 2049 template <typename _K2> 2050 _LIBCPP_INLINE_VISIBILITY 2051 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 2052 find(const _K2& __k) const {return __tree_.find(__k);} 2053#endif 2054 2055 _LIBCPP_INLINE_VISIBILITY 2056 size_type count(const key_type& __k) const 2057 {return __tree_.__count_multi(__k);} 2058#if _LIBCPP_STD_VER > 11 2059 template <typename _K2> 2060 _LIBCPP_INLINE_VISIBILITY 2061 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 2062 count(const _K2& __k) const {return __tree_.__count_multi(__k);} 2063#endif 2064 2065#if _LIBCPP_STD_VER > 17 2066 _LIBCPP_INLINE_VISIBILITY 2067 bool contains(const key_type& __k) const {return find(__k) != end();} 2068#endif // _LIBCPP_STD_VER > 17 2069 2070 _LIBCPP_INLINE_VISIBILITY 2071 iterator lower_bound(const key_type& __k) 2072 {return __tree_.lower_bound(__k);} 2073 _LIBCPP_INLINE_VISIBILITY 2074 const_iterator lower_bound(const key_type& __k) const 2075 {return __tree_.lower_bound(__k);} 2076#if _LIBCPP_STD_VER > 11 2077 template <typename _K2> 2078 _LIBCPP_INLINE_VISIBILITY 2079 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 2080 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 2081 2082 template <typename _K2> 2083 _LIBCPP_INLINE_VISIBILITY 2084 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 2085 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 2086#endif 2087 2088 _LIBCPP_INLINE_VISIBILITY 2089 iterator upper_bound(const key_type& __k) 2090 {return __tree_.upper_bound(__k);} 2091 _LIBCPP_INLINE_VISIBILITY 2092 const_iterator upper_bound(const key_type& __k) const 2093 {return __tree_.upper_bound(__k);} 2094#if _LIBCPP_STD_VER > 11 2095 template <typename _K2> 2096 _LIBCPP_INLINE_VISIBILITY 2097 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 2098 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 2099 template <typename _K2> 2100 _LIBCPP_INLINE_VISIBILITY 2101 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 2102 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 2103#endif 2104 2105 _LIBCPP_INLINE_VISIBILITY 2106 pair<iterator,iterator> equal_range(const key_type& __k) 2107 {return __tree_.__equal_range_multi(__k);} 2108 _LIBCPP_INLINE_VISIBILITY 2109 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 2110 {return __tree_.__equal_range_multi(__k);} 2111#if _LIBCPP_STD_VER > 11 2112 template <typename _K2> 2113 _LIBCPP_INLINE_VISIBILITY 2114 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 2115 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 2116 template <typename _K2> 2117 _LIBCPP_INLINE_VISIBILITY 2118 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 2119 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 2120#endif 2121 2122private: 2123 typedef typename __base::__node __node; 2124 typedef typename __base::__node_allocator __node_allocator; 2125 typedef typename __base::__node_pointer __node_pointer; 2126 2127 typedef __map_node_destructor<__node_allocator> _Dp; 2128 typedef unique_ptr<__node, _Dp> __node_holder; 2129}; 2130 2131#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES 2132template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>, 2133 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, 2134 class = _EnableIf<!__is_allocator<_Compare>::value, void>, 2135 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 2136multimap(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) 2137 -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>; 2138 2139template<class _Key, class _Tp, class _Compare = less<remove_const_t<_Key>>, 2140 class _Allocator = allocator<pair<const _Key, _Tp>>, 2141 class = _EnableIf<!__is_allocator<_Compare>::value, void>, 2142 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 2143multimap(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator()) 2144 -> multimap<remove_const_t<_Key>, _Tp, _Compare, _Allocator>; 2145 2146template<class _InputIterator, class _Allocator, 2147 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 2148multimap(_InputIterator, _InputIterator, _Allocator) 2149 -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, 2150 less<__iter_key_type<_InputIterator>>, _Allocator>; 2151 2152template<class _Key, class _Tp, class _Allocator, 2153 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 2154multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) 2155 -> multimap<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>; 2156#endif 2157 2158#ifndef _LIBCPP_CXX03_LANG 2159template <class _Key, class _Tp, class _Compare, class _Allocator> 2160multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a) 2161 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a)) 2162{ 2163 if (__a != __m.get_allocator()) 2164 { 2165 const_iterator __e = cend(); 2166 while (!__m.empty()) 2167 __tree_.__insert_multi(__e.__i_, 2168 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__move())); 2169 } 2170} 2171#endif 2172 2173template <class _Key, class _Tp, class _Compare, class _Allocator> 2174inline _LIBCPP_INLINE_VISIBILITY 2175bool 2176operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2177 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2178{ 2179 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 2180} 2181 2182template <class _Key, class _Tp, class _Compare, class _Allocator> 2183inline _LIBCPP_INLINE_VISIBILITY 2184bool 2185operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2186 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2187{ 2188 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 2189} 2190 2191template <class _Key, class _Tp, class _Compare, class _Allocator> 2192inline _LIBCPP_INLINE_VISIBILITY 2193bool 2194operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2195 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2196{ 2197 return !(__x == __y); 2198} 2199 2200template <class _Key, class _Tp, class _Compare, class _Allocator> 2201inline _LIBCPP_INLINE_VISIBILITY 2202bool 2203operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2204 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2205{ 2206 return __y < __x; 2207} 2208 2209template <class _Key, class _Tp, class _Compare, class _Allocator> 2210inline _LIBCPP_INLINE_VISIBILITY 2211bool 2212operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2213 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2214{ 2215 return !(__x < __y); 2216} 2217 2218template <class _Key, class _Tp, class _Compare, class _Allocator> 2219inline _LIBCPP_INLINE_VISIBILITY 2220bool 2221operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2222 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2223{ 2224 return !(__y < __x); 2225} 2226 2227template <class _Key, class _Tp, class _Compare, class _Allocator> 2228inline _LIBCPP_INLINE_VISIBILITY 2229void 2230swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2231 multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2232 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2233{ 2234 __x.swap(__y); 2235} 2236 2237#if _LIBCPP_STD_VER > 17 2238template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate> 2239inline _LIBCPP_INLINE_VISIBILITY 2240void erase_if(multimap<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) 2241{ __libcpp_erase_if_container(__c, __pred); } 2242#endif 2243 2244_LIBCPP_END_NAMESPACE_STD 2245 2246#endif // _LIBCPP_MAP 2247