contrib/libc++/include/map

   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