libcxx/include/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 <__algorithm/equal.h>
 516 #include <__algorithm/lexicographical_compare.h>
 517 #include <__algorithm/lexicographical_compare_three_way.h>
 518 #include <__assert>
 519 #include <__config>
 520 #include <__functional/is_transparent.h>
 521 #include <__functional/operations.h>
 522 #include <__iterator/erase_if_container.h>
 523 #include <__iterator/iterator_traits.h>
 524 #include <__iterator/ranges_iterator_traits.h>
 525 #include <__iterator/reverse_iterator.h>
 526 #include <__memory/allocator.h>
 527 #include <__memory/allocator_traits.h>
 528 #include <__memory_resource/polymorphic_allocator.h>
 529 #include <__node_handle>
 530 #include <__ranges/concepts.h>
 531 #include <__ranges/container_compatible_range.h>
 532 #include <__ranges/from_range.h>
 533 #include <__tree>
 534 #include <__type_traits/container_traits.h>
 535 #include <__type_traits/enable_if.h>
 536 #include <__type_traits/is_allocator.h>
 537 #include <__type_traits/is_nothrow_assignable.h>
 538 #include <__type_traits/is_nothrow_constructible.h>
 539 #include <__type_traits/is_same.h>
 540 #include <__type_traits/is_swappable.h>
 541 #include <__type_traits/type_identity.h>
 542 #include <__utility/forward.h>
 543 #include <__utility/move.h>
 544 #include <__utility/pair.h>
 545 #include <version>
 546
 547 // standard-mandated includes
 548
 549 // [iterator.range]
 550 #include <__iterator/access.h>
 551 #include <__iterator/data.h>
 552 #include <__iterator/empty.h>
 553 #include <__iterator/reverse_access.h>
 554 #include <__iterator/size.h>
 555
 556 // [associative.set.syn]
 557 #include <compare>
 558 #include <initializer_list>
 559
 560 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 561 #  pragma GCC system_header
 562 #endif
 563
 564 _LIBCPP_PUSH_MACROS
 565 #include <__undef_macros>
 566
 567 _LIBCPP_BEGIN_NAMESPACE_STD
 568
 569 template <class _Key, class _Compare, class _Allocator>
 570 class multiset;
 571
 572 template <class _Key, class _Compare = less<_Key>, class _Allocator = allocator<_Key> >
 573 class _LIBCPP_TEMPLATE_VIS set {
 574 public:
 575   // types:
 576   typedef _Key key_type;
 577   typedef key_type value_type;
 578   typedef __type_identity_t<_Compare> key_compare;
 579   typedef key_compare value_compare;
 580   typedef __type_identity_t<_Allocator> allocator_type;
 581   typedef value_type& reference;
 582   typedef const value_type& const_reference;
 583
 584   static_assert(is_same<typename allocator_type::value_type, value_type>::value,
 585                 "Allocator::value_type must be same type as value_type");
 586
 587 private:
 588   typedef __tree<value_type, value_compare, allocator_type> __base;
 589   typedef allocator_traits<allocator_type> __alloc_traits;
 590
 591   static_assert(__check_valid_allocator<allocator_type>::value, "");
 592
 593   __base __tree_;
 594
 595 public:
 596   typedef typename __base::pointer pointer;
 597   typedef typename __base::const_pointer const_pointer;
 598   typedef typename __base::size_type size_type;
 599   typedef typename __base::difference_type difference_type;
 600   typedef typename __base::const_iterator iterator;
 601   typedef typename __base::const_iterator const_iterator;
 602   typedef std::reverse_iterator<iterator> reverse_iterator;
 603   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 604
 605 #if _LIBCPP_STD_VER >= 17
 606   typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
 607   typedef __insert_return_type<iterator, node_type> insert_return_type;
 608 #endif
 609
 610   template <class _Key2, class _Compare2, class _Alloc2>
 611   friend class _LIBCPP_TEMPLATE_VIS set;
 612   template <class _Key2, class _Compare2, class _Alloc2>
 613   friend class _LIBCPP_TEMPLATE_VIS multiset;
 614
 615   _LIBCPP_HIDE_FROM_ABI set() _NOEXCEPT_(
 616       is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&&
 617           is_nothrow_copy_constructible<key_compare>::value)
 618       : __tree_(value_compare()) {}
 619
 620   _LIBCPP_HIDE_FROM_ABI explicit set(const value_compare& __comp) _NOEXCEPT_(
 621       is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value)
 622       : __tree_(__comp) {}
 623
 624   _LIBCPP_HIDE_FROM_ABI explicit set(const value_compare& __comp, const allocator_type& __a) : __tree_(__comp, __a) {}
 625   template <class _InputIterator>
 626   _LIBCPP_HIDE_FROM_ABI set(_InputIterator __f, _InputIterator __l, const value_compare& __comp = value_compare())
 627       : __tree_(__comp) {
 628     insert(__f, __l);
 629   }
 630
 631   template <class _InputIterator>
 632   _LIBCPP_HIDE_FROM_ABI
 633   set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, const allocator_type& __a)
 634       : __tree_(__comp, __a) {
 635     insert(__f, __l);
 636   }
 637
 638 #if _LIBCPP_STD_VER >= 23
 639   template <_ContainerCompatibleRange<value_type> _Range>
 640   _LIBCPP_HIDE_FROM_ABI
 641   set(from_range_t,
 642       _Range&& __range,
 643       const key_compare& __comp = key_compare(),
 644       const allocator_type& __a = allocator_type())
 645       : __tree_(__comp, __a) {
 646     insert_range(std::forward<_Range>(__range));
 647   }
 648 #endif
 649
 650 #if _LIBCPP_STD_VER >= 14
 651   template <class _InputIterator>
 652   _LIBCPP_HIDE_FROM_ABI set(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
 653       : set(__f, __l, key_compare(), __a) {}
 654 #endif
 655
 656 #if _LIBCPP_STD_VER >= 23
 657   template <_ContainerCompatibleRange<value_type> _Range>
 658   _LIBCPP_HIDE_FROM_ABI set(from_range_t, _Range&& __range, const allocator_type& __a)
 659       : set(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
 660 #endif
 661
 662   _LIBCPP_HIDE_FROM_ABI set(const set& __s) : __tree_(__s.__tree_) { insert(__s.begin(), __s.end()); }
 663
 664   _LIBCPP_HIDE_FROM_ABI set& operator=(const set& __s) {
 665     __tree_ = __s.__tree_;
 666     return *this;
 667   }
 668
 669 #ifndef _LIBCPP_CXX03_LANG
 670   _LIBCPP_HIDE_FROM_ABI set(set&& __s) noexcept(is_nothrow_move_constructible<__base>::value)
 671       : __tree_(std::move(__s.__tree_)) {}
 672 #endif // _LIBCPP_CXX03_LANG
 673
 674   _LIBCPP_HIDE_FROM_ABI explicit set(const allocator_type& __a) : __tree_(__a) {}
 675
 676   _LIBCPP_HIDE_FROM_ABI set(const set& __s, const allocator_type& __a) : __tree_(__s.__tree_.value_comp(), __a) {
 677     insert(__s.begin(), __s.end());
 678   }
 679
 680 #ifndef _LIBCPP_CXX03_LANG
 681   _LIBCPP_HIDE_FROM_ABI set(set&& __s, const allocator_type& __a);
 682
 683   _LIBCPP_HIDE_FROM_ABI set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
 684       : __tree_(__comp) {
 685     insert(__il.begin(), __il.end());
 686   }
 687
 688   _LIBCPP_HIDE_FROM_ABI set(initializer_list<value_type> __il, const value_compare& __comp, const allocator_type& __a)
 689       : __tree_(__comp, __a) {
 690     insert(__il.begin(), __il.end());
 691   }
 692
 693 #  if _LIBCPP_STD_VER >= 14
 694   _LIBCPP_HIDE_FROM_ABI set(initializer_list<value_type> __il, const allocator_type& __a)
 695       : set(__il, key_compare(), __a) {}
 696 #  endif
 697
 698   _LIBCPP_HIDE_FROM_ABI set& operator=(initializer_list<value_type> __il) {
 699     __tree_.__assign_unique(__il.begin(), __il.end());
 700     return *this;
 701   }
 702
 703   _LIBCPP_HIDE_FROM_ABI set& operator=(set&& __s) noexcept(is_nothrow_move_assignable<__base>::value) {
 704     __tree_ = std::move(__s.__tree_);
 705     return *this;
 706   }
 707 #endif // _LIBCPP_CXX03_LANG
 708
 709   _LIBCPP_HIDE_FROM_ABI ~set() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); }
 710
 711   _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }
 712   _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }
 713   _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }
 714   _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }
 715
 716   _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
 717   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
 718   _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
 719   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
 720
 721   _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
 722   _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
 723   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }
 724   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
 725
 726   [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }
 727   _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }
 728   _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }
 729
 730   // modifiers:
 731 #ifndef _LIBCPP_CXX03_LANG
 732   template <class... _Args>
 733   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {
 734     return __tree_.__emplace_unique(std::forward<_Args>(__args)...);
 735   }
 736   template <class... _Args>
 737   _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
 738     return __tree_.__emplace_hint_unique(__p, std::forward<_Args>(__args)...);
 739   }
 740 #endif // _LIBCPP_CXX03_LANG
 741
 742   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__insert_unique(__v); }
 743   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
 744     return __tree_.__insert_unique(__p, __v);
 745   }
 746
 747   template <class _InputIterator>
 748   _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
 749     for (const_iterator __e = cend(); __f != __l; ++__f)
 750       __tree_.__insert_unique(__e, *__f);
 751   }
 752
 753 #if _LIBCPP_STD_VER >= 23
 754   template <_ContainerCompatibleRange<value_type> _Range>
 755   _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
 756     const_iterator __end = cend();
 757     for (auto&& __element : __range) {
 758       __tree_.__insert_unique(__end, std::forward<decltype(__element)>(__element));
 759     }
 760   }
 761 #endif
 762
 763 #ifndef _LIBCPP_CXX03_LANG
 764   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __v) {
 765     return __tree_.__insert_unique(std::move(__v));
 766   }
 767
 768   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {
 769     return __tree_.__insert_unique(__p, std::move(__v));
 770   }
 771
 772   _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
 773 #endif // _LIBCPP_CXX03_LANG
 774
 775   _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p); }
 776   _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_unique(__k); }
 777   _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) { return __tree_.erase(__f, __l); }
 778   _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }
 779
 780 #if _LIBCPP_STD_VER >= 17
 781   _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) {
 782     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
 783                                         "node_type with incompatible allocator passed to set::insert()");
 784     return __tree_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));
 785   }
 786   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
 787     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
 788                                         "node_type with incompatible allocator passed to set::insert()");
 789     return __tree_.template __node_handle_insert_unique<node_type>(__hint, std::move(__nh));
 790   }
 791   _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
 792     return __tree_.template __node_handle_extract<node_type>(__key);
 793   }
 794   _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
 795     return __tree_.template __node_handle_extract<node_type>(__it);
 796   }
 797   template <class _Compare2>
 798   _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>& __source) {
 799     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
 800         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
 801     __tree_.__node_handle_merge_unique(__source.__tree_);
 802   }
 803   template <class _Compare2>
 804   _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>&& __source) {
 805     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
 806         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
 807     __tree_.__node_handle_merge_unique(__source.__tree_);
 808   }
 809   template <class _Compare2>
 810   _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>& __source) {
 811     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
 812         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
 813     __tree_.__node_handle_merge_unique(__source.__tree_);
 814   }
 815   template <class _Compare2>
 816   _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>&& __source) {
 817     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
 818         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
 819     __tree_.__node_handle_merge_unique(__source.__tree_);
 820   }
 821 #endif
 822
 823   _LIBCPP_HIDE_FROM_ABI void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) { __tree_.swap(__s.__tree_); }
 824
 825   _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return __tree_.__alloc(); }
 826   _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp(); }
 827   _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return __tree_.value_comp(); }
 828
 829   // set operations:
 830   _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }
 831   _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }
 832 #if _LIBCPP_STD_VER >= 14
 833   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
 834   _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
 835     return __tree_.find(__k);
 836   }
 837   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
 838   _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
 839     return __tree_.find(__k);
 840   }
 841 #endif
 842
 843   _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_unique(__k); }
 844 #if _LIBCPP_STD_VER >= 14
 845   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
 846   _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
 847     return __tree_.__count_multi(__k);
 848   }
 849 #endif
 850
 851 #if _LIBCPP_STD_VER >= 20
 852   _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
 853   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
 854   _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
 855     return find(__k) != end();
 856   }
 857 #endif // _LIBCPP_STD_VER >= 20
 858
 859   _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
 860   _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
 861 #if _LIBCPP_STD_VER >= 14
 862   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
 863   _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {
 864     return __tree_.lower_bound(__k);
 865   }
 866
 867   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
 868   _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const {
 869     return __tree_.lower_bound(__k);
 870   }
 871 #endif
 872
 873   _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
 874   _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
 875 #if _LIBCPP_STD_VER >= 14
 876   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
 877   _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {
 878     return __tree_.upper_bound(__k);
 879   }
 880   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
 881   _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const {
 882     return __tree_.upper_bound(__k);
 883   }
 884 #endif
 885
 886   _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
 887     return __tree_.__equal_range_unique(__k);
 888   }
 889   _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
 890     return __tree_.__equal_range_unique(__k);
 891   }
 892 #if _LIBCPP_STD_VER >= 14
 893   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
 894   _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
 895     return __tree_.__equal_range_multi(__k);
 896   }
 897   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
 898   _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
 899     return __tree_.__equal_range_multi(__k);
 900   }
 901 #endif
 902 };
 903
 904 #if _LIBCPP_STD_VER >= 17
 905 template <class _InputIterator,
 906           class _Compare   = less<__iter_value_type<_InputIterator>>,
 907           class _Allocator = allocator<__iter_value_type<_InputIterator>>,
 908           class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
 909           class            = enable_if_t<__is_allocator<_Allocator>::value, void>,
 910           class            = enable_if_t<!__is_allocator<_Compare>::value, void>>
 911 set(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
 912     -> set<__iter_value_type<_InputIterator>, _Compare, _Allocator>;
 913
 914 #  if _LIBCPP_STD_VER >= 23
 915 template <ranges::input_range _Range,
 916           class _Compare   = less<ranges::range_value_t<_Range>>,
 917           class _Allocator = allocator<ranges::range_value_t<_Range>>,
 918           class            = enable_if_t<__is_allocator<_Allocator>::value, void>,
 919           class            = enable_if_t<!__is_allocator<_Compare>::value, void>>
 920 set(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
 921     -> set<ranges::range_value_t<_Range>, _Compare, _Allocator>;
 922 #  endif
 923
 924 template <class _Key,
 925           class _Compare   = less<_Key>,
 926           class _Allocator = allocator<_Key>,
 927           class            = enable_if_t<!__is_allocator<_Compare>::value, void>,
 928           class            = enable_if_t<__is_allocator<_Allocator>::value, void>>
 929 set(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator()) -> set<_Key, _Compare, _Allocator>;
 930
 931 template <class _InputIterator,
 932           class _Allocator,
 933           class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
 934           class = enable_if_t<__is_allocator<_Allocator>::value, void>>
 935 set(_InputIterator,
 936     _InputIterator,
 937     _Allocator) -> set<__iter_value_type<_InputIterator>, less<__iter_value_type<_InputIterator>>, _Allocator>;
 938
 939 #  if _LIBCPP_STD_VER >= 23
 940 template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
 941 set(from_range_t,
 942     _Range&&,
 943     _Allocator) -> set<ranges::range_value_t<_Range>, less<ranges::range_value_t<_Range>>, _Allocator>;
 944 #  endif
 945
 946 template <class _Key, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
 947 set(initializer_list<_Key>, _Allocator) -> set<_Key, less<_Key>, _Allocator>;
 948 #endif
 949
 950 #ifndef _LIBCPP_CXX03_LANG
 951
 952 template <class _Key, class _Compare, class _Allocator>
 953 set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a) : __tree_(std::move(__s.__tree_), __a) {
 954   if (__a != __s.get_allocator()) {
 955     const_iterator __e = cend();
 956     while (!__s.empty())
 957       insert(__e, std::move(__s.__tree_.remove(__s.begin())->__value_));
 958   }
 959 }
 960
 961 #endif // _LIBCPP_CXX03_LANG
 962
 963 template <class _Key, class _Compare, class _Allocator>
 964 inline _LIBCPP_HIDE_FROM_ABI bool
 965 operator==(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
 966   return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
 967 }
 968
 969 #if _LIBCPP_STD_VER <= 17
 970
 971 template <class _Key, class _Compare, class _Allocator>
 972 inline _LIBCPP_HIDE_FROM_ABI bool
 973 operator<(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
 974   return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
 975 }
 976
 977 template <class _Key, class _Compare, class _Allocator>
 978 inline _LIBCPP_HIDE_FROM_ABI bool
 979 operator!=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
 980   return !(__x == __y);
 981 }
 982
 983 template <class _Key, class _Compare, class _Allocator>
 984 inline _LIBCPP_HIDE_FROM_ABI bool
 985 operator>(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
 986   return __y < __x;
 987 }
 988
 989 template <class _Key, class _Compare, class _Allocator>
 990 inline _LIBCPP_HIDE_FROM_ABI bool
 991 operator>=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
 992   return !(__x < __y);
 993 }
 994
 995 template <class _Key, class _Compare, class _Allocator>
 996 inline _LIBCPP_HIDE_FROM_ABI bool
 997 operator<=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
 998   return !(__y < __x);
 999 }
