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 _Tp, 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 typedef pair<typename std::remove_const<_Key>::type, _Tp> _Pp; 393 typedef pair<const _Key, _Tp> _CP; 394 public: 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 434 template <class _Key, class _Tp, class _Compare> 435 class __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 442 public: 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 483 template <class _Allocator> 484 class __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; 489 public: 490 typedef typename __alloc_traits::pointer pointer; 491 private: 492 typedef typename value_type::first_type first_type; 493 typedef typename value_type::second_type second_type; 494 495 allocator_type& __na_; 496 497 __map_node_destructor& operator=(const __map_node_destructor&); 498 499 public: 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_.second)); 526 if (__first_constructed) 527 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first)); 528 if (__p) 529 __alloc_traits::deallocate(__na_, __p, 1); 530 } 531 }; 532 533 template <class _Key, class _Tp, class _Compare, class _Allocator> 534 class map; 535 template <class _Key, class _Tp, class _Compare, class _Allocator> 536 class multimap; 537 template <class _TreeIterator> class __map_const_iterator; 538 539 template <class _TreeIterator> 540 class _LIBCPP_VISIBLE __map_iterator 541 { 542 _TreeIterator __i_; 543 544 typedef typename _TreeIterator::__pointer_traits __pointer_traits; 545 typedef const typename _TreeIterator::value_type::first_type __key_type; 546 typedef typename _TreeIterator::value_type::second_type __mapped_type; 547 public: 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 *operator->();} 568 _LIBCPP_INLINE_VISIBILITY 569 pointer operator->() const {return (pointer)__i_.operator->();} 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_VISIBLE map; 600 template <class, class, class, class> friend class _LIBCPP_VISIBLE multimap; 601 template <class> friend class _LIBCPP_VISIBLE __map_const_iterator; 602 }; 603 604 template <class _TreeIterator> 605 class _LIBCPP_VISIBLE __map_const_iterator 606 { 607 _TreeIterator __i_; 608 609 typedef typename _TreeIterator::__pointer_traits __pointer_traits; 610 typedef const typename _TreeIterator::value_type::first_type __key_type; 611 typedef typename _TreeIterator::value_type::second_type __mapped_type; 612 public: 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 *operator->();} 638 _LIBCPP_INLINE_VISIBILITY 639 pointer operator->() const {return (pointer)__i_.operator->();} 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_VISIBLE map; 669 template <class, class, class, class> friend class _LIBCPP_VISIBLE multimap; 670 template <class, class, class> friend class _LIBCPP_VISIBLE __tree_const_iterator; 671 }; 672 673 template <class _Key, class _Tp, class _Compare = less<_Key>, 674 class _Allocator = allocator<pair<const _Key, _Tp> > > 675 class _LIBCPP_VISIBLE map 676 { 677 public: 678 // types: 679 typedef _Key key_type; 680 typedef _Tp mapped_type; 681 typedef pair<const key_type, mapped_type> value_type; 682 typedef _Compare key_compare; 683 typedef _Allocator allocator_type; 684 typedef value_type& reference; 685 typedef const value_type& const_reference; 686 687 class _LIBCPP_VISIBLE value_compare 688 : public binary_function<value_type, value_type, bool> 689 { 690 friend class map; 691 protected: 692 key_compare comp; 693 694 _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {} 695 public: 696 _LIBCPP_INLINE_VISIBILITY 697 bool operator()(const value_type& __x, const value_type& __y) const 698 {return comp(__x.first, __y.first);} 699 }; 700 701 private: 702 typedef pair<key_type, mapped_type> __value_type; 703 typedef __map_value_compare<key_type, mapped_type, key_compare> __vc; 704 typedef typename allocator_traits<allocator_type>::template 705 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 706 rebind_alloc<__value_type> 707 #else 708 rebind_alloc<__value_type>::other 709 #endif 710 __allocator_type; 711 typedef __tree<__value_type, __vc, __allocator_type> __base; 712 typedef typename __base::__node_traits __node_traits; 713 typedef allocator_traits<allocator_type> __alloc_traits; 714 715 __base __tree_; 716 717 public: 718 typedef typename __alloc_traits::pointer pointer; 719 typedef typename __alloc_traits::const_pointer const_pointer; 720 typedef typename __alloc_traits::size_type size_type; 721 typedef typename __alloc_traits::difference_type difference_type; 722 typedef __map_iterator<typename __base::iterator> iterator; 723 typedef __map_const_iterator<typename __base::const_iterator> const_iterator; 724 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 725 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 726 727 _LIBCPP_INLINE_VISIBILITY 728 explicit map(const key_compare& __comp = key_compare()) 729 _NOEXCEPT_( 730 is_nothrow_default_constructible<allocator_type>::value && 731 is_nothrow_default_constructible<key_compare>::value && 732 is_nothrow_copy_constructible<key_compare>::value) 733 : __tree_(__vc(__comp)) {} 734 735 _LIBCPP_INLINE_VISIBILITY 736 explicit map(const key_compare& __comp, const allocator_type& __a) 737 : __tree_(__vc(__comp), __a) {} 738 739 template <class _InputIterator> 740 _LIBCPP_INLINE_VISIBILITY 741 map(_InputIterator __f, _InputIterator __l, 742 const key_compare& __comp = key_compare()) 743 : __tree_(__vc(__comp)) 744 { 745 insert(__f, __l); 746 } 747 748 template <class _InputIterator> 749 _LIBCPP_INLINE_VISIBILITY 750 map(_InputIterator __f, _InputIterator __l, 751 const key_compare& __comp, const allocator_type& __a) 752 : __tree_(__vc(__comp), __a) 753 { 754 insert(__f, __l); 755 } 756 757 _LIBCPP_INLINE_VISIBILITY 758 map(const map& __m) 759 : __tree_(__m.__tree_) 760 { 761 insert(__m.begin(), __m.end()); 762 } 763 764 _LIBCPP_INLINE_VISIBILITY 765 map& operator=(const map& __m) 766 { 767 __tree_ = __m.__tree_; 768 return *this; 769 } 770 771 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 772 773 _LIBCPP_INLINE_VISIBILITY 774 map(map&& __m) 775 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 776 : __tree_(_VSTD::move(__m.__tree_)) 777 { 778 } 779 780 map(map&& __m, const allocator_type& __a); 781 782 _LIBCPP_INLINE_VISIBILITY 783 map& operator=(map&& __m) 784 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 785 { 786 __tree_ = _VSTD::move(__m.__tree_); 787 return *this; 788 } 789 790 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 791 792 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 793 794 _LIBCPP_INLINE_VISIBILITY 795 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare()) 796 : __tree_(__vc(__comp)) 797 { 798 insert(__il.begin(), __il.end()); 799 } 800 801 _LIBCPP_INLINE_VISIBILITY 802 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a) 803 : __tree_(__vc(__comp), __a) 804 { 805 insert(__il.begin(), __il.end()); 806 } 807 808 _LIBCPP_INLINE_VISIBILITY 809 map& operator=(initializer_list<value_type> __il) 810 { 811 __tree_.__assign_unique(__il.begin(), __il.end()); 812 return *this; 813 } 814 815 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 816 817 _LIBCPP_INLINE_VISIBILITY 818 explicit map(const allocator_type& __a) 819 : __tree_(__a) 820 { 821 } 822 823 _LIBCPP_INLINE_VISIBILITY 824 map(const map& __m, const allocator_type& __a) 825 : __tree_(__m.__tree_.value_comp(), __a) 826 { 827 insert(__m.begin(), __m.end()); 828 } 829 830 _LIBCPP_INLINE_VISIBILITY 831 iterator begin() _NOEXCEPT {return __tree_.begin();} 832 _LIBCPP_INLINE_VISIBILITY 833 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 834 _LIBCPP_INLINE_VISIBILITY 835 iterator end() _NOEXCEPT {return __tree_.end();} 836 _LIBCPP_INLINE_VISIBILITY 837 const_iterator end() const _NOEXCEPT {return __tree_.end();} 838 839 _LIBCPP_INLINE_VISIBILITY 840 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());} 841 _LIBCPP_INLINE_VISIBILITY 842 const_reverse_iterator rbegin() const _NOEXCEPT 843 {return const_reverse_iterator(end());} 844 _LIBCPP_INLINE_VISIBILITY 845 reverse_iterator rend() _NOEXCEPT 846 {return reverse_iterator(begin());} 847 _LIBCPP_INLINE_VISIBILITY 848 const_reverse_iterator rend() const _NOEXCEPT 849 {return const_reverse_iterator(begin());} 850 851 _LIBCPP_INLINE_VISIBILITY 852 const_iterator cbegin() const _NOEXCEPT {return begin();} 853 _LIBCPP_INLINE_VISIBILITY 854 const_iterator cend() const _NOEXCEPT {return end();} 855 _LIBCPP_INLINE_VISIBILITY 856 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 857 _LIBCPP_INLINE_VISIBILITY 858 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 859 860 _LIBCPP_INLINE_VISIBILITY 861 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 862 _LIBCPP_INLINE_VISIBILITY 863 size_type size() const _NOEXCEPT {return __tree_.size();} 864 _LIBCPP_INLINE_VISIBILITY 865 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 866 867 mapped_type& operator[](const key_type& __k); 868 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 869 mapped_type& operator[](key_type&& __k); 870 #endif 871 872 mapped_type& at(const key_type& __k); 873 const mapped_type& at(const key_type& __k) const; 874 875 _LIBCPP_INLINE_VISIBILITY 876 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 877 _LIBCPP_INLINE_VISIBILITY 878 key_compare key_comp() const {return __tree_.value_comp().key_comp();} 879 _LIBCPP_INLINE_VISIBILITY 880 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());} 881 882 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 883 #ifndef _LIBCPP_HAS_NO_VARIADICS 884 885 template <class ..._Args> 886 pair<iterator, bool> 887 emplace(_Args&& ...__args); 888 889 template <class ..._Args> 890 iterator 891 emplace_hint(const_iterator __p, _Args&& ...__args); 892 893 #endif // _LIBCPP_HAS_NO_VARIADICS 894 895 template <class _Pp, 896 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 897 _LIBCPP_INLINE_VISIBILITY 898 pair<iterator, bool> insert(_Pp&& __p) 899 {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));} 900 901 template <class _Pp, 902 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 903 _LIBCPP_INLINE_VISIBILITY 904 iterator insert(const_iterator __pos, _Pp&& __p) 905 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));} 906 907 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 908 909 _LIBCPP_INLINE_VISIBILITY 910 pair<iterator, bool> 911 insert(const value_type& __v) {return __tree_.__insert_unique(__v);} 912 913 _LIBCPP_INLINE_VISIBILITY 914 iterator 915 insert(const_iterator __p, const value_type& __v) 916 {return __tree_.__insert_unique(__p.__i_, __v);} 917 918 template <class _InputIterator> 919 _LIBCPP_INLINE_VISIBILITY 920 void insert(_InputIterator __f, _InputIterator __l) 921 { 922 for (const_iterator __e = cend(); __f != __l; ++__f) 923 insert(__e.__i_, *__f); 924 } 925 926 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 927 928 _LIBCPP_INLINE_VISIBILITY 929 void insert(initializer_list<value_type> __il) 930 {insert(__il.begin(), __il.end());} 931 932 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 933 934 _LIBCPP_INLINE_VISIBILITY 935 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);} 936 _LIBCPP_INLINE_VISIBILITY 937 size_type erase(const key_type& __k) 938 {return __tree_.__erase_unique(__k);} 939 _LIBCPP_INLINE_VISIBILITY 940 iterator erase(const_iterator __f, const_iterator __l) 941 {return __tree_.erase(__f.__i_, __l.__i_);} 942 _LIBCPP_INLINE_VISIBILITY 943 void clear() _NOEXCEPT {__tree_.clear();} 944 945 _LIBCPP_INLINE_VISIBILITY 946 void swap(map& __m) 947 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 948 {__tree_.swap(__m.__tree_);} 949 950 _LIBCPP_INLINE_VISIBILITY 951 iterator find(const key_type& __k) {return __tree_.find(__k);} 952 _LIBCPP_INLINE_VISIBILITY 953 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 954 _LIBCPP_INLINE_VISIBILITY 955 size_type count(const key_type& __k) const 956 {return __tree_.__count_unique(__k);} 957 _LIBCPP_INLINE_VISIBILITY 958 iterator lower_bound(const key_type& __k) 959 {return __tree_.lower_bound(__k);} 960 _LIBCPP_INLINE_VISIBILITY 961 const_iterator lower_bound(const key_type& __k) const 962 {return __tree_.lower_bound(__k);} 963 _LIBCPP_INLINE_VISIBILITY 964 iterator upper_bound(const key_type& __k) 965 {return __tree_.upper_bound(__k);} 966 _LIBCPP_INLINE_VISIBILITY 967 const_iterator upper_bound(const key_type& __k) const 968 {return __tree_.upper_bound(__k);} 969 _LIBCPP_INLINE_VISIBILITY 970 pair<iterator,iterator> equal_range(const key_type& __k) 971 {return __tree_.__equal_range_unique(__k);} 972 _LIBCPP_INLINE_VISIBILITY 973 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 974 {return __tree_.__equal_range_unique(__k);} 975 976 private: 977 typedef typename __base::__node __node; 978 typedef typename __base::__node_allocator __node_allocator; 979 typedef typename __base::__node_pointer __node_pointer; 980 typedef typename __base::__node_const_pointer __node_const_pointer; 981 typedef typename __base::__node_base_pointer __node_base_pointer; 982 typedef typename __base::__node_base_const_pointer __node_base_const_pointer; 983 typedef __map_node_destructor<__node_allocator> _Dp; 984 typedef unique_ptr<__node, _Dp> __node_holder; 985 986 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 987 __node_holder __construct_node(); 988 template <class _A0> 989 typename enable_if 990 < 991 is_constructible<value_type, _A0>::value, 992 __node_holder 993 >::type 994 __construct_node(_A0&& __a0); 995 template <class _A0> 996 typename enable_if 997 < 998 is_constructible<key_type, _A0>::value, 999 __node_holder 1000 >::type 1001 __construct_node(_A0&& __a0); 1002 #ifndef _LIBCPP_HAS_NO_VARIADICS 1003 template <class _A0, class _A1, class ..._Args> 1004 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); 1005 #endif // _LIBCPP_HAS_NO_VARIADICS 1006 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1007 __node_holder __construct_node(const key_type& __k); 1008 #endif 1009 1010 __node_base_pointer& 1011 __find_equal_key(__node_base_pointer& __parent, const key_type& __k); 1012 __node_base_pointer& 1013 __find_equal_key(const_iterator __hint, 1014 __node_base_pointer& __parent, const key_type& __k); 1015 __node_base_const_pointer 1016 __find_equal_key(__node_base_const_pointer& __parent, const key_type& __k) const; 1017 }; 1018 1019 // Find place to insert if __k doesn't exist 1020 // Set __parent to parent of null leaf 1021 // Return reference to null leaf 1022 // If __k exists, set parent to node of __k and return reference to node of __k 1023 template <class _Key, class _Tp, class _Compare, class _Allocator> 1024 typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_pointer& 1025 map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_pointer& __parent, 1026 const key_type& __k) 1027 { 1028 __node_pointer __nd = __tree_.__root(); 1029 if (__nd != nullptr) 1030 { 1031 while (true) 1032 { 1033 if (__tree_.value_comp().key_comp()(__k, __nd->__value_.first)) 1034 { 1035 if (__nd->__left_ != nullptr) 1036 __nd = static_cast<__node_pointer>(__nd->__left_); 1037 else 1038 { 1039 __parent = __nd; 1040 return __parent->__left_; 1041 } 1042 } 1043 else if (__tree_.value_comp().key_comp()(__nd->__value_.first, __k)) 1044 { 1045 if (__nd->__right_ != nullptr) 1046 __nd = static_cast<__node_pointer>(__nd->__right_); 1047 else 1048 { 1049 __parent = __nd; 1050 return __parent->__right_; 1051 } 1052 } 1053 else 1054 { 1055 __parent = __nd; 1056 return __parent; 1057 } 1058 } 1059 } 1060 __parent = __tree_.__end_node(); 1061 return __parent->__left_; 1062 } 1063 1064 // Find place to insert if __k doesn't exist 1065 // First check prior to __hint. 1066 // Next check after __hint. 1067 // Next do O(log N) search. 1068 // Set __parent to parent of null leaf 1069 // Return reference to null leaf 1070 // If __k exists, set parent to node of __k and return reference to node of __k 1071 template <class _Key, class _Tp, class _Compare, class _Allocator> 1072 typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_pointer& 1073 map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(const_iterator __hint, 1074 __node_base_pointer& __parent, 1075 const key_type& __k) 1076 { 1077 if (__hint == end() || __tree_.value_comp().key_comp()(__k, __hint->first)) // check before 1078 { 1079 // __k < *__hint 1080 const_iterator __prior = __hint; 1081 if (__prior == begin() || __tree_.value_comp().key_comp()((--__prior)->first, __k)) 1082 { 1083 // *prev(__hint) < __k < *__hint 1084 if (__hint.__ptr_->__left_ == nullptr) 1085 { 1086 __parent = const_cast<__node_pointer&>(__hint.__ptr_); 1087 return __parent->__left_; 1088 } 1089 else 1090 { 1091 __parent = const_cast<__node_pointer&>(__prior.__ptr_); 1092 return __parent->__right_; 1093 } 1094 } 1095 // __k <= *prev(__hint) 1096 return __find_equal_key(__parent, __k); 1097 } 1098 else if (__tree_.value_comp().key_comp()(__hint->first, __k)) // check after 1099 { 1100 // *__hint < __k 1101 const_iterator __next = _VSTD::next(__hint); 1102 if (__next == end() || __tree_.value_comp().key_comp()(__k, __next->first)) 1103 { 1104 // *__hint < __k < *next(__hint) 1105 if (__hint.__ptr_->__right_ == nullptr) 1106 { 1107 __parent = const_cast<__node_pointer&>(__hint.__ptr_); 1108 return __parent->__right_; 1109 } 1110 else 1111 { 1112 __parent = const_cast<__node_pointer&>(__next.__ptr_); 1113 return __parent->__left_; 1114 } 1115 } 1116 // *next(__hint) <= __k 1117 return __find_equal_key(__parent, __k); 1118 } 1119 // else __k == *__hint 1120 __parent = const_cast<__node_pointer&>(__hint.__ptr_); 1121 return __parent; 1122 } 1123 1124 // Find __k 1125 // Set __parent to parent of null leaf and 1126 // return reference to null leaf iv __k does not exist. 1127 // If __k exists, set parent to node of __k and return reference to node of __k 1128 template <class _Key, class _Tp, class _Compare, class _Allocator> 1129 typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_const_pointer 1130 map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_const_pointer& __parent, 1131 const key_type& __k) const 1132 { 1133 __node_const_pointer __nd = __tree_.__root(); 1134 if (__nd != nullptr) 1135 { 1136 while (true) 1137 { 1138 if (__tree_.value_comp().key_comp()(__k, __nd->__value_.first)) 1139 { 1140 if (__nd->__left_ != nullptr) 1141 __nd = static_cast<__node_pointer>(__nd->__left_); 1142 else 1143 { 1144 __parent = __nd; 1145 return const_cast<const __node_base_const_pointer&>(__parent->__left_); 1146 } 1147 } 1148 else if (__tree_.value_comp().key_comp()(__nd->__value_.first, __k)) 1149 { 1150 if (__nd->__right_ != nullptr) 1151 __nd = static_cast<__node_pointer>(__nd->__right_); 1152 else 1153 { 1154 __parent = __nd; 1155 return const_cast<const __node_base_const_pointer&>(__parent->__right_); 1156 } 1157 } 1158 else 1159 { 1160 __parent = __nd; 1161 return __parent; 1162 } 1163 } 1164 } 1165 __parent = __tree_.__end_node(); 1166 return const_cast<const __node_base_const_pointer&>(__parent->__left_); 1167 } 1168 1169 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1170 1171 template <class _Key, class _Tp, class _Compare, class _Allocator> 1172 map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a) 1173 : __tree_(_VSTD::move(__m.__tree_), __a) 1174 { 1175 if (__a != __m.get_allocator()) 1176 { 1177 const_iterator __e = cend(); 1178 while (!__m.empty()) 1179 __tree_.__insert_unique(__e.__i_, 1180 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_)); 1181 } 1182 } 1183 1184 template <class _Key, class _Tp, class _Compare, class _Allocator> 1185 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder 1186 map<_Key, _Tp, _Compare, _Allocator>::__construct_node() 1187 { 1188 __node_allocator& __na = __tree_.__node_alloc(); 1189 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1190 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first)); 1191 __h.get_deleter().__first_constructed = true; 1192 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second)); 1193 __h.get_deleter().__second_constructed = true; 1194 return __h; 1195 } 1196 1197 template <class _Key, class _Tp, class _Compare, class _Allocator> 1198 template <class _A0> 1199 typename enable_if 1200 < 1201 is_constructible<pair<const _Key, _Tp>, _A0>::value, 1202 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder 1203 >::type 1204 map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0) 1205 { 1206 __node_allocator& __na = __tree_.__node_alloc(); 1207 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1208 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0)); 1209 __h.get_deleter().__first_constructed = true; 1210 __h.get_deleter().__second_constructed = true; 1211 return __h; 1212 } 1213 1214 template <class _Key, class _Tp, class _Compare, class _Allocator> 1215 template <class _A0> 1216 typename enable_if 1217 < 1218 is_constructible<_Key, _A0>::value, 1219 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder 1220 >::type 1221 map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0) 1222 { 1223 __node_allocator& __na = __tree_.__node_alloc(); 1224 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1225 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), _VSTD::forward<_A0>(__a0)); 1226 __h.get_deleter().__first_constructed = true; 1227 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second)); 1228 __h.get_deleter().__second_constructed = true; 1229 return __h; 1230 } 1231 1232 #ifndef _LIBCPP_HAS_NO_VARIADICS 1233 1234 template <class _Key, class _Tp, class _Compare, class _Allocator> 1235 template <class _A0, class _A1, class ..._Args> 1236 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder 1237 map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args) 1238 { 1239 __node_allocator& __na = __tree_.__node_alloc(); 1240 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1241 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1242 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), 1243 _VSTD::forward<_Args>(__args)...); 1244 __h.get_deleter().__first_constructed = true; 1245 __h.get_deleter().__second_constructed = true; 1246 return __h; 1247 } 1248 1249 #endif // _LIBCPP_HAS_NO_VARIADICS 1250 1251 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1252 1253 template <class _Key, class _Tp, class _Compare, class _Allocator> 1254 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder 1255 map<_Key, _Tp, _Compare, _Allocator>::__construct_node(const key_type& __k) 1256 { 1257 __node_allocator& __na = __tree_.__node_alloc(); 1258 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1259 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k); 1260 __h.get_deleter().__first_constructed = true; 1261 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second)); 1262 __h.get_deleter().__second_constructed = true; 1263 return _VSTD::move(__h); 1264 } 1265 1266 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1267 1268 template <class _Key, class _Tp, class _Compare, class _Allocator> 1269 _Tp& 1270 map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) 1271 { 1272 __node_base_pointer __parent; 1273 __node_base_pointer& __child = __find_equal_key(__parent, __k); 1274 __node_pointer __r = static_cast<__node_pointer>(__child); 1275 if (__child == nullptr) 1276 { 1277 __node_holder __h = __construct_node(__k); 1278 __tree_.__insert_node_at(__parent, __child, __h.get()); 1279 __r = __h.release(); 1280 } 1281 return __r->__value_.second; 1282 } 1283 1284 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1285 1286 template <class _Key, class _Tp, class _Compare, class _Allocator> 1287 _Tp& 1288 map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k) 1289 { 1290 __node_base_pointer __parent; 1291 __node_base_pointer& __child = __find_equal_key(__parent, __k); 1292 __node_pointer __r = static_cast<__node_pointer>(__child); 1293 if (__child == nullptr) 1294 { 1295 __node_holder __h = __construct_node(_VSTD::move(__k)); 1296 __tree_.__insert_node_at(__parent, __child, __h.get()); 1297 __r = __h.release(); 1298 } 1299 return __r->__value_.second; 1300 } 1301 1302 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1303 1304 template <class _Key, class _Tp, class _Compare, class _Allocator> 1305 _Tp& 1306 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) 1307 { 1308 __node_base_pointer __parent; 1309 __node_base_pointer& __child = __find_equal_key(__parent, __k); 1310 #ifndef _LIBCPP_NO_EXCEPTIONS 1311 if (__child == nullptr) 1312 throw out_of_range("map::at: key not found"); 1313 #endif // _LIBCPP_NO_EXCEPTIONS 1314 return static_cast<__node_pointer>(__child)->__value_.second; 1315 } 1316 1317 template <class _Key, class _Tp, class _Compare, class _Allocator> 1318 const _Tp& 1319 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const 1320 { 1321 __node_base_const_pointer __parent; 1322 __node_base_const_pointer __child = __find_equal_key(__parent, __k); 1323 #ifndef _LIBCPP_NO_EXCEPTIONS 1324 if (__child == nullptr) 1325 throw out_of_range("map::at: key not found"); 1326 #endif // _LIBCPP_NO_EXCEPTIONS 1327 return static_cast<__node_const_pointer>(__child)->__value_.second; 1328 } 1329 1330 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1331 1332 template <class _Key, class _Tp, class _Compare, class _Allocator> 1333 template <class ..._Args> 1334 pair<typename map<_Key, _Tp, _Compare, _Allocator>::iterator, bool> 1335 map<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args) 1336 { 1337 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1338 pair<iterator, bool> __r = __tree_.__node_insert_unique(__h.get()); 1339 if (__r.second) 1340 __h.release(); 1341 return __r; 1342 } 1343 1344 template <class _Key, class _Tp, class _Compare, class _Allocator> 1345 template <class ..._Args> 1346 typename map<_Key, _Tp, _Compare, _Allocator>::iterator 1347 map<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p, 1348 _Args&& ...__args) 1349 { 1350 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1351 iterator __r = __tree_.__node_insert_unique(__p.__i_, __h.get()); 1352 if (__r.__i_.__ptr_ == __h.get()) 1353 __h.release(); 1354 return __r; 1355 } 1356 1357 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1358 1359 template <class _Key, class _Tp, class _Compare, class _Allocator> 1360 inline _LIBCPP_INLINE_VISIBILITY 1361 bool 1362 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1363 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1364 { 1365 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 1366 } 1367 1368 template <class _Key, class _Tp, class _Compare, class _Allocator> 1369 inline _LIBCPP_INLINE_VISIBILITY 1370 bool 1371 operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x, 1372 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1373 { 1374 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 1375 } 1376 1377 template <class _Key, class _Tp, class _Compare, class _Allocator> 1378 inline _LIBCPP_INLINE_VISIBILITY 1379 bool 1380 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1381 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1382 { 1383 return !(__x == __y); 1384 } 1385 1386 template <class _Key, class _Tp, class _Compare, class _Allocator> 1387 inline _LIBCPP_INLINE_VISIBILITY 1388 bool 1389 operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x, 1390 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1391 { 1392 return __y < __x; 1393 } 1394 1395 template <class _Key, class _Tp, class _Compare, class _Allocator> 1396 inline _LIBCPP_INLINE_VISIBILITY 1397 bool 1398 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1399 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1400 { 1401 return !(__x < __y); 1402 } 1403 1404 template <class _Key, class _Tp, class _Compare, class _Allocator> 1405 inline _LIBCPP_INLINE_VISIBILITY 1406 bool 1407 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x, 1408 const map<_Key, _Tp, _Compare, _Allocator>& __y) 1409 { 1410 return !(__y < __x); 1411 } 1412 1413 template <class _Key, class _Tp, class _Compare, class _Allocator> 1414 inline _LIBCPP_INLINE_VISIBILITY 1415 void 1416 swap(map<_Key, _Tp, _Compare, _Allocator>& __x, 1417 map<_Key, _Tp, _Compare, _Allocator>& __y) 1418 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1419 { 1420 __x.swap(__y); 1421 } 1422 1423 template <class _Key, class _Tp, class _Compare = less<_Key>, 1424 class _Allocator = allocator<pair<const _Key, _Tp> > > 1425 class _LIBCPP_VISIBLE multimap 1426 { 1427 public: 1428 // types: 1429 typedef _Key key_type; 1430 typedef _Tp mapped_type; 1431 typedef pair<const key_type, mapped_type> value_type; 1432 typedef _Compare key_compare; 1433 typedef _Allocator allocator_type; 1434 typedef value_type& reference; 1435 typedef const value_type& const_reference; 1436 1437 class _LIBCPP_VISIBLE value_compare 1438 : public binary_function<value_type, value_type, bool> 1439 { 1440 friend class multimap; 1441 protected: 1442 key_compare comp; 1443 1444 _LIBCPP_INLINE_VISIBILITY 1445 value_compare(key_compare c) : comp(c) {} 1446 public: 1447 _LIBCPP_INLINE_VISIBILITY 1448 bool operator()(const value_type& __x, const value_type& __y) const 1449 {return comp(__x.first, __y.first);} 1450 }; 1451 1452 private: 1453 typedef pair<key_type, mapped_type> __value_type; 1454 typedef __map_value_compare<key_type, mapped_type, key_compare> __vc; 1455 typedef typename allocator_traits<allocator_type>::template 1456 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 1457 rebind_alloc<__value_type> 1458 #else 1459 rebind_alloc<__value_type>::other 1460 #endif 1461 __allocator_type; 1462 typedef __tree<__value_type, __vc, __allocator_type> __base; 1463 typedef typename __base::__node_traits __node_traits; 1464 typedef allocator_traits<allocator_type> __alloc_traits; 1465 1466 __base __tree_; 1467 1468 public: 1469 typedef typename __alloc_traits::pointer pointer; 1470 typedef typename __alloc_traits::const_pointer const_pointer; 1471 typedef typename __alloc_traits::size_type size_type; 1472 typedef typename __alloc_traits::difference_type difference_type; 1473 typedef __map_iterator<typename __base::iterator> iterator; 1474 typedef __map_const_iterator<typename __base::const_iterator> const_iterator; 1475 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 1476 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 1477 1478 _LIBCPP_INLINE_VISIBILITY 1479 explicit multimap(const key_compare& __comp = key_compare()) 1480 _NOEXCEPT_( 1481 is_nothrow_default_constructible<allocator_type>::value && 1482 is_nothrow_default_constructible<key_compare>::value && 1483 is_nothrow_copy_constructible<key_compare>::value) 1484 : __tree_(__vc(__comp)) {} 1485 1486 _LIBCPP_INLINE_VISIBILITY 1487 explicit multimap(const key_compare& __comp, const allocator_type& __a) 1488 : __tree_(__vc(__comp), __a) {} 1489 1490 template <class _InputIterator> 1491 _LIBCPP_INLINE_VISIBILITY 1492 multimap(_InputIterator __f, _InputIterator __l, 1493 const key_compare& __comp = key_compare()) 1494 : __tree_(__vc(__comp)) 1495 { 1496 insert(__f, __l); 1497 } 1498 1499 template <class _InputIterator> 1500 _LIBCPP_INLINE_VISIBILITY 1501 multimap(_InputIterator __f, _InputIterator __l, 1502 const key_compare& __comp, const allocator_type& __a) 1503 : __tree_(__vc(__comp), __a) 1504 { 1505 insert(__f, __l); 1506 } 1507 1508 _LIBCPP_INLINE_VISIBILITY 1509 multimap(const multimap& __m) 1510 : __tree_(__m.__tree_.value_comp(), 1511 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc())) 1512 { 1513 insert(__m.begin(), __m.end()); 1514 } 1515 1516 _LIBCPP_INLINE_VISIBILITY 1517 multimap& operator=(const multimap& __m) 1518 { 1519 __tree_ = __m.__tree_; 1520 return *this; 1521 } 1522 1523 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1524 1525 _LIBCPP_INLINE_VISIBILITY 1526 multimap(multimap&& __m) 1527 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 1528 : __tree_(_VSTD::move(__m.__tree_)) 1529 { 1530 } 1531 1532 multimap(multimap&& __m, const allocator_type& __a); 1533 1534 _LIBCPP_INLINE_VISIBILITY 1535 multimap& operator=(multimap&& __m) 1536 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 1537 { 1538 __tree_ = _VSTD::move(__m.__tree_); 1539 return *this; 1540 } 1541 1542 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1543 1544 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1545 1546 _LIBCPP_INLINE_VISIBILITY 1547 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare()) 1548 : __tree_(__vc(__comp)) 1549 { 1550 insert(__il.begin(), __il.end()); 1551 } 1552 1553 _LIBCPP_INLINE_VISIBILITY 1554 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a) 1555 : __tree_(__vc(__comp), __a) 1556 { 1557 insert(__il.begin(), __il.end()); 1558 } 1559 1560 _LIBCPP_INLINE_VISIBILITY 1561 multimap& operator=(initializer_list<value_type> __il) 1562 { 1563 __tree_.__assign_multi(__il.begin(), __il.end()); 1564 return *this; 1565 } 1566 1567 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1568 1569 _LIBCPP_INLINE_VISIBILITY 1570 explicit multimap(const allocator_type& __a) 1571 : __tree_(__a) 1572 { 1573 } 1574 1575 _LIBCPP_INLINE_VISIBILITY 1576 multimap(const multimap& __m, const allocator_type& __a) 1577 : __tree_(__m.__tree_.value_comp(), __a) 1578 { 1579 insert(__m.begin(), __m.end()); 1580 } 1581 1582 _LIBCPP_INLINE_VISIBILITY 1583 iterator begin() _NOEXCEPT {return __tree_.begin();} 1584 _LIBCPP_INLINE_VISIBILITY 1585 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 1586 _LIBCPP_INLINE_VISIBILITY 1587 iterator end() _NOEXCEPT {return __tree_.end();} 1588 _LIBCPP_INLINE_VISIBILITY 1589 const_iterator end() const _NOEXCEPT {return __tree_.end();} 1590 1591 _LIBCPP_INLINE_VISIBILITY 1592 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());} 1593 _LIBCPP_INLINE_VISIBILITY 1594 const_reverse_iterator rbegin() const _NOEXCEPT 1595 {return const_reverse_iterator(end());} 1596 _LIBCPP_INLINE_VISIBILITY 1597 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());} 1598 _LIBCPP_INLINE_VISIBILITY 1599 const_reverse_iterator rend() const _NOEXCEPT 1600 {return const_reverse_iterator(begin());} 1601 1602 _LIBCPP_INLINE_VISIBILITY 1603 const_iterator cbegin() const _NOEXCEPT {return begin();} 1604 _LIBCPP_INLINE_VISIBILITY 1605 const_iterator cend() const _NOEXCEPT {return end();} 1606 _LIBCPP_INLINE_VISIBILITY 1607 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 1608 _LIBCPP_INLINE_VISIBILITY 1609 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 1610 1611 _LIBCPP_INLINE_VISIBILITY 1612 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 1613 _LIBCPP_INLINE_VISIBILITY 1614 size_type size() const _NOEXCEPT {return __tree_.size();} 1615 _LIBCPP_INLINE_VISIBILITY 1616 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 1617 1618 _LIBCPP_INLINE_VISIBILITY 1619 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 1620 _LIBCPP_INLINE_VISIBILITY 1621 key_compare key_comp() const {return __tree_.value_comp().key_comp();} 1622 _LIBCPP_INLINE_VISIBILITY 1623 value_compare value_comp() const 1624 {return value_compare(__tree_.value_comp().key_comp());} 1625 1626 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1627 #ifndef _LIBCPP_HAS_NO_VARIADICS 1628 1629 template <class ..._Args> 1630 iterator 1631 emplace(_Args&& ...__args); 1632 1633 template <class ..._Args> 1634 iterator 1635 emplace_hint(const_iterator __p, _Args&& ...__args); 1636 1637 #endif // _LIBCPP_HAS_NO_VARIADICS 1638 1639 template <class _Pp, 1640 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1641 _LIBCPP_INLINE_VISIBILITY 1642 iterator insert(_Pp&& __p) 1643 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));} 1644 1645 template <class _Pp, 1646 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1647 _LIBCPP_INLINE_VISIBILITY 1648 iterator insert(const_iterator __pos, _Pp&& __p) 1649 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));} 1650 1651 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1652 1653 _LIBCPP_INLINE_VISIBILITY 1654 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);} 1655 1656 _LIBCPP_INLINE_VISIBILITY 1657 iterator insert(const_iterator __p, const value_type& __v) 1658 {return __tree_.__insert_multi(__p.__i_, __v);} 1659 1660 template <class _InputIterator> 1661 _LIBCPP_INLINE_VISIBILITY 1662 void insert(_InputIterator __f, _InputIterator __l) 1663 { 1664 for (const_iterator __e = cend(); __f != __l; ++__f) 1665 __tree_.__insert_multi(__e.__i_, *__f); 1666 } 1667 1668 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1669 1670 _LIBCPP_INLINE_VISIBILITY 1671 void insert(initializer_list<value_type> __il) 1672 {insert(__il.begin(), __il.end());} 1673 1674 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1675 1676 _LIBCPP_INLINE_VISIBILITY 1677 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);} 1678 _LIBCPP_INLINE_VISIBILITY 1679 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} 1680 _LIBCPP_INLINE_VISIBILITY 1681 iterator erase(const_iterator __f, const_iterator __l) 1682 {return __tree_.erase(__f.__i_, __l.__i_);} 1683 _LIBCPP_INLINE_VISIBILITY 1684 void clear() {__tree_.clear();} 1685 1686 _LIBCPP_INLINE_VISIBILITY 1687 void swap(multimap& __m) 1688 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 1689 {__tree_.swap(__m.__tree_);} 1690 1691 _LIBCPP_INLINE_VISIBILITY 1692 iterator find(const key_type& __k) {return __tree_.find(__k);} 1693 _LIBCPP_INLINE_VISIBILITY 1694 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 1695 _LIBCPP_INLINE_VISIBILITY 1696 size_type count(const key_type& __k) const 1697 {return __tree_.__count_multi(__k);} 1698 _LIBCPP_INLINE_VISIBILITY 1699 iterator lower_bound(const key_type& __k) 1700 {return __tree_.lower_bound(__k);} 1701 _LIBCPP_INLINE_VISIBILITY 1702 const_iterator lower_bound(const key_type& __k) const 1703 {return __tree_.lower_bound(__k);} 1704 _LIBCPP_INLINE_VISIBILITY 1705 iterator upper_bound(const key_type& __k) 1706 {return __tree_.upper_bound(__k);} 1707 _LIBCPP_INLINE_VISIBILITY 1708 const_iterator upper_bound(const key_type& __k) const 1709 {return __tree_.upper_bound(__k);} 1710 _LIBCPP_INLINE_VISIBILITY 1711 pair<iterator,iterator> equal_range(const key_type& __k) 1712 {return __tree_.__equal_range_multi(__k);} 1713 _LIBCPP_INLINE_VISIBILITY 1714 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 1715 {return __tree_.__equal_range_multi(__k);} 1716 1717 private: 1718 typedef typename __base::__node __node; 1719 typedef typename __base::__node_allocator __node_allocator; 1720 typedef typename __base::__node_pointer __node_pointer; 1721 typedef typename __base::__node_const_pointer __node_const_pointer; 1722 typedef __map_node_destructor<__node_allocator> _Dp; 1723 typedef unique_ptr<__node, _Dp> __node_holder; 1724 1725 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1726 __node_holder __construct_node(); 1727 template <class _A0> 1728 typename enable_if 1729 < 1730 is_constructible<value_type, _A0>::value, 1731 __node_holder 1732 >::type 1733 __construct_node(_A0&& __a0); 1734 template <class _A0> 1735 typename enable_if 1736 < 1737 is_constructible<key_type, _A0>::value, 1738 __node_holder 1739 >::type 1740 __construct_node(_A0&& __a0); 1741 #ifndef _LIBCPP_HAS_NO_VARIADICS 1742 template <class _A0, class _A1, class ..._Args> 1743 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); 1744 #endif // _LIBCPP_HAS_NO_VARIADICS 1745 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1746 }; 1747 1748 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1749 1750 template <class _Key, class _Tp, class _Compare, class _Allocator> 1751 multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a) 1752 : __tree_(_VSTD::move(__m.__tree_), __a) 1753 { 1754 if (__a != __m.get_allocator()) 1755 { 1756 const_iterator __e = cend(); 1757 while (!__m.empty()) 1758 __tree_.__insert_multi(__e.__i_, 1759 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_)); 1760 } 1761 } 1762 1763 template <class _Key, class _Tp, class _Compare, class _Allocator> 1764 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder 1765 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node() 1766 { 1767 __node_allocator& __na = __tree_.__node_alloc(); 1768 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1769 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first)); 1770 __h.get_deleter().__first_constructed = true; 1771 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second)); 1772 __h.get_deleter().__second_constructed = true; 1773 return __h; 1774 } 1775 1776 template <class _Key, class _Tp, class _Compare, class _Allocator> 1777 template <class _A0> 1778 typename enable_if 1779 < 1780 is_constructible<pair<const _Key, _Tp>, _A0>::value, 1781 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder 1782 >::type 1783 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0) 1784 { 1785 __node_allocator& __na = __tree_.__node_alloc(); 1786 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1787 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0)); 1788 __h.get_deleter().__first_constructed = true; 1789 __h.get_deleter().__second_constructed = true; 1790 return __h; 1791 } 1792 1793 template <class _Key, class _Tp, class _Compare, class _Allocator> 1794 template <class _A0> 1795 typename enable_if 1796 < 1797 is_constructible<_Key, _A0>::value, 1798 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder 1799 >::type 1800 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0) 1801 { 1802 __node_allocator& __na = __tree_.__node_alloc(); 1803 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1804 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), _VSTD::forward<_A0>(__a0)); 1805 __h.get_deleter().__first_constructed = true; 1806 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second)); 1807 __h.get_deleter().__second_constructed = true; 1808 return __h; 1809 } 1810 1811 #ifndef _LIBCPP_HAS_NO_VARIADICS 1812 1813 template <class _Key, class _Tp, class _Compare, class _Allocator> 1814 template <class _A0, class _A1, class ..._Args> 1815 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder 1816 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args) 1817 { 1818 __node_allocator& __na = __tree_.__node_alloc(); 1819 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1820 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1821 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), 1822 _VSTD::forward<_Args>(__args)...); 1823 __h.get_deleter().__first_constructed = true; 1824 __h.get_deleter().__second_constructed = true; 1825 return __h; 1826 } 1827 1828 #endif // _LIBCPP_HAS_NO_VARIADICS 1829 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1830 1831 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1832 1833 template <class _Key, class _Tp, class _Compare, class _Allocator> 1834 template <class ..._Args> 1835 typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator 1836 multimap<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args) 1837 { 1838 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1839 iterator __r = __tree_.__node_insert_multi(__h.get()); 1840 __h.release(); 1841 return __r; 1842 } 1843 1844 template <class _Key, class _Tp, class _Compare, class _Allocator> 1845 template <class ..._Args> 1846 typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator 1847 multimap<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p, 1848 _Args&& ...__args) 1849 { 1850 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1851 iterator __r = __tree_.__node_insert_multi(__p.__i_, __h.get()); 1852 __h.release(); 1853 return __r; 1854 } 1855 1856 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1857 1858 template <class _Key, class _Tp, class _Compare, class _Allocator> 1859 inline _LIBCPP_INLINE_VISIBILITY 1860 bool 1861 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 1862 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 1863 { 1864 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 1865 } 1866 1867 template <class _Key, class _Tp, class _Compare, class _Allocator> 1868 inline _LIBCPP_INLINE_VISIBILITY 1869 bool 1870 operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 1871 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 1872 { 1873 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 1874 } 1875 1876 template <class _Key, class _Tp, class _Compare, class _Allocator> 1877 inline _LIBCPP_INLINE_VISIBILITY 1878 bool 1879 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 1880 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 1881 { 1882 return !(__x == __y); 1883 } 1884 1885 template <class _Key, class _Tp, class _Compare, class _Allocator> 1886 inline _LIBCPP_INLINE_VISIBILITY 1887 bool 1888 operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 1889 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 1890 { 1891 return __y < __x; 1892 } 1893 1894 template <class _Key, class _Tp, class _Compare, class _Allocator> 1895 inline _LIBCPP_INLINE_VISIBILITY 1896 bool 1897 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 1898 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 1899 { 1900 return !(__x < __y); 1901 } 1902 1903 template <class _Key, class _Tp, class _Compare, class _Allocator> 1904 inline _LIBCPP_INLINE_VISIBILITY 1905 bool 1906 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, 1907 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) 1908 { 1909 return !(__y < __x); 1910 } 1911 1912 template <class _Key, class _Tp, class _Compare, class _Allocator> 1913 inline _LIBCPP_INLINE_VISIBILITY 1914 void 1915 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x, 1916 multimap<_Key, _Tp, _Compare, _Allocator>& __y) 1917 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1918 { 1919 __x.swap(__y); 1920 } 1921 1922 _LIBCPP_END_NAMESPACE_STD 1923 1924 #endif // _LIBCPP_MAP 1925
