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