contrib/llvm-project/libcxx/include/set

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