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