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