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