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