libcxx/include/__cxx03/set

   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_SET
  11 #define _LIBCPP_SET
  12
  13 /*
  14
  15     set synopsis
  16
  17 namespace std
  18 {
  19
  20 template <class Key, class Compare = less<Key>,
  21           class Allocator = allocator<Key>>
  22 class set
  23 {
  24 public:
  25     // types:
  26     typedef Key                                      key_type;
  27     typedef key_type                                 value_type;
  28     typedef Compare                                  key_compare;
  29     typedef key_compare                              value_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::size_type       size_type;
  34     typedef typename allocator_type::difference_type difference_type;
  35     typedef typename allocator_type::pointer         pointer;
  36     typedef typename allocator_type::const_pointer   const_pointer;
  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     // construct/copy/destroy:
  46     set()
  47         noexcept(
  48             is_nothrow_default_constructible<allocator_type>::value &&
  49             is_nothrow_default_constructible<key_compare>::value &&
  50             is_nothrow_copy_constructible<key_compare>::value);
  51     explicit set(const value_compare& comp);
  52     set(const value_compare& comp, const allocator_type& a);
  53     template <class InputIterator>
  54         set(InputIterator first, InputIterator last,
  55             const value_compare& comp = value_compare());
  56     template <class InputIterator>
  57         set(InputIterator first, InputIterator last, const value_compare& comp,
  58             const allocator_type& a);
  59     template<container-compatible-range<value_type> R>
  60       set(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23
  61     set(const set& s);
  62     set(set&& s)
  63         noexcept(
  64             is_nothrow_move_constructible<allocator_type>::value &&
  65             is_nothrow_move_constructible<key_compare>::value);
  66     explicit set(const allocator_type& a);
  67     set(const set& s, const allocator_type& a);
  68     set(set&& s, const allocator_type& a);
  69     set(initializer_list<value_type> il, const value_compare& comp = value_compare());
  70     set(initializer_list<value_type> il, const value_compare& comp,
  71         const allocator_type& a);
  72     template <class InputIterator>
  73         set(InputIterator first, InputIterator last, const allocator_type& a)
  74             : set(first, last, Compare(), a) {}  // C++14
  75     template<container-compatible-range<value_type> R>
  76       set(from_range_t, R&& rg, const Allocator& a))
  77         : set(from_range, std::forward<R>(rg), Compare(), a) { } // C++23
  78     set(initializer_list<value_type> il, const allocator_type& a)
  79         : set(il, Compare(), a) {}  // C++14
  80     ~set();
  81
  82     set& operator=(const set& s);
  83     set& operator=(set&& s)
  84         noexcept(
  85             allocator_type::propagate_on_container_move_assignment::value &&
  86             is_nothrow_move_assignable<allocator_type>::value &&
  87             is_nothrow_move_assignable<key_compare>::value);
  88     set& operator=(initializer_list<value_type> il);
  89
  90     // iterators:
  91           iterator begin() noexcept;
  92     const_iterator begin() const noexcept;
  93           iterator end() noexcept;
  94     const_iterator end()   const noexcept;
  95
  96           reverse_iterator rbegin() noexcept;
  97     const_reverse_iterator rbegin() const noexcept;
  98           reverse_iterator rend() noexcept;
  99     const_reverse_iterator rend()   const noexcept;
 100
 101     const_iterator         cbegin()  const noexcept;
 102     const_iterator         cend()    const noexcept;
 103     const_reverse_iterator crbegin() const noexcept;
 104     const_reverse_iterator crend()   const noexcept;
 105
 106     // capacity:
 107     bool      empty()    const noexcept;
 108     size_type size()     const noexcept;
 109     size_type max_size() const noexcept;
 110
 111     // modifiers:
 112     template <class... Args>
 113         pair<iterator, bool> emplace(Args&&... args);
 114     template <class... Args>
 115         iterator emplace_hint(const_iterator position, Args&&... args);
 116     pair<iterator,bool> insert(const value_type& v);
 117     pair<iterator,bool> insert(value_type&& v);
 118     iterator insert(const_iterator position, const value_type& v);
 119     iterator insert(const_iterator position, value_type&& v);
 120     template <class InputIterator>
 121         void insert(InputIterator first, InputIterator last);
 122     template<container-compatible-range<value_type> R>
 123       void insert_range(R&& rg);                                                      // C++23
 124     void insert(initializer_list<value_type> il);
 125
 126     node_type extract(const_iterator position);                                       // C++17
 127     node_type extract(const key_type& x);                                             // C++17
 128     insert_return_type insert(node_type&& nh);                                        // C++17
 129     iterator insert(const_iterator hint, node_type&& nh);                             // C++17
 130
 131     iterator  erase(const_iterator position);
 132     iterator  erase(iterator position);  // C++14
 133     size_type erase(const key_type& k);
 134     iterator  erase(const_iterator first, const_iterator last);
 135     void clear() noexcept;
 136
 137     template<class C2>
 138       void merge(set<Key, C2, Allocator>& source);         // C++17
 139     template<class C2>
 140       void merge(set<Key, C2, Allocator>&& source);        // C++17
 141     template<class C2>
 142       void merge(multiset<Key, C2, Allocator>& source);    // C++17
 143     template<class C2>
 144       void merge(multiset<Key, C2, Allocator>&& source);   // C++17
 145
 146     void swap(set& s)
 147         noexcept(
 148             __is_nothrow_swappable<key_compare>::value &&
 149             (!allocator_type::propagate_on_container_swap::value ||
 150              __is_nothrow_swappable<allocator_type>::value));
 151
 152     // observers:
 153     allocator_type get_allocator() const noexcept;
 154     key_compare    key_comp()      const;
 155     value_compare  value_comp()    const;
 156
 157     // set operations:
 158           iterator find(const key_type& k);
 159     const_iterator find(const key_type& k) const;
 160     template<typename K>
 161         iterator find(const K& x);
 162     template<typename K>
 163         const_iterator find(const K& x) const;  // C++14
 164
 165     template<typename K>
 166         size_type count(const K& x) const;        // C++14
 167     size_type      count(const key_type& k) const;
 168
 169     bool           contains(const key_type& x) const;  // C++20
 170     template<class K> bool contains(const K& x) const; // C++20
 171
 172           iterator lower_bound(const key_type& k);
 173     const_iterator lower_bound(const key_type& k) const;
 174     template<typename K>
 175         iterator lower_bound(const K& x);              // C++14
 176     template<typename K>
 177         const_iterator lower_bound(const K& x) const;  // C++14
 178
 179           iterator upper_bound(const key_type& k);
 180     const_iterator upper_bound(const key_type& k) const;
 181     template<typename K>
 182         iterator upper_bound(const K& x);              // C++14
 183     template<typename K>
 184         const_iterator upper_bound(const K& x) const;  // C++14
 185     pair<iterator,iterator>             equal_range(const key_type& k);
 186     pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
 187     template<typename K>
 188         pair<iterator,iterator>             equal_range(const K& x);        // C++14
 189     template<typename K>
 190         pair<const_iterator,const_iterator> equal_range(const K& x) const;  // C++14
 191 };
 192
 193 template <class InputIterator,
 194       class Compare = less<typename iterator_traits<InputIterator>::value_type>,
 195       class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
 196 set(InputIterator, InputIterator,
 197     Compare = Compare(), Allocator = Allocator())
 198   -> set<typename iterator_traits<InputIterator>::value_type, Compare, Allocator>; // C++17
 199
 200 template<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>,
 201          class Allocator = allocator<ranges::range_value_t<R>>>
 202   set(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
 203     -> set<ranges::range_value_t<R>, Compare, Allocator>; // C++23
 204
 205 template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
 206 set(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
 207   -> set<Key, Compare, Allocator>; // C++17
 208
 209 template<class InputIterator, class Allocator>
 210 set(InputIterator, InputIterator, Allocator)
 211   -> set<typename iterator_traits<InputIterator>::value_type,
 212           less<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17
 213
 214 template<ranges::input_range R, class Allocator>
 215   set(from_range_t, R&&, Allocator)
 216     -> set<ranges::range_value_t<R>, less<ranges::range_value_t<R>>, Allocator>; // C++23
 217
 218 template<class Key, class Allocator>
 219 set(initializer_list<Key>, Allocator) -> set<Key, less<Key>, Allocator>; // C++17
 220
 221 template <class Key, class Compare, class Allocator>
 222 bool
 223 operator==(const set<Key, Compare, Allocator>& x,
 224            const set<Key, Compare, Allocator>& y);
 225
 226 template <class Key, class Compare, class Allocator>
 227 bool
 228 operator< (const set<Key, Compare, Allocator>& x,
 229            const set<Key, Compare, Allocator>& y);                                // removed in C++20
 230
 231 template <class Key, class Compare, class Allocator>
 232 bool
 233 operator!=(const set<Key, Compare, Allocator>& x,
 234            const set<Key, Compare, Allocator>& y);                                // removed in C++20
 235
 236 template <class Key, class Compare, class Allocator>
 237 bool
 238 operator> (const set<Key, Compare, Allocator>& x,
 239            const set<Key, Compare, Allocator>& y);                                // removed in C++20
 240
 241 template <class Key, class Compare, class Allocator>
 242 bool
 243 operator>=(const set<Key, Compare, Allocator>& x,
 244            const set<Key, Compare, Allocator>& y);                                // removed in C++20
 245
 246 template <class Key, class Compare, class Allocator>
 247 bool
 248 operator<=(const set<Key, Compare, Allocator>& x,
 249            const set<Key, Compare, Allocator>& y);                                // removed in C++20
 250
 251 template<class Key, class Compare, class Allocator>
 252   synth-three-way-result<Key> operator<=>(const set<Key, Compare, Allocator>& x,
 253                                           const set<Key, Compare, Allocator>& y); // since C++20
 254
 255 // specialized algorithms:
 256 template <class Key, class Compare, class Allocator>
 257 void
 258 swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y)
 259     noexcept(noexcept(x.swap(y)));
 260
 261 template <class Key, class Compare, class Allocator, class Predicate>
 262 typename set<Key, Compare, Allocator>::size_type
 263 erase_if(set<Key, Compare, Allocator>& c, Predicate pred);  // C++20
 264
 265 template <class Key, class Compare = less<Key>,
 266           class Allocator = allocator<Key>>
 267 class multiset
 268 {
 269 public:
 270     // types:
 271     typedef Key                                      key_type;
 272     typedef key_type                                 value_type;
 273     typedef Compare                                  key_compare;
 274     typedef key_compare                              value_compare;
 275     typedef Allocator                                allocator_type;
 276     typedef typename allocator_type::reference       reference;
 277     typedef typename allocator_type::const_reference const_reference;
 278     typedef typename allocator_type::size_type       size_type;
 279     typedef typename allocator_type::difference_type difference_type;
 280     typedef typename allocator_type::pointer         pointer;
 281     typedef typename allocator_type::const_pointer   const_pointer;
 282
 283     typedef implementation-defined                   iterator;
 284     typedef implementation-defined                   const_iterator;
 285     typedef std::reverse_iterator<iterator>          reverse_iterator;
 286     typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
 287     typedef unspecified                              node_type;               // C++17
 288
 289     // construct/copy/destroy:
 290     multiset()
 291         noexcept(
 292             is_nothrow_default_constructible<allocator_type>::value &&
 293             is_nothrow_default_constructible<key_compare>::value &&
 294             is_nothrow_copy_constructible<key_compare>::value);
 295     explicit multiset(const value_compare& comp);
 296     multiset(const value_compare& comp, const allocator_type& a);
 297     template <class InputIterator>
 298         multiset(InputIterator first, InputIterator last,
 299                  const value_compare& comp = value_compare());
 300     template <class InputIterator>
 301         multiset(InputIterator first, InputIterator last,
 302                  const value_compare& comp, const allocator_type& a);
 303     template<container-compatible-range<value_type> R>
 304       multiset(from_range_t, R&& rg,
 305                const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23
 306     multiset(const multiset& s);
 307     multiset(multiset&& s)
 308         noexcept(
 309             is_nothrow_move_constructible<allocator_type>::value &&
 310             is_nothrow_move_constructible<key_compare>::value);
 311     explicit multiset(const allocator_type& a);
 312     multiset(const multiset& s, const allocator_type& a);
 313     multiset(multiset&& s, const allocator_type& a);
 314     multiset(initializer_list<value_type> il, const value_compare& comp = value_compare());
 315     multiset(initializer_list<value_type> il, const value_compare& comp,
 316              const allocator_type& a);
 317     template <class InputIterator>
 318         multiset(InputIterator first, InputIterator last, const allocator_type& a)
 319             : set(first, last, Compare(), a) {}  // C++14
 320     template<container-compatible-range<value_type> R>
 321       multiset(from_range_t, R&& rg, const Allocator& a))
 322         : multiset(from_range, std::forward<R>(rg), Compare(), a) { } // C++23
 323     multiset(initializer_list<value_type> il, const allocator_type& a)
 324         : set(il, Compare(), a) {}  // C++14
 325     ~multiset();
 326
 327     multiset& operator=(const multiset& s);
 328     multiset& operator=(multiset&& s)
 329         noexcept(
 330             allocator_type::propagate_on_container_move_assignment::value &&
 331             is_nothrow_move_assignable<allocator_type>::value &&
 332             is_nothrow_move_assignable<key_compare>::value);
 333     multiset& operator=(initializer_list<value_type> il);
 334
 335     // iterators:
 336           iterator begin() noexcept;
 337     const_iterator begin() const noexcept;
 338           iterator end() noexcept;
 339     const_iterator end()   const noexcept;
 340
 341           reverse_iterator rbegin() noexcept;
 342     const_reverse_iterator rbegin() const noexcept;
 343           reverse_iterator rend() noexcept;
 344     const_reverse_iterator rend()   const noexcept;
 345
 346     const_iterator         cbegin()  const noexcept;
 347     const_iterator         cend()    const noexcept;
 348     const_reverse_iterator crbegin() const noexcept;
 349     const_reverse_iterator crend()   const noexcept;
 350
 351     // capacity:
 352     bool      empty()    const noexcept;
 353     size_type size()     const noexcept;
 354     size_type max_size() const noexcept;
 355
 356     // modifiers:
 357     template <class... Args>
 358         iterator emplace(Args&&... args);
 359     template <class... Args>
 360         iterator emplace_hint(const_iterator position, Args&&... args);
 361     iterator insert(const value_type& v);
 362     iterator insert(value_type&& v);
 363     iterator insert(const_iterator position, const value_type& v);
 364     iterator insert(const_iterator position, value_type&& v);
 365     template <class InputIterator>
 366         void insert(InputIterator first, InputIterator last);
 367     template<container-compatible-range<value_type> R>
 368       void insert_range(R&& rg);                                                      // C++23
 369     void insert(initializer_list<value_type> il);
 370
 371     node_type extract(const_iterator position);                                       // C++17
 372     node_type extract(const key_type& x);                                             // C++17
 373     iterator insert(node_type&& nh);                                                  // C++17
 374     iterator insert(const_iterator hint, node_type&& nh);                             // C++17
 375
 376     iterator  erase(const_iterator position);
 377     iterator  erase(iterator position);  // C++14
 378     size_type erase(const key_type& k);
 379     iterator  erase(const_iterator first, const_iterator last);
 380     void clear() noexcept;
 381
 382     template<class C2>
 383       void merge(multiset<Key, C2, Allocator>& source);    // C++17
 384     template<class C2>
 385       void merge(multiset<Key, C2, Allocator>&& source);   // C++17
 386     template<class C2>
 387       void merge(set<Key, C2, Allocator>& source);         // C++17
 388     template<class C2>
 389       void merge(set<Key, C2, Allocator>&& source);        // C++17
 390
 391     void swap(multiset& s)
 392         noexcept(
 393             __is_nothrow_swappable<key_compare>::value &&
 394             (!allocator_type::propagate_on_container_swap::value ||
 395              __is_nothrow_swappable<allocator_type>::value));
 396
 397     // observers:
 398     allocator_type get_allocator() const noexcept;
 399     key_compare    key_comp()      const;
 400     value_compare  value_comp()    const;
 401
 402     // set operations:
 403           iterator find(const key_type& k);
 404     const_iterator find(const key_type& k) const;
 405     template<typename K>
 406         iterator find(const K& x);
 407     template<typename K>
 408         const_iterator find(const K& x) const;  // C++14
 409
 410     template<typename K>
 411         size_type count(const K& x) const;      // C++14
 412     size_type      count(const key_type& k) const;
 413
 414     bool           contains(const key_type& x) const;  // C++20
 415     template<class K> bool contains(const K& x) const; // C++20
 416
 417           iterator lower_bound(const key_type& k);
 418     const_iterator lower_bound(const key_type& k) const;
 419     template<typename K>
 420         iterator lower_bound(const K& x);              // C++14
 421     template<typename K>
 422         const_iterator lower_bound(const K& x) const;  // C++14
 423
 424           iterator upper_bound(const key_type& k);
 425     const_iterator upper_bound(const key_type& k) const;
 426     template<typename K>
 427         iterator upper_bound(const K& x);              // C++14
 428     template<typename K>
 429         const_iterator upper_bound(const K& x) const;  // C++14
 430
 431     pair<iterator,iterator>             equal_range(const key_type& k);
 432     pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
 433     template<typename K>
 434         pair<iterator,iterator>             equal_range(const K& x);        // C++14
 435     template<typename K>
 436         pair<const_iterator,const_iterator> equal_range(const K& x) const;  // C++14
 437 };
 438
 439 template <class InputIterator,
 440       class Compare = less<typename iterator_traits<InputIterator>::value_type>,
 441       class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
 442 multiset(InputIterator, InputIterator,
 443     Compare = Compare(), Allocator = Allocator())
 444   -> multiset<typename iterator_traits<InputIterator>::value_type, Compare, Allocator>; // C++17
 445
 446 template<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>,
 447           class Allocator = allocator<ranges::range_value_t<R>>>
 448   multiset(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
 449     -> multiset<ranges::range_value_t<R>, Compare, Allocator>;
 450
 451 template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
 452 multiset(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
 453   -> multiset<Key, Compare, Allocator>; // C++17
 454
 455 template<class InputIterator, class Allocator>
 456 multiset(InputIterator, InputIterator, Allocator)
 457   -> multiset<typename iterator_traits<InputIterator>::value_type,
 458           less<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17
 459
 460 template<ranges::input_range R, class Allocator>
 461   multiset(from_range_t, R&&, Allocator)
 462     -> multiset<ranges::range_value_t<R>, less<ranges::range_value_t<R>>, Allocator>;
 463
 464 template<class Key, class Allocator>
 465 multiset(initializer_list<Key>, Allocator) -> multiset<Key, less<Key>, Allocator>; // C++17
 466
 467 template <class Key, class Compare, class Allocator>
 468 bool
 469 operator==(const multiset<Key, Compare, Allocator>& x,
 470            const multiset<Key, Compare, Allocator>& y);
 471
 472 template <class Key, class Compare, class Allocator>
 473 bool
 474 operator< (const multiset<Key, Compare, Allocator>& x,
 475            const multiset<Key, Compare, Allocator>& y);                                // removed in C++20
 476
 477 template <class Key, class Compare, class Allocator>
 478 bool
 479 operator!=(const multiset<Key, Compare, Allocator>& x,
 480            const multiset<Key, Compare, Allocator>& y);                                // removed in C++20
 481
 482 template <class Key, class Compare, class Allocator>
 483 bool
 484 operator> (const multiset<Key, Compare, Allocator>& x,
 485            const multiset<Key, Compare, Allocator>& y);                                // removed in C++20
 486
 487 template <class Key, class Compare, class Allocator>
 488 bool
 489 operator>=(const multiset<Key, Compare, Allocator>& x,
 490            const multiset<Key, Compare, Allocator>& y);                                // removed in C++20
 491
 492 template <class Key, class Compare, class Allocator>
 493 bool
 494 operator<=(const multiset<Key, Compare, Allocator>& x,
 495            const multiset<Key, Compare, Allocator>& y);                                // removed in C++20
 496
 497 template<class Key, class Compare, class Allocator>
 498   synth-three-way-result<Key> operator<=>(const multiset<Key, Compare, Allocator>& x,
 499                                           const multiset<Key, Compare, Allocator>& y); // since C++20
 500
 501 // specialized algorithms:
 502 template <class Key, class Compare, class Allocator>
 503 void
 504 swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y)
 505     noexcept(noexcept(x.swap(y)));
 506
 507 template <class Key, class Compare, class Allocator, class Predicate>
 508 typename multiset<Key, Compare, Allocator>::size_type
 509 erase_if(multiset<Key, Compare, Allocator>& c, Predicate pred);  // C++20
 510
 511 }  // std
 512
 513 */
 514
 515 #include <__cxx03/__algorithm/equal.h>
 516 #include <__cxx03/__algorithm/lexicographical_compare.h>
 517 #include <__cxx03/__algorithm/lexicographical_compare_three_way.h>
 518 #include <__cxx03/__assert>
 519 #include <__cxx03/__config>
 520 #include <__cxx03/__functional/is_transparent.h>
 521 #include <__cxx03/__functional/operations.h>
 522 #include <__cxx03/__iterator/erase_if_container.h>
 523 #include <__cxx03/__iterator/iterator_traits.h>
 524 #include <__cxx03/__iterator/ranges_iterator_traits.h>
 525 #include <__cxx03/__iterator/reverse_iterator.h>
 526 #include <__cxx03/__memory/allocator.h>
 527 #include <__cxx03/__memory_resource/polymorphic_allocator.h>
 528 #include <__cxx03/__node_handle>
 529 #include <__cxx03/__ranges/concepts.h>
 530 #include <__cxx03/__ranges/container_compatible_range.h>
 531 #include <__cxx03/__ranges/from_range.h>
 532 #include <__cxx03/__tree>
 533 #include <__cxx03/__type_traits/is_allocator.h>
 534 #include <__cxx03/__utility/forward.h>
 535 #include <__cxx03/version>
 536
 537 // standard-mandated includes
 538
 539 // [iterator.range]
 540 #include <__cxx03/__iterator/access.h>
 541 #include <__cxx03/__iterator/data.h>
 542 #include <__cxx03/__iterator/empty.h>
 543 #include <__cxx03/__iterator/reverse_access.h>
 544 #include <__cxx03/__iterator/size.h>
 545
 546 // [associative.set.syn]
 547 #include <__cxx03/compare>
 548 #include <__cxx03/initializer_list>
 549
 550 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 551 #  pragma GCC system_header
 552 #endif
 553
 554 _LIBCPP_PUSH_MACROS
 555 #include <__cxx03/__undef_macros>
 556
 557 _LIBCPP_BEGIN_NAMESPACE_STD
 558
 559 template <class _Key, class _Compare, class _Allocator>
 560 class multiset;
 561
 562 template <class _Key, class _Compare = less<_Key>, class _Allocator = allocator<_Key> >
 563 class _LIBCPP_TEMPLATE_VIS set {
 564 public:
 565   // types:
 566   typedef _Key key_type;
 567   typedef key_type value_type;
 568   typedef __type_identity_t<_Compare> key_compare;
 569   typedef key_compare value_compare;
 570   typedef __type_identity_t<_Allocator> allocator_type;
 571   typedef value_type& reference;
 572   typedef const value_type& const_reference;
 573
 574   static_assert(is_same<typename allocator_type::value_type, value_type>::value,
 575                 "Allocator::value_type must be same type as value_type");
 576
 577 private:
 578   typedef __tree<value_type, value_compare, allocator_type> __base;
 579   typedef allocator_traits<allocator_type> __alloc_traits;
 580
 581   static_assert(__check_valid_allocator<allocator_type>::value, "");
 582
 583   __base __tree_;
 584
 585 public:
 586   typedef typename __base::pointer pointer;
 587   typedef typename __base::const_pointer const_pointer;
 588   typedef typename __base::size_type size_type;
 589   typedef typename __base::difference_type difference_type;
 590   typedef typename __base::const_iterator iterator;
 591   typedef typename __base::const_iterator const_iterator;
 592   typedef std::reverse_iterator<iterator> reverse_iterator;
 593   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 594
 595 #if _LIBCPP_STD_VER >= 17
 596   typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
 597   typedef __insert_return_type<iterator, node_type> insert_return_type;
 598 #endif
 599
 600   template <class _Key2, class _Compare2, class _Alloc2>
 601   friend class _LIBCPP_TEMPLATE_VIS set;
 602   template <class _Key2, class _Compare2, class _Alloc2>
 603   friend class _LIBCPP_TEMPLATE_VIS multiset;
 604
 605   _LIBCPP_HIDE_FROM_ABI set() _NOEXCEPT_(
 606       is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&&
 607           is_nothrow_copy_constructible<key_compare>::value)
 608       : __tree_(value_compare()) {}
 609
 610   _LIBCPP_HIDE_FROM_ABI explicit set(const value_compare& __comp) _NOEXCEPT_(
 611       is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value)
 612       : __tree_(__comp) {}
 613
 614   _LIBCPP_HIDE_FROM_ABI explicit set(const value_compare& __comp, const allocator_type& __a) : __tree_(__comp, __a) {}
 615   template <class _InputIterator>
 616   _LIBCPP_HIDE_FROM_ABI set(_InputIterator __f, _InputIterator __l, const value_compare& __comp = value_compare())
 617       : __tree_(__comp) {
 618     insert(__f, __l);
 619   }
 620
 621   template <class _InputIterator>
 622   _LIBCPP_HIDE_FROM_ABI
 623   set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, const allocator_type& __a)
 624       : __tree_(__comp, __a) {
 625     insert(__f, __l);
 626   }
 627
 628 #if _LIBCPP_STD_VER >= 23
 629   template <_ContainerCompatibleRange<value_type> _Range>
 630   _LIBCPP_HIDE_FROM_ABI
 631   set(from_range_t,
 632       _Range&& __range,
 633       const key_compare& __comp = key_compare(),
 634       const allocator_type& __a = allocator_type())
 635       : __tree_(__comp, __a) {
 636     insert_range(std::forward<_Range>(__range));
 637   }
 638 #endif
 639
 640 #if _LIBCPP_STD_VER >= 14
 641   template <class _InputIterator>
 642   _LIBCPP_HIDE_FROM_ABI set(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
 643       : set(__f, __l, key_compare(), __a) {}
 644 #endif
 645
 646 #if _LIBCPP_STD_VER >= 23
 647   template <_ContainerCompatibleRange<value_type> _Range>
 648   _LIBCPP_HIDE_FROM_ABI set(from_range_t, _Range&& __range, const allocator_type& __a)
 649       : set(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
 650 #endif
 651
 652   _LIBCPP_HIDE_FROM_ABI set(const set& __s) : __tree_(__s.__tree_) { insert(__s.begin(), __s.end()); }
 653
 654   _LIBCPP_HIDE_FROM_ABI set& operator=(const set& __s) {
 655     __tree_ = __s.__tree_;
 656     return *this;
 657   }
 658
 659 #ifndef _LIBCPP_CXX03_LANG
 660   _LIBCPP_HIDE_FROM_ABI set(set&& __s) noexcept(is_nothrow_move_constructible<__base>::value)
 661       : __tree_(std::move(__s.__tree_)) {}
 662 #endif // _LIBCPP_CXX03_LANG
 663
 664   _LIBCPP_HIDE_FROM_ABI explicit set(const allocator_type& __a) : __tree_(__a) {}
 665
 666   _LIBCPP_HIDE_FROM_ABI set(const set& __s, const allocator_type& __a) : __tree_(__s.__tree_.value_comp(), __a) {
 667     insert(__s.begin(), __s.end());
 668   }
 669
 670 #ifndef _LIBCPP_CXX03_LANG
 671   _LIBCPP_HIDE_FROM_ABI set(set&& __s, const allocator_type& __a);
 672
 673   _LIBCPP_HIDE_FROM_ABI set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
 674       : __tree_(__comp) {
 675     insert(__il.begin(), __il.end());
 676   }
 677
 678   _LIBCPP_HIDE_FROM_ABI set(initializer_list<value_type> __il, const value_compare& __comp, const allocator_type& __a)
 679       : __tree_(__comp, __a) {
 680     insert(__il.begin(), __il.end());
 681   }
 682
 683 #  if _LIBCPP_STD_VER >= 14
 684   _LIBCPP_HIDE_FROM_ABI set(initializer_list<value_type> __il, const allocator_type& __a)
 685       : set(__il, key_compare(), __a) {}
 686 #  endif
 687
 688   _LIBCPP_HIDE_FROM_ABI set& operator=(initializer_list<value_type> __il) {
 689     __tree_.__assign_unique(__il.begin(), __il.end());
 690     return *this;
 691   }
 692
 693   _LIBCPP_HIDE_FROM_ABI set& operator=(set&& __s) noexcept(is_nothrow_move_assignable<__base>::value) {
 694     __tree_ = std::move(__s.__tree_);
 695     return *this;
 696   }
 697 #endif // _LIBCPP_CXX03_LANG
 698
 699   _LIBCPP_HIDE_FROM_ABI ~set() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); }
 700
 701   _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }
 702   _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }
 703   _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }
 704   _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }
 705
 706   _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
 707   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
 708   _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
 709   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
 710
 711   _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
 712   _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
 713   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }
 714   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
 715
 716   _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }
 717   _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }
 718   _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }
 719
 720   // modifiers:
 721 #ifndef _LIBCPP_CXX03_LANG
 722   template <class... _Args>
 723   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {
 724     return __tree_.__emplace_unique(std::forward<_Args>(__args)...);
 725   }
 726   template <class... _Args>
 727   _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
 728     return __tree_.__emplace_hint_unique(__p, std::forward<_Args>(__args)...);
 729   }
 730 #endif // _LIBCPP_CXX03_LANG
 731
 732   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__insert_unique(__v); }
 733   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
 734     return __tree_.__insert_unique(__p, __v);
 735   }
 736
 737   template <class _InputIterator>
 738   _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
 739     for (const_iterator __e = cend(); __f != __l; ++__f)
 740       __tree_.__insert_unique(__e, *__f);
 741   }
 742
 743 #if _LIBCPP_STD_VER >= 23
 744   template <_ContainerCompatibleRange<value_type> _Range>
 745   _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
 746     const_iterator __end = cend();
 747     for (auto&& __element : __range) {
 748       __tree_.__insert_unique(__end, std::forward<decltype(__element)>(__element));
 749     }
 750   }
 751 #endif
 752
 753 #ifndef _LIBCPP_CXX03_LANG
 754   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __v) {
 755     return __tree_.__insert_unique(std::move(__v));
 756   }
 757
 758   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {
 759     return __tree_.__insert_unique(__p, std::move(__v));
 760   }
 761
 762   _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
 763 #endif // _LIBCPP_CXX03_LANG
 764
 765   _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p); }
 766   _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_unique(__k); }
 767   _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) { return __tree_.erase(__f, __l); }
 768   _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }
 769
 770 #if _LIBCPP_STD_VER >= 17
 771   _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) {
 772     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
 773                                         "node_type with incompatible allocator passed to set::insert()");
 774     return __tree_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));
 775   }
 776   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
 777     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
 778                                         "node_type with incompatible allocator passed to set::insert()");
 779     return __tree_.template __node_handle_insert_unique<node_type>(__hint, std::move(__nh));
 780   }
 781   _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
 782     return __tree_.template __node_handle_extract<node_type>(__key);
 783   }
 784   _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
 785     return __tree_.template __node_handle_extract<node_type>(__it);
 786   }
 787   template <class _Compare2>
 788   _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>& __source) {
 789     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
 790         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
 791     __tree_.__node_handle_merge_unique(__source.__tree_);
 792   }
 793   template <class _Compare2>
 794   _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>&& __source) {
 795     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
 796         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
 797     __tree_.__node_handle_merge_unique(__source.__tree_);
 798   }
 799   template <class _Compare2>
 800   _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>& __source) {
 801     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
 802         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
 803     __tree_.__node_handle_merge_unique(__source.__tree_);
 804   }
 805   template <class _Compare2>
 806   _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>&& __source) {
 807     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
 808         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
 809     __tree_.__node_handle_merge_unique(__source.__tree_);
 810   }
 811 #endif
 812
 813   _LIBCPP_HIDE_FROM_ABI void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) { __tree_.swap(__s.__tree_); }
 814
 815   _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return __tree_.__alloc(); }
 816   _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp(); }
 817   _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return __tree_.value_comp(); }
 818
 819   // set operations:
 820   _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }
 821   _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }
 822 #if _LIBCPP_STD_VER >= 14
 823   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
 824   _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
 825     return __tree_.find(__k);
 826   }
 827   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
 828   _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
 829     return __tree_.find(__k);
 830   }
 831 #endif
 832
 833   _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_unique(__k); }
 834 #if _LIBCPP_STD_VER >= 14
 835   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
 836   _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
 837     return __tree_.__count_multi(__k);
 838   }
 839 #endif
 840
 841 #if _LIBCPP_STD_VER >= 20
 842   _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
 843   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
 844   _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
 845     return find(__k) != end();
 846   }
 847 #endif // _LIBCPP_STD_VER >= 20
 848
 849   _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
 850   _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
 851 #if _LIBCPP_STD_VER >= 14
 852   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
 853   _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {
 854     return __tree_.lower_bound(__k);
 855   }
 856
 857   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
 858   _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const {
 859     return __tree_.lower_bound(__k);
 860   }
 861 #endif
 862
 863   _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
 864   _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
 865 #if _LIBCPP_STD_VER >= 14
 866   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
 867   _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {
 868     return __tree_.upper_bound(__k);
 869   }
 870   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
 871   _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const {
 872     return __tree_.upper_bound(__k);
 873   }
 874 #endif
 875
 876   _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
 877     return __tree_.__equal_range_unique(__k);
 878   }
 879   _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
 880     return __tree_.__equal_range_unique(__k);
 881   }
 882 #if _LIBCPP_STD_VER >= 14
 883   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
 884   _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
 885     return __tree_.__equal_range_multi(__k);
 886   }
 887   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
 888   _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
 889     return __tree_.__equal_range_multi(__k);
 890   }
 891 #endif
 892 };
 893
 894 #if _LIBCPP_STD_VER >= 17
 895 template <class _InputIterator,
 896           class _Compare   = less<__iter_value_type<_InputIterator>>,
 897           class _Allocator = allocator<__iter_value_type<_InputIterator>>,
 898           class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
 899           class            = enable_if_t<__is_allocator<_Allocator>::value, void>,
 900           class            = enable_if_t<!__is_allocator<_Compare>::value, void>>
 901 set(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
 902     -> set<__iter_value_type<_InputIterator>, _Compare, _Allocator>;
 903
 904 #  if _LIBCPP_STD_VER >= 23
 905 template <ranges::input_range _Range,
 906           class _Compare   = less<ranges::range_value_t<_Range>>,
 907           class _Allocator = allocator<ranges::range_value_t<_Range>>,
 908           class            = enable_if_t<__is_allocator<_Allocator>::value, void>,
 909           class            = enable_if_t<!__is_allocator<_Compare>::value, void>>
 910 set(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
 911     -> set<ranges::range_value_t<_Range>, _Compare, _Allocator>;
 912 #  endif
 913
 914 template <class _Key,
 915           class _Compare   = less<_Key>,
 916           class _Allocator = allocator<_Key>,
 917           class            = enable_if_t<!__is_allocator<_Compare>::value, void>,
 918           class            = enable_if_t<__is_allocator<_Allocator>::value, void>>
 919 set(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator()) -> set<_Key, _Compare, _Allocator>;
 920
 921 template <class _InputIterator,
 922           class _Allocator,
 923           class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
 924           class = enable_if_t<__is_allocator<_Allocator>::value, void>>
 925 set(_InputIterator,
 926     _InputIterator,
 927     _Allocator) -> set<__iter_value_type<_InputIterator>, less<__iter_value_type<_InputIterator>>, _Allocator>;
 928
 929 #  if _LIBCPP_STD_VER >= 23
 930 template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
 931 set(from_range_t,
 932     _Range&&,
 933     _Allocator) -> set<ranges::range_value_t<_Range>, less<ranges::range_value_t<_Range>>, _Allocator>;
 934 #  endif
 935
 936 template <class _Key, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
 937 set(initializer_list<_Key>, _Allocator) -> set<_Key, less<_Key>, _Allocator>;
 938 #endif
 939
 940 #ifndef _LIBCPP_CXX03_LANG
 941
 942 template <class _Key, class _Compare, class _Allocator>
 943 set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a) : __tree_(std::move(__s.__tree_), __a) {
 944   if (__a != __s.get_allocator()) {
 945     const_iterator __e = cend();
 946     while (!__s.empty())
 947       insert(__e, std::move(__s.__tree_.remove(__s.begin())->__value_));
 948   }
 949 }
 950
 951 #endif // _LIBCPP_CXX03_LANG
 952
 953 template <class _Key, class _Compare, class _Allocator>
 954 inline _LIBCPP_HIDE_FROM_ABI bool
 955 operator==(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
 956   return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
 957 }
 958
 959 #if _LIBCPP_STD_VER <= 17
 960
 961 template <class _Key, class _Compare, class _Allocator>
 962 inline _LIBCPP_HIDE_FROM_ABI bool
 963 operator<(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
 964   return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
 965 }
 966
 967 template <class _Key, class _Compare, class _Allocator>
 968 inline _LIBCPP_HIDE_FROM_ABI bool
 969 operator!=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
 970   return !(__x == __y);
 971 }
 972
 973 template <class _Key, class _Compare, class _Allocator>
 974 inline _LIBCPP_HIDE_FROM_ABI bool
 975 operator>(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
 976   return __y < __x;
 977 }
 978
 979 template <class _Key, class _Compare, class _Allocator>
 980 inline _LIBCPP_HIDE_FROM_ABI bool
 981 operator>=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
 982   return !(__x < __y);
 983 }
 984
 985 template <class _Key, class _Compare, class _Allocator>
 986 inline _LIBCPP_HIDE_FROM_ABI bool
 987 operator<=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
 988   return !(__y < __x);
 989 }
 990
 991 #else // _LIBCPP_STD_VER <= 17
 992
 993 template <class _Key, class _Allocator>
 994 _LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Key>
 995 operator<=>(const set<_Key, _Allocator>& __x, const set<_Key, _Allocator>& __y) {
 996   return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
 997 }
 998
 999 #endif // _LIBCPP_STD_VER <= 17
