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