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