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 464#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 465#pragma GCC system_header 466#endif 467 468_LIBCPP_BEGIN_NAMESPACE_STD 469 470template <class _Key, class _CP, class _Compare, bool _IsSmall> 471class __map_value_compare 472 : private _Compare 473{ 474public: 475 _LIBCPP_INLINE_VISIBILITY 476 __map_value_compare() 477 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value) 478 : _Compare() {} 479 _LIBCPP_INLINE_VISIBILITY 480 __map_value_compare(_Compare c) 481 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value) 482 : _Compare(c) {} 483 _LIBCPP_INLINE_VISIBILITY 484 const _Compare& key_comp() const _NOEXCEPT {return *this;} 485 _LIBCPP_INLINE_VISIBILITY 486 bool operator()(const _CP& __x, const _CP& __y) const 487 {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y.__get_value().first);} 488 _LIBCPP_INLINE_VISIBILITY 489 bool operator()(const _CP& __x, const _Key& __y) const 490 {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y);} 491 _LIBCPP_INLINE_VISIBILITY 492 bool operator()(const _Key& __x, const _CP& __y) const 493 {return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);} 494 void swap(__map_value_compare&__y) 495 _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value) 496 { 497 using _VSTD::swap; 498 swap(static_cast<_Compare&>(*this), static_cast<_Compare&>(__y)); 499 } 500 501#if _LIBCPP_STD_VER > 11 502 template <typename _K2> 503 _LIBCPP_INLINE_VISIBILITY 504 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type 505 operator () ( const _K2& __x, const _CP& __y ) const 506 {return static_cast<const _Compare&>(*this) (__x, __y.__get_value().first);} 507 508 template <typename _K2> 509 _LIBCPP_INLINE_VISIBILITY 510 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type 511 operator () (const _CP& __x, const _K2& __y) const 512 {return static_cast<const _Compare&>(*this) (__x.__get_value().first, __y);} 513#endif 514}; 515 516template <class _Key, class _CP, class _Compare> 517class __map_value_compare<_Key, _CP, _Compare, false> 518{ 519 _Compare comp; 520 521public: 522 _LIBCPP_INLINE_VISIBILITY 523 __map_value_compare() 524 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value) 525 : comp() {} 526 _LIBCPP_INLINE_VISIBILITY 527 __map_value_compare(_Compare c) 528 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value) 529 : comp(c) {} 530 _LIBCPP_INLINE_VISIBILITY 531 const _Compare& key_comp() const _NOEXCEPT {return comp;} 532 533 _LIBCPP_INLINE_VISIBILITY 534 bool operator()(const _CP& __x, const _CP& __y) const 535 {return comp(__x.__get_value().first, __y.__get_value().first);} 536 _LIBCPP_INLINE_VISIBILITY 537 bool operator()(const _CP& __x, const _Key& __y) const 538 {return comp(__x.__get_value().first, __y);} 539 _LIBCPP_INLINE_VISIBILITY 540 bool operator()(const _Key& __x, const _CP& __y) const 541 {return comp(__x, __y.__get_value().first);} 542 void swap(__map_value_compare&__y) 543 _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value) 544 { 545 using _VSTD::swap; 546 swap(comp, __y.comp); 547 } 548 549#if _LIBCPP_STD_VER > 11 550 template <typename _K2> 551 _LIBCPP_INLINE_VISIBILITY 552 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type 553 operator () ( const _K2& __x, const _CP& __y ) const 554 {return comp (__x, __y.__get_value().first);} 555 556 template <typename _K2> 557 _LIBCPP_INLINE_VISIBILITY 558 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type 559 operator () (const _CP& __x, const _K2& __y) const 560 {return comp (__x.__get_value().first, __y);} 561#endif 562}; 563 564template <class _Key, class _CP, class _Compare, bool __b> 565inline _LIBCPP_INLINE_VISIBILITY 566void 567swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x, 568 __map_value_compare<_Key, _CP, _Compare, __b>& __y) 569 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 570{ 571 __x.swap(__y); 572} 573 574template <class _Allocator> 575class __map_node_destructor 576{ 577 typedef _Allocator allocator_type; 578 typedef allocator_traits<allocator_type> __alloc_traits; 579 580public: 581 typedef typename __alloc_traits::pointer pointer; 582 583private: 584 allocator_type& __na_; 585 586 __map_node_destructor& operator=(const __map_node_destructor&); 587 588public: 589 bool __first_constructed; 590 bool __second_constructed; 591 592 _LIBCPP_INLINE_VISIBILITY 593 explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT 594 : __na_(__na), 595 __first_constructed(false), 596 __second_constructed(false) 597 {} 598 599#ifndef _LIBCPP_CXX03_LANG 600 _LIBCPP_INLINE_VISIBILITY 601 __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT 602 : __na_(__x.__na_), 603 __first_constructed(__x.__value_constructed), 604 __second_constructed(__x.__value_constructed) 605 { 606 __x.__value_constructed = false; 607 } 608#endif // _LIBCPP_CXX03_LANG 609 610 _LIBCPP_INLINE_VISIBILITY 611 void operator()(pointer __p) _NOEXCEPT 612 { 613 if (__second_constructed) 614 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().second)); 615 if (__first_constructed) 616 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().first)); 617 if (__p) 618 __alloc_traits::deallocate(__na_, __p, 1); 619 } 620}; 621 622template <class _Key, class _Tp, class _Compare, class _Allocator> 623 class map; 624template <class _Key, class _Tp, class _Compare, class _Allocator> 625 class multimap; 626template <class _TreeIterator> class __map_const_iterator; 627 628#ifndef _LIBCPP_CXX03_LANG 629 630template <class _Key, class _Tp> 631struct __value_type 632{ 633 typedef _Key key_type; 634 typedef _Tp mapped_type; 635 typedef pair<const key_type, mapped_type> value_type; 636 typedef pair<key_type&, mapped_type&> __nc_ref_pair_type; 637 typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type; 638 639private: 640 value_type __cc; 641 642public: 643 _LIBCPP_INLINE_VISIBILITY 644 value_type& __get_value() 645 { 646#if _LIBCPP_STD_VER > 14 647 return *_VSTD::launder(_VSTD::addressof(__cc)); 648#else 649 return __cc; 650#endif 651 } 652 653 _LIBCPP_INLINE_VISIBILITY 654 const value_type& __get_value() const 655 { 656#if _LIBCPP_STD_VER > 14 657 return *_VSTD::launder(_VSTD::addressof(__cc)); 658#else 659 return __cc; 660#endif 661 } 662 663 _LIBCPP_INLINE_VISIBILITY 664 __nc_ref_pair_type __ref() 665 { 666 value_type& __v = __get_value(); 667 return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second); 668 } 669 670 _LIBCPP_INLINE_VISIBILITY 671 __nc_rref_pair_type __move() 672 { 673 value_type& __v = __get_value(); 674 return __nc_rref_pair_type( 675 _VSTD::move(const_cast<key_type&>(__v.first)), 676 _VSTD::move(__v.second)); 677 } 678 679 _LIBCPP_INLINE_VISIBILITY 680 __value_type& operator=(const __value_type& __v) 681 { 682 __ref() = __v.__get_value(); 683 return *this; 684 } 685 686 _LIBCPP_INLINE_VISIBILITY 687 __value_type& operator=(__value_type&& __v) 688 { 689 __ref() = __v.__move(); 690 return *this; 691 } 692 693 template <class _ValueTp, 694 class = typename enable_if< 695 __is_same_uncvref<_ValueTp, value_type>::value 696 >::type 697 > 698 _LIBCPP_INLINE_VISIBILITY 699 __value_type& operator=(_ValueTp&& __v) 700 { 701 __ref() = _VSTD::forward<_ValueTp>(__v); 702 return *this; 703 } 704 705private: 706 __value_type() _LIBCPP_EQUAL_DELETE; 707 ~__value_type() _LIBCPP_EQUAL_DELETE; 708 __value_type(const __value_type& __v) _LIBCPP_EQUAL_DELETE; 709 __value_type(__value_type&& __v) _LIBCPP_EQUAL_DELETE; 710}; 711 712#else 713 714template <class _Key, class _Tp> 715struct __value_type 716{ 717 typedef _Key key_type; 718 typedef _Tp mapped_type; 719 typedef pair<const key_type, mapped_type> value_type; 720 721private: 722 value_type __cc; 723 724public: 725 _LIBCPP_INLINE_VISIBILITY 726 value_type& __get_value() { return __cc; } 727 _LIBCPP_INLINE_VISIBILITY 728 const value_type& __get_value() const { return __cc; } 729 730private: 731 __value_type(); 732 __value_type(__value_type const&); 733 __value_type& operator=(__value_type const&); 734 ~__value_type(); 735}; 736 737#endif // _LIBCPP_CXX03_LANG 738 739template <class _Tp> 740struct __extract_key_value_types; 741 742template <class _Key, class _Tp> 743struct __extract_key_value_types<__value_type<_Key, _Tp> > 744{ 745 typedef _Key const __key_type; 746 typedef _Tp __mapped_type; 747}; 748 749template <class _TreeIterator> 750class _LIBCPP_TEMPLATE_VIS __map_iterator 751{ 752 typedef typename _TreeIterator::_NodeTypes _NodeTypes; 753 typedef typename _TreeIterator::__pointer_traits __pointer_traits; 754 755 _TreeIterator __i_; 756 757public: 758 typedef bidirectional_iterator_tag iterator_category; 759 typedef typename _NodeTypes::__map_value_type value_type; 760 typedef typename _TreeIterator::difference_type difference_type; 761 typedef value_type& reference; 762 typedef typename _NodeTypes::__map_value_type_pointer pointer; 763 764 _LIBCPP_INLINE_VISIBILITY 765 __map_iterator() _NOEXCEPT {} 766 767 _LIBCPP_INLINE_VISIBILITY 768 __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {} 769 770 _LIBCPP_INLINE_VISIBILITY 771 reference operator*() const {return __i_->__get_value();} 772 _LIBCPP_INLINE_VISIBILITY 773 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());} 774 775 _LIBCPP_INLINE_VISIBILITY 776 __map_iterator& operator++() {++__i_; return *this;} 777 _LIBCPP_INLINE_VISIBILITY 778 __map_iterator operator++(int) 779 { 780 __map_iterator __t(*this); 781 ++(*this); 782 return __t; 783 } 784 785 _LIBCPP_INLINE_VISIBILITY 786 __map_iterator& operator--() {--__i_; return *this;} 787 _LIBCPP_INLINE_VISIBILITY 788 __map_iterator operator--(int) 789 { 790 __map_iterator __t(*this); 791 --(*this); 792 return __t; 793 } 794 795 friend _LIBCPP_INLINE_VISIBILITY 796 bool operator==(const __map_iterator& __x, const __map_iterator& __y) 797 {return __x.__i_ == __y.__i_;} 798 friend 799 _LIBCPP_INLINE_VISIBILITY 800 bool operator!=(const __map_iterator& __x, const __map_iterator& __y) 801 {return __x.__i_ != __y.__i_;} 802 803 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map; 804 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap; 805 template <class> friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator; 806}; 807 808template <class _TreeIterator> 809class _LIBCPP_TEMPLATE_VIS __map_const_iterator 810{ 811 typedef typename _TreeIterator::_NodeTypes _NodeTypes; 812 typedef typename _TreeIterator::__pointer_traits __pointer_traits; 813 814 _TreeIterator __i_; 815 816public: 817 typedef bidirectional_iterator_tag iterator_category; 818 typedef typename _NodeTypes::__map_value_type value_type; 819 typedef typename _TreeIterator::difference_type difference_type; 820 typedef const value_type& reference; 821 typedef typename _NodeTypes::__const_map_value_type_pointer pointer; 822 823 _LIBCPP_INLINE_VISIBILITY 824 __map_const_iterator() _NOEXCEPT {} 825 826 _LIBCPP_INLINE_VISIBILITY 827 __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {} 828 _LIBCPP_INLINE_VISIBILITY 829 __map_const_iterator(__map_iterator< 830 typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT 831 : __i_(__i.__i_) {} 832 833 _LIBCPP_INLINE_VISIBILITY 834 reference operator*() const {return __i_->__get_value();} 835 _LIBCPP_INLINE_VISIBILITY 836 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());} 837 838 _LIBCPP_INLINE_VISIBILITY 839 __map_const_iterator& operator++() {++__i_; return *this;} 840 _LIBCPP_INLINE_VISIBILITY 841 __map_const_iterator operator++(int) 842 { 843 __map_const_iterator __t(*this); 844 ++(*this); 845 return __t; 846 } 847 848 _LIBCPP_INLINE_VISIBILITY 849 __map_const_iterator& operator--() {--__i_; return *this;} 850 _LIBCPP_INLINE_VISIBILITY 851 __map_const_iterator operator--(int) 852 { 853 __map_const_iterator __t(*this); 854 --(*this); 855 return __t; 856 } 857 858 friend _LIBCPP_INLINE_VISIBILITY 859 bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y) 860 {return __x.__i_ == __y.__i_;} 861 friend _LIBCPP_INLINE_VISIBILITY 862 bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y) 863 {return __x.__i_ != __y.__i_;} 864 865 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map; 866 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap; 867 template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator; 868}; 869 870template <class _Key, class _Tp, class _Compare = less<_Key>, 871 class _Allocator = allocator<pair<const _Key, _Tp> > > 872class _LIBCPP_TEMPLATE_VIS map 873{ 874public: 875 // types: 876 typedef _Key key_type; 877 typedef _Tp mapped_type; 878 typedef pair<const key_type, mapped_type> value_type; 879 typedef _Compare key_compare; 880 typedef _Allocator allocator_type; 881 typedef value_type& reference; 882 typedef const value_type& const_reference; 883 884 static_assert((is_same<typename allocator_type::value_type, value_type>::value), 885 "Allocator::value_type must be same type as value_type"); 886 887 class _LIBCPP_TEMPLATE_VIS value_compare 888 : public binary_function<value_type, value_type, bool> 889 { 890 friend class map; 891 protected: 892 key_compare comp; 893 894 _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {} 895 public: 896 _LIBCPP_INLINE_VISIBILITY 897 bool operator()(const value_type& __x, const value_type& __y) const 898 {return comp(__x.first, __y.first);} 899 }; 900 901private: 902 903 typedef _VSTD::__value_type<key_type, mapped_type> __value_type; 904 typedef __map_value_compare<key_type, __value_type, key_compare> __vc; 905 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, 906 __value_type>::type __allocator_type; 907 typedef __tree<__value_type, __vc, __allocator_type> __base; 908 typedef typename __base::__node_traits __node_traits; 909 typedef allocator_traits<allocator_type> __alloc_traits; 910 911 __base __tree_; 912 913public: 914 typedef typename __alloc_traits::pointer pointer; 915 typedef typename __alloc_traits::const_pointer const_pointer; 916 typedef typename __alloc_traits::size_type size_type; 917 typedef typename __alloc_traits::difference_type difference_type; 918 typedef __map_iterator<typename __base::iterator> iterator; 919 typedef __map_const_iterator<typename __base::const_iterator> const_iterator; 920 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 921 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 922 923#if _LIBCPP_STD_VER > 14 924 typedef __map_node_handle<typename __base::__node, allocator_type> node_type; 925 typedef __insert_return_type<iterator, node_type> insert_return_type; 926#endif 927 928 _LIBCPP_INLINE_VISIBILITY 929 map() 930 _NOEXCEPT_( 931 is_nothrow_default_constructible<allocator_type>::value && 932 is_nothrow_default_constructible<key_compare>::value && 933 is_nothrow_copy_constructible<key_compare>::value) 934 : __tree_(__vc(key_compare())) {} 935 936 _LIBCPP_INLINE_VISIBILITY 937 explicit map(const key_compare& __comp) 938 _NOEXCEPT_( 939 is_nothrow_default_constructible<allocator_type>::value && 940 is_nothrow_copy_constructible<key_compare>::value) 941 : __tree_(__vc(__comp)) {} 942 943 _LIBCPP_INLINE_VISIBILITY 944 explicit map(const key_compare& __comp, const allocator_type& __a) 945 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {} 946 947 template <class _InputIterator> 948 _LIBCPP_INLINE_VISIBILITY 949 map(_InputIterator __f, _InputIterator __l, 950 const key_compare& __comp = key_compare()) 951 : __tree_(__vc(__comp)) 952 { 953 insert(__f, __l); 954 } 955 956 template <class _InputIterator> 957 _LIBCPP_INLINE_VISIBILITY 958 map(_InputIterator __f, _InputIterator __l, 959 const key_compare& __comp, const allocator_type& __a) 960 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) 961 { 962 insert(__f, __l); 963 } 964 965#if _LIBCPP_STD_VER > 11 966 template <class _InputIterator> 967 _LIBCPP_INLINE_VISIBILITY 968 map(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 969 : map(__f, __l, key_compare(), __a) {} 970#endif 971 972 _LIBCPP_INLINE_VISIBILITY 973 map(const map& __m) 974 : __tree_(__m.__tree_) 975 { 976 insert(__m.begin(), __m.end()); 977 } 978 979 _LIBCPP_INLINE_VISIBILITY 980 map& operator=(const map& __m) 981 { 982#ifndef _LIBCPP_CXX03_LANG 983 __tree_ = __m.__tree_; 984#else 985 if (this != &__m) { 986 __tree_.clear(); 987 __tree_.value_comp() = __m.__tree_.value_comp(); 988 __tree_.__copy_assign_alloc(__m.__tree_); 989 insert(__m.begin(), __m.end()); 990 } 991#endif 992 return *this; 993 } 994 995#ifndef _LIBCPP_CXX03_LANG 996 997 _LIBCPP_INLINE_VISIBILITY 998 map(map&& __m) 999 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 1000 : __tree_(_VSTD::move(__m.__tree_)) 1001 { 1002 } 1003 1004 map(map&& __m, const allocator_type& __a); 1005 1006 _LIBCPP_INLINE_VISIBILITY 1007 map& operator=(map&& __m) 1008 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 1009 { 1010 __tree_ = _VSTD::move(__m.__tree_); 1011 return *this; 1012 } 1013 1014 _LIBCPP_INLINE_VISIBILITY 1015 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare()) 1016 : __tree_(__vc(__comp)) 1017 { 1018 insert(__il.begin(), __il.end()); 1019 } 1020 1021 _LIBCPP_INLINE_VISIBILITY 1022 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a) 1023 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) 1024 { 1025 insert(__il.begin(), __il.end()); 1026 } 1027 1028#if _LIBCPP_STD_VER > 11 1029 _LIBCPP_INLINE_VISIBILITY 1030 map(initializer_list<value_type> __il, const allocator_type& __a) 1031 : map(__il, key_compare(), __a) {} 1032#endif 1033 1034 _LIBCPP_INLINE_VISIBILITY 1035 map& operator=(initializer_list<value_type> __il) 1036 { 1037 __tree_.__assign_unique(__il.begin(), __il.end()); 1038 return *this; 1039 } 1040 1041#endif // _LIBCPP_CXX03_LANG 1042 1043 _LIBCPP_INLINE_VISIBILITY 1044 explicit map(const allocator_type& __a) 1045 : __tree_(typename __base::allocator_type(__a)) 1046 { 1047 } 1048 1049 _LIBCPP_INLINE_VISIBILITY 1050 map(const map& __m, const allocator_type& __a) 1051 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) 1052 { 1053 insert(__m.begin(), __m.end()); 1054 } 1055 1056 _LIBCPP_INLINE_VISIBILITY 1057 iterator begin() _NOEXCEPT {return __tree_.begin();} 1058 _LIBCPP_INLINE_VISIBILITY 1059 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 1060 _LIBCPP_INLINE_VISIBILITY 1061 iterator end() _NOEXCEPT {return __tree_.end();} 1062 _LIBCPP_INLINE_VISIBILITY 1063 const_iterator end() const _NOEXCEPT {return __tree_.end();} 1064 1065 _LIBCPP_INLINE_VISIBILITY 1066 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());} 1067 _LIBCPP_INLINE_VISIBILITY 1068 const_reverse_iterator rbegin() const _NOEXCEPT 1069 {return const_reverse_iterator(end());} 1070 _LIBCPP_INLINE_VISIBILITY 1071 reverse_iterator rend() _NOEXCEPT 1072 {return reverse_iterator(begin());} 1073 _LIBCPP_INLINE_VISIBILITY 1074 const_reverse_iterator rend() const _NOEXCEPT 1075 {return const_reverse_iterator(begin());} 1076 1077 _LIBCPP_INLINE_VISIBILITY 1078 const_iterator cbegin() const _NOEXCEPT {return begin();} 1079 _LIBCPP_INLINE_VISIBILITY 1080 const_iterator cend() const _NOEXCEPT {return end();} 1081 _LIBCPP_INLINE_VISIBILITY 1082 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 1083 _LIBCPP_INLINE_VISIBILITY 1084 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 1085 1086 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 1087 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 1088 _LIBCPP_INLINE_VISIBILITY 1089 size_type size() const _NOEXCEPT {return __tree_.size();} 1090 _LIBCPP_INLINE_VISIBILITY 1091 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 1092 1093 mapped_type& operator[](const key_type& __k); 1094#ifndef _LIBCPP_CXX03_LANG 1095 mapped_type& operator[](key_type&& __k); 1096#endif 1097 1098 mapped_type& at(const key_type& __k); 1099 const mapped_type& at(const key_type& __k) const; 1100 1101 _LIBCPP_INLINE_VISIBILITY 1102 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());} 1103 _LIBCPP_INLINE_VISIBILITY 1104 key_compare key_comp() const {return __tree_.value_comp().key_comp();} 1105 _LIBCPP_INLINE_VISIBILITY 1106 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());} 1107 1108#ifndef _LIBCPP_CXX03_LANG 1109 template <class ..._Args> 1110 _LIBCPP_INLINE_VISIBILITY 1111 pair<iterator, bool> emplace(_Args&& ...__args) { 1112 return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...); 1113 } 1114 1115 template <class ..._Args> 1116 _LIBCPP_INLINE_VISIBILITY 1117 iterator emplace_hint(const_iterator __p, _Args&& ...__args) { 1118 return __tree_.__emplace_hint_unique(__p.__i_, _VSTD::forward<_Args>(__args)...); 1119 } 1120 1121 template <class _Pp, 1122 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1123 _LIBCPP_INLINE_VISIBILITY 1124 pair<iterator, bool> insert(_Pp&& __p) 1125 {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));} 1126 1127 template <class _Pp, 1128 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1129 _LIBCPP_INLINE_VISIBILITY 1130 iterator insert(const_iterator __pos, _Pp&& __p) 1131 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));} 1132 1133#endif // _LIBCPP_CXX03_LANG 1134 1135 _LIBCPP_INLINE_VISIBILITY 1136 pair<iterator, bool> 1137 insert(const value_type& __v) {return __tree_.__insert_unique(__v);} 1138 1139 _LIBCPP_INLINE_VISIBILITY 1140 iterator 1141 insert(const_iterator __p, const value_type& __v) 1142 {return __tree_.__insert_unique(__p.__i_, __v);} 1143 1144#ifndef _LIBCPP_CXX03_LANG 1145 _LIBCPP_INLINE_VISIBILITY 1146 pair<iterator, bool> 1147 insert(value_type&& __v) {return __tree_.__insert_unique(_VSTD::move(__v));} 1148 1149 _LIBCPP_INLINE_VISIBILITY 1150 iterator insert(const_iterator __p, value_type&& __v) 1151 {return __tree_.__insert_unique(__p.__i_, _VSTD::move(__v));} 1152 1153 _LIBCPP_INLINE_VISIBILITY 1154 void insert(initializer_list<value_type> __il) 1155 {insert(__il.begin(), __il.end());} 1156#endif 1157 1158 template <class _InputIterator> 1159 _LIBCPP_INLINE_VISIBILITY 1160 void insert(_InputIterator __f, _InputIterator __l) 1161 { 1162 for (const_iterator __e = cend(); __f != __l; ++__f) 1163 insert(__e.__i_, *__f); 1164 } 1165 1166#if _LIBCPP_STD_VER > 14 1167 1168 template <class... _Args> 1169 _LIBCPP_INLINE_VISIBILITY 1170 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) 1171 { 1172 return __tree_.__emplace_unique_key_args(__k, 1173 _VSTD::piecewise_construct, 1174 _VSTD::forward_as_tuple(__k), 1175 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); 1176 } 1177 1178 template <class... _Args> 1179 _LIBCPP_INLINE_VISIBILITY 1180 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) 1181 { 1182 return __tree_.__emplace_unique_key_args(__k, 1183 _VSTD::piecewise_construct, 1184 _VSTD::forward_as_tuple(_VSTD::move(__k)), 1185 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); 1186 } 1187 1188 template <class... _Args> 1189 _LIBCPP_INLINE_VISIBILITY 1190 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args) 1191 { 1192 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, 1193 _VSTD::piecewise_construct, 1194 _VSTD::forward_as_tuple(__k), 1195 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); 1196 } 1197 1198 template <class... _Args> 1199 _LIBCPP_INLINE_VISIBILITY 1200 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) 1201 { 1202 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, 1203 _VSTD::piecewise_construct, 1204 _VSTD::forward_as_tuple(_VSTD::move(__k)), 1205 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); 1206 } 1207 1208 template <class _Vp> 1209 _LIBCPP_INLINE_VISIBILITY 1210 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) 1211 { 1212 iterator __p = lower_bound(__k); 1213 if ( __p != end() && !key_comp()(__k, __p->first)) 1214 { 1215 __p->second = _VSTD::forward<_Vp>(__v); 1216 return _VSTD::make_pair(__p, false); 1217 } 1218 return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true); 1219 } 1220 1221 template <class _Vp> 1222 _LIBCPP_INLINE_VISIBILITY 1223 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) 1224 { 1225 iterator __p = lower_bound(__k); 1226 if ( __p != end() && !key_comp()(__k, __p->first)) 1227 { 1228 __p->second = _VSTD::forward<_Vp>(__v); 1229 return _VSTD::make_pair(__p, false); 1230 } 1231 return _VSTD::make_pair(emplace_hint(__p, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)), true); 1232 } 1233 1234 template <class _Vp> 1235 _LIBCPP_INLINE_VISIBILITY 1236 iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v) 1237 { 1238 iterator __p = lower_bound(__k); 1239 if ( __p != end() && !key_comp()(__k, __p->first)) 1240 { 1241 __p->second = _VSTD::forward<_Vp>(__v); 1242 return __p; 1243 } 1244 return emplace_hint(__h, __k, _VSTD::forward<_Vp>(__v)); 1245 } 1246 1247 template <class _Vp> 1248 _LIBCPP_INLINE_VISIBILITY 1249 iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v) 1250 { 1251 iterator __p = lower_bound(__k); 1252 if ( __p != end() && !key_comp()(__k, __p->first)) 1253 { 1254 __p->second = _VSTD::forward<_Vp>(__v); 1255 return __p; 1256 } 1257 return emplace_hint(__h, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)); 1258 } 1259 1260#endif // _LIBCPP_STD_VER > 14 1261 1262 _LIBCPP_INLINE_VISIBILITY 1263 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);} 1264 _LIBCPP_INLINE_VISIBILITY 1265 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);} 1266 _LIBCPP_INLINE_VISIBILITY 1267 size_type erase(const key_type& __k) 1268 {return __tree_.__erase_unique(__k);} 1269 _LIBCPP_INLINE_VISIBILITY 1270 iterator erase(const_iterator __f, const_iterator __l) 1271 {return __tree_.erase(__f.__i_, __l.__i_);} 1272 _LIBCPP_INLINE_VISIBILITY 1273 void clear() _NOEXCEPT {__tree_.clear();} 1274 1275#if _LIBCPP_STD_VER > 14 1276 _LIBCPP_INLINE_VISIBILITY 1277 insert_return_type insert(node_type&& __nh) 1278 { 1279 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1280 "node_type with incompatible allocator passed to map::insert()"); 1281 return __tree_.template __node_handle_insert_unique< 1282 node_type, insert_return_type>(_VSTD::move(__nh)); 1283 } 1284 _LIBCPP_INLINE_VISIBILITY 1285 iterator insert(const_iterator __hint, node_type&& __nh) 1286 { 1287 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1288 "node_type with incompatible allocator passed to map::insert()"); 1289 return __tree_.template __node_handle_insert_unique<node_type>( 1290 __hint.__i_, _VSTD::move(__nh)); 1291 } 1292 _LIBCPP_INLINE_VISIBILITY 1293 node_type extract(key_type const& __key) 1294 { 1295 return __tree_.template __node_handle_extract<node_type>(__key); 1296 } 1297 _LIBCPP_INLINE_VISIBILITY 1298 node_type extract(const_iterator __it) 1299 { 1300 return __tree_.template __node_handle_extract<node_type>(__it.__i_); 1301 } 1302#endif 1303 1304 _LIBCPP_INLINE_VISIBILITY 1305 void swap(map& __m) 1306 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 1307 {__tree_.swap(__m.__tree_);} 1308 1309 _LIBCPP_INLINE_VISIBILITY 1310 iterator find(const key_type& __k) {return __tree_.find(__k);} 1311 _LIBCPP_INLINE_VISIBILITY 1312 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 1313#if _LIBCPP_STD_VER > 11 1314 template <typename _K2> 1315 _LIBCPP_INLINE_VISIBILITY 1316 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 1317 find(const _K2& __k) {return __tree_.find(__k);} 1318 template <typename _K2> 1319 _LIBCPP_INLINE_VISIBILITY 1320 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 1321 find(const _K2& __k) const {return __tree_.find(__k);} 1322#endif 1323 1324 _LIBCPP_INLINE_VISIBILITY 1325 size_type count(const key_type& __k) const 1326 {return __tree_.__count_unique(__k);} 1327#if _LIBCPP_STD_VER > 11 1328 template <typename _K2> 1329 _LIBCPP_INLINE_VISIBILITY 1330 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 1331 count(const _K2& __k) const {return __tree_.__count_multi(__k);} 1332#endif 1333 _LIBCPP_INLINE_VISIBILITY 1334 iterator lower_bound(const key_type& __k) 1335 {return __tree_.lower_bound(__k);} 1336 _LIBCPP_INLINE_VISIBILITY 1337 const_iterator lower_bound(const key_type& __k) const 1338 {return __tree_.lower_bound(__k);} 1339#if _LIBCPP_STD_VER > 11 1340 template <typename _K2> 1341 _LIBCPP_INLINE_VISIBILITY 1342 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 1343 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 1344 1345 template <typename _K2> 1346 _LIBCPP_INLINE_VISIBILITY 1347 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 1348 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 1349#endif 1350 1351 _LIBCPP_INLINE_VISIBILITY 1352 iterator upper_bound(const key_type& __k) 1353 {return __tree_.upper_bound(__k);} 1354 _LIBCPP_INLINE_VISIBILITY 1355 const_iterator upper_bound(const key_type& __k) const 1356 {return __tree_.upper_bound(__k);} 1357#if _LIBCPP_STD_VER > 11 1358 template <typename _K2> 1359 _LIBCPP_INLINE_VISIBILITY 1360 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 1361 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 1362 template <typename _K2> 1363 _LIBCPP_INLINE_VISIBILITY 1364 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 1365 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 1366#endif 1367 1368 _LIBCPP_INLINE_VISIBILITY 1369 pair<iterator,iterator> equal_range(const key_type& __k) 1370 {return __tree_.__equal_range_unique(__k);} 1371 _LIBCPP_INLINE_VISIBILITY 1372 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 1373 {return __tree_.__equal_range_unique(__k);} 1374#if _LIBCPP_STD_VER > 11 1375 template <typename _K2> 1376 _LIBCPP_INLINE_VISIBILITY 1377 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 1378 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 1379 template <typename _K2> 1380 _LIBCPP_INLINE_VISIBILITY 1381 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 1382 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 1383#endif 1384 1385private: 1386 typedef typename __base::__node __node; 1387 typedef typename __base::__node_allocator __node_allocator; 1388 typedef typename __base::__node_pointer __node_pointer; 1389 typedef typename __base::__node_base_pointer __node_base_pointer; 1390 typedef typename __base::__parent_pointer __parent_pointer; 1391 1392 typedef __map_node_destructor<__node_allocator> _Dp; 1393 typedef unique_ptr<__node, _Dp> __node_holder; 1394 1395#ifdef _LIBCPP_CXX03_LANG 1396 __node_holder __construct_node_with_key(const key_type& __k); 1397#endif 1398}; 1399 1400 1401#ifndef _LIBCPP_CXX03_LANG 1402template <class _Key, class _Tp, class _Compare, class _Allocator> 1403map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a) 1404 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a)) 1405{ 1406 if (__a != __m.get_allocator()) 1407 { 1408 const_iterator __e = cend(); 1409 while (!__m.empty()) 1410 __tree_.__insert_unique(__e.__i_, 1411 __m.__tree_.remove(__m.begin().__i_)->__value_.__move()); 1412 } 1413} 1414 1415template <class _Key, class _Tp, class _Compare, class _Allocator> 1416_Tp& 1417map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) 1418{ 1419 return __tree_.__emplace_unique_key_args(__k, 1420 _VSTD::piecewise_construct, 1421 _VSTD::forward_as_tuple(__k), 1422 _VSTD::forward_as_tuple()).first->__get_value().second; 1423} 1424 1425template <class _Key, class _Tp, class _Compare, class _Allocator> 1426_Tp& 1427map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k) 1428{ 1429 return __tree_.__emplace_unique_key_args(__k, 1430 _VSTD::piecewise_construct, 1431 _VSTD::forward_as_tuple(_VSTD::move(__k)), 1432 _VSTD::forward_as_tuple()).first->__get_value().second; 1433} 1434 1435#else // _LIBCPP_CXX03_LANG 1436 1437template <class _Key, class _Tp, class _Compare, class _Allocator> 1438typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder 1439map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k) 1440{ 1441 __node_allocator& __na = __tree_.__node_alloc(); 1442 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1443 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().first), __k); 1444 __h.get_deleter().__first_constructed = true; 1445 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().second)); 1446 __h.get_deleter().__second_constructed = true; 1447 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03 1448} 1449 1450template <class _Key, class _Tp, class _Compare, class _Allocator> 1451_Tp& 1452map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) 1453{ 1454 __parent_pointer __parent; 1455 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k); 1456 __node_pointer __r = static_cast<__node_pointer>(__child); 1457 if (__child == nullptr) 1458 { 1459 __node_holder __h = __construct_node_with_key(__k); 1460 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1461 __r = __h.release(); 1462 } 1463 return __r->__value_.__get_value().second; 1464} 1465 1466#endif // _LIBCPP_CXX03_LANG 1467 1468template <class _Key, class _Tp, class _Compare, class _Allocator> 1469_Tp& 1470map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) 1471{ 1472 __parent_pointer __parent; 1473 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k); 1474#ifndef _LIBCPP_NO_EXCEPTIONS 1475 if (__child == nullptr) 1476 throw out_of_range("map::at: key not found"); 1477#endif // _LIBCPP_NO_EXCEPTIONS 1478 return static_cast<__node_pointer>(__child)->__value_.__get_value().second; 1479} 1480 1481template <class _Key, class _Tp, class _Compare, class _Allocator> 1482const _Tp& 1483map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const 1484{ 1485 __parent_pointer __parent; 1486 __node_base_pointer __child = __tree_.__find_equal(__parent, __k); 1487#ifndef _LIBCPP_NO_EXCEPTIONS 1488 if (__child == nullptr) 1489 throw out_of_range("map::at: key not found"); 1490#endif // _LIBCPP_NO_EXCEPTIONS 1491 return static_cast<__node_pointer>(__child)->__value_.__get_value().second; 1492} 1493 1494 1495template <class _Key, class _Tp, class _Compare, class _Allocator> 1496inline _LIBCPP_INLINE_VISIBILITY 1497bool 1498operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1499 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1500{ 1501 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 1502} 1503 1504template <class _Key, class _Tp, class _Compare, class _Allocator> 1505inline _LIBCPP_INLINE_VISIBILITY 1506bool 1507operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x, 1508 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1509{ 1510 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 1511} 1512 1513template <class _Key, class _Tp, class _Compare, class _Allocator> 1514inline _LIBCPP_INLINE_VISIBILITY 1515bool 1516operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1517 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1518{ 1519 return !(__x == __y); 1520} 1521 1522template <class _Key, class _Tp, class _Compare, class _Allocator> 1523inline _LIBCPP_INLINE_VISIBILITY 1524bool 1525operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x, 1526 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1527{ 1528 return __y < __x; 1529} 1530 1531template <class _Key, class _Tp, class _Compare, class _Allocator> 1532inline _LIBCPP_INLINE_VISIBILITY 1533bool 1534operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1535 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1536{ 1537 return !(__x < __y); 1538} 1539 1540template <class _Key, class _Tp, class _Compare, class _Allocator> 1541inline _LIBCPP_INLINE_VISIBILITY 1542bool 1543operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1544 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1545{ 1546 return !(__y < __x); 1547} 1548 1549template <class _Key, class _Tp, class _Compare, class _Allocator> 1550inline _LIBCPP_INLINE_VISIBILITY 1551void 1552swap(map<_Key, _Tp, _Compare, _Allocator>& __x, 1553 map<_Key, _Tp, _Compare, _Allocator>& __y) 1554 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1555{ 1556 __x.swap(__y); 1557} 1558 1559template <class _Key, class _Tp, class _Compare = less<_Key>, 1560 class _Allocator = allocator<pair<const _Key, _Tp> > > 1561class _LIBCPP_TEMPLATE_VIS multimap 1562{ 1563public: 1564 // types: 1565 typedef _Key key_type; 1566 typedef _Tp mapped_type; 1567 typedef pair<const key_type, mapped_type> value_type; 1568 typedef _Compare key_compare; 1569 typedef _Allocator allocator_type; 1570 typedef value_type& reference; 1571 typedef const value_type& const_reference; 1572 1573 static_assert((is_same<typename allocator_type::value_type, value_type>::value), 1574 "Allocator::value_type must be same type as value_type"); 1575 1576 class _LIBCPP_TEMPLATE_VIS value_compare 1577 : public binary_function<value_type, value_type, bool> 1578 { 1579 friend class multimap; 1580 protected: 1581 key_compare comp; 1582 1583 _LIBCPP_INLINE_VISIBILITY 1584 value_compare(key_compare c) : comp(c) {} 1585 public: 1586 _LIBCPP_INLINE_VISIBILITY 1587 bool operator()(const value_type& __x, const value_type& __y) const 1588 {return comp(__x.first, __y.first);} 1589 }; 1590 1591private: 1592 1593 typedef _VSTD::__value_type<key_type, mapped_type> __value_type; 1594 typedef __map_value_compare<key_type, __value_type, key_compare> __vc; 1595 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, 1596 __value_type>::type __allocator_type; 1597 typedef __tree<__value_type, __vc, __allocator_type> __base; 1598 typedef typename __base::__node_traits __node_traits; 1599 typedef allocator_traits<allocator_type> __alloc_traits; 1600 1601 __base __tree_; 1602 1603public: 1604 typedef typename __alloc_traits::pointer pointer; 1605 typedef typename __alloc_traits::const_pointer const_pointer; 1606 typedef typename __alloc_traits::size_type size_type; 1607 typedef typename __alloc_traits::difference_type difference_type; 1608 typedef __map_iterator<typename __base::iterator> iterator; 1609 typedef __map_const_iterator<typename __base::const_iterator> const_iterator; 1610 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 1611 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 1612 1613#if _LIBCPP_STD_VER > 14 1614 typedef __map_node_handle<typename __base::__node, allocator_type> node_type; 1615#endif 1616 1617 _LIBCPP_INLINE_VISIBILITY 1618 multimap() 1619 _NOEXCEPT_( 1620 is_nothrow_default_constructible<allocator_type>::value && 1621 is_nothrow_default_constructible<key_compare>::value && 1622 is_nothrow_copy_constructible<key_compare>::value) 1623 : __tree_(__vc(key_compare())) {} 1624 1625 _LIBCPP_INLINE_VISIBILITY 1626 explicit multimap(const key_compare& __comp) 1627 _NOEXCEPT_( 1628 is_nothrow_default_constructible<allocator_type>::value && 1629 is_nothrow_copy_constructible<key_compare>::value) 1630 : __tree_(__vc(__comp)) {} 1631 1632 _LIBCPP_INLINE_VISIBILITY 1633 explicit multimap(const key_compare& __comp, const allocator_type& __a) 1634 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {} 1635 1636 template <class _InputIterator> 1637 _LIBCPP_INLINE_VISIBILITY 1638 multimap(_InputIterator __f, _InputIterator __l, 1639 const key_compare& __comp = key_compare()) 1640 : __tree_(__vc(__comp)) 1641 { 1642 insert(__f, __l); 1643 } 1644 1645 template <class _InputIterator> 1646 _LIBCPP_INLINE_VISIBILITY 1647 multimap(_InputIterator __f, _InputIterator __l, 1648 const key_compare& __comp, const allocator_type& __a) 1649 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) 1650 { 1651 insert(__f, __l); 1652 } 1653 1654#if _LIBCPP_STD_VER > 11 1655 template <class _InputIterator> 1656 _LIBCPP_INLINE_VISIBILITY 1657 multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 1658 : multimap(__f, __l, key_compare(), __a) {} 1659#endif 1660 1661 _LIBCPP_INLINE_VISIBILITY 1662 multimap(const multimap& __m) 1663 : __tree_(__m.__tree_.value_comp(), 1664 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc())) 1665 { 1666 insert(__m.begin(), __m.end()); 1667 } 1668 1669 _LIBCPP_INLINE_VISIBILITY 1670 multimap& operator=(const multimap& __m) 1671 { 1672#ifndef _LIBCPP_CXX03_LANG 1673 __tree_ = __m.__tree_; 1674#else 1675 if (this != &__m) { 1676 __tree_.clear(); 1677 __tree_.value_comp() = __m.__tree_.value_comp(); 1678 __tree_.__copy_assign_alloc(__m.__tree_); 1679 insert(__m.begin(), __m.end()); 1680 } 1681#endif 1682 return *this; 1683 } 1684 1685#ifndef _LIBCPP_CXX03_LANG 1686 1687 _LIBCPP_INLINE_VISIBILITY 1688 multimap(multimap&& __m) 1689 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 1690 : __tree_(_VSTD::move(__m.__tree_)) 1691 { 1692 } 1693 1694 multimap(multimap&& __m, const allocator_type& __a); 1695 1696 _LIBCPP_INLINE_VISIBILITY 1697 multimap& operator=(multimap&& __m) 1698 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 1699 { 1700 __tree_ = _VSTD::move(__m.__tree_); 1701 return *this; 1702 } 1703 1704 _LIBCPP_INLINE_VISIBILITY 1705 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare()) 1706 : __tree_(__vc(__comp)) 1707 { 1708 insert(__il.begin(), __il.end()); 1709 } 1710 1711 _LIBCPP_INLINE_VISIBILITY 1712 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a) 1713 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) 1714 { 1715 insert(__il.begin(), __il.end()); 1716 } 1717 1718#if _LIBCPP_STD_VER > 11 1719 _LIBCPP_INLINE_VISIBILITY 1720 multimap(initializer_list<value_type> __il, const allocator_type& __a) 1721 : multimap(__il, key_compare(), __a) {} 1722#endif 1723 1724 _LIBCPP_INLINE_VISIBILITY 1725 multimap& operator=(initializer_list<value_type> __il) 1726 { 1727 __tree_.__assign_multi(__il.begin(), __il.end()); 1728 return *this; 1729 } 1730 1731#endif // _LIBCPP_CXX03_LANG 1732 1733 _LIBCPP_INLINE_VISIBILITY 1734 explicit multimap(const allocator_type& __a) 1735 : __tree_(typename __base::allocator_type(__a)) 1736 { 1737 } 1738 1739 _LIBCPP_INLINE_VISIBILITY 1740 multimap(const multimap& __m, const allocator_type& __a) 1741 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) 1742 { 1743 insert(__m.begin(), __m.end()); 1744 } 1745 1746 _LIBCPP_INLINE_VISIBILITY 1747 iterator begin() _NOEXCEPT {return __tree_.begin();} 1748 _LIBCPP_INLINE_VISIBILITY 1749 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 1750 _LIBCPP_INLINE_VISIBILITY 1751 iterator end() _NOEXCEPT {return __tree_.end();} 1752 _LIBCPP_INLINE_VISIBILITY 1753 const_iterator end() const _NOEXCEPT {return __tree_.end();} 1754 1755 _LIBCPP_INLINE_VISIBILITY 1756 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());} 1757 _LIBCPP_INLINE_VISIBILITY 1758 const_reverse_iterator rbegin() const _NOEXCEPT 1759 {return const_reverse_iterator(end());} 1760 _LIBCPP_INLINE_VISIBILITY 1761 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());} 1762 _LIBCPP_INLINE_VISIBILITY 1763 const_reverse_iterator rend() const _NOEXCEPT 1764 {return const_reverse_iterator(begin());} 1765 1766 _LIBCPP_INLINE_VISIBILITY 1767 const_iterator cbegin() const _NOEXCEPT {return begin();} 1768 _LIBCPP_INLINE_VISIBILITY 1769 const_iterator cend() const _NOEXCEPT {return end();} 1770 _LIBCPP_INLINE_VISIBILITY 1771 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 1772 _LIBCPP_INLINE_VISIBILITY 1773 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 1774 1775 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 1776 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 1777 _LIBCPP_INLINE_VISIBILITY 1778 size_type size() const _NOEXCEPT {return __tree_.size();} 1779 _LIBCPP_INLINE_VISIBILITY 1780 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 1781 1782 _LIBCPP_INLINE_VISIBILITY 1783 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());} 1784 _LIBCPP_INLINE_VISIBILITY 1785 key_compare key_comp() const {return __tree_.value_comp().key_comp();} 1786 _LIBCPP_INLINE_VISIBILITY 1787 value_compare value_comp() const 1788 {return value_compare(__tree_.value_comp().key_comp());} 1789 1790#ifndef _LIBCPP_CXX03_LANG 1791 1792 template <class ..._Args> 1793 _LIBCPP_INLINE_VISIBILITY 1794 iterator emplace(_Args&& ...__args) { 1795 return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...); 1796 } 1797 1798 template <class ..._Args> 1799 _LIBCPP_INLINE_VISIBILITY 1800 iterator emplace_hint(const_iterator __p, _Args&& ...__args) { 1801 return __tree_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...); 1802 } 1803 1804 template <class _Pp, 1805 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1806 _LIBCPP_INLINE_VISIBILITY 1807 iterator insert(_Pp&& __p) 1808 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));} 1809 1810 template <class _Pp, 1811 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1812 _LIBCPP_INLINE_VISIBILITY 1813 iterator insert(const_iterator __pos, _Pp&& __p) 1814 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));} 1815 1816 _LIBCPP_INLINE_VISIBILITY 1817 iterator insert(value_type&& __v) 1818 {return __tree_.__insert_multi(_VSTD::move(__v));} 1819 1820 _LIBCPP_INLINE_VISIBILITY 1821 iterator insert(const_iterator __p, value_type&& __v) 1822 {return __tree_.__insert_multi(__p.__i_, _VSTD::move(__v));} 1823 1824 1825 _LIBCPP_INLINE_VISIBILITY 1826 void insert(initializer_list<value_type> __il) 1827 {insert(__il.begin(), __il.end());} 1828 1829#endif // _LIBCPP_CXX03_LANG 1830 1831 _LIBCPP_INLINE_VISIBILITY 1832 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);} 1833 1834 _LIBCPP_INLINE_VISIBILITY 1835 iterator insert(const_iterator __p, const value_type& __v) 1836 {return __tree_.__insert_multi(__p.__i_, __v);} 1837 1838 template <class _InputIterator> 1839 _LIBCPP_INLINE_VISIBILITY 1840 void insert(_InputIterator __f, _InputIterator __l) 1841 { 1842 for (const_iterator __e = cend(); __f != __l; ++__f) 1843 __tree_.__insert_multi(__e.__i_, *__f); 1844 } 1845 1846 _LIBCPP_INLINE_VISIBILITY 1847 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);} 1848 _LIBCPP_INLINE_VISIBILITY 1849 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);} 1850 _LIBCPP_INLINE_VISIBILITY 1851 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} 1852 _LIBCPP_INLINE_VISIBILITY 1853 iterator erase(const_iterator __f, const_iterator __l) 1854 {return __tree_.erase(__f.__i_, __l.__i_);} 1855 1856#if _LIBCPP_STD_VER > 14 1857 _LIBCPP_INLINE_VISIBILITY 1858 iterator insert(node_type&& __nh) 1859 { 1860 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1861 "node_type with incompatible allocator passed to multimap::insert()"); 1862 return __tree_.template __node_handle_insert_multi<node_type>( 1863 _VSTD::move(__nh)); 1864 } 1865 _LIBCPP_INLINE_VISIBILITY 1866 iterator insert(const_iterator __hint, node_type&& __nh) 1867 { 1868 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1869 "node_type with incompatible allocator passed to multimap::insert()"); 1870 return __tree_.template __node_handle_insert_multi<node_type>( 1871 __hint.__i_, _VSTD::move(__nh)); 1872 } 1873 _LIBCPP_INLINE_VISIBILITY 1874 node_type extract(key_type const& __key) 1875 { 1876 return __tree_.template __node_handle_extract<node_type>(__key); 1877 } 1878 _LIBCPP_INLINE_VISIBILITY 1879 node_type extract(const_iterator __it) 1880 { 1881 return __tree_.template __node_handle_extract<node_type>( 1882 __it.__i_); 1883 } 1884#endif 1885 1886 _LIBCPP_INLINE_VISIBILITY 1887 void clear() {__tree_.clear();} 1888 1889 _LIBCPP_INLINE_VISIBILITY 1890 void swap(multimap& __m) 1891 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 1892 {__tree_.swap(__m.__tree_);} 1893 1894 _LIBCPP_INLINE_VISIBILITY 1895 iterator find(const key_type& __k) {return __tree_.find(__k);} 1896 _LIBCPP_INLINE_VISIBILITY 1897 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 1898#if _LIBCPP_STD_VER > 11 1899 template <typename _K2> 1900 _LIBCPP_INLINE_VISIBILITY 1901 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 1902 find(const _K2& __k) {return __tree_.find(__k);} 1903 template <typename _K2> 1904 _LIBCPP_INLINE_VISIBILITY 1905 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 1906 find(const _K2& __k) const {return __tree_.find(__k);} 1907#endif 1908 1909 _LIBCPP_INLINE_VISIBILITY 1910 size_type count(const key_type& __k) const 1911 {return __tree_.__count_multi(__k);} 1912#if _LIBCPP_STD_VER > 11 1913 template <typename _K2> 1914 _LIBCPP_INLINE_VISIBILITY 1915 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 1916 count(const _K2& __k) const {return __tree_.__count_multi(__k);} 1917#endif 1918 _LIBCPP_INLINE_VISIBILITY 1919 iterator lower_bound(const key_type& __k) 1920 {return __tree_.lower_bound(__k);} 1921 _LIBCPP_INLINE_VISIBILITY 1922 const_iterator lower_bound(const key_type& __k) const 1923 {return __tree_.lower_bound(__k);} 1924#if _LIBCPP_STD_VER > 11 1925 template <typename _K2> 1926 _LIBCPP_INLINE_VISIBILITY 1927 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 1928 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 1929 1930 template <typename _K2> 1931 _LIBCPP_INLINE_VISIBILITY 1932 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 1933 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 1934#endif 1935 1936 _LIBCPP_INLINE_VISIBILITY 1937 iterator upper_bound(const key_type& __k) 1938 {return __tree_.upper_bound(__k);} 1939 _LIBCPP_INLINE_VISIBILITY 1940 const_iterator upper_bound(const key_type& __k) const 1941 {return __tree_.upper_bound(__k);} 1942#if _LIBCPP_STD_VER > 11 1943 template <typename _K2> 1944 _LIBCPP_INLINE_VISIBILITY 1945 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 1946 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 1947 template <typename _K2> 1948 _LIBCPP_INLINE_VISIBILITY 1949 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 1950 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 1951#endif 1952 1953 _LIBCPP_INLINE_VISIBILITY 1954 pair<iterator,iterator> equal_range(const key_type& __k) 1955 {return __tree_.__equal_range_multi(__k);} 1956 _LIBCPP_INLINE_VISIBILITY 1957 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 1958 {return __tree_.__equal_range_multi(__k);} 1959#if _LIBCPP_STD_VER > 11 1960 template <typename _K2> 1961 _LIBCPP_INLINE_VISIBILITY 1962 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 1963 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 1964 template <typename _K2> 1965 _LIBCPP_INLINE_VISIBILITY 1966 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 1967 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 1968#endif 1969 1970private: 1971 typedef typename __base::__node __node; 1972 typedef typename __base::__node_allocator __node_allocator; 1973 typedef typename __base::__node_pointer __node_pointer; 1974 1975 typedef __map_node_destructor<__node_allocator> _Dp; 1976 typedef unique_ptr<__node, _Dp> __node_holder; 1977}; 1978 1979#ifndef _LIBCPP_CXX03_LANG 1980template <class _Key, class _Tp, class _Compare, class _Allocator> 1981multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a) 1982 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a)) 1983{ 1984 if (__a != __m.get_allocator()) 1985 { 1986 const_iterator __e = cend(); 1987 while (!__m.empty()) 1988 __tree_.__insert_multi(__e.__i_, 1989 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__move())); 1990 } 1991} 1992#endif 1993 1994template <class _Key, class _Tp, class _Compare, class _Allocator> 1995inline _LIBCPP_INLINE_VISIBILITY 1996bool 1997operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 1998 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 1999{ 2000 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 2001} 2002 2003template <class _Key, class _Tp, class _Compare, class _Allocator> 2004inline _LIBCPP_INLINE_VISIBILITY 2005bool 2006operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2007 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2008{ 2009 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 2010} 2011 2012template <class _Key, class _Tp, class _Compare, class _Allocator> 2013inline _LIBCPP_INLINE_VISIBILITY 2014bool 2015operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2016 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2017{ 2018 return !(__x == __y); 2019} 2020 2021template <class _Key, class _Tp, class _Compare, class _Allocator> 2022inline _LIBCPP_INLINE_VISIBILITY 2023bool 2024operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2025 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2026{ 2027 return __y < __x; 2028} 2029 2030template <class _Key, class _Tp, class _Compare, class _Allocator> 2031inline _LIBCPP_INLINE_VISIBILITY 2032bool 2033operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2034 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2035{ 2036 return !(__x < __y); 2037} 2038 2039template <class _Key, class _Tp, class _Compare, class _Allocator> 2040inline _LIBCPP_INLINE_VISIBILITY 2041bool 2042operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2043 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2044{ 2045 return !(__y < __x); 2046} 2047 2048template <class _Key, class _Tp, class _Compare, class _Allocator> 2049inline _LIBCPP_INLINE_VISIBILITY 2050void 2051swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x, 2052 multimap<_Key, _Tp, _Compare, _Allocator>& __y) 2053 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2054{ 2055 __x.swap(__y); 2056} 2057 2058_LIBCPP_END_NAMESPACE_STD 2059 2060#endif // _LIBCPP_MAP 2061