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