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