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