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