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