Home | History | Annotate | Download | only in v1
      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_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_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
   1219