1000
1001 #else // _LIBCPP_STD_VER <= 17
1002
1003 template <class _Key, class _Allocator>
1004 _LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Key>
1005 operator<=>(const set<_Key, _Allocator>& __x, const set<_Key, _Allocator>& __y) {
1006   return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
1007 }
1008
1009 #endif // _LIBCPP_STD_VER <= 17
1010
1011 // specialized algorithms:
1012 template <class _Key, class _Compare, class _Allocator>
1013 inline _LIBCPP_HIDE_FROM_ABI void swap(set<_Key, _Compare, _Allocator>& __x, set<_Key, _Compare, _Allocator>& __y)
1014     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1015   __x.swap(__y);
1016 }
1017
1018 #if _LIBCPP_STD_VER >= 20
1019 template <class _Key, class _Compare, class _Allocator, class _Predicate>
1020 inline _LIBCPP_HIDE_FROM_ABI typename set<_Key, _Compare, _Allocator>::size_type
1021 erase_if(set<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {
1022   return std::__libcpp_erase_if_container(__c, __pred);
1023 }
1024 #endif
1025
1026 template <class _Key, class _Compare, class _Allocator>
1027 struct __container_traits<set<_Key, _Compare, _Allocator> > {
1028   // http://eel.is/c++draft/associative.reqmts.except#2
1029   // For associative containers, if an exception is thrown by any operation from within
1030   // an insert or emplace function inserting a single element, the insertion has no effect.
1031   static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee = true;
1032 };
1033
1034 template <class _Key, class _Compare = less<_Key>, class _Allocator = allocator<_Key> >
1035 class _LIBCPP_TEMPLATE_VIS multiset {
1036 public:
1037   // types:
1038   typedef _Key key_type;
1039   typedef key_type value_type;
1040   typedef __type_identity_t<_Compare> key_compare;
1041   typedef key_compare value_compare;
1042   typedef __type_identity_t<_Allocator> allocator_type;
1043   typedef value_type& reference;
1044   typedef const value_type& const_reference;
1045
1046   static_assert(is_same<typename allocator_type::value_type, value_type>::value,
1047                 "Allocator::value_type must be same type as value_type");
1048
1049 private:
1050   typedef __tree<value_type, value_compare, allocator_type> __base;
1051   typedef allocator_traits<allocator_type> __alloc_traits;
1052
1053   static_assert(__check_valid_allocator<allocator_type>::value, "");
1054
1055   __base __tree_;
1056
1057 public:
1058   typedef typename __base::pointer pointer;
1059   typedef typename __base::const_pointer const_pointer;
1060   typedef typename __base::size_type size_type;
1061   typedef typename __base::difference_type difference_type;
1062   typedef typename __base::const_iterator iterator;
1063   typedef typename __base::const_iterator const_iterator;
1064   typedef std::reverse_iterator<iterator> reverse_iterator;
1065   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1066
1067 #if _LIBCPP_STD_VER >= 17
1068   typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
1069 #endif
1070
1071   template <class _Key2, class _Compare2, class _Alloc2>
1072   friend class _LIBCPP_TEMPLATE_VIS set;
1073   template <class _Key2, class _Compare2, class _Alloc2>
1074   friend class _LIBCPP_TEMPLATE_VIS multiset;
1075
1076   // construct/copy/destroy:
1077   _LIBCPP_HIDE_FROM_ABI multiset() _NOEXCEPT_(
1078       is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&&
1079           is_nothrow_copy_constructible<key_compare>::value)
1080       : __tree_(value_compare()) {}
1081
1082   _LIBCPP_HIDE_FROM_ABI explicit multiset(const value_compare& __comp) _NOEXCEPT_(
1083       is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value)
1084       : __tree_(__comp) {}
1085
1086   _LIBCPP_HIDE_FROM_ABI explicit multiset(const value_compare& __comp, const allocator_type& __a)
1087       : __tree_(__comp, __a) {}
1088   template <class _InputIterator>
1089   _LIBCPP_HIDE_FROM_ABI multiset(_InputIterator __f, _InputIterator __l, const value_compare& __comp = value_compare())
1090       : __tree_(__comp) {
1091     insert(__f, __l);
1092   }
1093
1094 #if _LIBCPP_STD_VER >= 14
1095   template <class _InputIterator>
1096   _LIBCPP_HIDE_FROM_ABI multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1097       : multiset(__f, __l, key_compare(), __a) {}
1098 #endif
1099
1100   template <class _InputIterator>
1101   _LIBCPP_HIDE_FROM_ABI
1102   multiset(_InputIterator __f, _InputIterator __l, const value_compare& __comp, const allocator_type& __a)
1103       : __tree_(__comp, __a) {
1104     insert(__f, __l);
1105   }
1106
1107 #if _LIBCPP_STD_VER >= 23
1108   template <_ContainerCompatibleRange<value_type> _Range>
1109   _LIBCPP_HIDE_FROM_ABI
1110   multiset(from_range_t,
1111            _Range&& __range,
1112            const key_compare& __comp = key_compare(),
1113            const allocator_type& __a = allocator_type())
1114       : __tree_(__comp, __a) {
1115     insert_range(std::forward<_Range>(__range));
1116   }
1117
1118   template <_ContainerCompatibleRange<value_type> _Range>
1119   _LIBCPP_HIDE_FROM_ABI multiset(from_range_t, _Range&& __range, const allocator_type& __a)
1120       : multiset(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
1121 #endif
1122
1123   _LIBCPP_HIDE_FROM_ABI multiset(const multiset& __s)
1124       : __tree_(__s.__tree_.value_comp(),
1125                 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) {
1126     insert(__s.begin(), __s.end());
1127   }
1128
1129   _LIBCPP_HIDE_FROM_ABI multiset& operator=(const multiset& __s) {
1130     __tree_ = __s.__tree_;
1131     return *this;
1132   }
1133
1134 #ifndef _LIBCPP_CXX03_LANG
1135   _LIBCPP_HIDE_FROM_ABI multiset(multiset&& __s) noexcept(is_nothrow_move_constructible<__base>::value)
1136       : __tree_(std::move(__s.__tree_)) {}
1137
1138   _LIBCPP_HIDE_FROM_ABI multiset(multiset&& __s, const allocator_type& __a);
1139 #endif // _LIBCPP_CXX03_LANG
1140   _LIBCPP_HIDE_FROM_ABI explicit multiset(const allocator_type& __a) : __tree_(__a) {}
1141   _LIBCPP_HIDE_FROM_ABI multiset(const multiset& __s, const allocator_type& __a)
1142       : __tree_(__s.__tree_.value_comp(), __a) {
1143     insert(__s.begin(), __s.end());
1144   }
1145
1146 #ifndef _LIBCPP_CXX03_LANG
1147   _LIBCPP_HIDE_FROM_ABI multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
1148       : __tree_(__comp) {
1149     insert(__il.begin(), __il.end());
1150   }
1151
1152   _LIBCPP_HIDE_FROM_ABI
1153   multiset(initializer_list<value_type> __il, const value_compare& __comp, const allocator_type& __a)
1154       : __tree_(__comp, __a) {
1155     insert(__il.begin(), __il.end());
1156   }
1157
1158 #  if _LIBCPP_STD_VER >= 14
1159   _LIBCPP_HIDE_FROM_ABI multiset(initializer_list<value_type> __il, const allocator_type& __a)
1160       : multiset(__il, key_compare(), __a) {}
1161 #  endif
1162
1163   _LIBCPP_HIDE_FROM_ABI multiset& operator=(initializer_list<value_type> __il) {
1164     __tree_.__assign_multi(__il.begin(), __il.end());
1165     return *this;
1166   }
1167
1168   _LIBCPP_HIDE_FROM_ABI multiset& operator=(multiset&& __s) _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) {
1169     __tree_ = std::move(__s.__tree_);
1170     return *this;
1171   }
1172 #endif // _LIBCPP_CXX03_LANG
1173
1174   _LIBCPP_HIDE_FROM_ABI ~multiset() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); }
1175
1176   _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }
1177   _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }
1178   _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }
1179   _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }
1180
1181   _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
1182   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
1183   _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
1184   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
1185
1186   _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
1187   _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
1188   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }
1189   _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
1190
1191   [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }
1192   _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }
1193   _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }
1194
1195   // modifiers:
1196 #ifndef _LIBCPP_CXX03_LANG
1197   template <class... _Args>
1198   _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) {
1199     return __tree_.__emplace_multi(std::forward<_Args>(__args)...);
1200   }
1201   template <class... _Args>
1202   _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1203     return __tree_.__emplace_hint_multi(__p, std::forward<_Args>(__args)...);
1204   }
1205 #endif // _LIBCPP_CXX03_LANG
1206
1207   _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __v) { return __tree_.__insert_multi(__v); }
1208   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
1209     return __tree_.__insert_multi(__p, __v);
1210   }
1211
1212   template <class _InputIterator>
1213   _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
1214     for (const_iterator __e = cend(); __f != __l; ++__f)
1215       __tree_.__insert_multi(__e, *__f);
1216   }
1217
1218 #if _LIBCPP_STD_VER >= 23
1219   template <_ContainerCompatibleRange<value_type> _Range>
1220   _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
1221     const_iterator __end = cend();
1222     for (auto&& __element : __range) {
1223       __tree_.__insert_multi(__end, std::forward<decltype(__element)>(__element));
1224     }
1225   }
1226 #endif
1227
1228 #ifndef _LIBCPP_CXX03_LANG
1229   _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __v) { return __tree_.__insert_multi(std::move(__v)); }
1230
1231   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {
1232     return __tree_.__insert_multi(__p, std::move(__v));
1233   }
1234
1235   _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
1236 #endif // _LIBCPP_CXX03_LANG
1237
1238   _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p); }
1239   _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_multi(__k); }
1240   _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) { return __tree_.erase(__f, __l); }
1241   _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }
1242
1243 #if _LIBCPP_STD_VER >= 17
1244   _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) {
1245     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1246                                         "node_type with incompatible allocator passed to multiset::insert()");
1247     return __tree_.template __node_handle_insert_multi<node_type>(std::move(__nh));
1248   }
1249   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
1250     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1251                                         "node_type with incompatible allocator passed to multiset::insert()");
1252     return __tree_.template __node_handle_insert_multi<node_type>(__hint, std::move(__nh));
1253   }
1254   _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
1255     return __tree_.template __node_handle_extract<node_type>(__key);
1256   }
1257   _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
1258     return __tree_.template __node_handle_extract<node_type>(__it);
1259   }
1260   template <class _Compare2>
1261   _LIBCPP_HIDE_FROM_ABI void merge(multiset<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   template <class _Compare2>
1267   _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>&& __source) {
1268     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1269         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1270     __tree_.__node_handle_merge_multi(__source.__tree_);
1271   }
1272   template <class _Compare2>
1273   _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>& __source) {
1274     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1275         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1276     __tree_.__node_handle_merge_multi(__source.__tree_);
1277   }
1278   template <class _Compare2>
1279   _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>&& __source) {
1280     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1281         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1282     __tree_.__node_handle_merge_multi(__source.__tree_);
1283   }
1284 #endif
1285
1286   _LIBCPP_HIDE_FROM_ABI void swap(multiset& __s) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) {
1287     __tree_.swap(__s.__tree_);
1288   }
1289
1290   _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return __tree_.__alloc(); }
1291   _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp(); }
1292   _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return __tree_.value_comp(); }
1293
1294   // set operations:
1295   _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }
1296   _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }
1297 #if _LIBCPP_STD_VER >= 14
1298   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1299   _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
1300     return __tree_.find(__k);
1301   }
1302   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1303   _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
1304     return __tree_.find(__k);
1305   }
1306 #endif
1307
1308   _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_multi(__k); }
1309 #if _LIBCPP_STD_VER >= 14
1310   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1311   _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
1312     return __tree_.__count_multi(__k);
1313   }
1314 #endif
1315
1316 #if _LIBCPP_STD_VER >= 20
1317   _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
1318   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1319   _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
1320     return find(__k) != end();
1321   }
1322 #endif // _LIBCPP_STD_VER >= 20
1323
1324   _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
1325   _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
1326 #if _LIBCPP_STD_VER >= 14
1327   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1328   _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {
1329     return __tree_.lower_bound(__k);
1330   }
1331
1332   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1333   _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const {
1334     return __tree_.lower_bound(__k);
1335   }
1336 #endif
1337
1338   _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
1339   _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
1340 #if _LIBCPP_STD_VER >= 14
1341   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1342   _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {
1343     return __tree_.upper_bound(__k);
1344   }
1345   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1346   _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const {
1347     return __tree_.upper_bound(__k);
1348   }
1349 #endif
1350
1351   _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
1352     return __tree_.__equal_range_multi(__k);
1353   }
1354   _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
1355     return __tree_.__equal_range_multi(__k);
1356   }
1357 #if _LIBCPP_STD_VER >= 14
1358   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1359   _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
1360     return __tree_.__equal_range_multi(__k);
1361   }
1362   template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1363   _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
1364     return __tree_.__equal_range_multi(__k);
1365   }
1366 #endif
1367 };
1368
1369 #if _LIBCPP_STD_VER >= 17
1370 template <class _InputIterator,
1371           class _Compare   = less<__iter_value_type<_InputIterator>>,
1372           class _Allocator = allocator<__iter_value_type<_InputIterator>>,
1373           class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1374           class            = enable_if_t<__is_allocator<_Allocator>::value, void>,
1375           class            = enable_if_t<!__is_allocator<_Compare>::value, void>>
1376 multiset(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1377     -> multiset<__iter_value_type<_InputIterator>, _Compare, _Allocator>;
1378
1379 #  if _LIBCPP_STD_VER >= 23
1380 template <ranges::input_range _Range,
1381           class _Compare   = less<ranges::range_value_t<_Range>>,
1382           class _Allocator = allocator<ranges::range_value_t<_Range>>,
1383           class            = enable_if_t<__is_allocator<_Allocator>::value, void>,
1384           class            = enable_if_t<!__is_allocator<_Compare>::value, void>>
1385 multiset(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
1386     -> multiset<ranges::range_value_t<_Range>, _Compare, _Allocator>;
1387 #  endif
1388
1389 template <class _Key,
1390           class _Compare   = less<_Key>,
1391           class _Allocator = allocator<_Key>,
1392           class            = enable_if_t<__is_allocator<_Allocator>::value, void>,
1393           class            = enable_if_t<!__is_allocator<_Compare>::value, void>>
1394 multiset(initializer_list<_Key>,
1395          _Compare   = _Compare(),
1396          _Allocator = _Allocator()) -> multiset<_Key, _Compare, _Allocator>;
1397
1398 template <class _InputIterator,
1399           class _Allocator,
1400           class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1401           class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1402 multiset(_InputIterator, _InputIterator, _Allocator)
1403     -> multiset<__iter_value_type<_InputIterator>, less<__iter_value_type<_InputIterator>>, _Allocator>;
1404
1405 #  if _LIBCPP_STD_VER >= 23
1406 template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1407 multiset(from_range_t,
1408          _Range&&,
1409          _Allocator) -> multiset<ranges::range_value_t<_Range>, less<ranges::range_value_t<_Range>>, _Allocator>;
1410 #  endif
1411
1412 template <class _Key, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1413 multiset(initializer_list<_Key>, _Allocator) -> multiset<_Key, less<_Key>, _Allocator>;
1414 #endif
1415
1416 #ifndef _LIBCPP_CXX03_LANG
1417
1418 template <class _Key, class _Compare, class _Allocator>
1419 multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a)
1420     : __tree_(std::move(__s.__tree_), __a) {
1421   if (__a != __s.get_allocator()) {
1422     const_iterator __e = cend();
1423     while (!__s.empty())
1424       insert(__e, std::move(__s.__tree_.remove(__s.begin())->__value_));
1425   }
1426 }
1427
1428 #endif // _LIBCPP_CXX03_LANG
1429
1430 template <class _Key, class _Compare, class _Allocator>
1431 inline _LIBCPP_HIDE_FROM_ABI bool
1432 operator==(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1433   return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
1434 }
1435
1436 #if _LIBCPP_STD_VER <= 17
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 std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
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 !(__x == __y);
1448 }
1449
1450 template <class _Key, class _Compare, class _Allocator>
1451 inline _LIBCPP_HIDE_FROM_ABI bool
1452 operator>(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1453   return __y < __x;
1454 }
1455
1456 template <class _Key, class _Compare, class _Allocator>
1457 inline _LIBCPP_HIDE_FROM_ABI bool
1458 operator>=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1459   return !(__x < __y);
1460 }
1461
1462 template <class _Key, class _Compare, class _Allocator>
1463 inline _LIBCPP_HIDE_FROM_ABI bool
1464 operator<=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1465   return !(__y < __x);
1466 }
1467
1468 #else // _LIBCPP_STD_VER <= 17
1469
1470 template <class _Key, class _Allocator>
1471 _LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Key>
1472 operator<=>(const multiset<_Key, _Allocator>& __x, const multiset<_Key, _Allocator>& __y) {
1473   return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), __synth_three_way);
1474 }
1475
1476 #endif // _LIBCPP_STD_VER <= 17
1477
1478 template <class _Key, class _Compare, class _Allocator>
1479 inline _LIBCPP_HIDE_FROM_ABI void
1480 swap(multiset<_Key, _Compare, _Allocator>& __x, multiset<_Key, _Compare, _Allocator>& __y)
1481     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1482   __x.swap(__y);
1483 }
1484
1485 #if _LIBCPP_STD_VER >= 20
1486 template <class _Key, class _Compare, class _Allocator, class _Predicate>
1487 inline _LIBCPP_HIDE_FROM_ABI typename multiset<_Key, _Compare, _Allocator>::size_type
1488 erase_if(multiset<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {
1489   return std::__libcpp_erase_if_container(__c, __pred);
1490 }
1491 #endif
1492
1493 template <class _Key, class _Compare, class _Allocator>
1494 struct __container_traits<multiset<_Key, _Compare, _Allocator> > {
1495   // http://eel.is/c++draft/associative.reqmts.except#2
1496   // For associative containers, if an exception is thrown by any operation from within
1497   // an insert or emplace function inserting a single element, the insertion has no effect.
1498   static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee = true;
1499 };
1500
1501 _LIBCPP_END_NAMESPACE_STD
1502
1503 #if _LIBCPP_STD_VER >= 17
1504 _LIBCPP_BEGIN_NAMESPACE_STD
1505 namespace pmr {
1506 template <class _KeyT, class _CompareT = std::less<_KeyT>>
1507 using set _LIBCPP_AVAILABILITY_PMR = std::set<_KeyT, _CompareT, polymorphic_allocator<_KeyT>>;
1508
1509 template <class _KeyT, class _CompareT = std::less<_KeyT>>
1510 using multiset _LIBCPP_AVAILABILITY_PMR = std::multiset<_KeyT, _CompareT, polymorphic_allocator<_KeyT>>;
1511 } // namespace pmr
1512 _LIBCPP_END_NAMESPACE_STD
1513 #endif
1514
1515 _LIBCPP_POP_MACROS
1516
1517 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
1518 #  include <concepts>
1519 #  include <cstdlib>
1520 #  include <functional>
1521 #  include <iterator>
1522 #  include <stdexcept>
1523 #  include <type_traits>
1524 #endif
1525
1526 #endif // _LIBCPP_SET