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(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); 911 static_assert((is_same<typename allocator_type::value_type, value_type>::value), 912 "Allocator::value_type must be same type as value_type"); 913 914 class _LIBCPP_TEMPLATE_VIS value_compare 915 : public binary_function<value_type, value_type, bool> 916 { 917 friend class map; 918 protected: 919 key_compare comp; 920 921 _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {} 922 public: 923 _LIBCPP_INLINE_VISIBILITY 924 bool operator()(const value_type& __x, const value_type& __y) const 925 {return comp(__x.first, __y.first);} 926 }; 927 928private: 929 930 typedef _VSTD::__value_type<key_type, mapped_type> __value_type; 931 typedef __map_value_compare<key_type, __value_type, key_compare> __vc; 932 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, 933 __value_type>::type __allocator_type; 934 typedef __tree<__value_type, __vc, __allocator_type> __base; 935 typedef typename __base::__node_traits __node_traits; 936 typedef allocator_traits<allocator_type> __alloc_traits; 937 938 __base __tree_; 939 940public: 941 typedef typename __alloc_traits::pointer pointer; 942 typedef typename __alloc_traits::const_pointer const_pointer; 943 typedef typename __alloc_traits::size_type size_type; 944 typedef typename __alloc_traits::difference_type difference_type; 945 typedef __map_iterator<typename __base::iterator> iterator; 946 typedef __map_const_iterator<typename __base::const_iterator> const_iterator; 947 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 948 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 949 950#if _LIBCPP_STD_VER > 14 951 typedef __map_node_handle<typename __base::__node, allocator_type> node_type; 952 typedef __insert_return_type<iterator, node_type> insert_return_type; 953#endif 954 955 template <class _Key2, class _Value2, class _Comp2, class _Alloc2> 956 friend class _LIBCPP_TEMPLATE_VIS map; 957 template <class _Key2, class _Value2, class _Comp2, class _Alloc2> 958 friend class _LIBCPP_TEMPLATE_VIS multimap; 959 960 _LIBCPP_INLINE_VISIBILITY 961 map() 962 _NOEXCEPT_( 963 is_nothrow_default_constructible<allocator_type>::value && 964 is_nothrow_default_constructible<key_compare>::value && 965 is_nothrow_copy_constructible<key_compare>::value) 966 : __tree_(__vc(key_compare())) {} 967 968 _LIBCPP_INLINE_VISIBILITY 969 explicit map(const key_compare& __comp) 970 _NOEXCEPT_( 971 is_nothrow_default_constructible<allocator_type>::value && 972 is_nothrow_copy_constructible<key_compare>::value) 973 : __tree_(__vc(__comp)) {} 974 975 _LIBCPP_INLINE_VISIBILITY 976 explicit map(const key_compare& __comp, const allocator_type& __a) 977 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {} 978 979 template <class _InputIterator> 980 _LIBCPP_INLINE_VISIBILITY 981 map(_InputIterator __f, _InputIterator __l, 982 const key_compare& __comp = key_compare()) 983 : __tree_(__vc(__comp)) 984 { 985 insert(__f, __l); 986 } 987 988 template <class _InputIterator> 989 _LIBCPP_INLINE_VISIBILITY 990 map(_InputIterator __f, _InputIterator __l, 991 const key_compare& __comp, const allocator_type& __a) 992 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) 993 { 994 insert(__f, __l); 995 } 996 997#if _LIBCPP_STD_VER > 11 998 template <class _InputIterator> 999 _LIBCPP_INLINE_VISIBILITY 1000 map(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 1001 : map(__f, __l, key_compare(), __a) {} 1002#endif 1003 1004 _LIBCPP_INLINE_VISIBILITY 1005 map(const map& __m) 1006 : __tree_(__m.__tree_) 1007 { 1008 insert(__m.begin(), __m.end()); 1009 } 1010 1011 _LIBCPP_INLINE_VISIBILITY 1012 map& operator=(const map& __m) 1013 { 1014#ifndef _LIBCPP_CXX03_LANG 1015 __tree_ = __m.__tree_; 1016#else 1017 if (this != &__m) { 1018 __tree_.clear(); 1019 __tree_.value_comp() = __m.__tree_.value_comp(); 1020 __tree_.__copy_assign_alloc(__m.__tree_); 1021 insert(__m.begin(), __m.end()); 1022 } 1023#endif 1024 return *this; 1025 } 1026 1027#ifndef _LIBCPP_CXX03_LANG 1028 1029 _LIBCPP_INLINE_VISIBILITY 1030 map(map&& __m) 1031 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 1032 : __tree_(_VSTD::move(__m.__tree_)) 1033 { 1034 } 1035 1036 map(map&& __m, const allocator_type& __a); 1037 1038 _LIBCPP_INLINE_VISIBILITY 1039 map& operator=(map&& __m) 1040 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 1041 { 1042 __tree_ = _VSTD::move(__m.__tree_); 1043 return *this; 1044 } 1045 1046 _LIBCPP_INLINE_VISIBILITY 1047 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare()) 1048 : __tree_(__vc(__comp)) 1049 { 1050 insert(__il.begin(), __il.end()); 1051 } 1052 1053 _LIBCPP_INLINE_VISIBILITY 1054 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a) 1055 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) 1056 { 1057 insert(__il.begin(), __il.end()); 1058 } 1059 1060#if _LIBCPP_STD_VER > 11 1061 _LIBCPP_INLINE_VISIBILITY 1062 map(initializer_list<value_type> __il, const allocator_type& __a) 1063 : map(__il, key_compare(), __a) {} 1064#endif 1065 1066 _LIBCPP_INLINE_VISIBILITY 1067 map& operator=(initializer_list<value_type> __il) 1068 { 1069 __tree_.__assign_unique(__il.begin(), __il.end()); 1070 return *this; 1071 } 1072 1073#endif // _LIBCPP_CXX03_LANG 1074 1075 _LIBCPP_INLINE_VISIBILITY 1076 explicit map(const allocator_type& __a) 1077 : __tree_(typename __base::allocator_type(__a)) 1078 { 1079 } 1080 1081 _LIBCPP_INLINE_VISIBILITY 1082 map(const map& __m, const allocator_type& __a) 1083 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) 1084 { 1085 insert(__m.begin(), __m.end()); 1086 } 1087 1088 _LIBCPP_INLINE_VISIBILITY 1089 iterator begin() _NOEXCEPT {return __tree_.begin();} 1090 _LIBCPP_INLINE_VISIBILITY 1091 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 1092 _LIBCPP_INLINE_VISIBILITY 1093 iterator end() _NOEXCEPT {return __tree_.end();} 1094 _LIBCPP_INLINE_VISIBILITY 1095 const_iterator end() const _NOEXCEPT {return __tree_.end();} 1096 1097 _LIBCPP_INLINE_VISIBILITY 1098 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());} 1099 _LIBCPP_INLINE_VISIBILITY 1100 const_reverse_iterator rbegin() const _NOEXCEPT 1101 {return const_reverse_iterator(end());} 1102 _LIBCPP_INLINE_VISIBILITY 1103 reverse_iterator rend() _NOEXCEPT 1104 {return reverse_iterator(begin());} 1105 _LIBCPP_INLINE_VISIBILITY 1106 const_reverse_iterator rend() const _NOEXCEPT 1107 {return const_reverse_iterator(begin());} 1108 1109 _LIBCPP_INLINE_VISIBILITY 1110 const_iterator cbegin() const _NOEXCEPT {return begin();} 1111 _LIBCPP_INLINE_VISIBILITY 1112 const_iterator cend() const _NOEXCEPT {return end();} 1113 _LIBCPP_INLINE_VISIBILITY 1114 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 1115 _LIBCPP_INLINE_VISIBILITY 1116 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 1117 1118 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 1119 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 1120 _LIBCPP_INLINE_VISIBILITY 1121 size_type size() const _NOEXCEPT {return __tree_.size();} 1122 _LIBCPP_INLINE_VISIBILITY 1123 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 1124 1125 mapped_type& operator[](const key_type& __k); 1126#ifndef _LIBCPP_CXX03_LANG 1127 mapped_type& operator[](key_type&& __k); 1128#endif 1129 1130 mapped_type& at(const key_type& __k); 1131 const mapped_type& at(const key_type& __k) const; 1132 1133 _LIBCPP_INLINE_VISIBILITY 1134 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());} 1135 _LIBCPP_INLINE_VISIBILITY 1136 key_compare key_comp() const {return __tree_.value_comp().key_comp();} 1137 _LIBCPP_INLINE_VISIBILITY 1138 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());} 1139 1140#ifndef _LIBCPP_CXX03_LANG 1141 template <class ..._Args> 1142 _LIBCPP_INLINE_VISIBILITY 1143 pair<iterator, bool> emplace(_Args&& ...__args) { 1144 return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...); 1145 } 1146 1147 template <class ..._Args> 1148 _LIBCPP_INLINE_VISIBILITY 1149 iterator emplace_hint(const_iterator __p, _Args&& ...__args) { 1150 return __tree_.__emplace_hint_unique(__p.__i_, _VSTD::forward<_Args>(__args)...); 1151 } 1152 1153 template <class _Pp, 1154 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1155 _LIBCPP_INLINE_VISIBILITY 1156 pair<iterator, bool> insert(_Pp&& __p) 1157 {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));} 1158 1159 template <class _Pp, 1160 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1161 _LIBCPP_INLINE_VISIBILITY 1162 iterator insert(const_iterator __pos, _Pp&& __p) 1163 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));} 1164 1165#endif // _LIBCPP_CXX03_LANG 1166 1167 _LIBCPP_INLINE_VISIBILITY 1168 pair<iterator, bool> 1169 insert(const value_type& __v) {return __tree_.__insert_unique(__v);} 1170 1171 _LIBCPP_INLINE_VISIBILITY 1172 iterator 1173 insert(const_iterator __p, const value_type& __v) 1174 {return __tree_.__insert_unique(__p.__i_, __v);} 1175 1176#ifndef _LIBCPP_CXX03_LANG 1177 _LIBCPP_INLINE_VISIBILITY 1178 pair<iterator, bool> 1179 insert(value_type&& __v) {return __tree_.__insert_unique(_VSTD::move(__v));} 1180 1181 _LIBCPP_INLINE_VISIBILITY 1182 iterator insert(const_iterator __p, value_type&& __v) 1183 {return __tree_.__insert_unique(__p.__i_, _VSTD::move(__v));} 1184 1185 _LIBCPP_INLINE_VISIBILITY 1186 void insert(initializer_list<value_type> __il) 1187 {insert(__il.begin(), __il.end());} 1188#endif 1189 1190 template <class _InputIterator> 1191 _LIBCPP_INLINE_VISIBILITY 1192 void insert(_InputIterator __f, _InputIterator __l) 1193 { 1194 for (const_iterator __e = cend(); __f != __l; ++__f) 1195 insert(__e.__i_, *__f); 1196 } 1197 1198#if _LIBCPP_STD_VER > 14 1199 1200 template <class... _Args> 1201 _LIBCPP_INLINE_VISIBILITY 1202 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) 1203 { 1204 return __tree_.__emplace_unique_key_args(__k, 1205 _VSTD::piecewise_construct, 1206 _VSTD::forward_as_tuple(__k), 1207 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); 1208 } 1209 1210 template <class... _Args> 1211 _LIBCPP_INLINE_VISIBILITY 1212 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) 1213 { 1214 return __tree_.__emplace_unique_key_args(__k, 1215 _VSTD::piecewise_construct, 1216 _VSTD::forward_as_tuple(_VSTD::move(__k)), 1217 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); 1218 } 1219 1220 template <class... _Args> 1221 _LIBCPP_INLINE_VISIBILITY 1222 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args) 1223 { 1224 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, 1225 _VSTD::piecewise_construct, 1226 _VSTD::forward_as_tuple(__k), 1227 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); 1228 } 1229 1230 template <class... _Args> 1231 _LIBCPP_INLINE_VISIBILITY 1232 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) 1233 { 1234 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, 1235 _VSTD::piecewise_construct, 1236 _VSTD::forward_as_tuple(_VSTD::move(__k)), 1237 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); 1238 } 1239 1240 template <class _Vp> 1241 _LIBCPP_INLINE_VISIBILITY 1242 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) 1243 { 1244 iterator __p = lower_bound(__k); 1245 if ( __p != end() && !key_comp()(__k, __p->first)) 1246 { 1247 __p->second = _VSTD::forward<_Vp>(__v); 1248 return _VSTD::make_pair(__p, false); 1249 } 1250 return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true); 1251 } 1252 1253 template <class _Vp> 1254 _LIBCPP_INLINE_VISIBILITY 1255 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) 1256 { 1257 iterator __p = lower_bound(__k); 1258 if ( __p != end() && !key_comp()(__k, __p->first)) 1259 { 1260 __p->second = _VSTD::forward<_Vp>(__v); 1261 return _VSTD::make_pair(__p, false); 1262 } 1263 return _VSTD::make_pair(emplace_hint(__p, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)), true); 1264 } 1265 1266 template <class _Vp> 1267 _LIBCPP_INLINE_VISIBILITY 1268 iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v) 1269 { 1270 iterator __p = lower_bound(__k); 1271 if ( __p != end() && !key_comp()(__k, __p->first)) 1272 { 1273 __p->second = _VSTD::forward<_Vp>(__v); 1274 return __p; 1275 } 1276 return emplace_hint(__h, __k, _VSTD::forward<_Vp>(__v)); 1277 } 1278 1279 template <class _Vp> 1280 _LIBCPP_INLINE_VISIBILITY 1281 iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v) 1282 { 1283 iterator __p = lower_bound(__k); 1284 if ( __p != end() && !key_comp()(__k, __p->first)) 1285 { 1286 __p->second = _VSTD::forward<_Vp>(__v); 1287 return __p; 1288 } 1289 return emplace_hint(__h, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)); 1290 } 1291 1292#endif // _LIBCPP_STD_VER > 14 1293 1294 _LIBCPP_INLINE_VISIBILITY 1295 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);} 1296 _LIBCPP_INLINE_VISIBILITY 1297 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);} 1298 _LIBCPP_INLINE_VISIBILITY 1299 size_type erase(const key_type& __k) 1300 {return __tree_.__erase_unique(__k);} 1301 _LIBCPP_INLINE_VISIBILITY 1302 iterator erase(const_iterator __f, const_iterator __l) 1303 {return __tree_.erase(__f.__i_, __l.__i_);} 1304 _LIBCPP_INLINE_VISIBILITY 1305 void clear() _NOEXCEPT {__tree_.clear();} 1306 1307#if _LIBCPP_STD_VER > 14 1308 _LIBCPP_INLINE_VISIBILITY 1309 insert_return_type insert(node_type&& __nh) 1310 { 1311 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1312 "node_type with incompatible allocator passed to map::insert()"); 1313 return __tree_.template __node_handle_insert_unique< 1314 node_type, insert_return_type>(_VSTD::move(__nh)); 1315 } 1316 _LIBCPP_INLINE_VISIBILITY 1317 iterator insert(const_iterator __hint, node_type&& __nh) 1318 { 1319 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1320 "node_type with incompatible allocator passed to map::insert()"); 1321 return __tree_.template __node_handle_insert_unique<node_type>( 1322 __hint.__i_, _VSTD::move(__nh)); 1323 } 1324 _LIBCPP_INLINE_VISIBILITY 1325 node_type extract(key_type const& __key) 1326 { 1327 return __tree_.template __node_handle_extract<node_type>(__key); 1328 } 1329 _LIBCPP_INLINE_VISIBILITY 1330 node_type extract(const_iterator __it) 1331 { 1332 return __tree_.template __node_handle_extract<node_type>(__it.__i_); 1333 } 1334 template <class _Compare2> 1335 _LIBCPP_INLINE_VISIBILITY 1336 void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source) 1337 { 1338 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1339 "merging container with incompatible allocator"); 1340 __tree_.__node_handle_merge_unique(__source.__tree_); 1341 } 1342 template <class _Compare2> 1343 _LIBCPP_INLINE_VISIBILITY 1344 void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source) 1345 { 1346 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1347 "merging container with incompatible allocator"); 1348 __tree_.__node_handle_merge_unique(__source.__tree_); 1349 } 1350 template <class _Compare2> 1351 _LIBCPP_INLINE_VISIBILITY 1352 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source) 1353 { 1354 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1355 "merging container with incompatible allocator"); 1356 __tree_.__node_handle_merge_unique(__source.__tree_); 1357 } 1358 template <class _Compare2> 1359 _LIBCPP_INLINE_VISIBILITY 1360 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source) 1361 { 1362 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1363 "merging container with incompatible allocator"); 1364 __tree_.__node_handle_merge_unique(__source.__tree_); 1365 } 1366#endif 1367 1368 _LIBCPP_INLINE_VISIBILITY 1369 void swap(map& __m) 1370 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 1371 {__tree_.swap(__m.__tree_);} 1372 1373 _LIBCPP_INLINE_VISIBILITY 1374 iterator find(const key_type& __k) {return __tree_.find(__k);} 1375 _LIBCPP_INLINE_VISIBILITY 1376 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 1377#if _LIBCPP_STD_VER > 11 1378 template <typename _K2> 1379 _LIBCPP_INLINE_VISIBILITY 1380 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 1381 find(const _K2& __k) {return __tree_.find(__k);} 1382 template <typename _K2> 1383 _LIBCPP_INLINE_VISIBILITY 1384 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 1385 find(const _K2& __k) const {return __tree_.find(__k);} 1386#endif 1387 1388 _LIBCPP_INLINE_VISIBILITY 1389 size_type count(const key_type& __k) const 1390 {return __tree_.__count_unique(__k);} 1391#if _LIBCPP_STD_VER > 11 1392 template <typename _K2> 1393 _LIBCPP_INLINE_VISIBILITY 1394 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 1395 count(const _K2& __k) const {return __tree_.__count_multi(__k);} 1396#endif 1397 _LIBCPP_INLINE_VISIBILITY 1398 iterator lower_bound(const key_type& __k) 1399 {return __tree_.lower_bound(__k);} 1400 _LIBCPP_INLINE_VISIBILITY 1401 const_iterator lower_bound(const key_type& __k) const 1402 {return __tree_.lower_bound(__k);} 1403#if _LIBCPP_STD_VER > 11 1404 template <typename _K2> 1405 _LIBCPP_INLINE_VISIBILITY 1406 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 1407 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 1408 1409 template <typename _K2> 1410 _LIBCPP_INLINE_VISIBILITY 1411 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 1412 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 1413#endif 1414 1415 _LIBCPP_INLINE_VISIBILITY 1416 iterator upper_bound(const key_type& __k) 1417 {return __tree_.upper_bound(__k);} 1418 _LIBCPP_INLINE_VISIBILITY 1419 const_iterator upper_bound(const key_type& __k) const 1420 {return __tree_.upper_bound(__k);} 1421#if _LIBCPP_STD_VER > 11 1422 template <typename _K2> 1423 _LIBCPP_INLINE_VISIBILITY 1424 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 1425 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 1426 template <typename _K2> 1427 _LIBCPP_INLINE_VISIBILITY 1428 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 1429 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 1430#endif 1431 1432 _LIBCPP_INLINE_VISIBILITY 1433 pair<iterator,iterator> equal_range(const key_type& __k) 1434 {return __tree_.__equal_range_unique(__k);} 1435 _LIBCPP_INLINE_VISIBILITY 1436 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 1437 {return __tree_.__equal_range_unique(__k);} 1438#if _LIBCPP_STD_VER > 11 1439 template <typename _K2> 1440 _LIBCPP_INLINE_VISIBILITY 1441 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 1442 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 1443 template <typename _K2> 1444 _LIBCPP_INLINE_VISIBILITY 1445 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 1446 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 1447#endif 1448 1449private: 1450 typedef typename __base::__node __node; 1451 typedef typename __base::__node_allocator __node_allocator; 1452 typedef typename __base::__node_pointer __node_pointer; 1453 typedef typename __base::__node_base_pointer __node_base_pointer; 1454 typedef typename __base::__parent_pointer __parent_pointer; 1455 1456 typedef __map_node_destructor<__node_allocator> _Dp; 1457 typedef unique_ptr<__node, _Dp> __node_holder; 1458 1459#ifdef _LIBCPP_CXX03_LANG 1460 __node_holder __construct_node_with_key(const key_type& __k); 1461#endif 1462}; 1463 1464 1465#ifndef _LIBCPP_CXX03_LANG 1466template <class _Key, class _Tp, class _Compare, class _Allocator> 1467map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a) 1468 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a)) 1469{ 1470 if (__a != __m.get_allocator()) 1471 { 1472 const_iterator __e = cend(); 1473 while (!__m.empty()) 1474 __tree_.__insert_unique(__e.__i_, 1475 __m.__tree_.remove(__m.begin().__i_)->__value_.__move()); 1476 } 1477} 1478 1479template <class _Key, class _Tp, class _Compare, class _Allocator> 1480_Tp& 1481map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) 1482{ 1483 return __tree_.__emplace_unique_key_args(__k, 1484 _VSTD::piecewise_construct, 1485 _VSTD::forward_as_tuple(__k), 1486 _VSTD::forward_as_tuple()).first->__get_value().second; 1487} 1488 1489template <class _Key, class _Tp, class _Compare, class _Allocator> 1490_Tp& 1491map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k) 1492{ 1493 return __tree_.__emplace_unique_key_args(__k, 1494 _VSTD::piecewise_construct, 1495 _VSTD::forward_as_tuple(_VSTD::move(__k)), 1496 _VSTD::forward_as_tuple()).first->__get_value().second; 1497} 1498 1499#else // _LIBCPP_CXX03_LANG 1500 1501template <class _Key, class _Tp, class _Compare, class _Allocator> 1502typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder 1503map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k) 1504{ 1505 __node_allocator& __na = __tree_.__node_alloc(); 1506 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1507 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().first), __k); 1508 __h.get_deleter().__first_constructed = true; 1509 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().second)); 1510 __h.get_deleter().__second_constructed = true; 1511 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03 1512} 1513 1514template <class _Key, class _Tp, class _Compare, class _Allocator> 1515_Tp& 1516map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) 1517{ 1518 __parent_pointer __parent; 1519 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k); 1520 __node_pointer __r = static_cast<__node_pointer>(__child); 1521 if (__child == nullptr) 1522 { 1523 __node_holder __h = __construct_node_with_key(__k); 1524 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1525 __r = __h.release(); 1526 } 1527 return __r->__value_.__get_value().second; 1528} 1529 1530#endif // _LIBCPP_CXX03_LANG 1531 1532template <class _Key, class _Tp, class _Compare, class _Allocator> 1533_Tp& 1534map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) 1535{ 1536 __parent_pointer __parent; 1537 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k); 1538 if (__child == nullptr) 1539 __throw_out_of_range("map::at: key not found"); 1540 return static_cast<__node_pointer>(__child)->__value_.__get_value().second; 1541} 1542 1543template <class _Key, class _Tp, class _Compare, class _Allocator> 1544const _Tp& 1545map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const 1546{ 1547 __parent_pointer __parent; 1548 __node_base_pointer __child = __tree_.__find_equal(__parent, __k); 1549 if (__child == nullptr) 1550 __throw_out_of_range("map::at: key not found"); 1551 return static_cast<__node_pointer>(__child)->__value_.__get_value().second; 1552} 1553 1554 1555template <class _Key, class _Tp, class _Compare, class _Allocator> 1556inline _LIBCPP_INLINE_VISIBILITY 1557bool 1558operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1559 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1560{ 1561 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 1562} 1563 1564template <class _Key, class _Tp, class _Compare, class _Allocator> 1565inline _LIBCPP_INLINE_VISIBILITY 1566bool 1567operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x, 1568 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1569{ 1570 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 1571} 1572 1573template <class _Key, class _Tp, class _Compare, class _Allocator> 1574inline _LIBCPP_INLINE_VISIBILITY 1575bool 1576operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1577 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1578{ 1579 return !(__x == __y); 1580} 1581 1582template <class _Key, class _Tp, class _Compare, class _Allocator> 1583inline _LIBCPP_INLINE_VISIBILITY 1584bool 1585operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x, 1586 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1587{ 1588 return __y < __x; 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 < __y); 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 !(__y < __x); 1607} 1608 1609template <class _Key, class _Tp, class _Compare, class _Allocator> 1610inline _LIBCPP_INLINE_VISIBILITY 1611void 1612swap(map<_Key, _Tp, _Compare, _Allocator>& __x, 1613 map<_Key, _Tp, _Compare, _Allocator>& __y) 1614 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1615{ 1616 __x.swap(__y); 1617} 1618 1619#if _LIBCPP_STD_VER > 17 1620template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate> 1621inline _LIBCPP_INLINE_VISIBILITY 1622void erase_if(map<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) 1623{ __libcpp_erase_if_container(__c, __pred); } 1624#endif 1625 1626 1627template <class _Key, class _Tp, class _Compare = less<_Key>, 1628 class _Allocator = allocator<pair<const _Key, _Tp> > > 1629class _LIBCPP_TEMPLATE_VIS multimap 1630{ 1631public: 1632 // types: 1633 typedef _Key key_type; 1634 typedef _Tp mapped_type; 1635 typedef pair<const key_type, mapped_type> value_type; 1636 typedef _Compare key_compare; 1637 typedef _Allocator allocator_type; 1638 typedef value_type& reference; 1639 typedef const value_type& const_reference; 1640 1641 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); 1642 static_assert((is_same<typename allocator_type::value_type, value_type>::value), 1643 "Allocator::value_type must be same type as value_type"); 1644 1645 class _LIBCPP_TEMPLATE_VIS value_compare 1646 : public binary_function<value_type, value_type, bool> 1647 { 1648 friend class multimap; 1649 protected: 1650 key_compare comp; 1651 1652 _LIBCPP_INLINE_VISIBILITY 1653 value_compare(key_compare c) : comp(c) {} 1654 public: 1655 _LIBCPP_INLINE_VISIBILITY 1656 bool operator()(const value_type& __x, const value_type& __y) const 1657 {return comp(__x.first, __y.first);} 1658 }; 1659 1660private: 1661 1662 typedef _VSTD::__value_type<key_type, mapped_type> __value_type; 1663 typedef __map_value_compare<key_type, __value_type, key_compare> __vc; 1664 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, 1665 __value_type>::type __allocator_type; 1666 typedef __tree<__value_type, __vc, __allocator_type> __base; 1667 typedef typename __base::__node_traits __node_traits; 1668 typedef allocator_traits<allocator_type> __alloc_traits; 1669 1670 __base __tree_; 1671 1672public: 1673 typedef typename __alloc_traits::pointer pointer; 1674 typedef typename __alloc_traits::const_pointer const_pointer; 1675 typedef typename __alloc_traits::size_type size_type; 1676 typedef typename __alloc_traits::difference_type difference_type; 1677 typedef __map_iterator<typename __base::iterator> iterator; 1678 typedef __map_const_iterator<typename __base::const_iterator> const_iterator; 1679 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 1680 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 1681 1682#if _LIBCPP_STD_VER > 14 1683 typedef __map_node_handle<typename __base::__node, allocator_type> node_type; 1684#endif 1685 1686 template <class _Key2, class _Value2, class _Comp2, class _Alloc2> 1687 friend class _LIBCPP_TEMPLATE_VIS map; 1688 template <class _Key2, class _Value2, class _Comp2, class _Alloc2> 1689 friend class _LIBCPP_TEMPLATE_VIS multimap; 1690 1691 _LIBCPP_INLINE_VISIBILITY 1692 multimap() 1693 _NOEXCEPT_( 1694 is_nothrow_default_constructible<allocator_type>::value && 1695 is_nothrow_default_constructible<key_compare>::value && 1696 is_nothrow_copy_constructible<key_compare>::value) 1697 : __tree_(__vc(key_compare())) {} 1698 1699 _LIBCPP_INLINE_VISIBILITY 1700 explicit multimap(const key_compare& __comp) 1701 _NOEXCEPT_( 1702 is_nothrow_default_constructible<allocator_type>::value && 1703 is_nothrow_copy_constructible<key_compare>::value) 1704 : __tree_(__vc(__comp)) {} 1705 1706 _LIBCPP_INLINE_VISIBILITY 1707 explicit multimap(const key_compare& __comp, const allocator_type& __a) 1708 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {} 1709 1710 template <class _InputIterator> 1711 _LIBCPP_INLINE_VISIBILITY 1712 multimap(_InputIterator __f, _InputIterator __l, 1713 const key_compare& __comp = key_compare()) 1714 : __tree_(__vc(__comp)) 1715 { 1716 insert(__f, __l); 1717 } 1718 1719 template <class _InputIterator> 1720 _LIBCPP_INLINE_VISIBILITY 1721 multimap(_InputIterator __f, _InputIterator __l, 1722 const key_compare& __comp, const allocator_type& __a) 1723 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) 1724 { 1725 insert(__f, __l); 1726 } 1727 1728#if _LIBCPP_STD_VER > 11 1729 template <class _InputIterator> 1730 _LIBCPP_INLINE_VISIBILITY 1731 multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 1732 : multimap(__f, __l, key_compare(), __a) {} 1733#endif 1734 1735 _LIBCPP_INLINE_VISIBILITY 1736 multimap(const multimap& __m) 1737 : __tree_(__m.__tree_.value_comp(), 1738 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc())) 1739 { 1740 insert(__m.begin(), __m.end()); 1741 } 1742 1743 _LIBCPP_INLINE_VISIBILITY 1744 multimap& operator=(const multimap& __m) 1745 { 1746#ifndef _LIBCPP_CXX03_LANG 1747 __tree_ = __m.__tree_; 1748#else 1749 if (this != &__m) { 1750 __tree_.clear(); 1751 __tree_.value_comp() = __m.__tree_.value_comp(); 1752 __tree_.__copy_assign_alloc(__m.__tree_); 1753 insert(__m.begin(), __m.end()); 1754 } 1755#endif 1756 return *this; 1757 } 1758 1759#ifndef _LIBCPP_CXX03_LANG 1760 1761 _LIBCPP_INLINE_VISIBILITY 1762 multimap(multimap&& __m) 1763 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 1764 : __tree_(_VSTD::move(__m.__tree_)) 1765 { 1766 } 1767 1768 multimap(multimap&& __m, const allocator_type& __a); 1769 1770 _LIBCPP_INLINE_VISIBILITY 1771 multimap& operator=(multimap&& __m) 1772 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 1773 { 1774 __tree_ = _VSTD::move(__m.__tree_); 1775 return *this; 1776 } 1777 1778 _LIBCPP_INLINE_VISIBILITY 1779 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare()) 1780 : __tree_(__vc(__comp)) 1781 { 1782 insert(__il.begin(), __il.end()); 1783 } 1784 1785 _LIBCPP_INLINE_VISIBILITY 1786 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a) 1787 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) 1788 { 1789 insert(__il.begin(), __il.end()); 1790 } 1791 1792#if _LIBCPP_STD_VER > 11 1793 _LIBCPP_INLINE_VISIBILITY 1794 multimap(initializer_list<value_type> __il, const allocator_type& __a) 1795 : multimap(__il, key_compare(), __a) {} 1796#endif 1797 1798 _LIBCPP_INLINE_VISIBILITY 1799 multimap& operator=(initializer_list<value_type> __il) 1800 { 1801 __tree_.__assign_multi(__il.begin(), __il.end()); 1802 return *this; 1803 } 1804 1805#endif // _LIBCPP_CXX03_LANG 1806 1807 _LIBCPP_INLINE_VISIBILITY 1808 explicit multimap(const allocator_type& __a) 1809 : __tree_(typename __base::allocator_type(__a)) 1810 { 1811 } 1812 1813 _LIBCPP_INLINE_VISIBILITY 1814 multimap(const multimap& __m, const allocator_type& __a) 1815 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) 1816 { 1817 insert(__m.begin(), __m.end()); 1818 } 1819 1820 _LIBCPP_INLINE_VISIBILITY 1821 iterator begin() _NOEXCEPT {return __tree_.begin();} 1822 _LIBCPP_INLINE_VISIBILITY 1823 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 1824 _LIBCPP_INLINE_VISIBILITY 1825 iterator end() _NOEXCEPT {return __tree_.end();} 1826 _LIBCPP_INLINE_VISIBILITY 1827 const_iterator end() const _NOEXCEPT {return __tree_.end();} 1828 1829 _LIBCPP_INLINE_VISIBILITY 1830 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());} 1831 _LIBCPP_INLINE_VISIBILITY 1832 const_reverse_iterator rbegin() const _NOEXCEPT 1833 {return const_reverse_iterator(end());} 1834 _LIBCPP_INLINE_VISIBILITY 1835 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());} 1836 _LIBCPP_INLINE_VISIBILITY 1837 const_reverse_iterator rend() const _NOEXCEPT 1838 {return const_reverse_iterator(begin());} 1839 1840 _LIBCPP_INLINE_VISIBILITY 1841 const_iterator cbegin() const _NOEXCEPT {return begin();} 1842 _LIBCPP_INLINE_VISIBILITY 1843 const_iterator cend() const _NOEXCEPT {return end();} 1844 _LIBCPP_INLINE_VISIBILITY 1845 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 1846 _LIBCPP_INLINE_VISIBILITY 1847 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 1848 1849 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 1850 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 1851 _LIBCPP_INLINE_VISIBILITY 1852 size_type size() const _NOEXCEPT {return __tree_.size();} 1853 _LIBCPP_INLINE_VISIBILITY 1854 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 1855 1856 _LIBCPP_INLINE_VISIBILITY 1857 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());} 1858 _LIBCPP_INLINE_VISIBILITY 1859 key_compare key_comp() const {return __tree_.value_comp().key_comp();} 1860 _LIBCPP_INLINE_VISIBILITY 1861 value_compare value_comp() const 1862 {return value_compare(__tree_.value_comp().key_comp());} 1863 1864#ifndef _LIBCPP_CXX03_LANG 1865 1866 template <class ..._Args> 1867 _LIBCPP_INLINE_VISIBILITY 1868 iterator emplace(_Args&& ...__args) { 1869 return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...); 1870 } 1871 1872 template <class ..._Args> 1873 _LIBCPP_INLINE_VISIBILITY 1874 iterator emplace_hint(const_iterator __p, _Args&& ...__args) { 1875 return __tree_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...); 1876 } 1877 1878 template <class _Pp, 1879 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1880 _LIBCPP_INLINE_VISIBILITY 1881 iterator insert(_Pp&& __p) 1882 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));} 1883 1884 template <class _Pp, 1885 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1886 _LIBCPP_INLINE_VISIBILITY 1887 iterator insert(const_iterator __pos, _Pp&& __p) 1888 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));} 1889 1890 _LIBCPP_INLINE_VISIBILITY 1891 iterator insert(value_type&& __v) 1892 {return __tree_.__insert_multi(_VSTD::move(__v));} 1893 1894 _LIBCPP_INLINE_VISIBILITY 1895 iterator insert(const_iterator __p, value_type&& __v) 1896 {return __tree_.__insert_multi(__p.__i_, _VSTD::move(__v));} 1897 1898 1899 _LIBCPP_INLINE_VISIBILITY 1900 void insert(initializer_list<value_type> __il) 1901 {insert(__il.begin(), __il.end());} 1902 1903#endif // _LIBCPP_CXX03_LANG 1904 1905 _LIBCPP_INLINE_VISIBILITY 1906 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);} 1907 1908 _LIBCPP_INLINE_VISIBILITY 1909 iterator insert(const_iterator __p, const value_type& __v) 1910 {return __tree_.__insert_multi(__p.__i_, __v);} 1911 1912 template <class _InputIterator> 1913 _LIBCPP_INLINE_VISIBILITY 1914 void insert(_InputIterator __f, _InputIterator __l) 1915 { 1916 for (const_iterator __e = cend(); __f != __l; ++__f) 1917 __tree_.__insert_multi(__e.__i_, *__f); 1918 } 1919 1920 _LIBCPP_INLINE_VISIBILITY 1921 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);} 1922 _LIBCPP_INLINE_VISIBILITY 1923 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);} 1924 _LIBCPP_INLINE_VISIBILITY 1925 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} 1926 _LIBCPP_INLINE_VISIBILITY 1927 iterator erase(const_iterator __f, const_iterator __l) 1928 {return __tree_.erase(__f.__i_, __l.__i_);} 1929 1930#if _LIBCPP_STD_VER > 14 1931 _LIBCPP_INLINE_VISIBILITY 1932 iterator insert(node_type&& __nh) 1933 { 1934 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1935 "node_type with incompatible allocator passed to multimap::insert()"); 1936 return __tree_.template __node_handle_insert_multi<node_type>( 1937 _VSTD::move(__nh)); 1938 } 1939 _LIBCPP_INLINE_VISIBILITY 1940 iterator insert(const_iterator __hint, 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 __hint.__i_, _VSTD::move(__nh)); 1946 } 1947 _LIBCPP_INLINE_VISIBILITY 1948 node_type extract(key_type const& __key) 1949 { 1950 return __tree_.template __node_handle_extract<node_type>(__key); 1951 } 1952 _LIBCPP_INLINE_VISIBILITY 1953 node_type extract(const_iterator __it) 1954 { 1955 return __tree_.template __node_handle_extract<node_type>( 1956 __it.__i_); 1957 } 1958 template <class _Compare2> 1959 _LIBCPP_INLINE_VISIBILITY 1960 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source) 1961 { 1962 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1963 "merging container with incompatible allocator"); 1964 return __tree_.__node_handle_merge_multi(__source.__tree_); 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(map<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#endif 1991 1992 _LIBCPP_INLINE_VISIBILITY 1993 void clear() _NOEXCEPT {__tree_.clear();} 1994 1995 _LIBCPP_INLINE_VISIBILITY 1996 void swap(multimap& __m) 1997 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 1998 {__tree_.swap(__m.__tree_);} 1999 2000 _LIBCPP_INLINE_VISIBILITY 2001 iterator find(const key_type& __k) {return __tree_.find(__k);} 2002 _LIBCPP_INLINE_VISIBILITY 2003 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 2004#if _LIBCPP_STD_VER > 11 2005 template <typename _K2> 2006 _LIBCPP_INLINE_VISIBILITY 2007 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 2008 find(const _K2& __k) {return __tree_.find(__k);} 2009 template <typename _K2> 2010 _LIBCPP_INLINE_VISIBILITY 2011 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 2012 find(const _K2& __k) const {return __tree_.find(__k);} 2013#endif 2014 2015 _LIBCPP_INLINE_VISIBILITY 2016 size_type count(const key_type& __k) const 2017 {return __tree_.__count_multi(__k);} 2018#if _LIBCPP_STD_VER > 11 2019 template <typename _K2> 2020 _LIBCPP_INLINE_VISIBILITY 2021 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 2022 count(const _K2& __k) const {return __tree_.__count_multi(__k);} 2023#endif 2024 _LIBCPP_INLINE_VISIBILITY 2025 iterator lower_bound(const key_type& __k) 2026 {return __tree_.lower_bound(__k);} 2027 _LIBCPP_INLINE_VISIBILITY 2028 const_iterator lower_bound(const key_type& __k) const 2029 {return __tree_.lower_bound(__k);} 2030#if _LIBCPP_STD_VER > 11 2031 template <typename _K2> 2032 _LIBCPP_INLINE_VISIBILITY 2033 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 2034 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 2035 2036 template <typename _K2> 2037 _LIBCPP_INLINE_VISIBILITY 2038 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 2039 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 2040#endif 2041 2042 _LIBCPP_INLINE_VISIBILITY 2043 iterator upper_bound(const key_type& __k) 2044 {return __tree_.upper_bound(__k);} 2045 _LIBCPP_INLINE_VISIBILITY 2046 const_iterator upper_bound(const key_type& __k) const 2047 {return __tree_.upper_bound(__k);} 2048#if _LIBCPP_STD_VER > 11 2049 template <typename _K2> 2050 _LIBCPP_INLINE_VISIBILITY 2051 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 2052 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 2053 template <typename _K2> 2054 _LIBCPP_INLINE_VISIBILITY 2055 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 2056 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 2057#endif 2058 2059 _LIBCPP_INLINE_VISIBILITY 2060 pair<iterator,iterator> equal_range(const key_type& __k) 2061 {return __tree_.__equal_range_multi(__k);} 2062 _LIBCPP_INLINE_VISIBILITY 2063 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 2064 {return __tree_.__equal_range_multi(__k);} 2065#if _LIBCPP_STD_VER > 11 2066 template <typename _K2> 2067 _LIBCPP_INLINE_VISIBILITY 2068 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 2069 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 2070 template <typename _K2> 2071 _LIBCPP_INLINE_VISIBILITY 2072 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 2073 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 2074#endif 2075 2076private: 2077 typedef typename __base::__node __node; 2078 typedef typename __base::__node_allocator __node_allocator; 2079 typedef typename __base::__node_pointer __node_pointer; 2080 2081 typedef __map_node_destructor<__node_allocator> _Dp; 2082 typedef unique_ptr<__node, _Dp> __node_holder; 2083}; 2084 2085#ifndef _LIBCPP_CXX03_LANG 2086template <class _Key, class _Tp, class _Compare, class _Allocator> 2087multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a) 2088 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a)) 2089{ 2090 if (__a != __m.get_allocator()) 2091 { 2092 const_iterator __e = cend(); 2093 while (!__m.empty()) 2094 __tree_.__insert_multi(__e.__i_, 2095 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__move())); 2096 } 2097} 2098#endif 2099 2100template <class _Key, class _Tp, class _Compare, class _Allocator> 2101inline _LIBCPP_INLINE_VISIBILITY 2102bool 2103operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2104 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2105{ 2106 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 2107} 2108 2109template <class _Key, class _Tp, class _Compare, class _Allocator> 2110inline _LIBCPP_INLINE_VISIBILITY 2111bool 2112operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2113 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2114{ 2115 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 2116} 2117 2118template <class _Key, class _Tp, class _Compare, class _Allocator> 2119inline _LIBCPP_INLINE_VISIBILITY 2120bool 2121operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2122 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2123{ 2124 return !(__x == __y); 2125} 2126 2127template <class _Key, class _Tp, class _Compare, class _Allocator> 2128inline _LIBCPP_INLINE_VISIBILITY 2129bool 2130operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2131 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2132{ 2133 return __y < __x; 2134} 2135 2136template <class _Key, class _Tp, class _Compare, class _Allocator> 2137inline _LIBCPP_INLINE_VISIBILITY 2138bool 2139operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2140 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2141{ 2142 return !(__x < __y); 2143} 2144 2145template <class _Key, class _Tp, class _Compare, class _Allocator> 2146inline _LIBCPP_INLINE_VISIBILITY 2147bool 2148operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2149 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2150{ 2151 return !(__y < __x); 2152} 2153 2154template <class _Key, class _Tp, class _Compare, class _Allocator> 2155inline _LIBCPP_INLINE_VISIBILITY 2156void 2157swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2158 multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2159 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2160{ 2161 __x.swap(__y); 2162} 2163 2164#if _LIBCPP_STD_VER > 17 2165template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate> 2166inline _LIBCPP_INLINE_VISIBILITY 2167void erase_if(multimap<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) 2168{ __libcpp_erase_if_container(__c, __pred); } 2169#endif 2170 2171_LIBCPP_END_NAMESPACE_STD 2172 2173#endif // _LIBCPP_MAP 2174