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