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> // all public C++ headers provide the assertion handler
 519 #include <__availability>
 520 #include <__config>
 521 #include <__functional/is_transparent.h>
 522 #include <__functional/operations.h>
 523 #include <__iterator/erase_if_container.h>
 524 #include <__iterator/iterator_traits.h>
 525 #include <__iterator/ranges_iterator_traits.h>
 526 #include <__iterator/reverse_iterator.h>
 527 #include <__memory/allocator.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/is_allocator.h>
 535 #include <__utility/forward.h>
 536 #include <version>
 537
 538 // standard-mandated includes
 539
 540 // [iterator.range]
 541 #include <__iterator/access.h>
 542 #include <__iterator/data.h>
 543 #include <__iterator/empty.h>
 544 #include <__iterator/reverse_access.h>
 545 #include <__iterator/size.h>
 546
 547 // [associative.set.syn]
 548 #include <compare>
 549 #include <initializer_list>
 550
 551 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 552 #  pragma GCC system_header
 553 #endif
 554
 555 _LIBCPP_BEGIN_NAMESPACE_STD
 556
 557 template <class _Key, class _Compare, class _Allocator>
 558 class multiset;
 559
 560 template <class _Key, class _Compare = less<_Key>,
 561           class _Allocator = allocator<_Key> >
 562 class _LIBCPP_TEMPLATE_VIS set
 563 {
 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(is_same<allocator_type, __rebind_alloc<__alloc_traits, value_type> >::value,
 582                   "[allocator.requirements] states that rebinding an allocator to the same type should result in the "
 583                   "original allocator");
 584
 585     __base __tree_;
 586
 587 public:
 588     typedef typename __base::pointer               pointer;
 589     typedef typename __base::const_pointer         const_pointer;
 590     typedef typename __base::size_type             size_type;
 591     typedef typename __base::difference_type       difference_type;
 592     typedef typename __base::const_iterator        iterator;
 593     typedef typename __base::const_iterator        const_iterator;
 594     typedef _VSTD::reverse_iterator<iterator>       reverse_iterator;
 595     typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
 596
 597 #if _LIBCPP_STD_VER >= 17
 598     typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
 599     typedef __insert_return_type<iterator, node_type> insert_return_type;
 600 #endif
 601
 602     template <class _Key2, class _Compare2, class _Alloc2>
 603         friend class _LIBCPP_TEMPLATE_VIS set;
 604     template <class _Key2, class _Compare2, class _Alloc2>
 605         friend class _LIBCPP_TEMPLATE_VIS multiset;
 606
 607     _LIBCPP_INLINE_VISIBILITY
 608     set()
 609         _NOEXCEPT_(
 610             is_nothrow_default_constructible<allocator_type>::value &&
 611             is_nothrow_default_constructible<key_compare>::value &&
 612             is_nothrow_copy_constructible<key_compare>::value)
 613         : __tree_(value_compare()) {}
 614
 615     _LIBCPP_INLINE_VISIBILITY
 616     explicit set(const value_compare& __comp)
 617         _NOEXCEPT_(
 618             is_nothrow_default_constructible<allocator_type>::value &&
 619             is_nothrow_copy_constructible<key_compare>::value)
 620         : __tree_(__comp) {}
 621
 622     _LIBCPP_INLINE_VISIBILITY
 623     explicit set(const value_compare& __comp, const allocator_type& __a)
 624         : __tree_(__comp, __a) {}
 625     template <class _InputIterator>
 626         _LIBCPP_INLINE_VISIBILITY
 627         set(_InputIterator __f, _InputIterator __l,
 628             const value_compare& __comp = value_compare())
 629         : __tree_(__comp)
 630         {
 631             insert(__f, __l);
 632         }
 633
 634     template <class _InputIterator>
 635         _LIBCPP_INLINE_VISIBILITY
 636         set(_InputIterator __f, _InputIterator __l, const value_compare& __comp,
 637             const allocator_type& __a)
 638         : __tree_(__comp, __a)
 639         {
 640             insert(__f, __l);
 641         }
 642
 643 #if _LIBCPP_STD_VER >= 23
 644     template <_ContainerCompatibleRange<value_type> _Range>
 645     _LIBCPP_HIDE_FROM_ABI
 646     set(from_range_t, _Range&& __range, const key_compare& __comp = key_compare(),
 647         const allocator_type& __a = allocator_type())
 648       : __tree_(__comp, __a) {
 649       insert_range(std::forward<_Range>(__range));
 650     }
 651 #endif
 652
 653 #if _LIBCPP_STD_VER >= 14
 654         template <class _InputIterator>
 655         _LIBCPP_INLINE_VISIBILITY
 656         set(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
 657             : set(__f, __l, key_compare(), __a) {}
 658 #endif
 659
 660 #if _LIBCPP_STD_VER >= 23
 661     template <_ContainerCompatibleRange<value_type> _Range>
 662     _LIBCPP_HIDE_FROM_ABI
 663     set(from_range_t, _Range&& __range, const allocator_type& __a)
 664       : set(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
 665 #endif
 666
 667     _LIBCPP_INLINE_VISIBILITY
 668     set(const set& __s)
 669         : __tree_(__s.__tree_)
 670         {
 671             insert(__s.begin(), __s.end());
 672         }
 673
 674     _LIBCPP_INLINE_VISIBILITY
 675     set& operator=(const set& __s)
 676         {
 677             __tree_ = __s.__tree_;
 678             return *this;
 679         }
 680
 681 #ifndef _LIBCPP_CXX03_LANG
 682     _LIBCPP_INLINE_VISIBILITY
 683     set(set&& __s)
 684         _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
 685         : __tree_(_VSTD::move(__s.__tree_)) {}
 686 #endif // _LIBCPP_CXX03_LANG
 687
 688     _LIBCPP_INLINE_VISIBILITY
 689     explicit set(const allocator_type& __a)
 690         : __tree_(__a) {}
 691
 692     _LIBCPP_INLINE_VISIBILITY
 693     set(const set& __s, const allocator_type& __a)
 694         : __tree_(__s.__tree_.value_comp(), __a)
 695         {
 696             insert(__s.begin(), __s.end());
 697         }
 698
 699 #ifndef _LIBCPP_CXX03_LANG
 700     _LIBCPP_HIDE_FROM_ABI set(set&& __s, const allocator_type& __a);
 701
 702     _LIBCPP_INLINE_VISIBILITY
 703     set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
 704         : __tree_(__comp)
 705         {
 706             insert(__il.begin(), __il.end());
 707         }
 708
 709     _LIBCPP_INLINE_VISIBILITY
 710     set(initializer_list<value_type> __il, const value_compare& __comp,
 711         const allocator_type& __a)
 712         : __tree_(__comp, __a)
 713         {
 714             insert(__il.begin(), __il.end());
 715         }
 716
 717 #if _LIBCPP_STD_VER >= 14
 718     _LIBCPP_INLINE_VISIBILITY
 719     set(initializer_list<value_type> __il, const allocator_type& __a)
 720         : set(__il, key_compare(), __a) {}
 721 #endif
 722
 723     _LIBCPP_INLINE_VISIBILITY
 724     set& operator=(initializer_list<value_type> __il)
 725         {
 726             __tree_.__assign_unique(__il.begin(), __il.end());
 727             return *this;
 728         }
 729
 730     _LIBCPP_INLINE_VISIBILITY
 731     set& operator=(set&& __s)
 732         _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
 733         {
 734             __tree_ = _VSTD::move(__s.__tree_);
 735             return *this;
 736         }
 737 #endif // _LIBCPP_CXX03_LANG
 738
 739     _LIBCPP_INLINE_VISIBILITY
 740     ~set() {
 741         static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
 742     }
 743
 744     _LIBCPP_INLINE_VISIBILITY
 745           iterator begin() _NOEXCEPT       {return __tree_.begin();}
 746     _LIBCPP_INLINE_VISIBILITY
 747     const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
 748     _LIBCPP_INLINE_VISIBILITY
 749           iterator end() _NOEXCEPT         {return __tree_.end();}
 750     _LIBCPP_INLINE_VISIBILITY
 751     const_iterator end()   const _NOEXCEPT {return __tree_.end();}
 752
 753     _LIBCPP_INLINE_VISIBILITY
 754           reverse_iterator rbegin() _NOEXCEPT
 755             {return reverse_iterator(end());}
 756     _LIBCPP_INLINE_VISIBILITY
 757     const_reverse_iterator rbegin() const _NOEXCEPT
 758         {return const_reverse_iterator(end());}
 759     _LIBCPP_INLINE_VISIBILITY
 760           reverse_iterator rend() _NOEXCEPT
 761             {return reverse_iterator(begin());}
 762     _LIBCPP_INLINE_VISIBILITY
 763     const_reverse_iterator rend() const _NOEXCEPT
 764         {return const_reverse_iterator(begin());}
 765
 766     _LIBCPP_INLINE_VISIBILITY
 767     const_iterator cbegin()  const _NOEXCEPT {return begin();}
 768     _LIBCPP_INLINE_VISIBILITY
 769     const_iterator cend() const _NOEXCEPT {return end();}
 770     _LIBCPP_INLINE_VISIBILITY
 771     const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
 772     _LIBCPP_INLINE_VISIBILITY
 773     const_reverse_iterator crend() const _NOEXCEPT {return rend();}
 774
 775     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
 776     bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
 777     _LIBCPP_INLINE_VISIBILITY
 778     size_type size() const _NOEXCEPT {return __tree_.size();}
 779     _LIBCPP_INLINE_VISIBILITY
 780     size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
 781
 782     // modifiers:
 783 #ifndef _LIBCPP_CXX03_LANG
 784     template <class... _Args>
 785         _LIBCPP_INLINE_VISIBILITY
 786         pair<iterator, bool> emplace(_Args&&... __args)
 787             {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
 788     template <class... _Args>
 789         _LIBCPP_INLINE_VISIBILITY
 790         iterator emplace_hint(const_iterator __p, _Args&&... __args)
 791             {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);}
 792 #endif // _LIBCPP_CXX03_LANG
 793
 794     _LIBCPP_INLINE_VISIBILITY
 795     pair<iterator,bool> insert(const value_type& __v)
 796         {return __tree_.__insert_unique(__v);}
 797     _LIBCPP_INLINE_VISIBILITY
 798     iterator insert(const_iterator __p, const value_type& __v)
 799         {return __tree_.__insert_unique(__p, __v);}
 800
 801     template <class _InputIterator>
 802         _LIBCPP_INLINE_VISIBILITY
 803         void insert(_InputIterator __f, _InputIterator __l)
 804         {
 805             for (const_iterator __e = cend(); __f != __l; ++__f)
 806                 __tree_.__insert_unique(__e, *__f);
 807         }
 808
 809 #if _LIBCPP_STD_VER >= 23
 810     template <_ContainerCompatibleRange<value_type> _Range>
 811     _LIBCPP_HIDE_FROM_ABI
 812     void insert_range(_Range&& __range) {
 813       const_iterator __end = cend();
 814       for (auto&& __element : __range) {
 815         __tree_.__insert_unique(__end, std::forward<decltype(__element)>(__element));
 816       }
 817     }
 818 #endif
 819
 820 #ifndef _LIBCPP_CXX03_LANG
 821     _LIBCPP_INLINE_VISIBILITY
 822     pair<iterator,bool> insert(value_type&& __v)
 823         {return __tree_.__insert_unique(_VSTD::move(__v));}
 824
 825     _LIBCPP_INLINE_VISIBILITY
 826     iterator insert(const_iterator __p, value_type&& __v)
 827         {return __tree_.__insert_unique(__p, _VSTD::move(__v));}
 828
 829     _LIBCPP_INLINE_VISIBILITY
 830     void insert(initializer_list<value_type> __il)
 831         {insert(__il.begin(), __il.end());}
 832 #endif // _LIBCPP_CXX03_LANG
 833
 834     _LIBCPP_INLINE_VISIBILITY
 835     iterator  erase(const_iterator __p) {return __tree_.erase(__p);}
 836     _LIBCPP_INLINE_VISIBILITY
 837     size_type erase(const key_type& __k)
 838         {return __tree_.__erase_unique(__k);}
 839     _LIBCPP_INLINE_VISIBILITY
 840     iterator  erase(const_iterator __f, const_iterator __l)
 841         {return __tree_.erase(__f, __l);}
 842     _LIBCPP_INLINE_VISIBILITY
 843     void clear() _NOEXCEPT {__tree_.clear();}
 844
 845 #if _LIBCPP_STD_VER >= 17
 846     _LIBCPP_INLINE_VISIBILITY
 847     insert_return_type insert(node_type&& __nh)
 848     {
 849         _LIBCPP_ASSERT_UNCATEGORIZED(__nh.empty() || __nh.get_allocator() == get_allocator(),
 850             "node_type with incompatible allocator passed to set::insert()");
 851         return __tree_.template __node_handle_insert_unique<
 852             node_type, insert_return_type>(_VSTD::move(__nh));
 853     }
 854     _LIBCPP_INLINE_VISIBILITY
 855     iterator insert(const_iterator __hint, node_type&& __nh)
 856     {
 857         _LIBCPP_ASSERT_UNCATEGORIZED(__nh.empty() || __nh.get_allocator() == get_allocator(),
 858             "node_type with incompatible allocator passed to set::insert()");
 859         return __tree_.template __node_handle_insert_unique<node_type>(
 860             __hint, _VSTD::move(__nh));
 861     }
 862     _LIBCPP_INLINE_VISIBILITY
 863     node_type extract(key_type const& __key)
 864     {
 865         return __tree_.template __node_handle_extract<node_type>(__key);
 866     }
 867     _LIBCPP_INLINE_VISIBILITY
 868     node_type extract(const_iterator __it)
 869     {
 870         return __tree_.template __node_handle_extract<node_type>(__it);
 871     }
 872     template <class _Compare2>
 873     _LIBCPP_INLINE_VISIBILITY
 874     void merge(set<key_type, _Compare2, allocator_type>& __source)
 875     {
 876         _LIBCPP_ASSERT_UNCATEGORIZED(__source.get_allocator() == get_allocator(),
 877                        "merging container with incompatible allocator");
 878         __tree_.__node_handle_merge_unique(__source.__tree_);
 879     }
 880     template <class _Compare2>
 881     _LIBCPP_INLINE_VISIBILITY
 882     void merge(set<key_type, _Compare2, allocator_type>&& __source)
 883     {
 884         _LIBCPP_ASSERT_UNCATEGORIZED(__source.get_allocator() == get_allocator(),
 885                        "merging container with incompatible allocator");
 886         __tree_.__node_handle_merge_unique(__source.__tree_);
 887     }
 888     template <class _Compare2>
 889     _LIBCPP_INLINE_VISIBILITY
 890     void merge(multiset<key_type, _Compare2, allocator_type>& __source)
 891     {
 892         _LIBCPP_ASSERT_UNCATEGORIZED(__source.get_allocator() == get_allocator(),
 893                        "merging container with incompatible allocator");
 894         __tree_.__node_handle_merge_unique(__source.__tree_);
 895     }
 896     template <class _Compare2>
 897     _LIBCPP_INLINE_VISIBILITY
 898     void merge(multiset<key_type, _Compare2, allocator_type>&& __source)
 899     {
 900         _LIBCPP_ASSERT_UNCATEGORIZED(__source.get_allocator() == get_allocator(),
 901                        "merging container with incompatible allocator");
 902         __tree_.__node_handle_merge_unique(__source.__tree_);
 903     }
 904 #endif
 905
 906     _LIBCPP_INLINE_VISIBILITY
 907     void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
 908         {__tree_.swap(__s.__tree_);}
 909
 910     _LIBCPP_INLINE_VISIBILITY
 911     allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
 912     _LIBCPP_INLINE_VISIBILITY
 913     key_compare    key_comp()      const {return __tree_.value_comp();}
 914     _LIBCPP_INLINE_VISIBILITY
 915     value_compare  value_comp()    const {return __tree_.value_comp();}
 916
 917     // set operations:
 918     _LIBCPP_INLINE_VISIBILITY
 919     iterator find(const key_type& __k)             {return __tree_.find(__k);}
 920     _LIBCPP_INLINE_VISIBILITY
 921     const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
 922 #if _LIBCPP_STD_VER >= 14
 923     template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
 924     _LIBCPP_INLINE_VISIBILITY
 925     iterator
 926     find(const _K2& __k)                           {return __tree_.find(__k);}
 927     template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
 928     _LIBCPP_INLINE_VISIBILITY
 929     const_iterator
 930     find(const _K2& __k) const                     {return __tree_.find(__k);}
 931 #endif
 932
 933     _LIBCPP_INLINE_VISIBILITY
 934     size_type      count(const key_type& __k) const
 935         {return __tree_.__count_unique(__k);}
 936 #if _LIBCPP_STD_VER >= 14
 937     template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
 938     _LIBCPP_INLINE_VISIBILITY
 939     size_type
 940     count(const _K2& __k) const                    {return __tree_.__count_multi(__k);}
 941 #endif
 942
 943 #if _LIBCPP_STD_VER >= 20
 944     _LIBCPP_INLINE_VISIBILITY
 945     bool contains(const key_type& __k) const {return find(__k) != end();}
 946     template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
 947     _LIBCPP_INLINE_VISIBILITY
 948     bool
 949     contains(const _K2& __k) const { return find(__k) != end(); }
 950 #endif // _LIBCPP_STD_VER >= 20
 951
 952     _LIBCPP_INLINE_VISIBILITY
 953     iterator lower_bound(const key_type& __k)
 954         {return __tree_.lower_bound(__k);}
 955     _LIBCPP_INLINE_VISIBILITY
 956     const_iterator lower_bound(const key_type& __k) const
 957         {return __tree_.lower_bound(__k);}
 958 #if _LIBCPP_STD_VER >= 14
 959     template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
 960     _LIBCPP_INLINE_VISIBILITY
 961     iterator
 962     lower_bound(const _K2& __k)       {return __tree_.lower_bound(__k);}
 963
 964     template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
 965     _LIBCPP_INLINE_VISIBILITY
 966     const_iterator
 967     lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
 968 #endif
 969
 970     _LIBCPP_INLINE_VISIBILITY
 971     iterator upper_bound(const key_type& __k)
 972         {return __tree_.upper_bound(__k);}
 973     _LIBCPP_INLINE_VISIBILITY
 974     const_iterator upper_bound(const key_type& __k) const
 975         {return __tree_.upper_bound(__k);}
 976 #if _LIBCPP_STD_VER >= 14
 977     template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
 978     _LIBCPP_INLINE_VISIBILITY
 979     iterator
 980     upper_bound(const _K2& __k)       {return __tree_.upper_bound(__k);}
 981     template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
 982     _LIBCPP_INLINE_VISIBILITY
 983     const_iterator
 984     upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
 985 #endif
 986
 987     _LIBCPP_INLINE_VISIBILITY
 988     pair<iterator,iterator> equal_range(const key_type& __k)
 989         {return __tree_.__equal_range_unique(__k);}
 990     _LIBCPP_INLINE_VISIBILITY
 991     pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
 992         {return __tree_.__equal_range_unique(__k);}
 993 #if _LIBCPP_STD_VER >= 14
 994     template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
 995     _LIBCPP_INLINE_VISIBILITY
 996     pair<iterator,iterator>
 997     equal_range(const _K2& __k)       {return __tree_.__equal_range_multi(__k);}
 998     template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
 999     _LIBCPP_INLINE_VISIBILITY
1000     pair<const_iterator,const_iterator>
1001     equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1002 #endif
1003 };
1004
1005 #if _LIBCPP_STD_VER >= 17
1006 template<class _InputIterator,
1007          class _Compare = less<__iter_value_type<_InputIterator>>,
1008          class _Allocator = allocator<__iter_value_type<_InputIterator>>,
1009          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1010          class = enable_if_t<__is_allocator<_Allocator>::value, void>,
1011          class = enable_if_t<!__is_allocator<_Compare>::value, void>>
1012 set(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1013   -> set<__iter_value_type<_InputIterator>, _Compare, _Allocator>;
1014
1015 #if _LIBCPP_STD_VER >= 23
1016 template <ranges::input_range _Range, class _Compare = less<ranges::range_value_t<_Range>>,
1017           class _Allocator = allocator<ranges::range_value_t<_Range>>,
1018           class = enable_if_t<__is_allocator<_Allocator>::value, void>,
1019           class = enable_if_t<!__is_allocator<_Compare>::value, void>>
1020 set(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
1021   -> set<ranges::range_value_t<_Range>, _Compare, _Allocator>;
1022 #endif
1023
1024 template<class _Key, class _Compare = less<_Key>,
1025          class _Allocator = allocator<_Key>,
1026          class = enable_if_t<!__is_allocator<_Compare>::value, void>,
1027          class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1028 set(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator())
1029   -> set<_Key, _Compare, _Allocator>;
1030
1031 template<class _InputIterator, class _Allocator,
1032          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1033          class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1034 set(_InputIterator, _InputIterator, _Allocator)
1035   -> set<__iter_value_type<_InputIterator>,
1036          less<__iter_value_type<_InputIterator>>, _Allocator>;
1037
1038 #if _LIBCPP_STD_VER >= 23
1039 template <ranges::input_range _Range, class _Allocator,
1040           class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1041 set(from_range_t, _Range&&, _Allocator)
1042   -> set<ranges::range_value_t<_Range>, less<ranges::range_value_t<_Range>>, _Allocator>;
1043 #endif
1044
1045 template<class _Key, class _Allocator,
1046          class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1047 set(initializer_list<_Key>, _Allocator)
1048   -> set<_Key, less<_Key>, _Allocator>;
1049 #endif
1050
1051 #ifndef _LIBCPP_CXX03_LANG
1052
1053 template <class _Key, class _Compare, class _Allocator>
1054 set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a)
1055     : __tree_(_VSTD::move(__s.__tree_), __a)
1056 {
1057     if (__a != __s.get_allocator())
1058     {
1059         const_iterator __e = cend();
1060         while (!__s.empty())
1061             insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
1062     }
1063 }
1064
1065 #endif // _LIBCPP_CXX03_LANG
1066
1067 template <class _Key, class _Compare, class _Allocator>
1068 inline _LIBCPP_INLINE_VISIBILITY
1069 bool
1070 operator==(const set<_Key, _Compare, _Allocator>& __x,
1071            const set<_Key, _Compare, _Allocator>& __y)
1072 {
1073     return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1074 }
1075
1076 #if _LIBCPP_STD_VER <= 17
1077
1078 template <class _Key, class _Compare, class _Allocator>
1079 inline _LIBCPP_INLINE_VISIBILITY
1080 bool
1081 operator< (const set<_Key, _Compare, _Allocator>& __x,
1082            const set<_Key, _Compare, _Allocator>& __y)
1083 {
1084     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1085 }
1086
1087 template <class _Key, class _Compare, class _Allocator>
1088 inline _LIBCPP_INLINE_VISIBILITY
1089 bool
1090 operator!=(const set<_Key, _Compare, _Allocator>& __x,
1091            const set<_Key, _Compare, _Allocator>& __y)
1092 {
1093     return !(__x == __y);
1094 }
1095
1096 template <class _Key, class _Compare, class _Allocator>
1097 inline _LIBCPP_INLINE_VISIBILITY
1098 bool
1099 operator> (const set<_Key, _Compare, _Allocator>& __x,
1100            const set<_Key, _Compare, _Allocator>& __y)
1101 {
1102     return __y < __x;
1103 }
1104
1105 template <class _Key, class _Compare, class _Allocator>
1106 inline _LIBCPP_INLINE_VISIBILITY
1107 bool
1108 operator>=(const set<_Key, _Compare, _Allocator>& __x,
1109            const set<_Key, _Compare, _Allocator>& __y)
1110 {
1111     return !(__x < __y);
1112 }
1113
1114 template <class _Key, class _Compare, class _Allocator>
1115 inline _LIBCPP_INLINE_VISIBILITY
1116 bool
1117 operator<=(const set<_Key, _Compare, _Allocator>& __x,
1118            const set<_Key, _Compare, _Allocator>& __y)
1119 {
1120     return !(__y < __x);
1121 }
1122
1123 #else // _LIBCPP_STD_VER <= 17
1124
1125 template <class _Key, class _Allocator>
1126 _LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Key>
1127 operator<=>(const set<_Key, _Allocator>& __x, const set<_Key, _Allocator>& __y) {
1128     return std::lexicographical_compare_three_way(
1129         __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way<_Key, _Key>);
1130 }
1131
1132 #endif // _LIBCPP_STD_VER <= 17
1133
1134 // specialized algorithms:
1135 template <class _Key, class _Compare, class _Allocator>
1136 inline _LIBCPP_INLINE_VISIBILITY
1137 void
1138 swap(set<_Key, _Compare, _Allocator>& __x,
1139      set<_Key, _Compare, _Allocator>& __y)
1140     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1141 {
1142     __x.swap(__y);
1143 }
1144
1145 #if _LIBCPP_STD_VER >= 20
1146 template <class _Key, class _Compare, class _Allocator, class _Predicate>
1147 inline _LIBCPP_INLINE_VISIBILITY
1148     typename set<_Key, _Compare, _Allocator>::size_type
1149     erase_if(set<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {
1150   return _VSTD::__libcpp_erase_if_container(__c, __pred);
1151 }
1152 #endif
1153
1154 template <class _Key, class _Compare = less<_Key>,
1155           class _Allocator = allocator<_Key> >
1156 class _LIBCPP_TEMPLATE_VIS multiset
1157 {
1158 public:
1159     // types:
1160     typedef _Key                                     key_type;
1161     typedef key_type                                 value_type;
1162     typedef __type_identity_t<_Compare>              key_compare;
1163     typedef key_compare                              value_compare;
1164     typedef __type_identity_t<_Allocator>            allocator_type;
1165     typedef value_type&                              reference;
1166     typedef const value_type&                        const_reference;
1167
1168     static_assert((is_same<typename allocator_type::value_type, value_type>::value),
1169                   "Allocator::value_type must be same type as value_type");
1170
1171 private:
1172     typedef __tree<value_type, value_compare, allocator_type> __base;
1173     typedef allocator_traits<allocator_type>                  __alloc_traits;
1174
1175     static_assert(is_same<allocator_type, __rebind_alloc<__alloc_traits, value_type> >::value,
1176                   "[allocator.requirements] states that rebinding an allocator to the same type should result in the "
1177                   "original allocator");
1178
1179     __base __tree_;
1180
1181 public:
1182     typedef typename __base::pointer               pointer;
1183     typedef typename __base::const_pointer         const_pointer;
1184     typedef typename __base::size_type             size_type;
1185     typedef typename __base::difference_type       difference_type;
1186     typedef typename __base::const_iterator        iterator;
1187     typedef typename __base::const_iterator        const_iterator;
1188     typedef _VSTD::reverse_iterator<iterator>       reverse_iterator;
1189     typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
1190
1191 #if _LIBCPP_STD_VER >= 17
1192     typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
1193 #endif
1194
1195     template <class _Key2, class _Compare2, class _Alloc2>
1196         friend class _LIBCPP_TEMPLATE_VIS set;
1197     template <class _Key2, class _Compare2, class _Alloc2>
1198         friend class _LIBCPP_TEMPLATE_VIS multiset;
1199
1200     // construct/copy/destroy:
1201     _LIBCPP_INLINE_VISIBILITY
1202     multiset()
1203         _NOEXCEPT_(
1204             is_nothrow_default_constructible<allocator_type>::value &&
1205             is_nothrow_default_constructible<key_compare>::value &&
1206             is_nothrow_copy_constructible<key_compare>::value)
1207         : __tree_(value_compare()) {}
1208
1209     _LIBCPP_INLINE_VISIBILITY
1210     explicit multiset(const value_compare& __comp)
1211         _NOEXCEPT_(
1212             is_nothrow_default_constructible<allocator_type>::value &&
1213             is_nothrow_copy_constructible<key_compare>::value)
1214         : __tree_(__comp) {}
1215
1216     _LIBCPP_INLINE_VISIBILITY
1217     explicit multiset(const value_compare& __comp, const allocator_type& __a)
1218         : __tree_(__comp, __a) {}
1219     template <class _InputIterator>
1220         _LIBCPP_INLINE_VISIBILITY
1221         multiset(_InputIterator __f, _InputIterator __l,
1222                  const value_compare& __comp = value_compare())
1223         : __tree_(__comp)
1224         {
1225             insert(__f, __l);
1226         }
1227
1228 #if _LIBCPP_STD_VER >= 14
1229         template <class _InputIterator>
1230         _LIBCPP_INLINE_VISIBILITY
1231         multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1232             : multiset(__f, __l, key_compare(), __a) {}
1233 #endif
1234
1235     template <class _InputIterator>
1236         _LIBCPP_INLINE_VISIBILITY
1237         multiset(_InputIterator __f, _InputIterator __l,
1238                  const value_compare& __comp, const allocator_type& __a)
1239         : __tree_(__comp, __a)
1240         {
1241             insert(__f, __l);
1242         }
1243
1244 #if _LIBCPP_STD_VER >= 23
1245     template <_ContainerCompatibleRange<value_type> _Range>
1246     _LIBCPP_HIDE_FROM_ABI
1247     multiset(from_range_t, _Range&& __range, const key_compare& __comp = key_compare(),
1248         const allocator_type& __a = allocator_type())
1249       : __tree_(__comp, __a) {
1250       insert_range(std::forward<_Range>(__range));
1251     }
1252
1253     template <_ContainerCompatibleRange<value_type> _Range>
1254     _LIBCPP_HIDE_FROM_ABI
1255     multiset(from_range_t, _Range&& __range, const allocator_type& __a)
1256       : multiset(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
1257 #endif
1258
1259     _LIBCPP_INLINE_VISIBILITY
1260     multiset(const multiset& __s)
1261         : __tree_(__s.__tree_.value_comp(),
1262           __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc()))
1263         {
1264             insert(__s.begin(), __s.end());
1265         }
1266
1267     _LIBCPP_INLINE_VISIBILITY
1268     multiset& operator=(const multiset& __s)
1269         {
1270             __tree_ = __s.__tree_;
1271             return *this;
1272         }
1273
1274 #ifndef _LIBCPP_CXX03_LANG
1275     _LIBCPP_INLINE_VISIBILITY
1276     multiset(multiset&& __s)
1277         _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1278         : __tree_(_VSTD::move(__s.__tree_)) {}
1279
1280     _LIBCPP_HIDE_FROM_ABI multiset(multiset&& __s, const allocator_type& __a);
1281 #endif // _LIBCPP_CXX03_LANG
1282     _LIBCPP_INLINE_VISIBILITY
1283     explicit multiset(const allocator_type& __a)
1284         : __tree_(__a) {}
1285     _LIBCPP_INLINE_VISIBILITY
1286     multiset(const multiset& __s, const allocator_type& __a)
1287         : __tree_(__s.__tree_.value_comp(), __a)
1288         {
1289             insert(__s.begin(), __s.end());
1290         }
1291
1292 #ifndef _LIBCPP_CXX03_LANG
1293     _LIBCPP_INLINE_VISIBILITY
1294     multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
1295         : __tree_(__comp)
1296         {
1297             insert(__il.begin(), __il.end());
1298         }
1299
1300     _LIBCPP_INLINE_VISIBILITY
1301     multiset(initializer_list<value_type> __il, const value_compare& __comp,
1302         const allocator_type& __a)
1303         : __tree_(__comp, __a)
1304         {
1305             insert(__il.begin(), __il.end());
1306         }
1307
1308 #if _LIBCPP_STD_VER >= 14
1309     _LIBCPP_INLINE_VISIBILITY
1310     multiset(initializer_list<value_type> __il, const allocator_type& __a)
1311         : multiset(__il, key_compare(), __a) {}
1312 #endif
1313
1314     _LIBCPP_INLINE_VISIBILITY
1315     multiset& operator=(initializer_list<value_type> __il)
1316         {
1317             __tree_.__assign_multi(__il.begin(), __il.end());
1318             return *this;
1319         }
1320
1321     _LIBCPP_INLINE_VISIBILITY
1322     multiset& operator=(multiset&& __s)
1323         _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1324         {
1325             __tree_ = _VSTD::move(__s.__tree_);
1326             return *this;
1327         }
1328 #endif // _LIBCPP_CXX03_LANG
1329
1330     _LIBCPP_INLINE_VISIBILITY
1331     ~multiset() {
1332         static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
1333     }
1334
1335     _LIBCPP_INLINE_VISIBILITY
1336           iterator begin() _NOEXCEPT       {return __tree_.begin();}
1337     _LIBCPP_INLINE_VISIBILITY
1338     const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
1339     _LIBCPP_INLINE_VISIBILITY
1340           iterator end() _NOEXCEPT         {return __tree_.end();}
1341     _LIBCPP_INLINE_VISIBILITY
1342     const_iterator end()   const _NOEXCEPT {return __tree_.end();}
1343
1344     _LIBCPP_INLINE_VISIBILITY
1345           reverse_iterator rbegin() _NOEXCEPT
1346             {return reverse_iterator(end());}
1347     _LIBCPP_INLINE_VISIBILITY
1348     const_reverse_iterator rbegin() const _NOEXCEPT
1349         {return const_reverse_iterator(end());}
1350     _LIBCPP_INLINE_VISIBILITY
1351           reverse_iterator rend() _NOEXCEPT
1352             {return       reverse_iterator(begin());}
1353     _LIBCPP_INLINE_VISIBILITY
1354     const_reverse_iterator rend() const _NOEXCEPT
1355         {return const_reverse_iterator(begin());}
1356
1357     _LIBCPP_INLINE_VISIBILITY
1358     const_iterator cbegin()  const _NOEXCEPT {return begin();}
1359     _LIBCPP_INLINE_VISIBILITY
1360     const_iterator cend() const _NOEXCEPT {return end();}
1361     _LIBCPP_INLINE_VISIBILITY
1362     const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1363     _LIBCPP_INLINE_VISIBILITY
1364     const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1365
1366     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1367     bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1368     _LIBCPP_INLINE_VISIBILITY
1369     size_type size() const _NOEXCEPT {return __tree_.size();}
1370     _LIBCPP_INLINE_VISIBILITY
1371     size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1372
1373     // modifiers:
1374 #ifndef _LIBCPP_CXX03_LANG
1375     template <class... _Args>
1376         _LIBCPP_INLINE_VISIBILITY
1377         iterator emplace(_Args&&... __args)
1378             {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
1379     template <class... _Args>
1380         _LIBCPP_INLINE_VISIBILITY
1381         iterator emplace_hint(const_iterator __p, _Args&&... __args)
1382             {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
1383 #endif // _LIBCPP_CXX03_LANG
1384
1385     _LIBCPP_INLINE_VISIBILITY
1386     iterator insert(const value_type& __v)
1387         {return __tree_.__insert_multi(__v);}
1388     _LIBCPP_INLINE_VISIBILITY
1389     iterator insert(const_iterator __p, const value_type& __v)
1390         {return __tree_.__insert_multi(__p, __v);}
1391
1392     template <class _InputIterator>
1393         _LIBCPP_INLINE_VISIBILITY
1394         void insert(_InputIterator __f, _InputIterator __l)
1395         {
1396             for (const_iterator __e = cend(); __f != __l; ++__f)
1397                 __tree_.__insert_multi(__e, *__f);
1398         }
1399
1400 #if _LIBCPP_STD_VER >= 23
1401     template <_ContainerCompatibleRange<value_type> _Range>
1402     _LIBCPP_HIDE_FROM_ABI
1403     void insert_range(_Range&& __range) {
1404       const_iterator __end = cend();
1405       for (auto&& __element : __range) {
1406         __tree_.__insert_multi(__end, std::forward<decltype(__element)>(__element));
1407       }
1408     }
1409 #endif
1410
1411 #ifndef _LIBCPP_CXX03_LANG
1412     _LIBCPP_INLINE_VISIBILITY
1413     iterator insert(value_type&& __v)
1414         {return __tree_.__insert_multi(_VSTD::move(__v));}
1415
1416     _LIBCPP_INLINE_VISIBILITY
1417     iterator insert(const_iterator __p, value_type&& __v)
1418         {return __tree_.__insert_multi(__p, _VSTD::move(__v));}
1419
1420     _LIBCPP_INLINE_VISIBILITY
1421     void insert(initializer_list<value_type> __il)
1422         {insert(__il.begin(), __il.end());}
1423 #endif // _LIBCPP_CXX03_LANG
1424
1425     _LIBCPP_INLINE_VISIBILITY
1426     iterator  erase(const_iterator __p) {return __tree_.erase(__p);}
1427     _LIBCPP_INLINE_VISIBILITY
1428     size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1429     _LIBCPP_INLINE_VISIBILITY
1430     iterator  erase(const_iterator __f, const_iterator __l)
1431         {return __tree_.erase(__f, __l);}
1432     _LIBCPP_INLINE_VISIBILITY
1433     void clear() _NOEXCEPT {__tree_.clear();}
1434
1435 #if _LIBCPP_STD_VER >= 17
1436     _LIBCPP_INLINE_VISIBILITY
1437     iterator insert(node_type&& __nh)
1438     {
1439         _LIBCPP_ASSERT_UNCATEGORIZED(__nh.empty() || __nh.get_allocator() == get_allocator(),
1440             "node_type with incompatible allocator passed to multiset::insert()");
1441         return __tree_.template __node_handle_insert_multi<node_type>(
1442             _VSTD::move(__nh));
1443     }
1444     _LIBCPP_INLINE_VISIBILITY
1445     iterator insert(const_iterator __hint, node_type&& __nh)
1446     {
1447         _LIBCPP_ASSERT_UNCATEGORIZED(__nh.empty() || __nh.get_allocator() == get_allocator(),
1448             "node_type with incompatible allocator passed to multiset::insert()");
1449         return __tree_.template __node_handle_insert_multi<node_type>(
1450             __hint, _VSTD::move(__nh));
1451     }
1452     _LIBCPP_INLINE_VISIBILITY
1453     node_type extract(key_type const& __key)
1454     {
1455         return __tree_.template __node_handle_extract<node_type>(__key);
1456     }
1457     _LIBCPP_INLINE_VISIBILITY
1458     node_type extract(const_iterator __it)
1459     {
1460         return __tree_.template __node_handle_extract<node_type>(__it);
1461     }
1462     template <class _Compare2>
1463     _LIBCPP_INLINE_VISIBILITY
1464     void merge(multiset<key_type, _Compare2, allocator_type>& __source)
1465     {
1466         _LIBCPP_ASSERT_UNCATEGORIZED(__source.get_allocator() == get_allocator(),
1467                        "merging container with incompatible allocator");
1468         __tree_.__node_handle_merge_multi(__source.__tree_);
1469     }
1470     template <class _Compare2>
1471     _LIBCPP_INLINE_VISIBILITY
1472     void merge(multiset<key_type, _Compare2, allocator_type>&& __source)
1473     {
1474         _LIBCPP_ASSERT_UNCATEGORIZED(__source.get_allocator() == get_allocator(),
1475                        "merging container with incompatible allocator");
1476         __tree_.__node_handle_merge_multi(__source.__tree_);
1477     }
1478     template <class _Compare2>
1479     _LIBCPP_INLINE_VISIBILITY
1480     void merge(set<key_type, _Compare2, allocator_type>& __source)
1481     {
1482         _LIBCPP_ASSERT_UNCATEGORIZED(__source.get_allocator() == get_allocator(),
1483                        "merging container with incompatible allocator");
1484         __tree_.__node_handle_merge_multi(__source.__tree_);
1485     }
1486     template <class _Compare2>
1487     _LIBCPP_INLINE_VISIBILITY
1488     void merge(set<key_type, _Compare2, allocator_type>&& __source)
1489     {
1490         _LIBCPP_ASSERT_UNCATEGORIZED(__source.get_allocator() == get_allocator(),
1491                        "merging container with incompatible allocator");
1492         __tree_.__node_handle_merge_multi(__source.__tree_);
1493     }
1494 #endif
1495
1496     _LIBCPP_INLINE_VISIBILITY
1497     void swap(multiset& __s)
1498         _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1499         {__tree_.swap(__s.__tree_);}
1500
1501     _LIBCPP_INLINE_VISIBILITY
1502     allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
1503     _LIBCPP_INLINE_VISIBILITY
1504     key_compare    key_comp()      const {return __tree_.value_comp();}
1505     _LIBCPP_INLINE_VISIBILITY
1506     value_compare  value_comp()    const {return __tree_.value_comp();}
1507
1508     // set operations:
1509     _LIBCPP_INLINE_VISIBILITY
1510     iterator find(const key_type& __k)             {return __tree_.find(__k);}
1511     _LIBCPP_INLINE_VISIBILITY
1512     const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1513 #if _LIBCPP_STD_VER >= 14
1514     template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1515     _LIBCPP_INLINE_VISIBILITY
1516     iterator
1517     find(const _K2& __k)                           {return __tree_.find(__k);}
1518     template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1519     _LIBCPP_INLINE_VISIBILITY
1520     const_iterator
1521     find(const _K2& __k) const                     {return __tree_.find(__k);}
1522 #endif
1523
1524     _LIBCPP_INLINE_VISIBILITY
1525     size_type      count(const key_type& __k) const
1526         {return __tree_.__count_multi(__k);}
1527 #if _LIBCPP_STD_VER >= 14
1528     template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1529     _LIBCPP_INLINE_VISIBILITY
1530     size_type
1531     count(const _K2& __k) const            {return __tree_.__count_multi(__k);}
1532 #endif
1533
1534 #if _LIBCPP_STD_VER >= 20
1535     _LIBCPP_INLINE_VISIBILITY
1536     bool contains(const key_type& __k) const {return find(__k) != end();}
1537     template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1538     _LIBCPP_INLINE_VISIBILITY
1539      bool
1540     contains(const _K2& __k) const { return find(__k) != end(); }
1541 #endif // _LIBCPP_STD_VER >= 20
1542
1543     _LIBCPP_INLINE_VISIBILITY
1544     iterator lower_bound(const key_type& __k)
1545         {return __tree_.lower_bound(__k);}
1546     _LIBCPP_INLINE_VISIBILITY
1547     const_iterator lower_bound(const key_type& __k) const
1548             {return __tree_.lower_bound(__k);}
1549 #if _LIBCPP_STD_VER >= 14
1550     template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1551     _LIBCPP_INLINE_VISIBILITY
1552     iterator
1553     lower_bound(const _K2& __k)       {return __tree_.lower_bound(__k);}
1554
1555     template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1556     _LIBCPP_INLINE_VISIBILITY
1557     const_iterator
1558     lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1559 #endif
1560
1561     _LIBCPP_INLINE_VISIBILITY
1562     iterator upper_bound(const key_type& __k)
1563             {return __tree_.upper_bound(__k);}
1564     _LIBCPP_INLINE_VISIBILITY
1565     const_iterator upper_bound(const key_type& __k) const
1566             {return __tree_.upper_bound(__k);}
1567 #if _LIBCPP_STD_VER >= 14
1568     template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1569     _LIBCPP_INLINE_VISIBILITY
1570     iterator
1571     upper_bound(const _K2& __k)       {return __tree_.upper_bound(__k);}
1572     template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1573     _LIBCPP_INLINE_VISIBILITY
1574     const_iterator
1575     upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1576 #endif
1577
1578     _LIBCPP_INLINE_VISIBILITY
1579     pair<iterator,iterator>             equal_range(const key_type& __k)
1580             {return __tree_.__equal_range_multi(__k);}
1581     _LIBCPP_INLINE_VISIBILITY
1582     pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1583             {return __tree_.__equal_range_multi(__k);}
1584 #if _LIBCPP_STD_VER >= 14
1585     template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1586     _LIBCPP_INLINE_VISIBILITY
1587     pair<iterator,iterator>
1588     equal_range(const _K2& __k)       {return __tree_.__equal_range_multi(__k);}
1589     template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1590     _LIBCPP_INLINE_VISIBILITY
1591     pair<const_iterator,const_iterator>
1592     equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1593 #endif
1594 };
1595
1596 #if _LIBCPP_STD_VER >= 17
1597 template<class _InputIterator,
1598          class _Compare = less<__iter_value_type<_InputIterator>>,
1599          class _Allocator = allocator<__iter_value_type<_InputIterator>>,
1600          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1601          class = enable_if_t<__is_allocator<_Allocator>::value, void>,
1602          class = enable_if_t<!__is_allocator<_Compare>::value, void>>
1603 multiset(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1604   -> multiset<__iter_value_type<_InputIterator>, _Compare, _Allocator>;
1605
1606 #if _LIBCPP_STD_VER >= 23
1607 template <ranges::input_range _Range, class _Compare = less<ranges::range_value_t<_Range>>,
1608           class _Allocator = allocator<ranges::range_value_t<_Range>>,
1609           class = enable_if_t<__is_allocator<_Allocator>::value, void>,
1610           class = enable_if_t<!__is_allocator<_Compare>::value, void>>
1611 multiset(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
1612   -> multiset<ranges::range_value_t<_Range>, _Compare, _Allocator>;
1613 #endif
1614
1615 template<class _Key, class _Compare = less<_Key>,
1616          class _Allocator = allocator<_Key>,
1617          class = enable_if_t<__is_allocator<_Allocator>::value, void>,
1618          class = enable_if_t<!__is_allocator<_Compare>::value, void>>
1619 multiset(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator())
1620   -> multiset<_Key, _Compare, _Allocator>;
1621
1622 template<class _InputIterator, class _Allocator,
1623          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1624          class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1625 multiset(_InputIterator, _InputIterator, _Allocator)
1626   -> multiset<__iter_value_type<_InputIterator>,
1627          less<__iter_value_type<_InputIterator>>, _Allocator>;
1628
1629 #if _LIBCPP_STD_VER >= 23
1630 template <ranges::input_range _Range, class _Allocator,
1631           class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1632 multiset(from_range_t, _Range&&, _Allocator)
1633   -> multiset<ranges::range_value_t<_Range>, less<ranges::range_value_t<_Range>>, _Allocator>;
1634 #endif
1635
1636 template<class _Key, class _Allocator,
1637          class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1638 multiset(initializer_list<_Key>, _Allocator)
1639   -> multiset<_Key, less<_Key>, _Allocator>;
1640 #endif
1641
1642 #ifndef _LIBCPP_CXX03_LANG
1643
1644 template <class _Key, class _Compare, class _Allocator>
1645 multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a)
1646     : __tree_(_VSTD::move(__s.__tree_), __a)
1647 {
1648     if (__a != __s.get_allocator())
1649     {
1650         const_iterator __e = cend();
1651         while (!__s.empty())
1652             insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
1653     }
1654 }
1655
1656 #endif // _LIBCPP_CXX03_LANG
1657
1658 template <class _Key, class _Compare, class _Allocator>
1659 inline _LIBCPP_INLINE_VISIBILITY
1660 bool
1661 operator==(const multiset<_Key, _Compare, _Allocator>& __x,
1662            const multiset<_Key, _Compare, _Allocator>& __y)
1663 {
1664     return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1665 }
1666
1667 #if _LIBCPP_STD_VER <= 17
1668
1669 template <class _Key, class _Compare, class _Allocator>
1670 inline _LIBCPP_INLINE_VISIBILITY
1671 bool
1672 operator< (const multiset<_Key, _Compare, _Allocator>& __x,
1673            const multiset<_Key, _Compare, _Allocator>& __y)
1674 {
1675     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1676 }
1677
1678 template <class _Key, class _Compare, class _Allocator>
1679 inline _LIBCPP_INLINE_VISIBILITY
1680 bool
1681 operator!=(const multiset<_Key, _Compare, _Allocator>& __x,
1682            const multiset<_Key, _Compare, _Allocator>& __y)
1683 {
1684     return !(__x == __y);
1685 }
1686
1687 template <class _Key, class _Compare, class _Allocator>
1688 inline _LIBCPP_INLINE_VISIBILITY
1689 bool
1690 operator> (const multiset<_Key, _Compare, _Allocator>& __x,
1691            const multiset<_Key, _Compare, _Allocator>& __y)
1692 {
1693     return __y < __x;
1694 }
1695
1696 template <class _Key, class _Compare, class _Allocator>
1697 inline _LIBCPP_INLINE_VISIBILITY
1698 bool
1699 operator>=(const multiset<_Key, _Compare, _Allocator>& __x,
1700            const multiset<_Key, _Compare, _Allocator>& __y)
1701 {
1702     return !(__x < __y);
1703 }
1704
1705 template <class _Key, class _Compare, class _Allocator>
1706 inline _LIBCPP_INLINE_VISIBILITY
1707 bool
1708 operator<=(const multiset<_Key, _Compare, _Allocator>& __x,
1709            const multiset<_Key, _Compare, _Allocator>& __y)
1710 {
1711     return !(__y < __x);
1712 }
1713
1714 #else // _LIBCPP_STD_VER <= 17
1715
1716 template <class _Key, class _Allocator>
1717 _LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Key>
1718 operator<=>(const multiset<_Key, _Allocator>& __x, const multiset<_Key, _Allocator>& __y) {
1719     return std::lexicographical_compare_three_way(
1720         __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way<_Key, _Key>);
1721 }
1722
1723 #endif // _LIBCPP_STD_VER <= 17
1724
1725 template <class _Key, class _Compare, class _Allocator>
1726 inline _LIBCPP_INLINE_VISIBILITY
1727 void
1728 swap(multiset<_Key, _Compare, _Allocator>& __x,
1729      multiset<_Key, _Compare, _Allocator>& __y)
1730     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1731 {
1732     __x.swap(__y);
1733 }
1734
1735 #if _LIBCPP_STD_VER >= 20
1736 template <class _Key, class _Compare, class _Allocator, class _Predicate>
1737 inline _LIBCPP_INLINE_VISIBILITY
1738     typename multiset<_Key, _Compare, _Allocator>::size_type
1739     erase_if(multiset<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {
1740   return _VSTD::__libcpp_erase_if_container(__c, __pred);
1741 }
1742 #endif
1743
1744 _LIBCPP_END_NAMESPACE_STD
1745
1746 #if _LIBCPP_STD_VER >= 17
1747 _LIBCPP_BEGIN_NAMESPACE_STD
1748 namespace pmr {
1749 template <class _KeyT, class _CompareT = std::less<_KeyT>>
1750 using set _LIBCPP_AVAILABILITY_PMR = std::set<_KeyT, _CompareT, polymorphic_allocator<_KeyT>>;
1751
1752 template <class _KeyT, class _CompareT = std::less<_KeyT>>
1753 using multiset _LIBCPP_AVAILABILITY_PMR = std::multiset<_KeyT, _CompareT, polymorphic_allocator<_KeyT>>;
1754 } // namespace pmr
1755 _LIBCPP_END_NAMESPACE_STD
1756 #endif
1757
1758 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
1759 #  include <concepts>
1760 #  include <cstdlib>
1761 #  include <functional>
1762 #  include <iterator>
1763 #  include <stdexcept>
1764 #  include <type_traits>
1765 #endif
1766
1767 #endif // _LIBCPP_SET