libcxx/include/map

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