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