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