1000
1001 // specialized algorithms:
1002 template <class _Key, class _Compare, class _Allocator>
1003 inline _LIBCPP_HIDE_FROM_ABI void swap(set<_Key, _Compare, _Allocator>& __x, set<_Key, _Compare, _Allocator>& __y)
1004     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1005   __x.swap(__y);
1006 }
1007
1008 #if _LIBCPP_STD_VER >= 20
1009 template <class _Key, class _Compare, class _Allocator, class _Predicate>
1010 inline _LIBCPP_HIDE_FROM_ABI typename set<_Key, _Compare, _Allocator>::size_type
1011 erase_if(set<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {
1012   return std::__libcpp_erase_if_container(__c, __pred);
1013 }
1014 #endif
1015
1016 template <class _Key, class _Compare = less<_Key>, class _Allocator = allocator<_Key> >
1017 class _LIBCPP_TEMPLATE_VIS multiset {
1018 public:
1019   // types:
1020   typedef _Key key_type;
1021   typedef key_type value_type;
1022   typedef __type_identity_t<_Compare> key_compare;
1023   typedef key_compare value_compare;
1024   typedef __type_identity_t<_Allocator> allocator_type;
1025   typedef value_type& reference;
1026   typedef const value_type& const_reference;
1027
1028   static_assert(is_same<typename allocator_type::value_type, value_type>::value,
1029                 "Allocator::value_type must be same type as value_type");
1030
1031 private:
1032   typedef __tree<value_type, value_compare, allocator_type> __base;
1033   typedef allocator_traits<allocator_type> __alloc_traits;
1034
1035   static_assert(__check_valid_allocator<allocator_type>::value, "");
1036
1037   __base __tree_;
1038
1039 public:
1040   typedef typename __base::pointer pointer;
1041   typedef typename __base::const_pointer const_pointer;
1042   typedef typename __base::size_type size_type;
1043   typedef typename __base::difference_type difference_type;
1044   typedef typename __base::const_iterator iterator;
1045   typedef typename __base::const_iterator const_iterator;
1046   typedef std::reverse_iterator<iterator> reverse_iterator;
1047   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1048
1049 #if _LIBCPP_STD_VER >= 17
1050   typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
1051 #endif
1052
1053   template <class _Key2, class _Compare2, class _Alloc2>
1054   friend class _LIBCPP_TEMPLATE_VIS set;
1055   template <class _Key2, class _Compare2, class _Alloc2>
1056   friend class _LIBCPP_TEMPLATE_VIS multiset;
1057
1058   // construct/copy/destroy:
1059   _LIBCPP_HIDE_FROM_ABI multiset() _NOEXCEPT_(
1060       is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&&
1061           is_nothrow_copy_constructible<key_compare>::value)
1062       : __tree_(value_compare()) {}
1063
1064   _LIBCPP_HIDE_FROM_ABI explicit multiset(const value_compare& __comp) _NOEXCEPT_(
1065       is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value)
1066       : __tree_(__comp) {}
1067
1068   _LIBCPP_HIDE_FROM_ABI explicit multiset(const value_compare& __comp, const allocator_type& __a)
1069       : __tree_(__comp, __a) {}
1070   template <class _InputIterator>
1071   _LIBCPP_HIDE_FROM_ABI multiset(_InputIterator __f, _InputIterator __l, const value_compare& __comp = value_compare())
1072       : __tree_(__comp) {
1073     insert(__f, __l);
1074   }
1075
1076 #if _LIBCPP_STD_VER >= 14
1077   template <class _InputIterator>
1078   _LIBCPP_HIDE_FROM_ABI multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1079       : multiset(__f, __l, key_compare(), __a) {}
1080 #endif
1081
1082   template <class _InputIterator>
1083   _LIBCPP_HIDE_FROM_ABI
1084   multiset(_InputIterator __f, _InputIterator __l, const value_compare& __comp, const allocator_type& __a)
1085       : __tree_(__comp, __a) {
1086     insert(__f, __l);
1087   }
1088
1089 #if _LIBCPP_STD_VER >= 23
1090   template <_ContainerCompatibleRange<value_type> _Range>
1091   _LIBCPP_HIDE_FROM_ABI
1092   multiset(from_range_t,
1093            _Range&& __range,
1094            const key_compare& __comp = key_compare(),
1095            const allocator_type& __a = allocator_type())
1096       : __tree_(__comp, __a) {
1097     insert_range(std::forward<_Range>(__range));
1098   }
1099
1100   template <_ContainerCompatibleRange<value_type> _Range>
1101   _LIBCPP_HIDE_FROM_ABI multiset(from_range_t, _Range&& __range, const allocator_type& __a)
1102       : multiset(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
1103 #endif
1104
1105   _LIBCPP_HIDE_FROM_ABI multiset(const multiset& __s)
1106       : __tree_(__s.__tree_.value_comp(),
1107                 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) {
1108     insert(__s.begin(), __s.end());
1109   }
1110
1111   _LIBCPP_HIDE_FROM_ABI multiset& operator=(const multiset& __s) {
1112     __tree_ = __s.__tree_;
1113     return *this;
1114   }
1115
1116 #ifndef _LIBCPP_CXX03_LANG
1117   _LIBCPP_HIDE_FROM_ABI multiset(multiset&& __s) noexcept(is_nothrow_move_constructible<__base>::value)
1118       : __tree_(std::move(__s.__tree_)) {}
1119
1120   _LIBCPP_HIDE_FROM_ABI multiset(multiset&& __s, const allocator_type& __a);
1121 #endif // _LIBCPP_CXX03_LANG
1122   _LIBCPP_HIDE_FROM_ABI explicit multiset(const allocator_type& __a) : __tree_(__a) {}
1123   _LIBCPP_HIDE_FROM_ABI multiset(const multiset& __s, const allocator_type& __a)
1124       : __tree_(__s.__tree_.value_comp(), __a) {
1125     insert(__s.begin(), __s.end());
1126   }
1127
1128 #ifndef _LIBCPP_CXX03_LANG
1129   _LIBCPP_HIDE_FROM_ABI multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
1130       : __tree_(__comp) {
1131     insert(__il.begin(), __il.end());
1132   }
1133
1134   _LIBCPP_HIDE_FROM_ABI
1135   multiset(initializer_list<value_type> __il, const value_compare& __comp, const allocator_type& __a)
1136       : __tree_(__comp, __a) {
1137     insert(__il.begin(), __il.end());
1138   }
1139
1140 #  if _LIBCPP_STD_VER >= 14
1141   _LIBCPP_HIDE_FROM_ABI multiset(initializer_list<value_type> __il, const allocator_type& __a)
1142       : multiset(__il, key_compare(), __a) {}
1143 #  endif
1144
1145   _LIBCPP_HIDE_FROM_ABI multiset& operator=(initializer_list<value_type> __il) {
1146     __tree_.__assign_multi(__il.begin(), __il.end());
1147     return *this;
1148   }
1149
1150   _LIBCPP_HIDE_FROM_ABI multiset& operator=(multiset&& __s) _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) {
1151     __tree_ = std::move(__s.__tree_);
1152     return *this;
1153   }
1154 #endif // _LIBCPP_CXX03_LANG
1155
1156   _LIBCPP_HIDE_FROM_ABI ~multiset() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); }
1157
1158   _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }
1159   _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }
1160   _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }
1161   _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }
1162
1163   _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
1164   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
1165   _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
1166   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
1167
1168   _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
1169   _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
1170   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }
1171   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
1172
1173   _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }
1174   _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }
1175   _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }
1176
1177   // modifiers:
1178 #ifndef _LIBCPP_CXX03_LANG
1179   template <class... _Args>
1180   _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) {
1181     return __tree_.__emplace_multi(std::forward<_Args>(__args)...);
1182   }
1183   template <class... _Args>
1184   _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1185     return __tree_.__emplace_hint_multi(__p, std::forward<_Args>(__args)...);
1186   }
1187 #endif // _LIBCPP_CXX03_LANG
1188
1189   _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __v) { return __tree_.__insert_multi(__v); }
1190   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
1191     return __tree_.__insert_multi(__p, __v);
1192   }
1193
1194   template <class _InputIterator>
1195   _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
1196     for (const_iterator __e = cend(); __f != __l; ++__f)
1197       __tree_.__insert_multi(__e, *__f);
1198   }
1199
1200 #if _LIBCPP_STD_VER >= 23
1201   template <_ContainerCompatibleRange<value_type> _Range>
1202   _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
1203     const_iterator __end = cend();
1204     for (auto&& __element : __range) {
1205       __tree_.__insert_multi(__end, std::forward<decltype(__element)>(__element));
1206     }
1207   }
1208 #endif
1209
1210 #ifndef _LIBCPP_CXX03_LANG
1211   _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __v) { return __tree_.__insert_multi(std::move(__v)); }
1212
1213   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {
1214     return __tree_.__insert_multi(__p, std::move(__v));
1215   }
1216
1217   _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
1218 #endif // _LIBCPP_CXX03_LANG
1219
1220   _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p); }
1221   _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_multi(__k); }
1222   _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) { return __tree_.erase(__f, __l); }
1223   _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }
1224
1225 #if _LIBCPP_STD_VER >= 17
1226   _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) {
1227     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1228                                         "node_type with incompatible allocator passed to multiset::insert()");
1229     return __tree_.template __node_handle_insert_multi<node_type>(std::move(__nh));
1230   }
1231   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
1232     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1233                                         "node_type with incompatible allocator passed to multiset::insert()");
1234     return __tree_.template __node_handle_insert_multi<node_type>(__hint, std::move(__nh));
1235   }
1236   _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
1237     return __tree_.template __node_handle_extract<node_type>(__key);
1238   }
1239   _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
1240     return __tree_.template __node_handle_extract<node_type>(__it);
1241   }
1242   template <class _Compare2>
1243   _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>& __source) {
1244     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1245         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1246     __tree_.__node_handle_merge_multi(__source.__tree_);
1247   }
1248   template <class _Compare2>
1249   _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>&& __source) {
1250     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1251         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1252     __tree_.__node_handle_merge_multi(__source.__tree_);
1253   }
1254   template <class _Compare2>
1255   _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>& __source) {
1256     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1257         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1258     __tree_.__node_handle_merge_multi(__source.__tree_);
1259   }
1260   template <class _Compare2>
1261   _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>&& __source) {
1262     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1263         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1264     __tree_.__node_handle_merge_multi(__source.__tree_);
1265   }
1266 #endif
1267
1268   _LIBCPP_HIDE_FROM_ABI void swap(multiset& __s) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) {
1269     __tree_.swap(__s.__tree_);
1270   }
1271
1272   _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return __tree_.__alloc(); }
1273   _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp(); }
1274   _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return __tree_.value_comp(); }
1275
1276   // set operations:
1277   _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }
1278   _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }
1279 #if _LIBCPP_STD_VER >= 14
1280   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1281   _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
1282     return __tree_.find(__k);
1283   }
1284   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1285   _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
1286     return __tree_.find(__k);
1287   }
1288 #endif
1289
1290   _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_multi(__k); }
1291 #if _LIBCPP_STD_VER >= 14
1292   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1293   _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
1294     return __tree_.__count_multi(__k);
1295   }
1296 #endif
1297
1298 #if _LIBCPP_STD_VER >= 20
1299   _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
1300   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1301   _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
1302     return find(__k) != end();
1303   }
1304 #endif // _LIBCPP_STD_VER >= 20
1305
1306   _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
1307   _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
1308 #if _LIBCPP_STD_VER >= 14
1309   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1310   _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {
1311     return __tree_.lower_bound(__k);
1312   }
1313
1314   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1315   _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const {
1316     return __tree_.lower_bound(__k);
1317   }
1318 #endif
1319
1320   _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
1321   _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
1322 #if _LIBCPP_STD_VER >= 14
1323   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1324   _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {
1325     return __tree_.upper_bound(__k);
1326   }
1327   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1328   _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const {
1329     return __tree_.upper_bound(__k);
1330   }
1331 #endif
1332
1333   _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
1334     return __tree_.__equal_range_multi(__k);
1335   }
1336   _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
1337     return __tree_.__equal_range_multi(__k);
1338   }
1339 #if _LIBCPP_STD_VER >= 14
1340   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1341   _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
1342     return __tree_.__equal_range_multi(__k);
1343   }
1344   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1345   _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
1346     return __tree_.__equal_range_multi(__k);
1347   }
1348 #endif
1349 };
1350
1351 #if _LIBCPP_STD_VER >= 17
1352 template <class _InputIterator,
1353           class _Compare   = less<__iter_value_type<_InputIterator>>,
1354           class _Allocator = allocator<__iter_value_type<_InputIterator>>,
1355           class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1356           class            = enable_if_t<__is_allocator<_Allocator>::value, void>,
1357           class            = enable_if_t<!__is_allocator<_Compare>::value, void>>
1358 multiset(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1359     -> multiset<__iter_value_type<_InputIterator>, _Compare, _Allocator>;
1360
1361 #  if _LIBCPP_STD_VER >= 23
1362 template <ranges::input_range _Range,
1363           class _Compare   = less<ranges::range_value_t<_Range>>,
1364           class _Allocator = allocator<ranges::range_value_t<_Range>>,
1365           class            = enable_if_t<__is_allocator<_Allocator>::value, void>,
1366           class            = enable_if_t<!__is_allocator<_Compare>::value, void>>
1367 multiset(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
1368     -> multiset<ranges::range_value_t<_Range>, _Compare, _Allocator>;
1369 #  endif
1370
1371 template <class _Key,
1372           class _Compare   = less<_Key>,
1373           class _Allocator = allocator<_Key>,
1374           class            = enable_if_t<__is_allocator<_Allocator>::value, void>,
1375           class            = enable_if_t<!__is_allocator<_Compare>::value, void>>
1376 multiset(initializer_list<_Key>,
1377          _Compare   = _Compare(),
1378          _Allocator = _Allocator()) -> multiset<_Key, _Compare, _Allocator>;
1379
1380 template <class _InputIterator,
1381           class _Allocator,
1382           class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1383           class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1384 multiset(_InputIterator, _InputIterator, _Allocator)
1385     -> multiset<__iter_value_type<_InputIterator>, less<__iter_value_type<_InputIterator>>, _Allocator>;
1386
1387 #  if _LIBCPP_STD_VER >= 23
1388 template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1389 multiset(from_range_t,
1390          _Range&&,
1391          _Allocator) -> multiset<ranges::range_value_t<_Range>, less<ranges::range_value_t<_Range>>, _Allocator>;
1392 #  endif
1393
1394 template <class _Key, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1395 multiset(initializer_list<_Key>, _Allocator) -> multiset<_Key, less<_Key>, _Allocator>;
1396 #endif
1397
1398 #ifndef _LIBCPP_CXX03_LANG
1399
1400 template <class _Key, class _Compare, class _Allocator>
1401 multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a)
1402     : __tree_(std::move(__s.__tree_), __a) {
1403   if (__a != __s.get_allocator()) {
1404     const_iterator __e = cend();
1405     while (!__s.empty())
1406       insert(__e, std::move(__s.__tree_.remove(__s.begin())->__value_));
1407   }
1408 }
1409
1410 #endif // _LIBCPP_CXX03_LANG
1411
1412 template <class _Key, class _Compare, class _Allocator>
1413 inline _LIBCPP_HIDE_FROM_ABI bool
1414 operator==(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1415   return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
1416 }
1417
1418 #if _LIBCPP_STD_VER <= 17
1419
1420 template <class _Key, class _Compare, class _Allocator>
1421 inline _LIBCPP_HIDE_FROM_ABI bool
1422 operator<(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1423   return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1424 }
1425
1426 template <class _Key, class _Compare, class _Allocator>
1427 inline _LIBCPP_HIDE_FROM_ABI bool
1428 operator!=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1429   return !(__x == __y);
1430 }
1431
1432 template <class _Key, class _Compare, class _Allocator>
1433 inline _LIBCPP_HIDE_FROM_ABI bool
1434 operator>(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1435   return __y < __x;
1436 }
1437
1438 template <class _Key, class _Compare, class _Allocator>
1439 inline _LIBCPP_HIDE_FROM_ABI bool
1440 operator>=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1441   return !(__x < __y);
1442 }
1443
1444 template <class _Key, class _Compare, class _Allocator>
1445 inline _LIBCPP_HIDE_FROM_ABI bool
1446 operator<=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1447   return !(__y < __x);
1448 }
1449
1450 #else // _LIBCPP_STD_VER <= 17
1451
1452 template <class _Key, class _Allocator>
1453 _LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Key>
1454 operator<=>(const multiset<_Key, _Allocator>& __x, const multiset<_Key, _Allocator>& __y) {
1455   return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), __synth_three_way);
1456 }
1457
1458 #endif // _LIBCPP_STD_VER <= 17
1459
1460 template <class _Key, class _Compare, class _Allocator>
1461 inline _LIBCPP_HIDE_FROM_ABI void
1462 swap(multiset<_Key, _Compare, _Allocator>& __x, multiset<_Key, _Compare, _Allocator>& __y)
1463     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1464   __x.swap(__y);
1465 }
1466
1467 #if _LIBCPP_STD_VER >= 20
1468 template <class _Key, class _Compare, class _Allocator, class _Predicate>
1469 inline _LIBCPP_HIDE_FROM_ABI typename multiset<_Key, _Compare, _Allocator>::size_type
1470 erase_if(multiset<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {
1471   return std::__libcpp_erase_if_container(__c, __pred);
1472 }
1473 #endif
1474
1475 _LIBCPP_END_NAMESPACE_STD
1476
1477 #if _LIBCPP_STD_VER >= 17
1478 _LIBCPP_BEGIN_NAMESPACE_STD
1479 namespace pmr {
1480 template <class _KeyT, class _CompareT = std::less<_KeyT>>
1481 using set _LIBCPP_AVAILABILITY_PMR = std::set<_KeyT, _CompareT, polymorphic_allocator<_KeyT>>;
1482
1483 template <class _KeyT, class _CompareT = std::less<_KeyT>>
1484 using multiset _LIBCPP_AVAILABILITY_PMR = std::multiset<_KeyT, _CompareT, polymorphic_allocator<_KeyT>>;
1485 } // namespace pmr
1486 _LIBCPP_END_NAMESPACE_STD
1487 #endif
1488
1489 _LIBCPP_POP_MACROS
1490
1491 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
1492 #  include <__cxx03/concepts>
1493 #  include <__cxx03/cstdlib>
1494 #  include <__cxx03/functional>
1495 #  include <__cxx03/iterator>
1496 #  include <__cxx03/stdexcept>
1497 #  include <__cxx03/type_traits>
1498 #endif
1499
1500 #endif // _LIBCPP_SET