libcxx/include/map

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