contrib/libc++/include/set

   1 // -*- C++ -*-
   2 //===---------------------------- set -------------------------------------===//
   3 //
   4 //                     The LLVM Compiler Infrastructure
   5 //
   6 // This file is dual licensed under the MIT and the University of Illinois Open
   7 // Source Licenses. See LICENSE.TXT for details.
   8 //
   9 //===----------------------------------------------------------------------===//
  10
  11 #ifndef _LIBCPP_SET
  12 #define _LIBCPP_SET
  13
  14 /*
  15
  16     set synopsis
  17
  18 namespace std
  19 {
  20
  21 template <class Key, class Compare = less<Key>,
  22           class Allocator = allocator<Key>>
  23 class set
  24 {
  25 public:
  26     // types:
  27     typedef Key                                      key_type;
  28     typedef key_type                                 value_type;
  29     typedef Compare                                  key_compare;
  30     typedef key_compare                              value_compare;
  31     typedef Allocator                                allocator_type;
  32     typedef typename allocator_type::reference       reference;
  33     typedef typename allocator_type::const_reference const_reference;
  34     typedef typename allocator_type::size_type       size_type;
  35     typedef typename allocator_type::difference_type difference_type;
  36     typedef typename allocator_type::pointer         pointer;
  37     typedef typename allocator_type::const_pointer   const_pointer;
  38
  39     typedef implementation-defined                   iterator;
  40     typedef implementation-defined                   const_iterator;
  41     typedef std::reverse_iterator<iterator>          reverse_iterator;
  42     typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
  43
  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 private:
 413     typedef __tree<value_type, value_compare, allocator_type> __base;
 414     typedef allocator_traits<allocator_type>                  __alloc_traits;
 415     typedef typename __base::__node_holder                    __node_holder;
 416
 417     __base __tree_;
 418
 419 public:
 420     typedef typename __base::pointer               pointer;
 421     typedef typename __base::const_pointer         const_pointer;
 422     typedef typename __base::size_type             size_type;
 423     typedef typename __base::difference_type       difference_type;
 424     typedef typename __base::const_iterator        iterator;
 425     typedef typename __base::const_iterator        const_iterator;
 426     typedef _VSTD::reverse_iterator<iterator>       reverse_iterator;
 427     typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
 428
 429     _LIBCPP_INLINE_VISIBILITY
 430     set()
 431         _NOEXCEPT_(
 432             is_nothrow_default_constructible<allocator_type>::value &&
 433             is_nothrow_default_constructible<key_compare>::value &&
 434             is_nothrow_copy_constructible<key_compare>::value)
 435         : __tree_(value_compare()) {}
 436
 437     _LIBCPP_INLINE_VISIBILITY
 438     explicit set(const value_compare& __comp)
 439         _NOEXCEPT_(
 440             is_nothrow_default_constructible<allocator_type>::value &&
 441             is_nothrow_copy_constructible<key_compare>::value)
 442         : __tree_(__comp) {}
 443
 444     _LIBCPP_INLINE_VISIBILITY
 445     explicit set(const value_compare& __comp, const allocator_type& __a)
 446         : __tree_(__comp, __a) {}
 447     template <class _InputIterator>
 448         _LIBCPP_INLINE_VISIBILITY
 449         set(_InputIterator __f, _InputIterator __l,
 450             const value_compare& __comp = value_compare())
 451         : __tree_(__comp)
 452         {
 453             insert(__f, __l);
 454         }
 455
 456     template <class _InputIterator>
 457         _LIBCPP_INLINE_VISIBILITY
 458         set(_InputIterator __f, _InputIterator __l, const value_compare& __comp,
 459             const allocator_type& __a)
 460         : __tree_(__comp, __a)
 461         {
 462             insert(__f, __l);
 463         }
 464
 465 #if _LIBCPP_STD_VER > 11
 466         template <class _InputIterator>
 467         _LIBCPP_INLINE_VISIBILITY
 468         set(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
 469             : set(__f, __l, key_compare(), __a) {}
 470 #endif
 471
 472     _LIBCPP_INLINE_VISIBILITY
 473     set(const set& __s)
 474         : __tree_(__s.__tree_)
 475         {
 476             insert(__s.begin(), __s.end());
 477         }
 478
 479     _LIBCPP_INLINE_VISIBILITY
 480     set& operator=(const set& __s)
 481         {
 482             __tree_ = __s.__tree_;
 483             return *this;
 484         }
 485
 486 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 487     _LIBCPP_INLINE_VISIBILITY
 488     set(set&& __s)
 489         _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
 490         : __tree_(_VSTD::move(__s.__tree_)) {}
 491 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 492
 493     _LIBCPP_INLINE_VISIBILITY
 494     explicit set(const allocator_type& __a)
 495         : __tree_(__a) {}
 496
 497     _LIBCPP_INLINE_VISIBILITY
 498     set(const set& __s, const allocator_type& __a)
 499         : __tree_(__s.__tree_.value_comp(), __a)
 500         {
 501             insert(__s.begin(), __s.end());
 502         }
 503
 504 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 505     set(set&& __s, const allocator_type& __a);
 506 #endif
 507
 508 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 509     _LIBCPP_INLINE_VISIBILITY
 510     set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
 511         : __tree_(__comp)
 512         {
 513             insert(__il.begin(), __il.end());
 514         }
 515
 516     _LIBCPP_INLINE_VISIBILITY
 517     set(initializer_list<value_type> __il, const value_compare& __comp,
 518         const allocator_type& __a)
 519         : __tree_(__comp, __a)
 520         {
 521             insert(__il.begin(), __il.end());
 522         }
 523
 524 #if _LIBCPP_STD_VER > 11
 525     _LIBCPP_INLINE_VISIBILITY
 526     set(initializer_list<value_type> __il, const allocator_type& __a)
 527         : set(__il, key_compare(), __a) {}
 528 #endif
 529
 530     _LIBCPP_INLINE_VISIBILITY
 531     set& operator=(initializer_list<value_type> __il)
 532         {
 533             __tree_.__assign_unique(__il.begin(), __il.end());
 534             return *this;
 535         }
 536 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 537
 538 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 539     _LIBCPP_INLINE_VISIBILITY
 540     set& operator=(set&& __s)
 541         _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
 542         {
 543             __tree_ = _VSTD::move(__s.__tree_);
 544             return *this;
 545         }
 546 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 547
 548     _LIBCPP_INLINE_VISIBILITY
 549           iterator begin() _NOEXCEPT       {return __tree_.begin();}
 550     _LIBCPP_INLINE_VISIBILITY
 551     const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
 552     _LIBCPP_INLINE_VISIBILITY
 553           iterator end() _NOEXCEPT         {return __tree_.end();}
 554     _LIBCPP_INLINE_VISIBILITY
 555     const_iterator end()   const _NOEXCEPT {return __tree_.end();}
 556
 557     _LIBCPP_INLINE_VISIBILITY
 558           reverse_iterator rbegin() _NOEXCEPT
 559             {return reverse_iterator(end());}
 560     _LIBCPP_INLINE_VISIBILITY
 561     const_reverse_iterator rbegin() const _NOEXCEPT
 562         {return const_reverse_iterator(end());}
 563     _LIBCPP_INLINE_VISIBILITY
 564           reverse_iterator rend() _NOEXCEPT
 565             {return reverse_iterator(begin());}
 566     _LIBCPP_INLINE_VISIBILITY
 567     const_reverse_iterator rend() const _NOEXCEPT
 568         {return const_reverse_iterator(begin());}
 569
 570     _LIBCPP_INLINE_VISIBILITY
 571     const_iterator cbegin()  const _NOEXCEPT {return begin();}
 572     _LIBCPP_INLINE_VISIBILITY
 573     const_iterator cend() const _NOEXCEPT {return end();}
 574     _LIBCPP_INLINE_VISIBILITY
 575     const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
 576     _LIBCPP_INLINE_VISIBILITY
 577     const_reverse_iterator crend() const _NOEXCEPT {return rend();}
 578
 579     _LIBCPP_INLINE_VISIBILITY
 580     bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
 581     _LIBCPP_INLINE_VISIBILITY
 582     size_type size() const _NOEXCEPT {return __tree_.size();}
 583     _LIBCPP_INLINE_VISIBILITY
 584     size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
 585
 586     // modifiers:
 587 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
 588     template <class... _Args>
 589         _LIBCPP_INLINE_VISIBILITY
 590         pair<iterator, bool> emplace(_Args&&... __args)
 591             {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
 592     template <class... _Args>
 593         _LIBCPP_INLINE_VISIBILITY
 594         iterator emplace_hint(const_iterator __p, _Args&&... __args)
 595             {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);}
 596 #endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
 597     _LIBCPP_INLINE_VISIBILITY
 598     pair<iterator,bool> insert(const value_type& __v)
 599         {return __tree_.__insert_unique(__v);}
 600 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 601     _LIBCPP_INLINE_VISIBILITY
 602     pair<iterator,bool> insert(value_type&& __v)
 603         {return __tree_.__insert_unique(_VSTD::move(__v));}
 604 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 605     _LIBCPP_INLINE_VISIBILITY
 606     iterator insert(const_iterator __p, const value_type& __v)
 607         {return __tree_.__insert_unique(__p, __v);}
 608 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 609     _LIBCPP_INLINE_VISIBILITY
 610     iterator insert(const_iterator __p, value_type&& __v)
 611         {return __tree_.__insert_unique(__p, _VSTD::move(__v));}
 612 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 613     template <class _InputIterator>
 614         _LIBCPP_INLINE_VISIBILITY
 615         void insert(_InputIterator __f, _InputIterator __l)
 616         {
 617             for (const_iterator __e = cend(); __f != __l; ++__f)
 618                 __tree_.__insert_unique(__e, *__f);
 619         }
 620
 621 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 622     _LIBCPP_INLINE_VISIBILITY
 623     void insert(initializer_list<value_type> __il)
 624         {insert(__il.begin(), __il.end());}
 625 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 626
 627     _LIBCPP_INLINE_VISIBILITY
 628     iterator  erase(const_iterator __p) {return __tree_.erase(__p);}
 629     _LIBCPP_INLINE_VISIBILITY
 630     size_type erase(const key_type& __k)
 631         {return __tree_.__erase_unique(__k);}
 632     _LIBCPP_INLINE_VISIBILITY
 633     iterator  erase(const_iterator __f, const_iterator __l)
 634         {return __tree_.erase(__f, __l);}
 635     _LIBCPP_INLINE_VISIBILITY
 636     void clear() _NOEXCEPT {__tree_.clear();}
 637
 638     _LIBCPP_INLINE_VISIBILITY
 639     void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
 640         {__tree_.swap(__s.__tree_);}
 641
 642     _LIBCPP_INLINE_VISIBILITY
 643     allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
 644     _LIBCPP_INLINE_VISIBILITY
 645     key_compare    key_comp()      const {return __tree_.value_comp();}
 646     _LIBCPP_INLINE_VISIBILITY
 647     value_compare  value_comp()    const {return __tree_.value_comp();}
 648
 649     // set operations:
 650     _LIBCPP_INLINE_VISIBILITY
 651     iterator find(const key_type& __k)             {return __tree_.find(__k);}
 652     _LIBCPP_INLINE_VISIBILITY
 653     const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
 654 #if _LIBCPP_STD_VER > 11
 655     template <typename _K2>
 656     _LIBCPP_INLINE_VISIBILITY
 657     typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
 658     find(const _K2& __k)                           {return __tree_.find(__k);}
 659     template <typename _K2>
 660     _LIBCPP_INLINE_VISIBILITY
 661     typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
 662     find(const _K2& __k) const                     {return __tree_.find(__k);}
 663 #endif
 664
 665     _LIBCPP_INLINE_VISIBILITY
 666     size_type      count(const key_type& __k) const
 667         {return __tree_.__count_unique(__k);}
 668 #if _LIBCPP_STD_VER > 11
 669     template <typename _K2>
 670     _LIBCPP_INLINE_VISIBILITY
 671     typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
 672     count(const _K2& __k)                  {return __tree_.__count_unique(__k);}
 673 #endif
 674     _LIBCPP_INLINE_VISIBILITY
 675     iterator lower_bound(const key_type& __k)
 676         {return __tree_.lower_bound(__k);}
 677     _LIBCPP_INLINE_VISIBILITY
 678     const_iterator lower_bound(const key_type& __k) const
 679         {return __tree_.lower_bound(__k);}
 680 #if _LIBCPP_STD_VER > 11
 681     template <typename _K2>
 682     _LIBCPP_INLINE_VISIBILITY
 683     typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
 684     lower_bound(const _K2& __k)       {return __tree_.lower_bound(__k);}
 685
 686     template <typename _K2>
 687     _LIBCPP_INLINE_VISIBILITY
 688     typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
 689     lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
 690 #endif
 691
 692     _LIBCPP_INLINE_VISIBILITY
 693     iterator upper_bound(const key_type& __k)
 694         {return __tree_.upper_bound(__k);}
 695     _LIBCPP_INLINE_VISIBILITY
 696     const_iterator upper_bound(const key_type& __k) const
 697         {return __tree_.upper_bound(__k);}
 698 #if _LIBCPP_STD_VER > 11
 699     template <typename _K2>
 700     _LIBCPP_INLINE_VISIBILITY
 701     typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
 702     upper_bound(const _K2& __k)       {return __tree_.upper_bound(__k);}
 703     template <typename _K2>
 704     _LIBCPP_INLINE_VISIBILITY
 705     typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
 706     upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
 707 #endif
 708
 709     _LIBCPP_INLINE_VISIBILITY
 710     pair<iterator,iterator> equal_range(const key_type& __k)
 711         {return __tree_.__equal_range_unique(__k);}
 712     _LIBCPP_INLINE_VISIBILITY
 713     pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
 714         {return __tree_.__equal_range_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,pair<iterator,iterator>>::type
 719     equal_range(const _K2& __k)       {return __tree_.__equal_range_unique(__k);}
 720     template <typename _K2>
 721     _LIBCPP_INLINE_VISIBILITY
 722     typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
 723     equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);}
 724 #endif
 725 };
 726
 727 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 728
 729 template <class _Key, class _Compare, class _Allocator>
 730 set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a)
 731     : __tree_(_VSTD::move(__s.__tree_), __a)
 732 {
 733     if (__a != __s.get_allocator())
 734     {
 735         const_iterator __e = cend();
 736         while (!__s.empty())
 737             insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
 738     }
 739 }
 740
 741 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 742
 743 template <class _Key, class _Compare, class _Allocator>
 744 inline _LIBCPP_INLINE_VISIBILITY
 745 bool
 746 operator==(const set<_Key, _Compare, _Allocator>& __x,
 747            const set<_Key, _Compare, _Allocator>& __y)
 748 {
 749     return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
 750 }
 751
 752 template <class _Key, class _Compare, class _Allocator>
 753 inline _LIBCPP_INLINE_VISIBILITY
 754 bool
 755 operator< (const set<_Key, _Compare, _Allocator>& __x,
 756            const set<_Key, _Compare, _Allocator>& __y)
 757 {
 758     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
 759 }
 760
 761 template <class _Key, class _Compare, class _Allocator>
 762 inline _LIBCPP_INLINE_VISIBILITY
 763 bool
 764 operator!=(const set<_Key, _Compare, _Allocator>& __x,
 765            const set<_Key, _Compare, _Allocator>& __y)
 766 {
 767     return !(__x == __y);
 768 }
 769
 770 template <class _Key, class _Compare, class _Allocator>
 771 inline _LIBCPP_INLINE_VISIBILITY
 772 bool
 773 operator> (const set<_Key, _Compare, _Allocator>& __x,
 774            const set<_Key, _Compare, _Allocator>& __y)
 775 {
 776     return __y < __x;
 777 }
 778
 779 template <class _Key, class _Compare, class _Allocator>
 780 inline _LIBCPP_INLINE_VISIBILITY
 781 bool
 782 operator>=(const set<_Key, _Compare, _Allocator>& __x,
 783            const set<_Key, _Compare, _Allocator>& __y)
 784 {
 785     return !(__x < __y);
 786 }
 787
 788 template <class _Key, class _Compare, class _Allocator>
 789 inline _LIBCPP_INLINE_VISIBILITY
 790 bool
 791 operator<=(const set<_Key, _Compare, _Allocator>& __x,
 792            const set<_Key, _Compare, _Allocator>& __y)
 793 {
 794     return !(__y < __x);
 795 }
 796
 797 // specialized algorithms:
 798 template <class _Key, class _Compare, class _Allocator>
 799 inline _LIBCPP_INLINE_VISIBILITY
 800 void
 801 swap(set<_Key, _Compare, _Allocator>& __x,
 802      set<_Key, _Compare, _Allocator>& __y)
 803     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
 804 {
 805     __x.swap(__y);
 806 }
 807
 808 template <class _Key, class _Compare = less<_Key>,
 809           class _Allocator = allocator<_Key> >
 810 class _LIBCPP_TYPE_VIS_ONLY multiset
 811 {
 812 public:
 813     // types:
 814     typedef _Key                                      key_type;
 815     typedef key_type                                 value_type;
 816     typedef _Compare                                  key_compare;
 817     typedef key_compare                              value_compare;
 818     typedef _Allocator                                allocator_type;
 819     typedef value_type&                              reference;
 820     typedef const value_type&                        const_reference;
 821
 822 private:
 823     typedef __tree<value_type, value_compare, allocator_type> __base;
 824     typedef allocator_traits<allocator_type>                  __alloc_traits;
 825     typedef typename __base::__node_holder                    __node_holder;
 826
 827     __base __tree_;
 828
 829 public:
 830     typedef typename __base::pointer               pointer;
 831     typedef typename __base::const_pointer         const_pointer;
 832     typedef typename __base::size_type             size_type;
 833     typedef typename __base::difference_type       difference_type;
 834     typedef typename __base::const_iterator        iterator;
 835     typedef typename __base::const_iterator        const_iterator;
 836     typedef _VSTD::reverse_iterator<iterator>       reverse_iterator;
 837     typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
 838
 839     // construct/copy/destroy:
 840     _LIBCPP_INLINE_VISIBILITY
 841     multiset()
 842         _NOEXCEPT_(
 843             is_nothrow_default_constructible<allocator_type>::value &&
 844             is_nothrow_default_constructible<key_compare>::value &&
 845             is_nothrow_copy_constructible<key_compare>::value)
 846         : __tree_(value_compare()) {}
 847
 848     _LIBCPP_INLINE_VISIBILITY
 849     explicit multiset(const value_compare& __comp)
 850         _NOEXCEPT_(
 851             is_nothrow_default_constructible<allocator_type>::value &&
 852             is_nothrow_copy_constructible<key_compare>::value)
 853         : __tree_(__comp) {}
 854
 855     _LIBCPP_INLINE_VISIBILITY
 856     explicit multiset(const value_compare& __comp, const allocator_type& __a)
 857         : __tree_(__comp, __a) {}
 858     template <class _InputIterator>
 859         _LIBCPP_INLINE_VISIBILITY
 860         multiset(_InputIterator __f, _InputIterator __l,
 861                  const value_compare& __comp = value_compare())
 862         : __tree_(__comp)
 863         {
 864             insert(__f, __l);
 865         }
 866
 867 #if _LIBCPP_STD_VER > 11
 868         template <class _InputIterator>
 869         _LIBCPP_INLINE_VISIBILITY
 870         multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
 871             : multiset(__f, __l, key_compare(), __a) {}
 872 #endif
 873
 874     template <class _InputIterator>
 875         _LIBCPP_INLINE_VISIBILITY
 876         multiset(_InputIterator __f, _InputIterator __l,
 877                  const value_compare& __comp, const allocator_type& __a)
 878         : __tree_(__comp, __a)
 879         {
 880             insert(__f, __l);
 881         }
 882
 883     _LIBCPP_INLINE_VISIBILITY
 884     multiset(const multiset& __s)
 885         : __tree_(__s.__tree_.value_comp(),
 886           __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc()))
 887         {
 888             insert(__s.begin(), __s.end());
 889         }
 890
 891     _LIBCPP_INLINE_VISIBILITY
 892     multiset& operator=(const multiset& __s)
 893         {
 894             __tree_ = __s.__tree_;
 895             return *this;
 896         }
 897
 898 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 899     _LIBCPP_INLINE_VISIBILITY
 900     multiset(multiset&& __s)
 901         _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
 902         : __tree_(_VSTD::move(__s.__tree_)) {}
 903 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 904     _LIBCPP_INLINE_VISIBILITY
 905     explicit multiset(const allocator_type& __a)
 906         : __tree_(__a) {}
 907     _LIBCPP_INLINE_VISIBILITY
 908     multiset(const multiset& __s, const allocator_type& __a)
 909         : __tree_(__s.__tree_.value_comp(), __a)
 910         {
 911             insert(__s.begin(), __s.end());
 912         }
 913 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 914     multiset(multiset&& __s, const allocator_type& __a);
 915 #endif
 916
 917 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 918     _LIBCPP_INLINE_VISIBILITY
 919     multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
 920         : __tree_(__comp)
 921         {
 922             insert(__il.begin(), __il.end());
 923         }
 924
 925     _LIBCPP_INLINE_VISIBILITY
 926     multiset(initializer_list<value_type> __il, const value_compare& __comp,
 927         const allocator_type& __a)
 928         : __tree_(__comp, __a)
 929         {
 930             insert(__il.begin(), __il.end());
 931         }
 932
 933 #if _LIBCPP_STD_VER > 11
 934     _LIBCPP_INLINE_VISIBILITY
 935     multiset(initializer_list<value_type> __il, const allocator_type& __a)
 936         : multiset(__il, key_compare(), __a) {}
 937 #endif
 938
 939     _LIBCPP_INLINE_VISIBILITY
 940     multiset& operator=(initializer_list<value_type> __il)
 941         {
 942             __tree_.__assign_multi(__il.begin(), __il.end());
 943             return *this;
 944         }
 945 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 946
 947 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 948     _LIBCPP_INLINE_VISIBILITY
 949     multiset& operator=(multiset&& __s)
 950         _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
 951         {
 952             __tree_ = _VSTD::move(__s.__tree_);
 953             return *this;
 954         }
 955 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 956
 957     _LIBCPP_INLINE_VISIBILITY
 958           iterator begin() _NOEXCEPT       {return __tree_.begin();}
 959     _LIBCPP_INLINE_VISIBILITY
 960     const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
 961     _LIBCPP_INLINE_VISIBILITY
 962           iterator end() _NOEXCEPT         {return __tree_.end();}
 963     _LIBCPP_INLINE_VISIBILITY
 964     const_iterator end()   const _NOEXCEPT {return __tree_.end();}
 965
 966     _LIBCPP_INLINE_VISIBILITY
 967           reverse_iterator rbegin() _NOEXCEPT
 968             {return reverse_iterator(end());}
 969     _LIBCPP_INLINE_VISIBILITY
 970     const_reverse_iterator rbegin() const _NOEXCEPT
 971         {return const_reverse_iterator(end());}
 972     _LIBCPP_INLINE_VISIBILITY
 973           reverse_iterator rend() _NOEXCEPT
 974             {return       reverse_iterator(begin());}
 975     _LIBCPP_INLINE_VISIBILITY
 976     const_reverse_iterator rend() const _NOEXCEPT
 977         {return const_reverse_iterator(begin());}
 978
 979     _LIBCPP_INLINE_VISIBILITY
 980     const_iterator cbegin()  const _NOEXCEPT {return begin();}
 981     _LIBCPP_INLINE_VISIBILITY
 982     const_iterator cend() const _NOEXCEPT {return end();}
 983     _LIBCPP_INLINE_VISIBILITY
 984     const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
 985     _LIBCPP_INLINE_VISIBILITY
 986     const_reverse_iterator crend() const _NOEXCEPT {return rend();}
 987
 988     _LIBCPP_INLINE_VISIBILITY
 989     bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
 990     _LIBCPP_INLINE_VISIBILITY
 991     size_type size() const _NOEXCEPT {return __tree_.size();}
 992     _LIBCPP_INLINE_VISIBILITY
 993     size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
 994
 995     // modifiers:
 996 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
 997     template <class... _Args>
 998         _LIBCPP_INLINE_VISIBILITY
 999         iterator emplace(_Args&&... __args)
1000             {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
1001     template <class... _Args>
1002         _LIBCPP_INLINE_VISIBILITY
1003         iterator emplace_hint(const_iterator __p, _Args&&... __args)
1004             {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
1005 #endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1006     _LIBCPP_INLINE_VISIBILITY
1007     iterator insert(const value_type& __v)
1008         {return __tree_.__insert_multi(__v);}
1009 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1010     _LIBCPP_INLINE_VISIBILITY
1011     iterator insert(value_type&& __v)
1012         {return __tree_.__insert_multi(_VSTD::move(__v));}
1013 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1014     _LIBCPP_INLINE_VISIBILITY
1015     iterator insert(const_iterator __p, const value_type& __v)
1016         {return __tree_.__insert_multi(__p, __v);}
1017 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1018     _LIBCPP_INLINE_VISIBILITY
1019     iterator insert(const_iterator __p, value_type&& __v)
1020         {return __tree_.__insert_multi(_VSTD::move(__v));}
1021 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1022     template <class _InputIterator>
1023         _LIBCPP_INLINE_VISIBILITY
1024         void insert(_InputIterator __f, _InputIterator __l)
1025         {
1026             for (const_iterator __e = cend(); __f != __l; ++__f)
1027                 __tree_.__insert_multi(__e, *__f);
1028         }
1029
1030 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1031     _LIBCPP_INLINE_VISIBILITY
1032     void insert(initializer_list<value_type> __il)
1033         {insert(__il.begin(), __il.end());}
1034 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1035
1036     _LIBCPP_INLINE_VISIBILITY
1037     iterator  erase(const_iterator __p) {return __tree_.erase(__p);}
1038     _LIBCPP_INLINE_VISIBILITY
1039     size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1040     _LIBCPP_INLINE_VISIBILITY
1041     iterator  erase(const_iterator __f, const_iterator __l)
1042         {return __tree_.erase(__f, __l);}
1043     _LIBCPP_INLINE_VISIBILITY
1044     void clear() _NOEXCEPT {__tree_.clear();}
1045
1046     _LIBCPP_INLINE_VISIBILITY
1047     void swap(multiset& __s)
1048         _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1049         {__tree_.swap(__s.__tree_);}
1050
1051     _LIBCPP_INLINE_VISIBILITY
1052     allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
1053     _LIBCPP_INLINE_VISIBILITY
1054     key_compare    key_comp()      const {return __tree_.value_comp();}
1055     _LIBCPP_INLINE_VISIBILITY
1056     value_compare  value_comp()    const {return __tree_.value_comp();}
1057
1058     // set operations:
1059     _LIBCPP_INLINE_VISIBILITY
1060     iterator find(const key_type& __k)             {return __tree_.find(__k);}
1061     _LIBCPP_INLINE_VISIBILITY
1062     const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1063 #if _LIBCPP_STD_VER > 11
1064     template <typename _K2>
1065     _LIBCPP_INLINE_VISIBILITY
1066     typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1067     find(const _K2& __k)                           {return __tree_.find(__k);}
1068     template <typename _K2>
1069     _LIBCPP_INLINE_VISIBILITY
1070     typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1071     find(const _K2& __k) const                     {return __tree_.find(__k);}
1072 #endif
1073
1074     _LIBCPP_INLINE_VISIBILITY
1075     size_type      count(const key_type& __k) const
1076         {return __tree_.__count_multi(__k);}
1077 #if _LIBCPP_STD_VER > 11
1078     template <typename _K2>
1079     _LIBCPP_INLINE_VISIBILITY
1080     typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1081     count(const _K2& __k)                  {return __tree_.__count_multi(__k);}
1082 #endif
1083
1084     _LIBCPP_INLINE_VISIBILITY
1085     iterator lower_bound(const key_type& __k)
1086         {return __tree_.lower_bound(__k);}
1087     _LIBCPP_INLINE_VISIBILITY
1088     const_iterator lower_bound(const key_type& __k) const
1089             {return __tree_.lower_bound(__k);}
1090 #if _LIBCPP_STD_VER > 11
1091     template <typename _K2>
1092     _LIBCPP_INLINE_VISIBILITY
1093     typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1094     lower_bound(const _K2& __k)       {return __tree_.lower_bound(__k);}
1095
1096     template <typename _K2>
1097     _LIBCPP_INLINE_VISIBILITY
1098     typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1099     lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1100 #endif
1101
1102     _LIBCPP_INLINE_VISIBILITY
1103     iterator upper_bound(const key_type& __k)
1104             {return __tree_.upper_bound(__k);}
1105     _LIBCPP_INLINE_VISIBILITY
1106     const_iterator upper_bound(const key_type& __k) const
1107             {return __tree_.upper_bound(__k);}
1108 #if _LIBCPP_STD_VER > 11
1109     template <typename _K2>
1110     _LIBCPP_INLINE_VISIBILITY
1111     typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1112     upper_bound(const _K2& __k)       {return __tree_.upper_bound(__k);}
1113     template <typename _K2>
1114     _LIBCPP_INLINE_VISIBILITY
1115     typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1116     upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1117 #endif
1118
1119     _LIBCPP_INLINE_VISIBILITY
1120     pair<iterator,iterator>             equal_range(const key_type& __k)
1121             {return __tree_.__equal_range_multi(__k);}
1122     _LIBCPP_INLINE_VISIBILITY
1123     pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1124             {return __tree_.__equal_range_multi(__k);}
1125 #if _LIBCPP_STD_VER > 11
1126     template <typename _K2>
1127     _LIBCPP_INLINE_VISIBILITY
1128     typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1129     equal_range(const _K2& __k)       {return __tree_.__equal_range_multi(__k);}
1130     template <typename _K2>
1131     _LIBCPP_INLINE_VISIBILITY
1132     typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1133     equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1134 #endif
1135 };
1136
1137 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1138
1139 template <class _Key, class _Compare, class _Allocator>
1140 multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a)
1141     : __tree_(_VSTD::move(__s.__tree_), __a)
1142 {
1143     if (__a != __s.get_allocator())
1144     {
1145         const_iterator __e = cend();
1146         while (!__s.empty())
1147             insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
1148     }
1149 }
1150
1151 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1152
1153 template <class _Key, class _Compare, class _Allocator>
1154 inline _LIBCPP_INLINE_VISIBILITY
1155 bool
1156 operator==(const multiset<_Key, _Compare, _Allocator>& __x,
1157            const multiset<_Key, _Compare, _Allocator>& __y)
1158 {
1159     return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1160 }
1161
1162 template <class _Key, class _Compare, class _Allocator>
1163 inline _LIBCPP_INLINE_VISIBILITY
1164 bool
1165 operator< (const multiset<_Key, _Compare, _Allocator>& __x,
1166            const multiset<_Key, _Compare, _Allocator>& __y)
1167 {
1168     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1169 }
1170
1171 template <class _Key, class _Compare, class _Allocator>
1172 inline _LIBCPP_INLINE_VISIBILITY
1173 bool
1174 operator!=(const multiset<_Key, _Compare, _Allocator>& __x,
1175            const multiset<_Key, _Compare, _Allocator>& __y)
1176 {
1177     return !(__x == __y);
1178 }
1179
1180 template <class _Key, class _Compare, class _Allocator>
1181 inline _LIBCPP_INLINE_VISIBILITY
1182 bool
1183 operator> (const multiset<_Key, _Compare, _Allocator>& __x,
1184            const multiset<_Key, _Compare, _Allocator>& __y)
1185 {
1186     return __y < __x;
1187 }
1188
1189 template <class _Key, class _Compare, class _Allocator>
1190 inline _LIBCPP_INLINE_VISIBILITY
1191 bool
1192 operator>=(const multiset<_Key, _Compare, _Allocator>& __x,
1193            const multiset<_Key, _Compare, _Allocator>& __y)
1194 {
1195     return !(__x < __y);
1196 }
1197
1198 template <class _Key, class _Compare, class _Allocator>
1199 inline _LIBCPP_INLINE_VISIBILITY
1200 bool
1201 operator<=(const multiset<_Key, _Compare, _Allocator>& __x,
1202            const multiset<_Key, _Compare, _Allocator>& __y)
1203 {
1204     return !(__y < __x);
1205 }
1206
1207 template <class _Key, class _Compare, class _Allocator>
1208 inline _LIBCPP_INLINE_VISIBILITY
1209 void
1210 swap(multiset<_Key, _Compare, _Allocator>& __x,
1211      multiset<_Key, _Compare, _Allocator>& __y)
1212     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1213 {
1214     __x.swap(__y);
1215 }
1216
1217 _LIBCPP_END_NAMESPACE_STD
1218
1219 #endif  // _LIBCPP_SET