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