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 #if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
 575 #  include <__cxx03/map>
 576 #else
 577 #  include <__algorithm/equal.h>
 578 #  include <__algorithm/lexicographical_compare.h>
 579 #  include <__algorithm/lexicographical_compare_three_way.h>
 580 #  include <__assert>
 581 #  include <__config>
 582 #  include <__functional/binary_function.h>
 583 #  include <__functional/is_transparent.h>
 584 #  include <__functional/operations.h>
 585 #  include <__iterator/erase_if_container.h>
 586 #  include <__iterator/iterator_traits.h>
 587 #  include <__iterator/ranges_iterator_traits.h>
 588 #  include <__iterator/reverse_iterator.h>
 589 #  include <__memory/addressof.h>
 590 #  include <__memory/allocator.h>
 591 #  include <__memory/allocator_traits.h>
 592 #  include <__memory/pointer_traits.h>
 593 #  include <__memory/unique_ptr.h>
 594 #  include <__memory_resource/polymorphic_allocator.h>
 595 #  include <__new/launder.h>
 596 #  include <__node_handle>
 597 #  include <__ranges/concepts.h>
 598 #  include <__ranges/container_compatible_range.h>
 599 #  include <__ranges/from_range.h>
 600 #  include <__tree>
 601 #  include <__type_traits/container_traits.h>
 602 #  include <__type_traits/is_allocator.h>
 603 #  include <__type_traits/remove_const.h>
 604 #  include <__type_traits/type_identity.h>
 605 #  include <__utility/forward.h>
 606 #  include <__utility/pair.h>
 607 #  include <__utility/piecewise_construct.h>
 608 #  include <__utility/swap.h>
 609 #  include <stdexcept>
 610 #  include <tuple>
 611 #  include <version>
 612
 613 // standard-mandated includes
 614
 615 // [iterator.range]
 616 #  include <__iterator/access.h>
 617 #  include <__iterator/data.h>
 618 #  include <__iterator/empty.h>
 619 #  include <__iterator/reverse_access.h>
 620 #  include <__iterator/size.h>
 621
 622 // [associative.map.syn]
 623 #  include <compare>
 624 #  include <initializer_list>
 625
 626 #  if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 627 #    pragma GCC system_header
 628 #  endif
 629
 630 _LIBCPP_PUSH_MACROS
 631 #  include <__undef_macros>
 632
 633 _LIBCPP_BEGIN_NAMESPACE_STD
 634
 635 template <class _Key,
 636           class _CP,
 637           class _Compare,
 638           bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value>
 639 class __map_value_compare : private _Compare {
 640 public:
 641   _LIBCPP_HIDE_FROM_ABI __map_value_compare() _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
 642       : _Compare() {}
 643   _LIBCPP_HIDE_FROM_ABI __map_value_compare(_Compare __c) _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
 644       : _Compare(__c) {}
 645   _LIBCPP_HIDE_FROM_ABI const _Compare& key_comp() const _NOEXCEPT { return *this; }
 646   _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _CP& __y) const {
 647     return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y.__get_value().first);
 648   }
 649   _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _Key& __y) const {
 650     return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y);
 651   }
 652   _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _CP& __y) const {
 653     return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);
 654   }
 655   _LIBCPP_HIDE_FROM_ABI void swap(__map_value_compare& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Compare>) {
 656     using std::swap;
 657     swap(static_cast<_Compare&>(*this), static_cast<_Compare&>(__y));
 658   }
 659
 660 #  if _LIBCPP_STD_VER >= 14
 661   template <typename _K2>
 662   _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _CP& __y) const {
 663     return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);
 664   }
 665
 666   template <typename _K2>
 667   _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _K2& __y) const {
 668     return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y);
 669   }
 670 #  endif
 671 };
 672
 673 template <class _Key, class _CP, class _Compare>
 674 class __map_value_compare<_Key, _CP, _Compare, false> {
 675   _Compare __comp_;
 676
 677 public:
 678   _LIBCPP_HIDE_FROM_ABI __map_value_compare() _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
 679       : __comp_() {}
 680   _LIBCPP_HIDE_FROM_ABI __map_value_compare(_Compare __c) _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
 681       : __comp_(__c) {}
 682   _LIBCPP_HIDE_FROM_ABI const _Compare& key_comp() const _NOEXCEPT { return __comp_; }
 683
 684   _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _CP& __y) const {
 685     return __comp_(__x.__get_value().first, __y.__get_value().first);
 686   }
 687   _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _Key& __y) const {
 688     return __comp_(__x.__get_value().first, __y);
 689   }
 690   _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _CP& __y) const {
 691     return __comp_(__x, __y.__get_value().first);
 692   }
 693   void swap(__map_value_compare& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Compare>) {
 694     using std::swap;
 695     swap(__comp_, __y.__comp_);
 696   }
 697
 698 #  if _LIBCPP_STD_VER >= 14
 699   template <typename _K2>
 700   _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _CP& __y) const {
 701     return __comp_(__x, __y.__get_value().first);
 702   }
 703
 704   template <typename _K2>
 705   _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _K2& __y) const {
 706     return __comp_(__x.__get_value().first, __y);
 707   }
 708 #  endif
 709 };
 710
 711 template <class _Key, class _CP, class _Compare, bool __b>
 712 inline _LIBCPP_HIDE_FROM_ABI void
 713 swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x, __map_value_compare<_Key, _CP, _Compare, __b>& __y)
 714     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
 715   __x.swap(__y);
 716 }
 717
 718 template <class _Allocator>
 719 class __map_node_destructor {
 720   typedef _Allocator allocator_type;
 721   typedef allocator_traits<allocator_type> __alloc_traits;
 722
 723 public:
 724   typedef typename __alloc_traits::pointer pointer;
 725
 726 private:
 727   allocator_type& __na_;
 728
 729 public:
 730   bool __first_constructed;
 731   bool __second_constructed;
 732
 733   _LIBCPP_HIDE_FROM_ABI explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT
 734       : __na_(__na),
 735         __first_constructed(false),
 736         __second_constructed(false) {}
 737
 738 #  ifndef _LIBCPP_CXX03_LANG
 739   _LIBCPP_HIDE_FROM_ABI __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT
 740       : __na_(__x.__na_),
 741         __first_constructed(__x.__value_constructed),
 742         __second_constructed(__x.__value_constructed) {
 743     __x.__value_constructed = false;
 744   }
 745 #  endif // _LIBCPP_CXX03_LANG
 746
 747   __map_node_destructor& operator=(const __map_node_destructor&) = delete;
 748
 749   _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT {
 750     if (__second_constructed)
 751       __alloc_traits::destroy(__na_, std::addressof(__p->__value_.__get_value().second));
 752     if (__first_constructed)
 753       __alloc_traits::destroy(__na_, std::addressof(__p->__value_.__get_value().first));
 754     if (__p)
 755       __alloc_traits::deallocate(__na_, __p, 1);
 756   }
 757 };
 758
 759 template <class _Key, class _Tp, class _Compare, class _Allocator>
 760 class map;
 761 template <class _Key, class _Tp, class _Compare, class _Allocator>
 762 class multimap;
 763 template <class _TreeIterator>
 764 class __map_const_iterator;
 765
 766 #  ifndef _LIBCPP_CXX03_LANG
 767
 768 template <class _Key, class _Tp>
 769 struct _LIBCPP_STANDALONE_DEBUG __value_type {
 770   typedef _Key key_type;
 771   typedef _Tp mapped_type;
 772   typedef pair<const key_type, mapped_type> value_type;
 773   typedef pair<key_type&, mapped_type&> __nc_ref_pair_type;
 774   typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type;
 775
 776 private:
 777   value_type __cc_;
 778
 779 public:
 780   _LIBCPP_HIDE_FROM_ABI value_type& __get_value() {
 781 #    if _LIBCPP_STD_VER >= 17
 782     return *std::launder(std::addressof(__cc_));
 783 #    else
 784     return __cc_;
 785 #    endif
 786   }
 787
 788   _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const {
 789 #    if _LIBCPP_STD_VER >= 17
 790     return *std::launder(std::addressof(__cc_));
 791 #    else
 792     return __cc_;
 793 #    endif
 794   }
 795
 796   _LIBCPP_HIDE_FROM_ABI __nc_ref_pair_type __ref() {
 797     value_type& __v = __get_value();
 798     return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second);
 799   }
 800
 801   _LIBCPP_HIDE_FROM_ABI __nc_rref_pair_type __move() {
 802     value_type& __v = __get_value();
 803     return __nc_rref_pair_type(std::move(const_cast<key_type&>(__v.first)), std::move(__v.second));
 804   }
 805
 806   _LIBCPP_HIDE_FROM_ABI __value_type& operator=(const __value_type& __v) {
 807     __ref() = __v.__get_value();
 808     return *this;
 809   }
 810
 811   _LIBCPP_HIDE_FROM_ABI __value_type& operator=(__value_type&& __v) {
 812     __ref() = __v.__move();
 813     return *this;
 814   }
 815
 816   template <class _ValueTp, __enable_if_t<__is_same_uncvref<_ValueTp, value_type>::value, int> = 0>
 817   _LIBCPP_HIDE_FROM_ABI __value_type& operator=(_ValueTp&& __v) {
 818     __ref() = std::forward<_ValueTp>(__v);
 819     return *this;
 820   }
 821
 822   __value_type()                    = delete;
 823   ~__value_type()                   = delete;
 824   __value_type(const __value_type&) = delete;
 825   __value_type(__value_type&&)      = delete;
 826 };
 827
 828 #  else
 829
 830 template <class _Key, class _Tp>
 831 struct __value_type {
 832   typedef _Key key_type;
 833   typedef _Tp mapped_type;
 834   typedef pair<const key_type, mapped_type> value_type;
 835
 836 private:
 837   value_type __cc_;
 838
 839 public:
 840   _LIBCPP_HIDE_FROM_ABI value_type& __get_value() { return __cc_; }
 841   _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const { return __cc_; }
 842
 843   __value_type()                               = delete;
 844   __value_type(__value_type const&)            = delete;
 845   __value_type& operator=(__value_type const&) = delete;
 846   ~__value_type()                              = delete;
 847 };
 848
 849 #  endif // _LIBCPP_CXX03_LANG
 850
 851 template <class _Tp>
 852 struct __extract_key_value_types;
 853
 854 template <class _Key, class _Tp>
 855 struct __extract_key_value_types<__value_type<_Key, _Tp> > {
 856   typedef _Key const __key_type;
 857   typedef _Tp __mapped_type;
 858 };
 859
 860 template <class _TreeIterator>
 861 class _LIBCPP_TEMPLATE_VIS __map_iterator {
 862   typedef typename _TreeIterator::_NodeTypes _NodeTypes;
 863   typedef typename _TreeIterator::__pointer_traits __pointer_traits;
 864
 865   _TreeIterator __i_;
 866
 867 public:
 868   typedef bidirectional_iterator_tag iterator_category;
 869   typedef typename _NodeTypes::__map_value_type value_type;
 870   typedef typename _TreeIterator::difference_type difference_type;
 871   typedef value_type& reference;
 872   typedef typename _NodeTypes::__map_value_type_pointer pointer;
 873
 874   _LIBCPP_HIDE_FROM_ABI __map_iterator() _NOEXCEPT {}
 875
 876   _LIBCPP_HIDE_FROM_ABI __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
 877
 878   _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); }
 879   _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); }
 880
 881   _LIBCPP_HIDE_FROM_ABI __map_iterator& operator++() {
 882     ++__i_;
 883     return *this;
 884   }
 885   _LIBCPP_HIDE_FROM_ABI __map_iterator operator++(int) {
 886     __map_iterator __t(*this);
 887     ++(*this);
 888     return __t;
 889   }
 890
 891   _LIBCPP_HIDE_FROM_ABI __map_iterator& operator--() {
 892     --__i_;
 893     return *this;
 894   }
 895   _LIBCPP_HIDE_FROM_ABI __map_iterator operator--(int) {
 896     __map_iterator __t(*this);
 897     --(*this);
 898     return __t;
 899   }
 900
 901   friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __map_iterator& __x, const __map_iterator& __y) {
 902     return __x.__i_ == __y.__i_;
 903   }
 904   friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __map_iterator& __x, const __map_iterator& __y) {
 905     return __x.__i_ != __y.__i_;
 906   }
 907
 908   template <class, class, class, class>
 909   friend class _LIBCPP_TEMPLATE_VIS map;
 910   template <class, class, class, class>
 911   friend class _LIBCPP_TEMPLATE_VIS multimap;
 912   template <class>
 913   friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator;
 914 };
 915
 916 template <class _TreeIterator>
 917 class _LIBCPP_TEMPLATE_VIS __map_const_iterator {
 918   typedef typename _TreeIterator::_NodeTypes _NodeTypes;
 919   typedef typename _TreeIterator::__pointer_traits __pointer_traits;
 920
 921   _TreeIterator __i_;
 922
 923 public:
 924   typedef bidirectional_iterator_tag iterator_category;
 925   typedef typename _NodeTypes::__map_value_type value_type;
 926   typedef typename _TreeIterator::difference_type difference_type;
 927   typedef const value_type& reference;
 928   typedef typename _NodeTypes::__const_map_value_type_pointer pointer;
 929
 930   _LIBCPP_HIDE_FROM_ABI __map_const_iterator() _NOEXCEPT {}
 931
 932   _LIBCPP_HIDE_FROM_ABI __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
 933   _LIBCPP_HIDE_FROM_ABI
 934   __map_const_iterator(__map_iterator< typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT : __i_(__i.__i_) {}
 935
 936   _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); }
 937   _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); }
 938
 939   _LIBCPP_HIDE_FROM_ABI __map_const_iterator& operator++() {
 940     ++__i_;
 941     return *this;
 942   }
 943   _LIBCPP_HIDE_FROM_ABI __map_const_iterator operator++(int) {
 944     __map_const_iterator __t(*this);
 945     ++(*this);
 946     return __t;
 947   }
 948
 949   _LIBCPP_HIDE_FROM_ABI __map_const_iterator& operator--() {
 950     --__i_;
 951     return *this;
 952   }
 953   _LIBCPP_HIDE_FROM_ABI __map_const_iterator operator--(int) {
 954     __map_const_iterator __t(*this);
 955     --(*this);
 956     return __t;
 957   }
 958
 959   friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y) {
 960     return __x.__i_ == __y.__i_;
 961   }
 962   friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y) {
 963     return __x.__i_ != __y.__i_;
 964   }
 965
 966   template <class, class, class, class>
 967   friend class _LIBCPP_TEMPLATE_VIS map;
 968   template <class, class, class, class>
 969   friend class _LIBCPP_TEMPLATE_VIS multimap;
 970   template <class, class, class>
 971   friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator;
 972 };
 973
 974 template <class _Key, class _Tp, class _Compare = less<_Key>, class _Allocator = allocator<pair<const _Key, _Tp> > >
 975 class _LIBCPP_TEMPLATE_VIS map {
 976 public:
 977   // types:
 978   typedef _Key key_type;
 979   typedef _Tp mapped_type;
 980   typedef pair<const key_type, mapped_type> value_type;
 981   typedef __type_identity_t<_Compare> key_compare;
 982   typedef __type_identity_t<_Allocator> allocator_type;
 983   typedef value_type& reference;
 984   typedef const value_type& const_reference;
 985
 986   static_assert(is_same<typename allocator_type::value_type, value_type>::value,
 987                 "Allocator::value_type must be same type as value_type");
 988
 989   class _LIBCPP_TEMPLATE_VIS value_compare : public __binary_function<value_type, value_type, bool> {
 990     friend class map;
 991
 992   protected:
 993     key_compare comp;
 994
 995     _LIBCPP_HIDE_FROM_ABI value_compare(key_compare __c) : comp(__c) {}
 996
 997   public:
 998     _LIBCPP_HIDE_FROM_ABI bool operator()(const value_type& __x, const value_type& __y) const {
 999       return comp(__x.first, __y.first);
1000     }
1001   };
1002
1003 private:
1004   typedef std::__value_type<key_type, mapped_type> __value_type;
1005   typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
1006   typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type;
1007   typedef __tree<__value_type, __vc, __allocator_type> __base;
1008   typedef typename __base::__node_traits __node_traits;
1009   typedef allocator_traits<allocator_type> __alloc_traits;
1010
1011   static_assert(__check_valid_allocator<allocator_type>::value, "");
1012
1013   __base __tree_;
1014
1015 public:
1016   typedef typename __alloc_traits::pointer pointer;
1017   typedef typename __alloc_traits::const_pointer const_pointer;
1018   typedef typename __alloc_traits::size_type size_type;
1019   typedef typename __alloc_traits::difference_type difference_type;
1020   typedef __map_iterator<typename __base::iterator> iterator;
1021   typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1022   typedef std::reverse_iterator<iterator> reverse_iterator;
1023   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1024
1025 #  if _LIBCPP_STD_VER >= 17
1026   typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
1027   typedef __insert_return_type<iterator, node_type> insert_return_type;
1028 #  endif
1029
1030   template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1031   friend class _LIBCPP_TEMPLATE_VIS map;
1032   template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1033   friend class _LIBCPP_TEMPLATE_VIS multimap;
1034
1035   _LIBCPP_HIDE_FROM_ABI map() _NOEXCEPT_(
1036       is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&&
1037           is_nothrow_copy_constructible<key_compare>::value)
1038       : __tree_(__vc(key_compare())) {}
1039
1040   _LIBCPP_HIDE_FROM_ABI explicit map(const key_compare& __comp) _NOEXCEPT_(
1041       is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value)
1042       : __tree_(__vc(__comp)) {}
1043
1044   _LIBCPP_HIDE_FROM_ABI explicit map(const key_compare& __comp, const allocator_type& __a)
1045       : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
1046
1047   template <class _InputIterator>
1048   _LIBCPP_HIDE_FROM_ABI map(_InputIterator __f, _InputIterator __l, const key_compare& __comp = key_compare())
1049       : __tree_(__vc(__comp)) {
1050     insert(__f, __l);
1051   }
1052
1053   template <class _InputIterator>
1054   _LIBCPP_HIDE_FROM_ABI
1055   map(_InputIterator __f, _InputIterator __l, const key_compare& __comp, const allocator_type& __a)
1056       : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1057     insert(__f, __l);
1058   }
1059
1060 #  if _LIBCPP_STD_VER >= 23
1061   template <_ContainerCompatibleRange<value_type> _Range>
1062   _LIBCPP_HIDE_FROM_ABI
1063   map(from_range_t,
1064       _Range&& __range,
1065       const key_compare& __comp = key_compare(),
1066       const allocator_type& __a = allocator_type())
1067       : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1068     insert_range(std::forward<_Range>(__range));
1069   }
1070 #  endif
1071
1072 #  if _LIBCPP_STD_VER >= 14
1073   template <class _InputIterator>
1074   _LIBCPP_HIDE_FROM_ABI map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1075       : map(__f, __l, key_compare(), __a) {}
1076 #  endif
1077
1078 #  if _LIBCPP_STD_VER >= 23
1079   template <_ContainerCompatibleRange<value_type> _Range>
1080   _LIBCPP_HIDE_FROM_ABI map(from_range_t, _Range&& __range, const allocator_type& __a)
1081       : map(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
1082 #  endif
1083
1084   _LIBCPP_HIDE_FROM_ABI map(const map& __m) : __tree_(__m.__tree_) { insert(__m.begin(), __m.end()); }
1085
1086   _LIBCPP_HIDE_FROM_ABI map& operator=(const map& __m) {
1087 #  ifndef _LIBCPP_CXX03_LANG
1088     __tree_ = __m.__tree_;
1089 #  else
1090     if (this != std::addressof(__m)) {
1091       __tree_.clear();
1092       __tree_.value_comp() = __m.__tree_.value_comp();
1093       __tree_.__copy_assign_alloc(__m.__tree_);
1094       insert(__m.begin(), __m.end());
1095     }
1096 #  endif
1097     return *this;
1098   }
1099
1100 #  ifndef _LIBCPP_CXX03_LANG
1101
1102   _LIBCPP_HIDE_FROM_ABI map(map&& __m) noexcept(is_nothrow_move_constructible<__base>::value)
1103       : __tree_(std::move(__m.__tree_)) {}
1104
1105   _LIBCPP_HIDE_FROM_ABI map(map&& __m, const allocator_type& __a);
1106
1107   _LIBCPP_HIDE_FROM_ABI map& operator=(map&& __m) noexcept(is_nothrow_move_assignable<__base>::value) {
1108     __tree_ = std::move(__m.__tree_);
1109     return *this;
1110   }
1111
1112   _LIBCPP_HIDE_FROM_ABI map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1113       : __tree_(__vc(__comp)) {
1114     insert(__il.begin(), __il.end());
1115   }
1116
1117   _LIBCPP_HIDE_FROM_ABI map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1118       : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1119     insert(__il.begin(), __il.end());
1120   }
1121
1122 #    if _LIBCPP_STD_VER >= 14
1123   _LIBCPP_HIDE_FROM_ABI map(initializer_list<value_type> __il, const allocator_type& __a)
1124       : map(__il, key_compare(), __a) {}
1125 #    endif
1126
1127   _LIBCPP_HIDE_FROM_ABI map& operator=(initializer_list<value_type> __il) {
1128     __tree_.__assign_unique(__il.begin(), __il.end());
1129     return *this;
1130   }
1131
1132 #  endif // _LIBCPP_CXX03_LANG
1133
1134   _LIBCPP_HIDE_FROM_ABI explicit map(const allocator_type& __a) : __tree_(typename __base::allocator_type(__a)) {}
1135
1136   _LIBCPP_HIDE_FROM_ABI map(const map& __m, const allocator_type& __a)
1137       : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) {
1138     insert(__m.begin(), __m.end());
1139   }
1140
1141   _LIBCPP_HIDE_FROM_ABI ~map() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); }
1142
1143   _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }
1144   _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }
1145   _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }
1146   _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }
1147
1148   _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
1149   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
1150   _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
1151   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
1152
1153   _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
1154   _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
1155   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }
1156   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
1157
1158   [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }
1159   _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }
1160   _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }
1161
1162   _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k);
1163 #  ifndef _LIBCPP_CXX03_LANG
1164   _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](key_type&& __k);
1165 #  endif
1166
1167   _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __k);
1168   _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __k) const;
1169
1170   _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(__tree_.__alloc()); }
1171   _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp().key_comp(); }
1172   _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return value_compare(__tree_.value_comp().key_comp()); }
1173
1174 #  ifndef _LIBCPP_CXX03_LANG
1175   template <class... _Args>
1176   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {
1177     return __tree_.__emplace_unique(std::forward<_Args>(__args)...);
1178   }
1179
1180   template <class... _Args>
1181   _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1182     return __tree_.__emplace_hint_unique(__p.__i_, std::forward<_Args>(__args)...);
1183   }
1184
1185   template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
1186   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(_Pp&& __p) {
1187     return __tree_.__insert_unique(std::forward<_Pp>(__p));
1188   }
1189
1190   template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
1191   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __pos, _Pp&& __p) {
1192     return __tree_.__insert_unique(__pos.__i_, std::forward<_Pp>(__p));
1193   }
1194
1195 #  endif // _LIBCPP_CXX03_LANG
1196
1197   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__insert_unique(__v); }
1198
1199   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
1200     return __tree_.__insert_unique(__p.__i_, __v);
1201   }
1202
1203 #  ifndef _LIBCPP_CXX03_LANG
1204   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __v) {
1205     return __tree_.__insert_unique(std::move(__v));
1206   }
1207
1208   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {
1209     return __tree_.__insert_unique(__p.__i_, std::move(__v));
1210   }
1211
1212   _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
1213 #  endif
1214
1215   template <class _InputIterator>
1216   _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
1217     for (const_iterator __e = cend(); __f != __l; ++__f)
1218       insert(__e.__i_, *__f);
1219   }
1220
1221 #  if _LIBCPP_STD_VER >= 23
1222   template <_ContainerCompatibleRange<value_type> _Range>
1223   _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
1224     const_iterator __end = cend();
1225     for (auto&& __element : __range) {
1226       insert(__end.__i_, std::forward<decltype(__element)>(__element));
1227     }
1228   }
1229 #  endif
1230
1231 #  if _LIBCPP_STD_VER >= 17
1232
1233   template <class... _Args>
1234   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) {
1235     return __tree_.__emplace_unique_key_args(
1236         __k,
1237         std::piecewise_construct,
1238         std::forward_as_tuple(__k),
1239         std::forward_as_tuple(std::forward<_Args>(__args)...));
1240   }
1241
1242   template <class... _Args>
1243   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) {
1244     return __tree_.__emplace_unique_key_args(
1245         __k,
1246         std::piecewise_construct,
1247         std::forward_as_tuple(std::move(__k)),
1248         std::forward_as_tuple(std::forward<_Args>(__args)...));
1249   }
1250
1251   template <class... _Args>
1252   _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args) {
1253     return __tree_
1254         .__emplace_hint_unique_key_args(
1255             __h.__i_,
1256             __k,
1257             std::piecewise_construct,
1258             std::forward_as_tuple(__k),
1259             std::forward_as_tuple(std::forward<_Args>(__args)...))
1260         .first;
1261   }
1262
1263   template <class... _Args>
1264   _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) {
1265     return __tree_
1266         .__emplace_hint_unique_key_args(
1267             __h.__i_,
1268             __k,
1269             std::piecewise_construct,
1270             std::forward_as_tuple(std::move(__k)),
1271             std::forward_as_tuple(std::forward<_Args>(__args)...))
1272         .first;
1273   }
1274
1275   template <class _Vp>
1276   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) {
1277     iterator __p = lower_bound(__k);
1278     if (__p != end() && !key_comp()(__k, __p->first)) {
1279       __p->second = std::forward<_Vp>(__v);
1280       return std::make_pair(__p, false);
1281     }
1282     return std::make_pair(emplace_hint(__p, __k, std::forward<_Vp>(__v)), true);
1283   }
1284
1285   template <class _Vp>
1286   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) {
1287     iterator __p = lower_bound(__k);
1288     if (__p != end() && !key_comp()(__k, __p->first)) {
1289       __p->second = std::forward<_Vp>(__v);
1290       return std::make_pair(__p, false);
1291     }
1292     return std::make_pair(emplace_hint(__p, std::move(__k), std::forward<_Vp>(__v)), true);
1293   }
1294
1295   template <class _Vp>
1296   _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v) {
1297     auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, __k, std::forward<_Vp>(__v));
1298
1299     if (!__inserted)
1300       __r->__get_value().second = std::forward<_Vp>(__v);
1301
1302     return __r;
1303   }
1304
1305   template <class _Vp>
1306   _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v) {
1307     auto [__r, __inserted] =
1308         __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, std::move(__k), std::forward<_Vp>(__v));
1309
1310     if (!__inserted)
1311       __r->__get_value().second = std::forward<_Vp>(__v);
1312
1313     return __r;
1314   }
1315
1316 #  endif // _LIBCPP_STD_VER >= 17
1317
1318   _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p.__i_); }
1319   _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __tree_.erase(__p.__i_); }
1320   _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_unique(__k); }
1321   _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) {
1322     return __tree_.erase(__f.__i_, __l.__i_);
1323   }
1324   _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }
1325
1326 #  if _LIBCPP_STD_VER >= 17
1327   _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) {
1328     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1329                                         "node_type with incompatible allocator passed to map::insert()");
1330     return __tree_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));
1331   }
1332   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
1333     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1334                                         "node_type with incompatible allocator passed to map::insert()");
1335     return __tree_.template __node_handle_insert_unique<node_type>(__hint.__i_, std::move(__nh));
1336   }
1337   _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
1338     return __tree_.template __node_handle_extract<node_type>(__key);
1339   }
1340   _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
1341     return __tree_.template __node_handle_extract<node_type>(__it.__i_);
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(map<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   template <class _Compare2>
1362   _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source) {
1363     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1364         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1365     __tree_.__node_handle_merge_unique(__source.__tree_);
1366   }
1367 #  endif
1368
1369   _LIBCPP_HIDE_FROM_ABI void swap(map& __m) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) { __tree_.swap(__m.__tree_); }
1370
1371   _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }
1372   _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }
1373 #  if _LIBCPP_STD_VER >= 14
1374   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1375   _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
1376     return __tree_.find(__k);
1377   }
1378   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1379   _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
1380     return __tree_.find(__k);
1381   }
1382 #  endif
1383
1384   _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_unique(__k); }
1385 #  if _LIBCPP_STD_VER >= 14
1386   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1387   _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
1388     return __tree_.__count_multi(__k);
1389   }
1390 #  endif
1391
1392 #  if _LIBCPP_STD_VER >= 20
1393   _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
1394   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1395   _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
1396     return find(__k) != end();
1397   }
1398 #  endif // _LIBCPP_STD_VER >= 20
1399
1400   _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
1401   _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
1402 #  if _LIBCPP_STD_VER >= 14
1403   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1404   _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {
1405     return __tree_.lower_bound(__k);
1406   }
1407
1408   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1409   _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const {
1410     return __tree_.lower_bound(__k);
1411   }
1412 #  endif
1413
1414   _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
1415   _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
1416 #  if _LIBCPP_STD_VER >= 14
1417   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1418   _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {
1419     return __tree_.upper_bound(__k);
1420   }
1421   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1422   _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const {
1423     return __tree_.upper_bound(__k);
1424   }
1425 #  endif
1426
1427   _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
1428     return __tree_.__equal_range_unique(__k);
1429   }
1430   _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
1431     return __tree_.__equal_range_unique(__k);
1432   }
1433 #  if _LIBCPP_STD_VER >= 14
1434   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1435   _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
1436     return __tree_.__equal_range_multi(__k);
1437   }
1438   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1439   _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
1440     return __tree_.__equal_range_multi(__k);
1441   }
1442 #  endif
1443
1444 private:
1445   typedef typename __base::__node __node;
1446   typedef typename __base::__node_allocator __node_allocator;
1447   typedef typename __base::__node_pointer __node_pointer;
1448   typedef typename __base::__node_base_pointer __node_base_pointer;
1449   typedef typename __base::__parent_pointer __parent_pointer;
1450
1451   typedef __map_node_destructor<__node_allocator> _Dp;
1452   typedef unique_ptr<__node, _Dp> __node_holder;
1453
1454 #  ifdef _LIBCPP_CXX03_LANG
1455   _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_with_key(const key_type& __k);
1456 #  endif
1457 };
1458
1459 #  if _LIBCPP_STD_VER >= 17
1460 template <class _InputIterator,
1461           class _Compare   = less<__iter_key_type<_InputIterator>>,
1462           class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
1463           class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1464           class            = enable_if_t<!__is_allocator<_Compare>::value, void>,
1465           class            = enable_if_t<__is_allocator<_Allocator>::value, void>>
1466 map(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1467     -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
1468
1469 #    if _LIBCPP_STD_VER >= 23
1470 template <ranges::input_range _Range,
1471           class _Compare   = less<__range_key_type<_Range>>,
1472           class _Allocator = allocator<__range_to_alloc_type<_Range>>,
1473           class            = enable_if_t<!__is_allocator<_Compare>::value, void>,
1474           class            = enable_if_t<__is_allocator<_Allocator>::value, void>>
1475 map(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
1476     -> map<__range_key_type<_Range>, __range_mapped_type<_Range>, _Compare, _Allocator>;
1477 #    endif
1478
1479 template <class _Key,
1480           class _Tp,
1481           class _Compare   = less<remove_const_t<_Key>>,
1482           class _Allocator = allocator<pair<const _Key, _Tp>>,
1483           class            = enable_if_t<!__is_allocator<_Compare>::value, void>,
1484           class            = enable_if_t<__is_allocator<_Allocator>::value, void>>
1485 map(initializer_list<pair<_Key, _Tp>>,
1486     _Compare   = _Compare(),
1487     _Allocator = _Allocator()) -> map<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
1488
1489 template <class _InputIterator,
1490           class _Allocator,
1491           class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1492           class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1493 map(_InputIterator, _InputIterator, _Allocator)
1494     -> map<__iter_key_type<_InputIterator>,
1495            __iter_mapped_type<_InputIterator>,
1496            less<__iter_key_type<_InputIterator>>,
1497            _Allocator>;
1498
1499 #    if _LIBCPP_STD_VER >= 23
1500 template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1501 map(from_range_t, _Range&&, _Allocator)
1502     -> map<__range_key_type<_Range>, __range_mapped_type<_Range>, less<__range_key_type<_Range>>, _Allocator>;
1503 #    endif
1504
1505 template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1506 map(initializer_list<pair<_Key, _Tp>>,
1507     _Allocator) -> map<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;
1508 #  endif
1509
1510 #  ifndef _LIBCPP_CXX03_LANG
1511 template <class _Key, class _Tp, class _Compare, class _Allocator>
1512 map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
1513     : __tree_(std::move(__m.__tree_), typename __base::allocator_type(__a)) {
1514   if (__a != __m.get_allocator()) {
1515     const_iterator __e = cend();
1516     while (!__m.empty())
1517       __tree_.__insert_unique(__e.__i_, __m.__tree_.remove(__m.begin().__i_)->__value_.__move());
1518   }
1519 }
1520
1521 template <class _Key, class _Tp, class _Compare, class _Allocator>
1522 _Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) {
1523   return __tree_
1524       .__emplace_unique_key_args(__k, std::piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple())
1525       .first->__get_value()
1526       .second;
1527 }
1528
1529 template <class _Key, class _Tp, class _Compare, class _Allocator>
1530 _Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k) {
1531   // TODO investigate this clang-tidy warning.
1532   // NOLINTBEGIN(bugprone-use-after-move)
1533   return __tree_
1534       .__emplace_unique_key_args(
1535           __k, std::piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple())
1536       .first->__get_value()
1537       .second;
1538   // NOLINTEND(bugprone-use-after-move)
1539 }
1540
1541 #  else // _LIBCPP_CXX03_LANG
1542
1543 template <class _Key, class _Tp, class _Compare, class _Allocator>
1544 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1545 map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k) {
1546   __node_allocator& __na = __tree_.__node_alloc();
1547   __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1548   __node_traits::construct(__na, std::addressof(__h->__value_.__get_value().first), __k);
1549   __h.get_deleter().__first_constructed = true;
1550   __node_traits::construct(__na, std::addressof(__h->__value_.__get_value().second));
1551   __h.get_deleter().__second_constructed = true;
1552   return __h;
1553 }
1554
1555 template <class _Key, class _Tp, class _Compare, class _Allocator>
1556 _Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) {
1557   __parent_pointer __parent;
1558   __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1559   __node_pointer __r           = static_cast<__node_pointer>(__child);
1560   if (__child == nullptr) {
1561     __node_holder __h = __construct_node_with_key(__k);
1562     __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1563     __r = __h.release();
1564   }
1565   return __r->__value_.__get_value().second;
1566 }
1567
1568 #  endif // _LIBCPP_CXX03_LANG
1569
1570 template <class _Key, class _Tp, class _Compare, class _Allocator>
1571 _Tp& map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) {
1572   __parent_pointer __parent;
1573   __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1574   if (__child == nullptr)
1575     __throw_out_of_range("map::at:  key not found");
1576   return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
1577 }
1578
1579 template <class _Key, class _Tp, class _Compare, class _Allocator>
1580 const _Tp& map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const {
1581   __parent_pointer __parent;
1582   __node_base_pointer __child = __tree_.__find_equal(__parent, __k);
1583   if (__child == nullptr)
1584     __throw_out_of_range("map::at:  key not found");
1585   return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
1586 }
1587
1588 template <class _Key, class _Tp, class _Compare, class _Allocator>
1589 inline _LIBCPP_HIDE_FROM_ABI bool
1590 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1591   return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
1592 }
1593
1594 #  if _LIBCPP_STD_VER <= 17
1595
1596 template <class _Key, class _Tp, class _Compare, class _Allocator>
1597 inline _LIBCPP_HIDE_FROM_ABI bool
1598 operator<(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1599   return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1600 }
1601
1602 template <class _Key, class _Tp, class _Compare, class _Allocator>
1603 inline _LIBCPP_HIDE_FROM_ABI bool
1604 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1605   return !(__x == __y);
1606 }
1607
1608 template <class _Key, class _Tp, class _Compare, class _Allocator>
1609 inline _LIBCPP_HIDE_FROM_ABI bool
1610 operator>(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1611   return __y < __x;
1612 }
1613
1614 template <class _Key, class _Tp, class _Compare, class _Allocator>
1615 inline _LIBCPP_HIDE_FROM_ABI bool
1616 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1617   return !(__x < __y);
1618 }
1619
1620 template <class _Key, class _Tp, class _Compare, class _Allocator>
1621 inline _LIBCPP_HIDE_FROM_ABI bool
1622 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1623   return !(__y < __x);
1624 }
1625
1626 #  else // #if _LIBCPP_STD_VER <= 17
1627
1628 template <class _Key, class _Tp, class _Compare, class _Allocator>
1629 _LIBCPP_HIDE_FROM_ABI __synth_three_way_result<pair<const _Key, _Tp>>
1630 operator<=>(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1631   return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
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, class _Allocator>
1652 struct __container_traits<map<_Key, _Tp, _Compare, _Allocator> > {
1653   // http://eel.is/c++draft/associative.reqmts.except#2
1654   // For associative containers, if an exception is thrown by any operation from within
1655   // an insert or emplace function inserting a single element, the insertion has no effect.
1656   static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee = true;
1657 };
1658
1659 template <class _Key, class _Tp, class _Compare = less<_Key>, class _Allocator = allocator<pair<const _Key, _Tp> > >
1660 class _LIBCPP_TEMPLATE_VIS multimap {
1661 public:
1662   // types:
1663   typedef _Key key_type;
1664   typedef _Tp mapped_type;
1665   typedef pair<const key_type, mapped_type> value_type;
1666   typedef __type_identity_t<_Compare> key_compare;
1667   typedef __type_identity_t<_Allocator> allocator_type;
1668   typedef value_type& reference;
1669   typedef const value_type& const_reference;
1670
1671   static_assert(__check_valid_allocator<allocator_type>::value, "");
1672   static_assert(is_same<typename allocator_type::value_type, value_type>::value,
1673                 "Allocator::value_type must be same type as value_type");
1674
1675   class _LIBCPP_TEMPLATE_VIS value_compare : public __binary_function<value_type, value_type, bool> {
1676     friend class multimap;
1677
1678   protected:
1679     key_compare comp;
1680
1681     _LIBCPP_HIDE_FROM_ABI value_compare(key_compare __c) : comp(__c) {}
1682
1683   public:
1684     _LIBCPP_HIDE_FROM_ABI bool operator()(const value_type& __x, const value_type& __y) const {
1685       return comp(__x.first, __y.first);
1686     }
1687   };
1688
1689 private:
1690   typedef std::__value_type<key_type, mapped_type> __value_type;
1691   typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
1692   typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type;
1693   typedef __tree<__value_type, __vc, __allocator_type> __base;
1694   typedef typename __base::__node_traits __node_traits;
1695   typedef allocator_traits<allocator_type> __alloc_traits;
1696
1697   __base __tree_;
1698
1699 public:
1700   typedef typename __alloc_traits::pointer pointer;
1701   typedef typename __alloc_traits::const_pointer const_pointer;
1702   typedef typename __alloc_traits::size_type size_type;
1703   typedef typename __alloc_traits::difference_type difference_type;
1704   typedef __map_iterator<typename __base::iterator> iterator;
1705   typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1706   typedef std::reverse_iterator<iterator> reverse_iterator;
1707   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1708
1709 #  if _LIBCPP_STD_VER >= 17
1710   typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
1711 #  endif
1712
1713   template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1714   friend class _LIBCPP_TEMPLATE_VIS map;
1715   template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1716   friend class _LIBCPP_TEMPLATE_VIS multimap;
1717
1718   _LIBCPP_HIDE_FROM_ABI multimap() _NOEXCEPT_(
1719       is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&&
1720           is_nothrow_copy_constructible<key_compare>::value)
1721       : __tree_(__vc(key_compare())) {}
1722
1723   _LIBCPP_HIDE_FROM_ABI explicit multimap(const key_compare& __comp) _NOEXCEPT_(
1724       is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value)
1725       : __tree_(__vc(__comp)) {}
1726
1727   _LIBCPP_HIDE_FROM_ABI explicit multimap(const key_compare& __comp, const allocator_type& __a)
1728       : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
1729
1730   template <class _InputIterator>
1731   _LIBCPP_HIDE_FROM_ABI multimap(_InputIterator __f, _InputIterator __l, const key_compare& __comp = key_compare())
1732       : __tree_(__vc(__comp)) {
1733     insert(__f, __l);
1734   }
1735
1736   template <class _InputIterator>
1737   _LIBCPP_HIDE_FROM_ABI
1738   multimap(_InputIterator __f, _InputIterator __l, const key_compare& __comp, const allocator_type& __a)
1739       : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1740     insert(__f, __l);
1741   }
1742
1743 #  if _LIBCPP_STD_VER >= 23
1744   template <_ContainerCompatibleRange<value_type> _Range>
1745   _LIBCPP_HIDE_FROM_ABI
1746   multimap(from_range_t,
1747            _Range&& __range,
1748            const key_compare& __comp = key_compare(),
1749            const allocator_type& __a = allocator_type())
1750       : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1751     insert_range(std::forward<_Range>(__range));
1752   }
1753 #  endif
1754
1755 #  if _LIBCPP_STD_VER >= 14
1756   template <class _InputIterator>
1757   _LIBCPP_HIDE_FROM_ABI multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1758       : multimap(__f, __l, key_compare(), __a) {}
1759 #  endif
1760
1761 #  if _LIBCPP_STD_VER >= 23
1762   template <_ContainerCompatibleRange<value_type> _Range>
1763   _LIBCPP_HIDE_FROM_ABI multimap(from_range_t, _Range&& __range, const allocator_type& __a)
1764       : multimap(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
1765 #  endif
1766
1767   _LIBCPP_HIDE_FROM_ABI multimap(const multimap& __m)
1768       : __tree_(__m.__tree_.value_comp(),
1769                 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc())) {
1770     insert(__m.begin(), __m.end());
1771   }
1772
1773   _LIBCPP_HIDE_FROM_ABI multimap& operator=(const multimap& __m) {
1774 #  ifndef _LIBCPP_CXX03_LANG
1775     __tree_ = __m.__tree_;
1776 #  else
1777     if (this != std::addressof(__m)) {
1778       __tree_.clear();
1779       __tree_.value_comp() = __m.__tree_.value_comp();
1780       __tree_.__copy_assign_alloc(__m.__tree_);
1781       insert(__m.begin(), __m.end());
1782     }
1783 #  endif
1784     return *this;
1785   }
1786
1787 #  ifndef _LIBCPP_CXX03_LANG
1788
1789   _LIBCPP_HIDE_FROM_ABI multimap(multimap&& __m) noexcept(is_nothrow_move_constructible<__base>::value)
1790       : __tree_(std::move(__m.__tree_)) {}
1791
1792   _LIBCPP_HIDE_FROM_ABI multimap(multimap&& __m, const allocator_type& __a);
1793
1794   _LIBCPP_HIDE_FROM_ABI multimap& operator=(multimap&& __m) noexcept(is_nothrow_move_assignable<__base>::value) {
1795     __tree_ = std::move(__m.__tree_);
1796     return *this;
1797   }
1798
1799   _LIBCPP_HIDE_FROM_ABI multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1800       : __tree_(__vc(__comp)) {
1801     insert(__il.begin(), __il.end());
1802   }
1803
1804   _LIBCPP_HIDE_FROM_ABI
1805   multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1806       : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1807     insert(__il.begin(), __il.end());
1808   }
1809
1810 #    if _LIBCPP_STD_VER >= 14
1811   _LIBCPP_HIDE_FROM_ABI multimap(initializer_list<value_type> __il, const allocator_type& __a)
1812       : multimap(__il, key_compare(), __a) {}
1813 #    endif
1814
1815   _LIBCPP_HIDE_FROM_ABI multimap& operator=(initializer_list<value_type> __il) {
1816     __tree_.__assign_multi(__il.begin(), __il.end());
1817     return *this;
1818   }
1819
1820 #  endif // _LIBCPP_CXX03_LANG
1821
1822   _LIBCPP_HIDE_FROM_ABI explicit multimap(const allocator_type& __a) : __tree_(typename __base::allocator_type(__a)) {}
1823
1824   _LIBCPP_HIDE_FROM_ABI multimap(const multimap& __m, const allocator_type& __a)
1825       : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) {
1826     insert(__m.begin(), __m.end());
1827   }
1828
1829   _LIBCPP_HIDE_FROM_ABI ~multimap() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); }
1830
1831   _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }
1832   _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }
1833   _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }
1834   _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }
1835
1836   _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
1837   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
1838   _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
1839   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
1840
1841   _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
1842   _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
1843   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }
1844   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
1845
1846   [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }
1847   _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }
1848   _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }
1849
1850   _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(__tree_.__alloc()); }
1851   _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp().key_comp(); }
1852   _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return value_compare(__tree_.value_comp().key_comp()); }
1853
1854 #  ifndef _LIBCPP_CXX03_LANG
1855
1856   template <class... _Args>
1857   _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) {
1858     return __tree_.__emplace_multi(std::forward<_Args>(__args)...);
1859   }
1860
1861   template <class... _Args>
1862   _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1863     return __tree_.__emplace_hint_multi(__p.__i_, std::forward<_Args>(__args)...);
1864   }
1865
1866   template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
1867   _LIBCPP_HIDE_FROM_ABI iterator insert(_Pp&& __p) {
1868     return __tree_.__insert_multi(std::forward<_Pp>(__p));
1869   }
1870
1871   template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
1872   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __pos, _Pp&& __p) {
1873     return __tree_.__insert_multi(__pos.__i_, std::forward<_Pp>(__p));
1874   }
1875
1876   _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __v) { return __tree_.__insert_multi(std::move(__v)); }
1877
1878   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {
1879     return __tree_.__insert_multi(__p.__i_, std::move(__v));
1880   }
1881
1882   _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
1883
1884 #  endif // _LIBCPP_CXX03_LANG
1885
1886   _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __v) { return __tree_.__insert_multi(__v); }
1887
1888   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
1889     return __tree_.__insert_multi(__p.__i_, __v);
1890   }
1891
1892   template <class _InputIterator>
1893   _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
1894     for (const_iterator __e = cend(); __f != __l; ++__f)
1895       __tree_.__insert_multi(__e.__i_, *__f);
1896   }
1897
1898 #  if _LIBCPP_STD_VER >= 23
1899   template <_ContainerCompatibleRange<value_type> _Range>
1900   _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
1901     const_iterator __end = cend();
1902     for (auto&& __element : __range) {
1903       __tree_.__insert_multi(__end.__i_, std::forward<decltype(__element)>(__element));
1904     }
1905   }
1906 #  endif
1907
1908   _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p.__i_); }
1909   _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __tree_.erase(__p.__i_); }
1910   _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_multi(__k); }
1911   _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) {
1912     return __tree_.erase(__f.__i_, __l.__i_);
1913   }
1914
1915 #  if _LIBCPP_STD_VER >= 17
1916   _LIBCPP_HIDE_FROM_ABI iterator insert(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>(std::move(__nh));
1920   }
1921   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
1922     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1923                                         "node_type with incompatible allocator passed to multimap::insert()");
1924     return __tree_.template __node_handle_insert_multi<node_type>(__hint.__i_, std::move(__nh));
1925   }
1926   _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
1927     return __tree_.template __node_handle_extract<node_type>(__key);
1928   }
1929   _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
1930     return __tree_.template __node_handle_extract<node_type>(__it.__i_);
1931   }
1932   template <class _Compare2>
1933   _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source) {
1934     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1935         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1936     return __tree_.__node_handle_merge_multi(__source.__tree_);
1937   }
1938   template <class _Compare2>
1939   _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source) {
1940     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1941         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1942     return __tree_.__node_handle_merge_multi(__source.__tree_);
1943   }
1944   template <class _Compare2>
1945   _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source) {
1946     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1947         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1948     return __tree_.__node_handle_merge_multi(__source.__tree_);
1949   }
1950   template <class _Compare2>
1951   _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source) {
1952     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1953         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1954     return __tree_.__node_handle_merge_multi(__source.__tree_);
1955   }
1956 #  endif
1957
1958   _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }
1959
1960   _LIBCPP_HIDE_FROM_ABI void swap(multimap& __m) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) {
1961     __tree_.swap(__m.__tree_);
1962   }
1963
1964   _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }
1965   _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }
1966 #  if _LIBCPP_STD_VER >= 14
1967   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1968   _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
1969     return __tree_.find(__k);
1970   }
1971   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1972   _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
1973     return __tree_.find(__k);
1974   }
1975 #  endif
1976
1977   _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_multi(__k); }
1978 #  if _LIBCPP_STD_VER >= 14
1979   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1980   _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
1981     return __tree_.__count_multi(__k);
1982   }
1983 #  endif
1984
1985 #  if _LIBCPP_STD_VER >= 20
1986   _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
1987   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1988   _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
1989     return find(__k) != end();
1990   }
1991 #  endif // _LIBCPP_STD_VER >= 20
1992
1993   _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
1994   _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
1995 #  if _LIBCPP_STD_VER >= 14
1996   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1997   _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {
1998     return __tree_.lower_bound(__k);
1999   }
2000
2001   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
2002   _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const {
2003     return __tree_.lower_bound(__k);
2004   }
2005 #  endif
2006
2007   _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
2008   _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
2009 #  if _LIBCPP_STD_VER >= 14
2010   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
2011   _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {
2012     return __tree_.upper_bound(__k);
2013   }
2014   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
2015   _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const {
2016     return __tree_.upper_bound(__k);
2017   }
2018 #  endif
2019
2020   _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
2021     return __tree_.__equal_range_multi(__k);
2022   }
2023   _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
2024     return __tree_.__equal_range_multi(__k);
2025   }
2026 #  if _LIBCPP_STD_VER >= 14
2027   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
2028   _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
2029     return __tree_.__equal_range_multi(__k);
2030   }
2031   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
2032   _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
2033     return __tree_.__equal_range_multi(__k);
2034   }
2035 #  endif
2036
2037 private:
2038   typedef typename __base::__node __node;
2039   typedef typename __base::__node_allocator __node_allocator;
2040   typedef typename __base::__node_pointer __node_pointer;
2041
2042   typedef __map_node_destructor<__node_allocator> _Dp;
2043   typedef unique_ptr<__node, _Dp> __node_holder;
2044 };
2045
2046 #  if _LIBCPP_STD_VER >= 17
2047 template <class _InputIterator,
2048           class _Compare   = less<__iter_key_type<_InputIterator>>,
2049           class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
2050           class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
2051           class            = enable_if_t<!__is_allocator<_Compare>::value, void>,
2052           class            = enable_if_t<__is_allocator<_Allocator>::value, void>>
2053 multimap(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
2054     -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
2055
2056 #    if _LIBCPP_STD_VER >= 23
2057 template <ranges::input_range _Range,
2058           class _Compare   = less<__range_key_type<_Range>>,
2059           class _Allocator = allocator<__range_to_alloc_type<_Range>>,
2060           class            = enable_if_t<!__is_allocator<_Compare>::value, void>,
2061           class            = enable_if_t<__is_allocator<_Allocator>::value, void>>
2062 multimap(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
2063     -> multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, _Compare, _Allocator>;
2064 #    endif
2065
2066 template <class _Key,
2067           class _Tp,
2068           class _Compare   = less<remove_const_t<_Key>>,
2069           class _Allocator = allocator<pair<const _Key, _Tp>>,
2070           class            = enable_if_t<!__is_allocator<_Compare>::value, void>,
2071           class            = enable_if_t<__is_allocator<_Allocator>::value, void>>
2072 multimap(initializer_list<pair<_Key, _Tp>>,
2073          _Compare   = _Compare(),
2074          _Allocator = _Allocator()) -> multimap<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
2075
2076 template <class _InputIterator,
2077           class _Allocator,
2078           class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
2079           class = enable_if_t<__is_allocator<_Allocator>::value, void>>
2080 multimap(_InputIterator, _InputIterator, _Allocator)
2081     -> multimap<__iter_key_type<_InputIterator>,
2082                 __iter_mapped_type<_InputIterator>,
2083                 less<__iter_key_type<_InputIterator>>,
2084                 _Allocator>;
2085
2086 #    if _LIBCPP_STD_VER >= 23
2087 template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
2088 multimap(from_range_t, _Range&&, _Allocator)
2089     -> multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, less<__range_key_type<_Range>>, _Allocator>;
2090 #    endif
2091
2092 template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
2093 multimap(initializer_list<pair<_Key, _Tp>>,
2094          _Allocator) -> multimap<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;
2095 #  endif
2096
2097 #  ifndef _LIBCPP_CXX03_LANG
2098 template <class _Key, class _Tp, class _Compare, class _Allocator>
2099 multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
2100     : __tree_(std::move(__m.__tree_), typename __base::allocator_type(__a)) {
2101   if (__a != __m.get_allocator()) {
2102     const_iterator __e = cend();
2103     while (!__m.empty())
2104       __tree_.__insert_multi(__e.__i_, std::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__move()));
2105   }
2106 }
2107 #  endif
2108
2109 template <class _Key, class _Tp, class _Compare, class _Allocator>
2110 inline _LIBCPP_HIDE_FROM_ABI bool
2111 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2112   return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
2113 }
2114
2115 #  if _LIBCPP_STD_VER <= 17
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 std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2121 }
2122
2123 template <class _Key, class _Tp, class _Compare, class _Allocator>
2124 inline _LIBCPP_HIDE_FROM_ABI bool
2125 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2126   return !(__x == __y);
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 __y < __x;
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 !(__x < __y);
2139 }
2140
2141 template <class _Key, class _Tp, class _Compare, class _Allocator>
2142 inline _LIBCPP_HIDE_FROM_ABI bool
2143 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2144   return !(__y < __x);
2145 }
2146
2147 #  else // #if _LIBCPP_STD_VER <= 17
2148
2149 template <class _Key, class _Tp, class _Compare, class _Allocator>
2150 _LIBCPP_HIDE_FROM_ABI __synth_three_way_result<pair<const _Key, _Tp>>
2151 operator<=>(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2152             const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2153   return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), __synth_three_way);
2154 }
2155
2156 #  endif // #if _LIBCPP_STD_VER <= 17
2157
2158 template <class _Key, class _Tp, class _Compare, class _Allocator>
2159 inline _LIBCPP_HIDE_FROM_ABI void
2160 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x, multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2161     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
2162   __x.swap(__y);
2163 }
2164
2165 #  if _LIBCPP_STD_VER >= 20
2166 template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate>
2167 inline _LIBCPP_HIDE_FROM_ABI typename multimap<_Key, _Tp, _Compare, _Allocator>::size_type
2168 erase_if(multimap<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) {
2169   return std::__libcpp_erase_if_container(__c, __pred);
2170 }
2171 #  endif
2172
2173 template <class _Key, class _Tp, class _Compare, class _Allocator>
2174 struct __container_traits<multimap<_Key, _Tp, _Compare, _Allocator> > {
2175   // http://eel.is/c++draft/associative.reqmts.except#2
2176   // For associative containers, if an exception is thrown by any operation from within
2177   // an insert or emplace function inserting a single element, the insertion has no effect.
2178   static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee = true;
2179 };
2180
2181 _LIBCPP_END_NAMESPACE_STD
2182
2183 #  if _LIBCPP_STD_VER >= 17
2184 _LIBCPP_BEGIN_NAMESPACE_STD
2185 namespace pmr {
2186 template <class _KeyT, class _ValueT, class _CompareT = std::less<_KeyT>>
2187 using map _LIBCPP_AVAILABILITY_PMR =
2188     std::map<_KeyT, _ValueT, _CompareT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;
2189
2190 template <class _KeyT, class _ValueT, class _CompareT = std::less<_KeyT>>
2191 using multimap _LIBCPP_AVAILABILITY_PMR =
2192     std::multimap<_KeyT, _ValueT, _CompareT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;
2193 } // namespace pmr
2194 _LIBCPP_END_NAMESPACE_STD
2195 #  endif
2196
2197 _LIBCPP_POP_MACROS
2198
2199 #  if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
2200 #    include <concepts>
2201 #    include <cstdlib>
2202 #    include <functional>
2203 #    include <iterator>
2204 #    include <type_traits>
2205 #    include <utility>
2206 #  endif
2207 #endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
2208
2209 #endif // _LIBCPP_MAP