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