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