libcxx/include/map

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