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