contrib/llvm-project/libcxx/include/map

   1 // -*- C++ -*-
   2 //===----------------------------- map ------------------------------------===//
   3 //
   4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   5 // See https://llvm.org/LICENSE.txt for license information.
   6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef _LIBCPP_MAP
  11 #define _LIBCPP_MAP
  12
  13 /*
  14
  15     map synopsis
  16
  17 namespace std
  18 {
  19
  20 template <class Key, class T, class Compare = less<Key>,
  21           class Allocator = allocator<pair<const Key, T>>>
  22 class map
  23 {
  24 public:
  25     // types:
  26     typedef Key                                      key_type;
  27     typedef T                                        mapped_type;
  28     typedef pair<const key_type, mapped_type>        value_type;
  29     typedef Compare                                  key_compare;
  30     typedef Allocator                                allocator_type;
  31     typedef typename allocator_type::reference       reference;
  32     typedef typename allocator_type::const_reference const_reference;
  33     typedef typename allocator_type::pointer         pointer;
  34     typedef typename allocator_type::const_pointer   const_pointer;
  35     typedef typename allocator_type::size_type       size_type;
  36     typedef typename allocator_type::difference_type difference_type;
  37
  38     typedef implementation-defined                   iterator;
  39     typedef implementation-defined                   const_iterator;
  40     typedef std::reverse_iterator<iterator>          reverse_iterator;
  41     typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
  42     typedef unspecified                              node_type;              // C++17
  43     typedef INSERT_RETURN_TYPE<iterator, node_type>  insert_return_type;     // C++17
  44
  45     class value_compare
  46         : public binary_function<value_type, value_type, bool>
  47     {
  48         friend class map;
  49     protected:
  50         key_compare comp;
  51
  52         value_compare(key_compare c);
  53     public:
  54         bool operator()(const value_type& x, const value_type& y) const;
  55     };
  56
  57     // construct/copy/destroy:
  58     map()
  59         noexcept(
  60             is_nothrow_default_constructible<allocator_type>::value &&
  61             is_nothrow_default_constructible<key_compare>::value &&
  62             is_nothrow_copy_constructible<key_compare>::value);
  63     explicit map(const key_compare& comp);
  64     map(const key_compare& comp, const allocator_type& a);
  65     template <class InputIterator>
  66         map(InputIterator first, InputIterator last,
  67             const key_compare& comp = key_compare());
  68     template <class InputIterator>
  69         map(InputIterator first, InputIterator last,
  70             const key_compare& comp, const allocator_type& a);
  71     map(const map& m);
  72     map(map&& m)
  73         noexcept(
  74             is_nothrow_move_constructible<allocator_type>::value &&
  75             is_nothrow_move_constructible<key_compare>::value);
  76     explicit map(const allocator_type& a);
  77     map(const map& m, const allocator_type& a);
  78     map(map&& m, const allocator_type& a);
  79     map(initializer_list<value_type> il, const key_compare& comp = key_compare());
  80     map(initializer_list<value_type> il, const key_compare& comp, const allocator_type& a);
  81     template <class InputIterator>
  82         map(InputIterator first, InputIterator last, const allocator_type& a)
  83             : map(first, last, Compare(), a) {}  // C++14
  84     map(initializer_list<value_type> il, const allocator_type& a)
  85         : map(il, Compare(), a) {}  // C++14
  86    ~map();
  87
  88     map& operator=(const map& m);
  89     map& operator=(map&& m)
  90         noexcept(
  91             allocator_type::propagate_on_container_move_assignment::value &&
  92             is_nothrow_move_assignable<allocator_type>::value &&
  93             is_nothrow_move_assignable<key_compare>::value);
  94     map& operator=(initializer_list<value_type> il);
  95
  96     // iterators:
  97           iterator begin() noexcept;
  98     const_iterator begin() const noexcept;
  99           iterator end() noexcept;
 100     const_iterator end()   const noexcept;
 101
 102           reverse_iterator rbegin() noexcept;
 103     const_reverse_iterator rbegin() const noexcept;
 104           reverse_iterator rend() noexcept;
 105     const_reverse_iterator rend()   const noexcept;
 106
 107     const_iterator         cbegin()  const noexcept;
 108     const_iterator         cend()    const noexcept;
 109     const_reverse_iterator crbegin() const noexcept;
 110     const_reverse_iterator crend()   const noexcept;
 111
 112     // capacity:
 113     bool      empty()    const noexcept;
 114     size_type size()     const noexcept;
 115     size_type max_size() const noexcept;
 116
 117     // element access:
 118     mapped_type& operator[](const key_type& k);
 119     mapped_type& operator[](key_type&& k);
 120
 121           mapped_type& at(const key_type& k);
 122     const mapped_type& at(const key_type& k) const;
 123
 124     // modifiers:
 125     template <class... Args>
 126         pair<iterator, bool> emplace(Args&&... args);
 127     template <class... Args>
 128         iterator emplace_hint(const_iterator position, Args&&... args);
 129     pair<iterator, bool> insert(const value_type& v);
 130     pair<iterator, bool> insert(      value_type&& v);                                // C++17
 131     template <class P>
 132         pair<iterator, bool> insert(P&& p);
 133     iterator insert(const_iterator position, const value_type& v);
 134     iterator insert(const_iterator position,       value_type&& v);                   // C++17
 135     template <class P>
 136         iterator insert(const_iterator position, P&& p);
 137     template <class InputIterator>
 138         void insert(InputIterator first, InputIterator last);
 139     void insert(initializer_list<value_type> il);
 140
 141     node_type extract(const_iterator position);                                       // C++17
 142     node_type extract(const key_type& x);                                             // C++17
 143     insert_return_type insert(node_type&& nh);                                        // C++17
 144     iterator insert(const_iterator hint, node_type&& nh);                             // C++17
 145
 146     template <class... Args>
 147         pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);          // C++17
 148     template <class... Args>
 149         pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);               // C++17
 150     template <class... Args>
 151         iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17
 152     template <class... Args>
 153         iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);      // C++17
 154     template <class M>
 155         pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);            // C++17
 156     template <class M>
 157         pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);                 // C++17
 158     template <class M>
 159         iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);   // C++17
 160     template <class M>
 161         iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);        // C++17
 162
 163     iterator  erase(const_iterator position);
 164     iterator  erase(iterator position); // C++14
 165     size_type erase(const key_type& k);
 166     iterator  erase(const_iterator first, const_iterator last);
 167     void clear() noexcept;
 168
 169     template<class C2>
 170       void merge(map<Key, T, C2, Allocator>& source);         // C++17
 171     template<class C2>
 172       void merge(map<Key, T, C2, Allocator>&& source);        // C++17
 173     template<class C2>
 174       void merge(multimap<Key, T, C2, Allocator>& source);    // C++17
 175     template<class C2>
 176       void merge(multimap<Key, T, C2, Allocator>&& source);   // C++17
 177
 178     void swap(map& m)
 179         noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
 180             is_nothrow_swappable<key_compare>::value); // C++17
 181
 182     // observers:
 183     allocator_type get_allocator() const noexcept;
 184     key_compare    key_comp()      const;
 185     value_compare  value_comp()    const;
 186
 187     // map operations:
 188           iterator find(const key_type& k);
 189     const_iterator find(const key_type& k) const;
 190     template<typename K>
 191         iterator find(const K& x);              // C++14
 192     template<typename K>
 193         const_iterator find(const K& x) const;  // C++14
 194     template<typename K>
 195       size_type count(const K& x) const;        // C++14
 196     size_type      count(const key_type& k) const;
 197         bool contains(const key_type& x) const; // C++20
 198           iterator lower_bound(const key_type& k);
 199     const_iterator lower_bound(const key_type& k) const;
 200     template<typename K>
 201         iterator lower_bound(const K& x);              // C++14
 202     template<typename K>
 203         const_iterator lower_bound(const K& x) const;  // C++14
 204
 205           iterator upper_bound(const key_type& k);
 206     const_iterator upper_bound(const key_type& k) const;
 207     template<typename K>
 208         iterator upper_bound(const K& x);              // C++14
 209     template<typename K>
 210         const_iterator upper_bound(const K& x) const;  // C++14
 211
 212     pair<iterator,iterator>             equal_range(const key_type& k);
 213     pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
 214     template<typename K>
 215         pair<iterator,iterator>             equal_range(const K& x);        // C++14
 216     template<typename K>
 217         pair<const_iterator,const_iterator> equal_range(const K& x) const;  // C++14
 218 };
 219
 220 template <class Key, class T, class Compare, class Allocator>
 221 bool
 222 operator==(const map<Key, T, Compare, Allocator>& x,
 223            const map<Key, T, Compare, Allocator>& y);
 224
 225 template <class Key, class T, class Compare, class Allocator>
 226 bool
 227 operator< (const map<Key, T, Compare, Allocator>& x,
 228            const map<Key, T, Compare, Allocator>& y);
 229
 230 template <class Key, class T, class Compare, class Allocator>
 231 bool
 232 operator!=(const map<Key, T, Compare, Allocator>& x,
 233            const map<Key, T, Compare, Allocator>& y);
 234
 235 template <class Key, class T, class Compare, class Allocator>
 236 bool
 237 operator> (const map<Key, T, Compare, Allocator>& x,
 238            const map<Key, T, Compare, Allocator>& y);
 239
 240 template <class Key, class T, class Compare, class Allocator>
 241 bool
 242 operator>=(const map<Key, T, Compare, Allocator>& x,
 243            const map<Key, T, Compare, Allocator>& y);
 244
 245 template <class Key, class T, class Compare, class Allocator>
 246 bool
 247 operator<=(const map<Key, T, Compare, Allocator>& x,
 248            const map<Key, T, Compare, Allocator>& y);
 249
 250 // specialized algorithms:
 251 template <class Key, class T, class Compare, class Allocator>
 252 void
 253 swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y)
 254     noexcept(noexcept(x.swap(y)));
 255
 256 template <class Key, class T, class Compare, class Allocator, class Predicate>
 257 typename map<Key, T, Compare, Allocator>::size_type
 258 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     size_type      count(const key_type& k) const;
 412         bool contains(const key_type& x) const; // C++20
 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 typename multimap<Key, T, Compare, Allocator>::size_type
 474 erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred);  // C++20
 475
 476 }  // std
 477
 478 */
 479
 480 #include <__config>
 481 #include <__tree>
 482 #include <__node_handle>
 483 #include <iterator>
 484 #include <memory>
 485 #include <utility>
 486 #include <functional>
 487 #include <initializer_list>
 488 #include <type_traits>
 489 #include <version>
 490
 491 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 492 #pragma GCC system_header
 493 #endif
 494
 495 _LIBCPP_BEGIN_NAMESPACE_STD
 496
 497 template <class _Key, class _CP, class _Compare,
 498           bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value>
 499 class __map_value_compare
 500     : private _Compare
 501 {
 502 public:
 503     _LIBCPP_INLINE_VISIBILITY
 504     __map_value_compare()
 505         _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
 506         : _Compare() {}
 507     _LIBCPP_INLINE_VISIBILITY
 508     __map_value_compare(_Compare c)
 509         _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
 510         : _Compare(c) {}
 511     _LIBCPP_INLINE_VISIBILITY
 512     const _Compare& key_comp() const _NOEXCEPT {return *this;}
 513     _LIBCPP_INLINE_VISIBILITY
 514     bool operator()(const _CP& __x, const _CP& __y) const
 515         {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y.__get_value().first);}
 516     _LIBCPP_INLINE_VISIBILITY
 517     bool operator()(const _CP& __x, const _Key& __y) const
 518         {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y);}
 519     _LIBCPP_INLINE_VISIBILITY
 520     bool operator()(const _Key& __x, const _CP& __y) const
 521         {return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);}
 522     void swap(__map_value_compare&__y)
 523         _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
 524     {
 525       using _VSTD::swap;
 526       swap(static_cast<_Compare&>(*this), static_cast<_Compare&>(__y));
 527     }
 528
 529 #if _LIBCPP_STD_VER > 11
 530     template <typename _K2>
 531     _LIBCPP_INLINE_VISIBILITY
 532     typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
 533     operator () ( const _K2& __x, const _CP& __y ) const
 534         {return static_cast<const _Compare&>(*this) (__x, __y.__get_value().first);}
 535
 536     template <typename _K2>
 537     _LIBCPP_INLINE_VISIBILITY
 538     typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
 539     operator () (const _CP& __x, const _K2& __y) const
 540         {return static_cast<const _Compare&>(*this) (__x.__get_value().first, __y);}
 541 #endif
 542 };
 543
 544 template <class _Key, class _CP, class _Compare>
 545 class __map_value_compare<_Key, _CP, _Compare, false>
 546 {
 547     _Compare comp;
 548
 549 public:
 550     _LIBCPP_INLINE_VISIBILITY
 551     __map_value_compare()
 552         _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
 553         : comp() {}
 554     _LIBCPP_INLINE_VISIBILITY
 555     __map_value_compare(_Compare c)
 556         _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
 557         : comp(c) {}
 558     _LIBCPP_INLINE_VISIBILITY
 559     const _Compare& key_comp() const _NOEXCEPT {return comp;}
 560
 561     _LIBCPP_INLINE_VISIBILITY
 562     bool operator()(const _CP& __x, const _CP& __y) const
 563         {return comp(__x.__get_value().first, __y.__get_value().first);}
 564     _LIBCPP_INLINE_VISIBILITY
 565     bool operator()(const _CP& __x, const _Key& __y) const
 566         {return comp(__x.__get_value().first, __y);}
 567     _LIBCPP_INLINE_VISIBILITY
 568     bool operator()(const _Key& __x, const _CP& __y) const
 569         {return comp(__x, __y.__get_value().first);}
 570     void swap(__map_value_compare&__y)
 571         _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
 572     {
 573         using _VSTD::swap;
 574         swap(comp, __y.comp);
 575     }
 576
 577 #if _LIBCPP_STD_VER > 11
 578     template <typename _K2>
 579     _LIBCPP_INLINE_VISIBILITY
 580     typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
 581     operator () ( const _K2& __x, const _CP& __y ) const
 582         {return comp (__x, __y.__get_value().first);}
 583
 584     template <typename _K2>
 585     _LIBCPP_INLINE_VISIBILITY
 586     typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
 587     operator () (const _CP& __x, const _K2& __y) const
 588         {return comp (__x.__get_value().first, __y);}
 589 #endif
 590 };
 591
 592 template <class _Key, class _CP, class _Compare, bool __b>
 593 inline _LIBCPP_INLINE_VISIBILITY
 594 void
 595 swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x,
 596      __map_value_compare<_Key, _CP, _Compare, __b>& __y)
 597     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
 598 {
 599     __x.swap(__y);
 600 }
 601
 602 template <class _Allocator>
 603 class __map_node_destructor
 604 {
 605     typedef _Allocator                          allocator_type;
 606     typedef allocator_traits<allocator_type>    __alloc_traits;
 607
 608 public:
 609     typedef typename __alloc_traits::pointer    pointer;
 610
 611 private:
 612     allocator_type& __na_;
 613
 614     __map_node_destructor& operator=(const __map_node_destructor&);
 615
 616 public:
 617     bool __first_constructed;
 618     bool __second_constructed;
 619
 620     _LIBCPP_INLINE_VISIBILITY
 621     explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT
 622         : __na_(__na),
 623           __first_constructed(false),
 624           __second_constructed(false)
 625         {}
 626
 627 #ifndef _LIBCPP_CXX03_LANG
 628     _LIBCPP_INLINE_VISIBILITY
 629     __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT
 630         : __na_(__x.__na_),
 631           __first_constructed(__x.__value_constructed),
 632           __second_constructed(__x.__value_constructed)
 633         {
 634             __x.__value_constructed = false;
 635         }
 636 #endif  // _LIBCPP_CXX03_LANG
 637
 638     _LIBCPP_INLINE_VISIBILITY
 639     void operator()(pointer __p) _NOEXCEPT
 640     {
 641         if (__second_constructed)
 642             __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().second));
 643         if (__first_constructed)
 644             __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().first));
 645         if (__p)
 646             __alloc_traits::deallocate(__na_, __p, 1);
 647     }
 648 };
 649
 650 template <class _Key, class _Tp, class _Compare, class _Allocator>
 651     class map;
 652 template <class _Key, class _Tp, class _Compare, class _Allocator>
 653     class multimap;
 654 template <class _TreeIterator> class __map_const_iterator;
 655
 656 #ifndef _LIBCPP_CXX03_LANG
 657
 658 template <class _Key, class _Tp>
 659 struct __value_type
 660 {
 661     typedef _Key                                     key_type;
 662     typedef _Tp                                      mapped_type;
 663     typedef pair<const key_type, mapped_type>        value_type;
 664     typedef pair<key_type&, mapped_type&>            __nc_ref_pair_type;
 665     typedef pair<key_type&&, mapped_type&&>          __nc_rref_pair_type;
 666
 667 private:
 668     value_type __cc;
 669
 670 public:
 671     _LIBCPP_INLINE_VISIBILITY
 672     value_type& __get_value()
 673     {
 674 #if _LIBCPP_STD_VER > 14
 675         return *_VSTD::launder(_VSTD::addressof(__cc));
 676 #else
 677         return __cc;
 678 #endif
 679     }
 680
 681     _LIBCPP_INLINE_VISIBILITY
 682     const value_type& __get_value() const
 683     {
 684 #if _LIBCPP_STD_VER > 14
 685         return *_VSTD::launder(_VSTD::addressof(__cc));
 686 #else
 687         return __cc;
 688 #endif
 689     }
 690
 691     _LIBCPP_INLINE_VISIBILITY
 692     __nc_ref_pair_type __ref()
 693     {
 694         value_type& __v = __get_value();
 695         return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second);
 696     }
 697
 698     _LIBCPP_INLINE_VISIBILITY
 699     __nc_rref_pair_type __move()
 700     {
 701         value_type& __v = __get_value();
 702         return __nc_rref_pair_type(
 703             _VSTD::move(const_cast<key_type&>(__v.first)),
 704             _VSTD::move(__v.second));
 705     }
 706
 707     _LIBCPP_INLINE_VISIBILITY
 708     __value_type& operator=(const __value_type& __v)
 709     {
 710         __ref() = __v.__get_value();
 711         return *this;
 712     }
 713
 714     _LIBCPP_INLINE_VISIBILITY
 715     __value_type& operator=(__value_type&& __v)
 716     {
 717         __ref() = __v.__move();
 718         return *this;
 719     }
 720
 721     template <class _ValueTp,
 722               class = typename enable_if<
 723                     __is_same_uncvref<_ValueTp, value_type>::value
 724                  >::type
 725              >
 726     _LIBCPP_INLINE_VISIBILITY
 727     __value_type& operator=(_ValueTp&& __v)
 728     {
 729         __ref() = _VSTD::forward<_ValueTp>(__v);
 730         return *this;
 731     }
 732
 733 private:
 734     __value_type() _LIBCPP_EQUAL_DELETE;
 735     ~__value_type() _LIBCPP_EQUAL_DELETE;
 736     __value_type(const __value_type& __v) _LIBCPP_EQUAL_DELETE;
 737     __value_type(__value_type&& __v) _LIBCPP_EQUAL_DELETE;
 738 };
 739
 740 #else
 741
 742 template <class _Key, class _Tp>
 743 struct __value_type
 744 {
 745     typedef _Key                                     key_type;
 746     typedef _Tp                                      mapped_type;
 747     typedef pair<const key_type, mapped_type>        value_type;
 748
 749 private:
 750     value_type __cc;
 751
 752 public:
 753     _LIBCPP_INLINE_VISIBILITY
 754     value_type& __get_value() { return __cc; }
 755     _LIBCPP_INLINE_VISIBILITY
 756     const value_type& __get_value() const { return __cc; }
 757
 758 private:
 759    __value_type();
 760    __value_type(__value_type const&);
 761    __value_type& operator=(__value_type const&);
 762    ~__value_type();
 763 };
 764
 765 #endif // _LIBCPP_CXX03_LANG
 766
 767 template <class _Tp>
 768 struct __extract_key_value_types;
 769
 770 template <class _Key, class _Tp>
 771 struct __extract_key_value_types<__value_type<_Key, _Tp> >
 772 {
 773   typedef _Key const __key_type;
 774   typedef _Tp        __mapped_type;
 775 };
 776
 777 template <class _TreeIterator>
 778 class _LIBCPP_TEMPLATE_VIS __map_iterator
 779 {
 780     typedef typename _TreeIterator::_NodeTypes                   _NodeTypes;
 781     typedef typename _TreeIterator::__pointer_traits             __pointer_traits;
 782
 783     _TreeIterator __i_;
 784
 785 public:
 786     typedef bidirectional_iterator_tag                           iterator_category;
 787     typedef typename _NodeTypes::__map_value_type                value_type;
 788     typedef typename _TreeIterator::difference_type              difference_type;
 789     typedef value_type&                                          reference;
 790     typedef typename _NodeTypes::__map_value_type_pointer        pointer;
 791
 792     _LIBCPP_INLINE_VISIBILITY
 793     __map_iterator() _NOEXCEPT {}
 794
 795     _LIBCPP_INLINE_VISIBILITY
 796     __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
 797
 798     _LIBCPP_INLINE_VISIBILITY
 799     reference operator*() const {return __i_->__get_value();}
 800     _LIBCPP_INLINE_VISIBILITY
 801     pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
 802
 803     _LIBCPP_INLINE_VISIBILITY
 804     __map_iterator& operator++() {++__i_; return *this;}
 805     _LIBCPP_INLINE_VISIBILITY
 806     __map_iterator operator++(int)
 807     {
 808         __map_iterator __t(*this);
 809         ++(*this);
 810         return __t;
 811     }
 812
 813     _LIBCPP_INLINE_VISIBILITY
 814     __map_iterator& operator--() {--__i_; return *this;}
 815     _LIBCPP_INLINE_VISIBILITY
 816     __map_iterator operator--(int)
 817     {
 818         __map_iterator __t(*this);
 819         --(*this);
 820         return __t;
 821     }
 822
 823     friend _LIBCPP_INLINE_VISIBILITY
 824     bool operator==(const __map_iterator& __x, const __map_iterator& __y)
 825         {return __x.__i_ == __y.__i_;}
 826     friend
 827     _LIBCPP_INLINE_VISIBILITY
 828     bool operator!=(const __map_iterator& __x, const __map_iterator& __y)
 829         {return __x.__i_ != __y.__i_;}
 830
 831     template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
 832     template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
 833     template <class> friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator;
 834 };
 835
 836 template <class _TreeIterator>
 837 class _LIBCPP_TEMPLATE_VIS __map_const_iterator
 838 {
 839     typedef typename _TreeIterator::_NodeTypes                   _NodeTypes;
 840     typedef typename _TreeIterator::__pointer_traits             __pointer_traits;
 841
 842     _TreeIterator __i_;
 843
 844 public:
 845     typedef bidirectional_iterator_tag                           iterator_category;
 846     typedef typename _NodeTypes::__map_value_type                value_type;
 847     typedef typename _TreeIterator::difference_type              difference_type;
 848     typedef const value_type&                                    reference;
 849     typedef typename _NodeTypes::__const_map_value_type_pointer  pointer;
 850
 851     _LIBCPP_INLINE_VISIBILITY
 852     __map_const_iterator() _NOEXCEPT {}
 853
 854     _LIBCPP_INLINE_VISIBILITY
 855     __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
 856     _LIBCPP_INLINE_VISIBILITY
 857     __map_const_iterator(__map_iterator<
 858         typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT
 859         : __i_(__i.__i_) {}
 860
 861     _LIBCPP_INLINE_VISIBILITY
 862     reference operator*() const {return __i_->__get_value();}
 863     _LIBCPP_INLINE_VISIBILITY
 864     pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
 865
 866     _LIBCPP_INLINE_VISIBILITY
 867     __map_const_iterator& operator++() {++__i_; return *this;}
 868     _LIBCPP_INLINE_VISIBILITY
 869     __map_const_iterator operator++(int)
 870     {
 871         __map_const_iterator __t(*this);
 872         ++(*this);
 873         return __t;
 874     }
 875
 876     _LIBCPP_INLINE_VISIBILITY
 877     __map_const_iterator& operator--() {--__i_; return *this;}
 878     _LIBCPP_INLINE_VISIBILITY
 879     __map_const_iterator operator--(int)
 880     {
 881         __map_const_iterator __t(*this);
 882         --(*this);
 883         return __t;
 884     }
 885
 886     friend _LIBCPP_INLINE_VISIBILITY
 887     bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y)
 888         {return __x.__i_ == __y.__i_;}
 889     friend _LIBCPP_INLINE_VISIBILITY
 890     bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y)
 891         {return __x.__i_ != __y.__i_;}
 892
 893     template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
 894     template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
 895     template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator;
 896 };
 897
 898 template <class _Key, class _Tp, class _Compare = less<_Key>,
 899           class _Allocator = allocator<pair<const _Key, _Tp> > >
 900 class _LIBCPP_TEMPLATE_VIS map
 901 {
 902 public:
 903     // types:
 904     typedef _Key                                     key_type;
 905     typedef _Tp                                      mapped_type;
 906     typedef pair<const key_type, mapped_type>        value_type;
 907     typedef typename __identity<_Compare>::type      key_compare;
 908     typedef typename __identity<_Allocator>::type    allocator_type;
 909     typedef value_type&                              reference;
 910     typedef const value_type&                        const_reference;
 911
 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     ~map() {
1091         static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
1092     }
1093
1094     _LIBCPP_INLINE_VISIBILITY
1095           iterator begin() _NOEXCEPT {return __tree_.begin();}
1096     _LIBCPP_INLINE_VISIBILITY
1097     const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
1098     _LIBCPP_INLINE_VISIBILITY
1099           iterator end() _NOEXCEPT {return __tree_.end();}
1100     _LIBCPP_INLINE_VISIBILITY
1101     const_iterator end() const _NOEXCEPT {return __tree_.end();}
1102
1103     _LIBCPP_INLINE_VISIBILITY
1104           reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
1105     _LIBCPP_INLINE_VISIBILITY
1106     const_reverse_iterator rbegin() const _NOEXCEPT
1107         {return const_reverse_iterator(end());}
1108     _LIBCPP_INLINE_VISIBILITY
1109           reverse_iterator rend() _NOEXCEPT
1110             {return       reverse_iterator(begin());}
1111     _LIBCPP_INLINE_VISIBILITY
1112     const_reverse_iterator rend() const _NOEXCEPT
1113         {return const_reverse_iterator(begin());}
1114
1115     _LIBCPP_INLINE_VISIBILITY
1116     const_iterator cbegin() const _NOEXCEPT {return begin();}
1117     _LIBCPP_INLINE_VISIBILITY
1118     const_iterator cend() const _NOEXCEPT {return end();}
1119     _LIBCPP_INLINE_VISIBILITY
1120     const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1121     _LIBCPP_INLINE_VISIBILITY
1122     const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1123
1124     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1125     bool      empty() const _NOEXCEPT {return __tree_.size() == 0;}
1126     _LIBCPP_INLINE_VISIBILITY
1127     size_type size() const _NOEXCEPT {return __tree_.size();}
1128     _LIBCPP_INLINE_VISIBILITY
1129     size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1130
1131     mapped_type& operator[](const key_type& __k);
1132 #ifndef _LIBCPP_CXX03_LANG
1133     mapped_type& operator[](key_type&& __k);
1134 #endif
1135
1136           mapped_type& at(const key_type& __k);
1137     const mapped_type& at(const key_type& __k) const;
1138
1139     _LIBCPP_INLINE_VISIBILITY
1140     allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
1141     _LIBCPP_INLINE_VISIBILITY
1142     key_compare    key_comp()      const {return __tree_.value_comp().key_comp();}
1143     _LIBCPP_INLINE_VISIBILITY
1144     value_compare  value_comp()    const {return value_compare(__tree_.value_comp().key_comp());}
1145
1146 #ifndef _LIBCPP_CXX03_LANG
1147     template <class ..._Args>
1148     _LIBCPP_INLINE_VISIBILITY
1149     pair<iterator, bool> emplace(_Args&& ...__args) {
1150         return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);
1151     }
1152
1153     template <class ..._Args>
1154     _LIBCPP_INLINE_VISIBILITY
1155     iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1156         return __tree_.__emplace_hint_unique(__p.__i_, _VSTD::forward<_Args>(__args)...);
1157     }
1158
1159     template <class _Pp,
1160               class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1161         _LIBCPP_INLINE_VISIBILITY
1162         pair<iterator, bool> insert(_Pp&& __p)
1163             {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));}
1164
1165     template <class _Pp,
1166               class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1167         _LIBCPP_INLINE_VISIBILITY
1168         iterator insert(const_iterator __pos, _Pp&& __p)
1169             {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1170
1171 #endif  // _LIBCPP_CXX03_LANG
1172
1173     _LIBCPP_INLINE_VISIBILITY
1174     pair<iterator, bool>
1175         insert(const value_type& __v) {return __tree_.__insert_unique(__v);}
1176
1177     _LIBCPP_INLINE_VISIBILITY
1178     iterator
1179         insert(const_iterator __p, const value_type& __v)
1180             {return __tree_.__insert_unique(__p.__i_, __v);}
1181
1182 #ifndef _LIBCPP_CXX03_LANG
1183     _LIBCPP_INLINE_VISIBILITY
1184     pair<iterator, bool>
1185     insert(value_type&& __v) {return __tree_.__insert_unique(_VSTD::move(__v));}
1186
1187     _LIBCPP_INLINE_VISIBILITY
1188     iterator insert(const_iterator __p,  value_type&& __v)
1189     {return __tree_.__insert_unique(__p.__i_, _VSTD::move(__v));}
1190
1191     _LIBCPP_INLINE_VISIBILITY
1192     void insert(initializer_list<value_type> __il)
1193         {insert(__il.begin(), __il.end());}
1194 #endif
1195
1196     template <class _InputIterator>
1197         _LIBCPP_INLINE_VISIBILITY
1198         void insert(_InputIterator __f, _InputIterator __l)
1199         {
1200             for (const_iterator __e = cend(); __f != __l; ++__f)
1201                 insert(__e.__i_, *__f);
1202         }
1203
1204 #if _LIBCPP_STD_VER > 14
1205
1206     template <class... _Args>
1207         _LIBCPP_INLINE_VISIBILITY
1208         pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
1209     {
1210         return __tree_.__emplace_unique_key_args(__k,
1211             _VSTD::piecewise_construct,
1212             _VSTD::forward_as_tuple(__k),
1213             _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1214     }
1215
1216     template <class... _Args>
1217         _LIBCPP_INLINE_VISIBILITY
1218         pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
1219     {
1220         return __tree_.__emplace_unique_key_args(__k,
1221             _VSTD::piecewise_construct,
1222             _VSTD::forward_as_tuple(_VSTD::move(__k)),
1223             _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1224     }
1225
1226     template <class... _Args>
1227         _LIBCPP_INLINE_VISIBILITY
1228         iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
1229     {
1230         return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
1231             _VSTD::piecewise_construct,
1232             _VSTD::forward_as_tuple(__k),
1233             _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1234     }
1235
1236     template <class... _Args>
1237         _LIBCPP_INLINE_VISIBILITY
1238         iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
1239     {
1240         return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
1241             _VSTD::piecewise_construct,
1242             _VSTD::forward_as_tuple(_VSTD::move(__k)),
1243             _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1244     }
1245
1246     template <class _Vp>
1247         _LIBCPP_INLINE_VISIBILITY
1248         pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)
1249     {
1250         iterator __p = lower_bound(__k);
1251         if ( __p != end() && !key_comp()(__k, __p->first))
1252         {
1253             __p->second = _VSTD::forward<_Vp>(__v);
1254             return _VSTD::make_pair(__p, false);
1255         }
1256         return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true);
1257     }
1258
1259     template <class _Vp>
1260         _LIBCPP_INLINE_VISIBILITY
1261         pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)
1262     {
1263         iterator __p = lower_bound(__k);
1264         if ( __p != end() && !key_comp()(__k, __p->first))
1265         {
1266             __p->second = _VSTD::forward<_Vp>(__v);
1267             return _VSTD::make_pair(__p, false);
1268         }
1269         return _VSTD::make_pair(emplace_hint(__p, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)), true);
1270     }
1271
1272     template <class _Vp>
1273         _LIBCPP_INLINE_VISIBILITY
1274         iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v)
1275      {
1276         iterator __p = lower_bound(__k);
1277         if ( __p != end() && !key_comp()(__k, __p->first))
1278         {
1279             __p->second = _VSTD::forward<_Vp>(__v);
1280             return __p;
1281         }
1282         return emplace_hint(__h, __k, _VSTD::forward<_Vp>(__v));
1283      }
1284
1285     template <class _Vp>
1286         _LIBCPP_INLINE_VISIBILITY
1287         iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v)
1288      {
1289         iterator __p = lower_bound(__k);
1290         if ( __p != end() && !key_comp()(__k, __p->first))
1291         {
1292             __p->second = _VSTD::forward<_Vp>(__v);
1293             return __p;
1294         }
1295         return emplace_hint(__h, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
1296      }
1297
1298 #endif // _LIBCPP_STD_VER > 14
1299
1300     _LIBCPP_INLINE_VISIBILITY
1301     iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1302     _LIBCPP_INLINE_VISIBILITY
1303     iterator erase(iterator __p)       {return __tree_.erase(__p.__i_);}
1304     _LIBCPP_INLINE_VISIBILITY
1305     size_type erase(const key_type& __k)
1306         {return __tree_.__erase_unique(__k);}
1307     _LIBCPP_INLINE_VISIBILITY
1308     iterator  erase(const_iterator __f, const_iterator __l)
1309         {return __tree_.erase(__f.__i_, __l.__i_);}
1310     _LIBCPP_INLINE_VISIBILITY
1311     void clear() _NOEXCEPT {__tree_.clear();}
1312
1313 #if _LIBCPP_STD_VER > 14
1314     _LIBCPP_INLINE_VISIBILITY
1315     insert_return_type insert(node_type&& __nh)
1316     {
1317         _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1318             "node_type with incompatible allocator passed to map::insert()");
1319         return __tree_.template __node_handle_insert_unique<
1320             node_type, insert_return_type>(_VSTD::move(__nh));
1321     }
1322     _LIBCPP_INLINE_VISIBILITY
1323     iterator insert(const_iterator __hint, node_type&& __nh)
1324     {
1325         _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1326             "node_type with incompatible allocator passed to map::insert()");
1327         return __tree_.template __node_handle_insert_unique<node_type>(
1328             __hint.__i_, _VSTD::move(__nh));
1329     }
1330     _LIBCPP_INLINE_VISIBILITY
1331     node_type extract(key_type const& __key)
1332     {
1333         return __tree_.template __node_handle_extract<node_type>(__key);
1334     }
1335     _LIBCPP_INLINE_VISIBILITY
1336     node_type extract(const_iterator __it)
1337     {
1338         return __tree_.template __node_handle_extract<node_type>(__it.__i_);
1339     }
1340     template <class _Compare2>
1341     _LIBCPP_INLINE_VISIBILITY
1342     void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source)
1343     {
1344         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1345                        "merging container with incompatible allocator");
1346         __tree_.__node_handle_merge_unique(__source.__tree_);
1347     }
1348     template <class _Compare2>
1349     _LIBCPP_INLINE_VISIBILITY
1350     void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source)
1351     {
1352         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1353                        "merging container with incompatible allocator");
1354         __tree_.__node_handle_merge_unique(__source.__tree_);
1355     }
1356     template <class _Compare2>
1357     _LIBCPP_INLINE_VISIBILITY
1358     void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source)
1359     {
1360         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1361                        "merging container with incompatible allocator");
1362         __tree_.__node_handle_merge_unique(__source.__tree_);
1363     }
1364     template <class _Compare2>
1365     _LIBCPP_INLINE_VISIBILITY
1366     void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source)
1367     {
1368         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1369                        "merging container with incompatible allocator");
1370         __tree_.__node_handle_merge_unique(__source.__tree_);
1371     }
1372 #endif
1373
1374     _LIBCPP_INLINE_VISIBILITY
1375     void swap(map& __m)
1376         _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1377         {__tree_.swap(__m.__tree_);}
1378
1379     _LIBCPP_INLINE_VISIBILITY
1380     iterator find(const key_type& __k)             {return __tree_.find(__k);}
1381     _LIBCPP_INLINE_VISIBILITY
1382     const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1383 #if _LIBCPP_STD_VER > 11
1384     template <typename _K2>
1385     _LIBCPP_INLINE_VISIBILITY
1386     typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1387     find(const _K2& __k)                           {return __tree_.find(__k);}
1388     template <typename _K2>
1389     _LIBCPP_INLINE_VISIBILITY
1390     typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1391     find(const _K2& __k) const                     {return __tree_.find(__k);}
1392 #endif
1393
1394     _LIBCPP_INLINE_VISIBILITY
1395     size_type      count(const key_type& __k) const
1396         {return __tree_.__count_unique(__k);}
1397 #if _LIBCPP_STD_VER > 11
1398     template <typename _K2>
1399     _LIBCPP_INLINE_VISIBILITY
1400     typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1401     count(const _K2& __k) const {return __tree_.__count_multi(__k);}
1402 #endif
1403
1404 #if _LIBCPP_STD_VER > 17
1405     _LIBCPP_INLINE_VISIBILITY
1406     bool contains(const key_type& __k) const {return find(__k) != end();}
1407 #endif // _LIBCPP_STD_VER > 17
1408
1409     _LIBCPP_INLINE_VISIBILITY
1410     iterator lower_bound(const key_type& __k)
1411         {return __tree_.lower_bound(__k);}
1412     _LIBCPP_INLINE_VISIBILITY
1413     const_iterator lower_bound(const key_type& __k) const
1414         {return __tree_.lower_bound(__k);}
1415 #if _LIBCPP_STD_VER > 11
1416     template <typename _K2>
1417     _LIBCPP_INLINE_VISIBILITY
1418     typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1419     lower_bound(const _K2& __k)       {return __tree_.lower_bound(__k);}
1420
1421     template <typename _K2>
1422     _LIBCPP_INLINE_VISIBILITY
1423     typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1424     lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1425 #endif
1426
1427     _LIBCPP_INLINE_VISIBILITY
1428     iterator upper_bound(const key_type& __k)
1429         {return __tree_.upper_bound(__k);}
1430     _LIBCPP_INLINE_VISIBILITY
1431     const_iterator upper_bound(const key_type& __k) const
1432         {return __tree_.upper_bound(__k);}
1433 #if _LIBCPP_STD_VER > 11
1434     template <typename _K2>
1435     _LIBCPP_INLINE_VISIBILITY
1436     typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1437     upper_bound(const _K2& __k)       {return __tree_.upper_bound(__k);}
1438     template <typename _K2>
1439     _LIBCPP_INLINE_VISIBILITY
1440     typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1441     upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1442 #endif
1443
1444     _LIBCPP_INLINE_VISIBILITY
1445     pair<iterator,iterator> equal_range(const key_type& __k)
1446         {return __tree_.__equal_range_unique(__k);}
1447     _LIBCPP_INLINE_VISIBILITY
1448     pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1449         {return __tree_.__equal_range_unique(__k);}
1450 #if _LIBCPP_STD_VER > 11
1451     template <typename _K2>
1452     _LIBCPP_INLINE_VISIBILITY
1453     typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1454     equal_range(const _K2& __k)       {return __tree_.__equal_range_multi(__k);}
1455     template <typename _K2>
1456     _LIBCPP_INLINE_VISIBILITY
1457     typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1458     equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1459 #endif
1460
1461 private:
1462     typedef typename __base::__node                    __node;
1463     typedef typename __base::__node_allocator          __node_allocator;
1464     typedef typename __base::__node_pointer            __node_pointer;
1465     typedef typename __base::__node_base_pointer       __node_base_pointer;
1466     typedef typename __base::__parent_pointer          __parent_pointer;
1467
1468     typedef __map_node_destructor<__node_allocator> _Dp;
1469     typedef unique_ptr<__node, _Dp> __node_holder;
1470
1471 #ifdef _LIBCPP_CXX03_LANG
1472     __node_holder __construct_node_with_key(const key_type& __k);
1473 #endif
1474 };
1475
1476 #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
1477 template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>,
1478          class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
1479          class = _EnableIf<!__is_allocator<_Compare>::value, void>,
1480          class = _EnableIf<__is_allocator<_Allocator>::value, void>>
1481 map(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1482   -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
1483
1484 template<class _Key, class _Tp, class _Compare = less<remove_const_t<_Key>>,
1485          class _Allocator = allocator<pair<const _Key, _Tp>>,
1486          class = _EnableIf<!__is_allocator<_Compare>::value, void>,
1487          class = _EnableIf<__is_allocator<_Allocator>::value, void>>
1488 map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator())
1489   -> map<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
1490
1491 template<class _InputIterator, class _Allocator,
1492          class = _EnableIf<__is_allocator<_Allocator>::value, void>>
1493 map(_InputIterator, _InputIterator, _Allocator)
1494   -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
1495          less<__iter_key_type<_InputIterator>>, _Allocator>;
1496
1497 template<class _Key, class _Tp, class _Allocator,
1498          class = _EnableIf<__is_allocator<_Allocator>::value, void>>
1499 map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1500   -> map<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;
1501 #endif
1502
1503 #ifndef _LIBCPP_CXX03_LANG
1504 template <class _Key, class _Tp, class _Compare, class _Allocator>
1505 map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
1506     : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
1507 {
1508     if (__a != __m.get_allocator())
1509     {
1510         const_iterator __e = cend();
1511         while (!__m.empty())
1512             __tree_.__insert_unique(__e.__i_,
1513                     __m.__tree_.remove(__m.begin().__i_)->__value_.__move());
1514     }
1515 }
1516
1517 template <class _Key, class _Tp, class _Compare, class _Allocator>
1518 _Tp&
1519 map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1520 {
1521     return __tree_.__emplace_unique_key_args(__k,
1522         _VSTD::piecewise_construct,
1523         _VSTD::forward_as_tuple(__k),
1524         _VSTD::forward_as_tuple()).first->__get_value().second;
1525 }
1526
1527 template <class _Key, class _Tp, class _Compare, class _Allocator>
1528 _Tp&
1529 map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
1530 {
1531     return __tree_.__emplace_unique_key_args(__k,
1532         _VSTD::piecewise_construct,
1533         _VSTD::forward_as_tuple(_VSTD::move(__k)),
1534         _VSTD::forward_as_tuple()).first->__get_value().second;
1535 }
1536
1537 #else // _LIBCPP_CXX03_LANG
1538
1539 template <class _Key, class _Tp, class _Compare, class _Allocator>
1540 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1541 map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
1542 {
1543     __node_allocator& __na = __tree_.__node_alloc();
1544     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1545     __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().first), __k);
1546     __h.get_deleter().__first_constructed = true;
1547     __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().second));
1548     __h.get_deleter().__second_constructed = true;
1549     return _LIBCPP_EXPLICIT_MOVE(__h);  // explicitly moved for C++03
1550 }
1551
1552 template <class _Key, class _Tp, class _Compare, class _Allocator>
1553 _Tp&
1554 map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1555 {
1556     __parent_pointer __parent;
1557     __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1558     __node_pointer __r = static_cast<__node_pointer>(__child);
1559     if (__child == nullptr)
1560     {
1561         __node_holder __h = __construct_node_with_key(__k);
1562         __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1563         __r = __h.release();
1564     }
1565     return __r->__value_.__get_value().second;
1566 }
1567
1568 #endif  // _LIBCPP_CXX03_LANG
1569
1570 template <class _Key, class _Tp, class _Compare, class _Allocator>
1571 _Tp&
1572 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
1573 {
1574     __parent_pointer __parent;
1575     __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1576     if (__child == nullptr)
1577         __throw_out_of_range("map::at:  key not found");
1578     return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
1579 }
1580
1581 template <class _Key, class _Tp, class _Compare, class _Allocator>
1582 const _Tp&
1583 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
1584 {
1585     __parent_pointer __parent;
1586     __node_base_pointer __child = __tree_.__find_equal(__parent, __k);
1587     if (__child == nullptr)
1588         __throw_out_of_range("map::at:  key not found");
1589     return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
1590 }
1591
1592
1593 template <class _Key, class _Tp, class _Compare, class _Allocator>
1594 inline _LIBCPP_INLINE_VISIBILITY
1595 bool
1596 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1597            const map<_Key, _Tp, _Compare, _Allocator>& __y)
1598 {
1599     return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1600 }
1601
1602 template <class _Key, class _Tp, class _Compare, class _Allocator>
1603 inline _LIBCPP_INLINE_VISIBILITY
1604 bool
1605 operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1606            const map<_Key, _Tp, _Compare, _Allocator>& __y)
1607 {
1608     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1609 }
1610
1611 template <class _Key, class _Tp, class _Compare, class _Allocator>
1612 inline _LIBCPP_INLINE_VISIBILITY
1613 bool
1614 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1615            const map<_Key, _Tp, _Compare, _Allocator>& __y)
1616 {
1617     return !(__x == __y);
1618 }
1619
1620 template <class _Key, class _Tp, class _Compare, class _Allocator>
1621 inline _LIBCPP_INLINE_VISIBILITY
1622 bool
1623 operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1624            const map<_Key, _Tp, _Compare, _Allocator>& __y)
1625 {
1626     return __y < __x;
1627 }
1628
1629 template <class _Key, class _Tp, class _Compare, class _Allocator>
1630 inline _LIBCPP_INLINE_VISIBILITY
1631 bool
1632 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1633            const map<_Key, _Tp, _Compare, _Allocator>& __y)
1634 {
1635     return !(__x < __y);
1636 }
1637
1638 template <class _Key, class _Tp, class _Compare, class _Allocator>
1639 inline _LIBCPP_INLINE_VISIBILITY
1640 bool
1641 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1642            const map<_Key, _Tp, _Compare, _Allocator>& __y)
1643 {
1644     return !(__y < __x);
1645 }
1646
1647 template <class _Key, class _Tp, class _Compare, class _Allocator>
1648 inline _LIBCPP_INLINE_VISIBILITY
1649 void
1650 swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
1651      map<_Key, _Tp, _Compare, _Allocator>& __y)
1652     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1653 {
1654     __x.swap(__y);
1655 }
1656
1657 #if _LIBCPP_STD_VER > 17
1658 template <class _Key, class _Tp, class _Compare, class _Allocator,
1659           class _Predicate>
1660 inline _LIBCPP_INLINE_VISIBILITY
1661     typename map<_Key, _Tp, _Compare, _Allocator>::size_type
1662     erase_if(map<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) {
1663   return __libcpp_erase_if_container(__c, __pred);
1664 }
1665 #endif
1666
1667
1668 template <class _Key, class _Tp, class _Compare = less<_Key>,
1669           class _Allocator = allocator<pair<const _Key, _Tp> > >
1670 class _LIBCPP_TEMPLATE_VIS multimap
1671 {
1672 public:
1673     // types:
1674     typedef _Key                                     key_type;
1675     typedef _Tp                                      mapped_type;
1676     typedef pair<const key_type, mapped_type>        value_type;
1677     typedef typename __identity<_Compare>::type      key_compare;
1678     typedef typename __identity<_Allocator>::type    allocator_type;
1679     typedef value_type&                              reference;
1680     typedef const value_type&                        const_reference;
1681
1682     static_assert((is_same<typename allocator_type::value_type, value_type>::value),
1683                   "Allocator::value_type must be same type as value_type");
1684
1685     class _LIBCPP_TEMPLATE_VIS value_compare
1686         : public binary_function<value_type, value_type, bool>
1687     {
1688         friend class multimap;
1689     protected:
1690         key_compare comp;
1691
1692         _LIBCPP_INLINE_VISIBILITY
1693         value_compare(key_compare c) : comp(c) {}
1694     public:
1695         _LIBCPP_INLINE_VISIBILITY
1696         bool operator()(const value_type& __x, const value_type& __y) const
1697             {return comp(__x.first, __y.first);}
1698     };
1699
1700 private:
1701
1702     typedef _VSTD::__value_type<key_type, mapped_type>             __value_type;
1703     typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
1704     typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
1705                                                  __value_type>::type __allocator_type;
1706     typedef __tree<__value_type, __vc, __allocator_type>            __base;
1707     typedef typename __base::__node_traits                          __node_traits;
1708     typedef allocator_traits<allocator_type>                        __alloc_traits;
1709
1710     __base __tree_;
1711
1712 public:
1713     typedef typename __alloc_traits::pointer               pointer;
1714     typedef typename __alloc_traits::const_pointer         const_pointer;
1715     typedef typename __alloc_traits::size_type             size_type;
1716     typedef typename __alloc_traits::difference_type       difference_type;
1717     typedef __map_iterator<typename __base::iterator>      iterator;
1718     typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1719     typedef _VSTD::reverse_iterator<iterator>               reverse_iterator;
1720     typedef _VSTD::reverse_iterator<const_iterator>         const_reverse_iterator;
1721
1722 #if _LIBCPP_STD_VER > 14
1723     typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
1724 #endif
1725
1726     template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1727         friend class _LIBCPP_TEMPLATE_VIS map;
1728     template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1729         friend class _LIBCPP_TEMPLATE_VIS multimap;
1730
1731     _LIBCPP_INLINE_VISIBILITY
1732     multimap()
1733         _NOEXCEPT_(
1734             is_nothrow_default_constructible<allocator_type>::value &&
1735             is_nothrow_default_constructible<key_compare>::value &&
1736             is_nothrow_copy_constructible<key_compare>::value)
1737         : __tree_(__vc(key_compare())) {}
1738
1739     _LIBCPP_INLINE_VISIBILITY
1740     explicit multimap(const key_compare& __comp)
1741         _NOEXCEPT_(
1742             is_nothrow_default_constructible<allocator_type>::value &&
1743             is_nothrow_copy_constructible<key_compare>::value)
1744         : __tree_(__vc(__comp)) {}
1745
1746     _LIBCPP_INLINE_VISIBILITY
1747     explicit multimap(const key_compare& __comp, const allocator_type& __a)
1748         : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
1749
1750     template <class _InputIterator>
1751         _LIBCPP_INLINE_VISIBILITY
1752         multimap(_InputIterator __f, _InputIterator __l,
1753             const key_compare& __comp = key_compare())
1754         : __tree_(__vc(__comp))
1755         {
1756             insert(__f, __l);
1757         }
1758
1759     template <class _InputIterator>
1760         _LIBCPP_INLINE_VISIBILITY
1761         multimap(_InputIterator __f, _InputIterator __l,
1762             const key_compare& __comp, const allocator_type& __a)
1763         : __tree_(__vc(__comp), typename __base::allocator_type(__a))
1764         {
1765             insert(__f, __l);
1766         }
1767
1768 #if _LIBCPP_STD_VER > 11
1769     template <class _InputIterator>
1770     _LIBCPP_INLINE_VISIBILITY
1771     multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1772         : multimap(__f, __l, key_compare(), __a) {}
1773 #endif
1774
1775     _LIBCPP_INLINE_VISIBILITY
1776     multimap(const multimap& __m)
1777         : __tree_(__m.__tree_.value_comp(),
1778           __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
1779         {
1780             insert(__m.begin(), __m.end());
1781         }
1782
1783     _LIBCPP_INLINE_VISIBILITY
1784     multimap& operator=(const multimap& __m)
1785         {
1786 #ifndef _LIBCPP_CXX03_LANG
1787             __tree_ = __m.__tree_;
1788 #else
1789             if (this != &__m) {
1790                 __tree_.clear();
1791                 __tree_.value_comp() = __m.__tree_.value_comp();
1792                 __tree_.__copy_assign_alloc(__m.__tree_);
1793                 insert(__m.begin(), __m.end());
1794             }
1795 #endif
1796             return *this;
1797         }
1798
1799 #ifndef _LIBCPP_CXX03_LANG
1800
1801     _LIBCPP_INLINE_VISIBILITY
1802     multimap(multimap&& __m)
1803         _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1804         : __tree_(_VSTD::move(__m.__tree_))
1805         {
1806         }
1807
1808     multimap(multimap&& __m, const allocator_type& __a);
1809
1810     _LIBCPP_INLINE_VISIBILITY
1811     multimap& operator=(multimap&& __m)
1812         _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1813         {
1814             __tree_ = _VSTD::move(__m.__tree_);
1815             return *this;
1816         }
1817
1818     _LIBCPP_INLINE_VISIBILITY
1819     multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1820         : __tree_(__vc(__comp))
1821         {
1822             insert(__il.begin(), __il.end());
1823         }
1824
1825     _LIBCPP_INLINE_VISIBILITY
1826     multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1827         : __tree_(__vc(__comp), typename __base::allocator_type(__a))
1828         {
1829             insert(__il.begin(), __il.end());
1830         }
1831
1832 #if _LIBCPP_STD_VER > 11
1833     _LIBCPP_INLINE_VISIBILITY
1834     multimap(initializer_list<value_type> __il, const allocator_type& __a)
1835         : multimap(__il, key_compare(), __a) {}
1836 #endif
1837
1838     _LIBCPP_INLINE_VISIBILITY
1839     multimap& operator=(initializer_list<value_type> __il)
1840         {
1841             __tree_.__assign_multi(__il.begin(), __il.end());
1842             return *this;
1843         }
1844
1845 #endif  // _LIBCPP_CXX03_LANG
1846
1847     _LIBCPP_INLINE_VISIBILITY
1848     explicit multimap(const allocator_type& __a)
1849         : __tree_(typename __base::allocator_type(__a))
1850         {
1851         }
1852
1853     _LIBCPP_INLINE_VISIBILITY
1854     multimap(const multimap& __m, const allocator_type& __a)
1855         : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
1856         {
1857             insert(__m.begin(), __m.end());
1858         }
1859
1860     _LIBCPP_INLINE_VISIBILITY
1861     ~multimap() {
1862         static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
1863     }
1864
1865     _LIBCPP_INLINE_VISIBILITY
1866           iterator begin() _NOEXCEPT {return __tree_.begin();}
1867     _LIBCPP_INLINE_VISIBILITY
1868     const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
1869     _LIBCPP_INLINE_VISIBILITY
1870           iterator end() _NOEXCEPT {return __tree_.end();}
1871     _LIBCPP_INLINE_VISIBILITY
1872     const_iterator end() const _NOEXCEPT {return __tree_.end();}
1873
1874     _LIBCPP_INLINE_VISIBILITY
1875           reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
1876     _LIBCPP_INLINE_VISIBILITY
1877     const_reverse_iterator rbegin() const _NOEXCEPT
1878         {return const_reverse_iterator(end());}
1879     _LIBCPP_INLINE_VISIBILITY
1880           reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());}
1881     _LIBCPP_INLINE_VISIBILITY
1882     const_reverse_iterator rend() const _NOEXCEPT
1883         {return const_reverse_iterator(begin());}
1884
1885     _LIBCPP_INLINE_VISIBILITY
1886     const_iterator cbegin()  const _NOEXCEPT {return begin();}
1887     _LIBCPP_INLINE_VISIBILITY
1888     const_iterator cend() const _NOEXCEPT {return end();}
1889     _LIBCPP_INLINE_VISIBILITY
1890     const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1891     _LIBCPP_INLINE_VISIBILITY
1892     const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1893
1894     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1895     bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1896     _LIBCPP_INLINE_VISIBILITY
1897     size_type size() const _NOEXCEPT {return __tree_.size();}
1898     _LIBCPP_INLINE_VISIBILITY
1899     size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1900
1901     _LIBCPP_INLINE_VISIBILITY
1902     allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
1903     _LIBCPP_INLINE_VISIBILITY
1904     key_compare    key_comp() const {return __tree_.value_comp().key_comp();}
1905     _LIBCPP_INLINE_VISIBILITY
1906     value_compare  value_comp() const
1907         {return value_compare(__tree_.value_comp().key_comp());}
1908
1909 #ifndef _LIBCPP_CXX03_LANG
1910
1911     template <class ..._Args>
1912     _LIBCPP_INLINE_VISIBILITY
1913     iterator emplace(_Args&& ...__args) {
1914         return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);
1915     }
1916
1917     template <class ..._Args>
1918     _LIBCPP_INLINE_VISIBILITY
1919     iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1920         return __tree_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...);
1921     }
1922
1923     template <class _Pp,
1924               class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1925         _LIBCPP_INLINE_VISIBILITY
1926         iterator insert(_Pp&& __p)
1927             {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));}
1928
1929     template <class _Pp,
1930               class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1931         _LIBCPP_INLINE_VISIBILITY
1932         iterator insert(const_iterator __pos, _Pp&& __p)
1933             {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1934
1935     _LIBCPP_INLINE_VISIBILITY
1936     iterator insert(value_type&& __v)
1937         {return __tree_.__insert_multi(_VSTD::move(__v));}
1938
1939     _LIBCPP_INLINE_VISIBILITY
1940     iterator insert(const_iterator __p, value_type&& __v)
1941         {return __tree_.__insert_multi(__p.__i_, _VSTD::move(__v));}
1942
1943
1944     _LIBCPP_INLINE_VISIBILITY
1945     void insert(initializer_list<value_type> __il)
1946         {insert(__il.begin(), __il.end());}
1947
1948 #endif  // _LIBCPP_CXX03_LANG
1949
1950     _LIBCPP_INLINE_VISIBILITY
1951     iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
1952
1953     _LIBCPP_INLINE_VISIBILITY
1954     iterator insert(const_iterator __p, const value_type& __v)
1955             {return __tree_.__insert_multi(__p.__i_, __v);}
1956
1957     template <class _InputIterator>
1958         _LIBCPP_INLINE_VISIBILITY
1959         void insert(_InputIterator __f, _InputIterator __l)
1960         {
1961             for (const_iterator __e = cend(); __f != __l; ++__f)
1962                 __tree_.__insert_multi(__e.__i_, *__f);
1963         }
1964
1965     _LIBCPP_INLINE_VISIBILITY
1966     iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1967     _LIBCPP_INLINE_VISIBILITY
1968     iterator erase(iterator __p)       {return __tree_.erase(__p.__i_);}
1969     _LIBCPP_INLINE_VISIBILITY
1970     size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1971     _LIBCPP_INLINE_VISIBILITY
1972     iterator  erase(const_iterator __f, const_iterator __l)
1973         {return __tree_.erase(__f.__i_, __l.__i_);}
1974
1975 #if _LIBCPP_STD_VER > 14
1976     _LIBCPP_INLINE_VISIBILITY
1977     iterator insert(node_type&& __nh)
1978     {
1979         _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1980             "node_type with incompatible allocator passed to multimap::insert()");
1981         return __tree_.template __node_handle_insert_multi<node_type>(
1982             _VSTD::move(__nh));
1983     }
1984     _LIBCPP_INLINE_VISIBILITY
1985     iterator insert(const_iterator __hint, node_type&& __nh)
1986     {
1987         _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1988             "node_type with incompatible allocator passed to multimap::insert()");
1989         return __tree_.template __node_handle_insert_multi<node_type>(
1990             __hint.__i_, _VSTD::move(__nh));
1991     }
1992     _LIBCPP_INLINE_VISIBILITY
1993     node_type extract(key_type const& __key)
1994     {
1995         return __tree_.template __node_handle_extract<node_type>(__key);
1996     }
1997     _LIBCPP_INLINE_VISIBILITY
1998     node_type extract(const_iterator __it)
1999     {
2000         return __tree_.template __node_handle_extract<node_type>(
2001             __it.__i_);
2002     }
2003     template <class _Compare2>
2004     _LIBCPP_INLINE_VISIBILITY
2005     void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source)
2006     {
2007         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2008                        "merging container with incompatible allocator");
2009         return __tree_.__node_handle_merge_multi(__source.__tree_);
2010     }
2011     template <class _Compare2>
2012     _LIBCPP_INLINE_VISIBILITY
2013     void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source)
2014     {
2015         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2016                        "merging container with incompatible allocator");
2017         return __tree_.__node_handle_merge_multi(__source.__tree_);
2018     }
2019     template <class _Compare2>
2020     _LIBCPP_INLINE_VISIBILITY
2021     void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source)
2022     {
2023         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2024                        "merging container with incompatible allocator");
2025         return __tree_.__node_handle_merge_multi(__source.__tree_);
2026     }
2027     template <class _Compare2>
2028     _LIBCPP_INLINE_VISIBILITY
2029     void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source)
2030     {
2031         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2032                        "merging container with incompatible allocator");
2033         return __tree_.__node_handle_merge_multi(__source.__tree_);
2034     }
2035 #endif
2036
2037     _LIBCPP_INLINE_VISIBILITY
2038     void clear() _NOEXCEPT {__tree_.clear();}
2039
2040     _LIBCPP_INLINE_VISIBILITY
2041     void swap(multimap& __m)
2042         _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
2043         {__tree_.swap(__m.__tree_);}
2044
2045     _LIBCPP_INLINE_VISIBILITY
2046     iterator find(const key_type& __k)             {return __tree_.find(__k);}
2047     _LIBCPP_INLINE_VISIBILITY
2048     const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
2049 #if _LIBCPP_STD_VER > 11
2050     template <typename _K2>
2051     _LIBCPP_INLINE_VISIBILITY
2052     typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
2053     find(const _K2& __k)                           {return __tree_.find(__k);}
2054     template <typename _K2>
2055     _LIBCPP_INLINE_VISIBILITY
2056     typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
2057     find(const _K2& __k) const                     {return __tree_.find(__k);}
2058 #endif
2059
2060     _LIBCPP_INLINE_VISIBILITY
2061     size_type      count(const key_type& __k) const
2062         {return __tree_.__count_multi(__k);}
2063 #if _LIBCPP_STD_VER > 11
2064     template <typename _K2>
2065     _LIBCPP_INLINE_VISIBILITY
2066     typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
2067     count(const _K2& __k) const {return __tree_.__count_multi(__k);}
2068 #endif
2069
2070 #if _LIBCPP_STD_VER > 17
2071     _LIBCPP_INLINE_VISIBILITY
2072     bool contains(const key_type& __k) const {return find(__k) != end();}
2073 #endif // _LIBCPP_STD_VER > 17
2074
2075     _LIBCPP_INLINE_VISIBILITY
2076     iterator lower_bound(const key_type& __k)
2077         {return __tree_.lower_bound(__k);}
2078     _LIBCPP_INLINE_VISIBILITY
2079     const_iterator lower_bound(const key_type& __k) const
2080             {return __tree_.lower_bound(__k);}
2081 #if _LIBCPP_STD_VER > 11
2082     template <typename _K2>
2083     _LIBCPP_INLINE_VISIBILITY
2084     typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
2085     lower_bound(const _K2& __k)       {return __tree_.lower_bound(__k);}
2086
2087     template <typename _K2>
2088     _LIBCPP_INLINE_VISIBILITY
2089     typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
2090     lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
2091 #endif
2092
2093     _LIBCPP_INLINE_VISIBILITY
2094     iterator upper_bound(const key_type& __k)
2095             {return __tree_.upper_bound(__k);}
2096     _LIBCPP_INLINE_VISIBILITY
2097     const_iterator upper_bound(const key_type& __k) const
2098             {return __tree_.upper_bound(__k);}
2099 #if _LIBCPP_STD_VER > 11
2100     template <typename _K2>
2101     _LIBCPP_INLINE_VISIBILITY
2102     typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
2103     upper_bound(const _K2& __k)       {return __tree_.upper_bound(__k);}
2104     template <typename _K2>
2105     _LIBCPP_INLINE_VISIBILITY
2106     typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
2107     upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
2108 #endif
2109
2110     _LIBCPP_INLINE_VISIBILITY
2111     pair<iterator,iterator>             equal_range(const key_type& __k)
2112             {return __tree_.__equal_range_multi(__k);}
2113     _LIBCPP_INLINE_VISIBILITY
2114     pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
2115             {return __tree_.__equal_range_multi(__k);}
2116 #if _LIBCPP_STD_VER > 11
2117     template <typename _K2>
2118     _LIBCPP_INLINE_VISIBILITY
2119     typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
2120     equal_range(const _K2& __k)       {return __tree_.__equal_range_multi(__k);}
2121     template <typename _K2>
2122     _LIBCPP_INLINE_VISIBILITY
2123     typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
2124     equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
2125 #endif
2126
2127 private:
2128     typedef typename __base::__node                    __node;
2129     typedef typename __base::__node_allocator          __node_allocator;
2130     typedef typename __base::__node_pointer            __node_pointer;
2131
2132     typedef __map_node_destructor<__node_allocator> _Dp;
2133     typedef unique_ptr<__node, _Dp> __node_holder;
2134 };
2135
2136 #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
2137 template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>,
2138          class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
2139          class = _EnableIf<!__is_allocator<_Compare>::value, void>,
2140          class = _EnableIf<__is_allocator<_Allocator>::value, void>>
2141 multimap(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
2142   -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
2143
2144 template<class _Key, class _Tp, class _Compare = less<remove_const_t<_Key>>,
2145          class _Allocator = allocator<pair<const _Key, _Tp>>,
2146          class = _EnableIf<!__is_allocator<_Compare>::value, void>,
2147          class = _EnableIf<__is_allocator<_Allocator>::value, void>>
2148 multimap(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator())
2149   -> multimap<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
2150
2151 template<class _InputIterator, class _Allocator,
2152          class = _EnableIf<__is_allocator<_Allocator>::value, void>>
2153 multimap(_InputIterator, _InputIterator, _Allocator)
2154   -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
2155          less<__iter_key_type<_InputIterator>>, _Allocator>;
2156
2157 template<class _Key, class _Tp, class _Allocator,
2158          class = _EnableIf<__is_allocator<_Allocator>::value, void>>
2159 multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2160   -> multimap<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;
2161 #endif
2162
2163 #ifndef _LIBCPP_CXX03_LANG
2164 template <class _Key, class _Tp, class _Compare, class _Allocator>
2165 multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
2166     : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
2167 {
2168     if (__a != __m.get_allocator())
2169     {
2170         const_iterator __e = cend();
2171         while (!__m.empty())
2172             __tree_.__insert_multi(__e.__i_,
2173                     _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__move()));
2174     }
2175 }
2176 #endif
2177
2178 template <class _Key, class _Tp, class _Compare, class _Allocator>
2179 inline _LIBCPP_INLINE_VISIBILITY
2180 bool
2181 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2182            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2183 {
2184     return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
2185 }
2186
2187 template <class _Key, class _Tp, class _Compare, class _Allocator>
2188 inline _LIBCPP_INLINE_VISIBILITY
2189 bool
2190 operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2191            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2192 {
2193     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2194 }
2195
2196 template <class _Key, class _Tp, class _Compare, class _Allocator>
2197 inline _LIBCPP_INLINE_VISIBILITY
2198 bool
2199 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2200            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2201 {
2202     return !(__x == __y);
2203 }
2204
2205 template <class _Key, class _Tp, class _Compare, class _Allocator>
2206 inline _LIBCPP_INLINE_VISIBILITY
2207 bool
2208 operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2209            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2210 {
2211     return __y < __x;
2212 }
2213
2214 template <class _Key, class _Tp, class _Compare, class _Allocator>
2215 inline _LIBCPP_INLINE_VISIBILITY
2216 bool
2217 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2218            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2219 {
2220     return !(__x < __y);
2221 }
2222
2223 template <class _Key, class _Tp, class _Compare, class _Allocator>
2224 inline _LIBCPP_INLINE_VISIBILITY
2225 bool
2226 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2227            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2228 {
2229     return !(__y < __x);
2230 }
2231
2232 template <class _Key, class _Tp, class _Compare, class _Allocator>
2233 inline _LIBCPP_INLINE_VISIBILITY
2234 void
2235 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2236      multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2237     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2238 {
2239     __x.swap(__y);
2240 }
2241
2242 #if _LIBCPP_STD_VER > 17
2243 template <class _Key, class _Tp, class _Compare, class _Allocator,
2244           class _Predicate>
2245 inline _LIBCPP_INLINE_VISIBILITY
2246     typename multimap<_Key, _Tp, _Compare, _Allocator>::size_type
2247     erase_if(multimap<_Key, _Tp, _Compare, _Allocator>& __c,
2248              _Predicate __pred) {
2249   return __libcpp_erase_if_container(__c, __pred);
2250 }
2251 #endif
2252
2253 _LIBCPP_END_NAMESPACE_STD
2254
2255 #endif  // _LIBCPP_MAP