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