contrib/libc++/include/set

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