set revision 227825 
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
18namespace std
19{
20
21template <class Key, class Compare = less<Key>,
22          class Allocator = allocator<Key>>
23class set
24{
25public:
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
141template <class Key, class Compare, class Allocator>
142bool
143operator==(const set<Key, Compare, Allocator>& x,
144           const set<Key, Compare, Allocator>& y);
145
146template <class Key, class Compare, class Allocator>
147bool
148operator< (const set<Key, Compare, Allocator>& x,
149           const set<Key, Compare, Allocator>& y);
150
151template <class Key, class Compare, class Allocator>
152bool
153operator!=(const set<Key, Compare, Allocator>& x,
154           const set<Key, Compare, Allocator>& y);
155
156template <class Key, class Compare, class Allocator>
157bool
158operator> (const set<Key, Compare, Allocator>& x,
159           const set<Key, Compare, Allocator>& y);
160
161template <class Key, class Compare, class Allocator>
162bool
163operator>=(const set<Key, Compare, Allocator>& x,
164           const set<Key, Compare, Allocator>& y);
165
166template <class Key, class Compare, class Allocator>
167bool
168operator<=(const set<Key, Compare, Allocator>& x,
169           const set<Key, Compare, Allocator>& y);
170
171// specialized algorithms:
172template <class Key, class Compare, class Allocator>
173void
174swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y)
175    noexcept(noexcept(x.swap(y)));
176
177template <class Key, class Compare = less<Key>,
178          class Allocator = allocator<Key>>
179class multiset
180{
181public:
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
297template <class Key, class Compare, class Allocator>
298bool
299operator==(const multiset<Key, Compare, Allocator>& x,
300           const multiset<Key, Compare, Allocator>& y);
301
302template <class Key, class Compare, class Allocator>
303bool
304operator< (const multiset<Key, Compare, Allocator>& x,
305           const multiset<Key, Compare, Allocator>& y);
306
307template <class Key, class Compare, class Allocator>
308bool
309operator!=(const multiset<Key, Compare, Allocator>& x,
310           const multiset<Key, Compare, Allocator>& y);
311
312template <class Key, class Compare, class Allocator>
313bool
314operator> (const multiset<Key, Compare, Allocator>& x,
315           const multiset<Key, Compare, Allocator>& y);
316
317template <class Key, class Compare, class Allocator>
318bool
319operator>=(const multiset<Key, Compare, Allocator>& x,
320           const multiset<Key, Compare, Allocator>& y);
321
322template <class Key, class Compare, class Allocator>
323bool
324operator<=(const multiset<Key, Compare, Allocator>& x,
325           const multiset<Key, Compare, Allocator>& y);
326
327// specialized algorithms:
328template <class Key, class Compare, class Allocator>
329void
330swap(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
347template <class _Key, class _Compare = less<_Key>,
348          class _Allocator = allocator<_Key> >
349class _LIBCPP_VISIBLE set
350{
351public:
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
361private:
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
368public:
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
607template <class _Key, class _Compare, class _Allocator>
608set<_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
621template <class _Key, class _Compare, class _Allocator>
622inline _LIBCPP_INLINE_VISIBILITY
623bool
624operator==(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
630template <class _Key, class _Compare, class _Allocator>
631inline _LIBCPP_INLINE_VISIBILITY
632bool
633operator< (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
639template <class _Key, class _Compare, class _Allocator>
640inline _LIBCPP_INLINE_VISIBILITY
641bool
642operator!=(const set<_Key, _Compare, _Allocator>& __x,
643           const set<_Key, _Compare, _Allocator>& __y)
644{
645    return !(__x == __y);
646}
647
648template <class _Key, class _Compare, class _Allocator>
649inline _LIBCPP_INLINE_VISIBILITY
650bool
651operator> (const set<_Key, _Compare, _Allocator>& __x,
652           const set<_Key, _Compare, _Allocator>& __y)
653{
654    return __y < __x;
655}
656
657template <class _Key, class _Compare, class _Allocator>
658inline _LIBCPP_INLINE_VISIBILITY
659bool
660operator>=(const set<_Key, _Compare, _Allocator>& __x,
661           const set<_Key, _Compare, _Allocator>& __y)
662{
663    return !(__x < __y);
664}
665
666template <class _Key, class _Compare, class _Allocator>
667inline _LIBCPP_INLINE_VISIBILITY
668bool
669operator<=(const set<_Key, _Compare, _Allocator>& __x,
670           const set<_Key, _Compare, _Allocator>& __y)
671{
672    return !(__y < __x);
673}
674
675// specialized algorithms:
676template <class _Key, class _Compare, class _Allocator>
677inline _LIBCPP_INLINE_VISIBILITY
678void
679swap(set<_Key, _Compare, _Allocator>& __x,
680     set<_Key, _Compare, _Allocator>& __y)
681    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
682{
683    __x.swap(__y);
684}
685
686template <class _Key, class _Compare = less<_Key>,
687          class _Allocator = allocator<_Key> >
688class _LIBCPP_VISIBLE multiset
689{
690public:
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
700private:
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
707public:
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
945template <class _Key, class _Compare, class _Allocator>
946multiset<_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
959template <class _Key, class _Compare, class _Allocator>
960inline _LIBCPP_INLINE_VISIBILITY
961bool
962operator==(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
968template <class _Key, class _Compare, class _Allocator>
969inline _LIBCPP_INLINE_VISIBILITY
970bool
971operator< (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
977template <class _Key, class _Compare, class _Allocator>
978inline _LIBCPP_INLINE_VISIBILITY
979bool
980operator!=(const multiset<_Key, _Compare, _Allocator>& __x,
981           const multiset<_Key, _Compare, _Allocator>& __y)
982{
983    return !(__x == __y);
984}
985
986template <class _Key, class _Compare, class _Allocator>
987inline _LIBCPP_INLINE_VISIBILITY
988bool
989operator> (const multiset<_Key, _Compare, _Allocator>& __x,
990           const multiset<_Key, _Compare, _Allocator>& __y)
991{
992    return __y < __x;
993}
994
995template <class _Key, class _Compare, class _Allocator>
996inline _LIBCPP_INLINE_VISIBILITY
997bool
998operator>=(const multiset<_Key, _Compare, _Allocator>& __x,
999           const multiset<_Key, _Compare, _Allocator>& __y)
1000{
1001    return !(__x < __y);
1002}
1003
1004template <class _Key, class _Compare, class _Allocator>
1005inline _LIBCPP_INLINE_VISIBILITY
1006bool
1007operator<=(const multiset<_Key, _Compare, _Allocator>& __x,
1008           const multiset<_Key, _Compare, _Allocator>& __y)
1009{
1010    return !(__y < __x);
1011}
1012
1013template <class _Key, class _Compare, class _Allocator>
1014inline _LIBCPP_INLINE_VISIBILITY
1015void
1016swap(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