xref: /netbsd-src/external/apache2/llvm/dist/libcxx/include/set (revision 4d6fc14bc9b0c5bf3e30be318c143ee82cadd108)
1// -*- C++ -*-
2//===---------------------------- set -------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP_SET
11#define _LIBCPP_SET
12
13/*
14
15    set synopsis
16
17namespace std
18{
19
20template <class Key, class Compare = less<Key>,
21          class Allocator = allocator<Key>>
22class set
23{
24public:
25    // types:
26    typedef Key                                      key_type;
27    typedef key_type                                 value_type;
28    typedef Compare                                  key_compare;
29    typedef key_compare                              value_compare;
30    typedef Allocator                                allocator_type;
31    typedef typename allocator_type::reference       reference;
32    typedef typename allocator_type::const_reference const_reference;
33    typedef typename allocator_type::size_type       size_type;
34    typedef typename allocator_type::difference_type difference_type;
35    typedef typename allocator_type::pointer         pointer;
36    typedef typename allocator_type::const_pointer   const_pointer;
37
38    typedef implementation-defined                   iterator;
39    typedef implementation-defined                   const_iterator;
40    typedef std::reverse_iterator<iterator>          reverse_iterator;
41    typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
42    typedef unspecified                              node_type;               // C++17
43    typedef INSERT_RETURN_TYPE<iterator, node_type>  insert_return_type;      // C++17
44
45    // construct/copy/destroy:
46    set()
47        noexcept(
48            is_nothrow_default_constructible<allocator_type>::value &&
49            is_nothrow_default_constructible<key_compare>::value &&
50            is_nothrow_copy_constructible<key_compare>::value);
51    explicit set(const value_compare& comp);
52    set(const value_compare& comp, const allocator_type& a);
53    template <class InputIterator>
54        set(InputIterator first, InputIterator last,
55            const value_compare& comp = value_compare());
56    template <class InputIterator>
57        set(InputIterator first, InputIterator last, const value_compare& comp,
58            const allocator_type& a);
59    set(const set& s);
60    set(set&& s)
61        noexcept(
62            is_nothrow_move_constructible<allocator_type>::value &&
63            is_nothrow_move_constructible<key_compare>::value);
64    explicit set(const allocator_type& a);
65    set(const set& s, const allocator_type& a);
66    set(set&& s, const allocator_type& a);
67    set(initializer_list<value_type> il, const value_compare& comp = value_compare());
68    set(initializer_list<value_type> il, const value_compare& comp,
69        const allocator_type& a);
70    template <class InputIterator>
71        set(InputIterator first, InputIterator last, const allocator_type& a)
72            : set(first, last, Compare(), a) {}  // C++14
73    set(initializer_list<value_type> il, const allocator_type& a)
74        : set(il, Compare(), a) {}  // C++14
75    ~set();
76
77    set& operator=(const set& s);
78    set& operator=(set&& s)
79        noexcept(
80            allocator_type::propagate_on_container_move_assignment::value &&
81            is_nothrow_move_assignable<allocator_type>::value &&
82            is_nothrow_move_assignable<key_compare>::value);
83    set& operator=(initializer_list<value_type> il);
84
85    // iterators:
86          iterator begin() noexcept;
87    const_iterator begin() const noexcept;
88          iterator end() noexcept;
89    const_iterator end()   const noexcept;
90
91          reverse_iterator rbegin() noexcept;
92    const_reverse_iterator rbegin() const noexcept;
93          reverse_iterator rend() noexcept;
94    const_reverse_iterator rend()   const noexcept;
95
96    const_iterator         cbegin()  const noexcept;
97    const_iterator         cend()    const noexcept;
98    const_reverse_iterator crbegin() const noexcept;
99    const_reverse_iterator crend()   const noexcept;
100
101    // capacity:
102    bool      empty()    const noexcept;
103    size_type size()     const noexcept;
104    size_type max_size() const noexcept;
105
106    // modifiers:
107    template <class... Args>
108        pair<iterator, bool> emplace(Args&&... args);
109    template <class... Args>
110        iterator emplace_hint(const_iterator position, Args&&... args);
111    pair<iterator,bool> insert(const value_type& v);
112    pair<iterator,bool> insert(value_type&& v);
113    iterator insert(const_iterator position, const value_type& v);
114    iterator insert(const_iterator position, value_type&& v);
115    template <class InputIterator>
116        void insert(InputIterator first, InputIterator last);
117    void insert(initializer_list<value_type> il);
118
119    node_type extract(const_iterator position);                                       // C++17
120    node_type extract(const key_type& x);                                             // C++17
121    insert_return_type insert(node_type&& nh);                                        // C++17
122    iterator insert(const_iterator hint, node_type&& nh);                             // C++17
123
124    iterator  erase(const_iterator position);
125    iterator  erase(iterator position);  // C++14
126    size_type erase(const key_type& k);
127    iterator  erase(const_iterator first, const_iterator last);
128    void clear() noexcept;
129
130    template<class C2>
131      void merge(set<Key, C2, Allocator>& source);         // C++17
132    template<class C2>
133      void merge(set<Key, C2, Allocator>&& source);        // C++17
134    template<class C2>
135      void merge(multiset<Key, C2, Allocator>& source);    // C++17
136    template<class C2>
137      void merge(multiset<Key, C2, Allocator>&& source);   // C++17
138
139    void swap(set& s)
140        noexcept(
141            __is_nothrow_swappable<key_compare>::value &&
142            (!allocator_type::propagate_on_container_swap::value ||
143             __is_nothrow_swappable<allocator_type>::value));
144
145    // observers:
146    allocator_type get_allocator() const noexcept;
147    key_compare    key_comp()      const;
148    value_compare  value_comp()    const;
149
150    // set operations:
151          iterator find(const key_type& k);
152    const_iterator find(const key_type& k) const;
153    template<typename K>
154        iterator find(const K& x);
155    template<typename K>
156        const_iterator find(const K& x) const;  // C++14
157
158    template<typename K>
159        size_type count(const K& x) const;        // C++14
160    size_type      count(const key_type& k) const;
161
162    bool           contains(const key_type& x) const;  // C++20
163    template<class K> bool contains(const K& x) const; // C++20
164
165          iterator lower_bound(const key_type& k);
166    const_iterator lower_bound(const key_type& k) const;
167    template<typename K>
168        iterator lower_bound(const K& x);              // C++14
169    template<typename K>
170        const_iterator lower_bound(const K& x) const;  // C++14
171
172          iterator upper_bound(const key_type& k);
173    const_iterator upper_bound(const key_type& k) const;
174    template<typename K>
175        iterator upper_bound(const K& x);              // C++14
176    template<typename K>
177        const_iterator upper_bound(const K& x) const;  // C++14
178    pair<iterator,iterator>             equal_range(const key_type& k);
179    pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
180    template<typename K>
181        pair<iterator,iterator>             equal_range(const K& x);        // C++14
182    template<typename K>
183        pair<const_iterator,const_iterator> equal_range(const K& x) const;  // C++14
184};
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
196template <class Key, class Compare, class Allocator>
197bool
198operator!=(const set<Key, Compare, Allocator>& x,
199           const set<Key, Compare, Allocator>& y);
200
201template <class Key, class Compare, class Allocator>
202bool
203operator> (const set<Key, Compare, Allocator>& x,
204           const set<Key, Compare, Allocator>& y);
205
206template <class Key, class Compare, class Allocator>
207bool
208operator>=(const set<Key, Compare, Allocator>& x,
209           const set<Key, Compare, Allocator>& y);
210
211template <class Key, class Compare, class Allocator>
212bool
213operator<=(const set<Key, Compare, Allocator>& x,
214           const set<Key, Compare, Allocator>& y);
215
216// specialized algorithms:
217template <class Key, class Compare, class Allocator>
218void
219swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y)
220    noexcept(noexcept(x.swap(y)));
221
222template <class Key, class Compare, class Allocator, class Predicate>
223typename set<Key, Compare, Allocator>::size_type
224erase_if(set<Key, Compare, Allocator>& c, Predicate pred);  // C++20
225
226template <class Key, class Compare = less<Key>,
227          class Allocator = allocator<Key>>
228class multiset
229{
230public:
231    // types:
232    typedef Key                                      key_type;
233    typedef key_type                                 value_type;
234    typedef Compare                                  key_compare;
235    typedef key_compare                              value_compare;
236    typedef Allocator                                allocator_type;
237    typedef typename allocator_type::reference       reference;
238    typedef typename allocator_type::const_reference const_reference;
239    typedef typename allocator_type::size_type       size_type;
240    typedef typename allocator_type::difference_type difference_type;
241    typedef typename allocator_type::pointer         pointer;
242    typedef typename allocator_type::const_pointer   const_pointer;
243
244    typedef implementation-defined                   iterator;
245    typedef implementation-defined                   const_iterator;
246    typedef std::reverse_iterator<iterator>          reverse_iterator;
247    typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
248    typedef unspecified                              node_type;               // C++17
249
250    // construct/copy/destroy:
251    multiset()
252        noexcept(
253            is_nothrow_default_constructible<allocator_type>::value &&
254            is_nothrow_default_constructible<key_compare>::value &&
255            is_nothrow_copy_constructible<key_compare>::value);
256    explicit multiset(const value_compare& comp);
257    multiset(const value_compare& comp, const allocator_type& a);
258    template <class InputIterator>
259        multiset(InputIterator first, InputIterator last,
260                 const value_compare& comp = value_compare());
261    template <class InputIterator>
262        multiset(InputIterator first, InputIterator last,
263                 const value_compare& comp, const allocator_type& a);
264    multiset(const multiset& s);
265    multiset(multiset&& s)
266        noexcept(
267            is_nothrow_move_constructible<allocator_type>::value &&
268            is_nothrow_move_constructible<key_compare>::value);
269    explicit multiset(const allocator_type& a);
270    multiset(const multiset& s, const allocator_type& a);
271    multiset(multiset&& s, const allocator_type& a);
272    multiset(initializer_list<value_type> il, const value_compare& comp = value_compare());
273    multiset(initializer_list<value_type> il, const value_compare& comp,
274             const allocator_type& a);
275    template <class InputIterator>
276        multiset(InputIterator first, InputIterator last, const allocator_type& a)
277            : set(first, last, Compare(), a) {}  // C++14
278    multiset(initializer_list<value_type> il, const allocator_type& a)
279        : set(il, Compare(), a) {}  // C++14
280    ~multiset();
281
282    multiset& operator=(const multiset& s);
283    multiset& operator=(multiset&& s)
284        noexcept(
285            allocator_type::propagate_on_container_move_assignment::value &&
286            is_nothrow_move_assignable<allocator_type>::value &&
287            is_nothrow_move_assignable<key_compare>::value);
288    multiset& operator=(initializer_list<value_type> il);
289
290    // iterators:
291          iterator begin() noexcept;
292    const_iterator begin() const noexcept;
293          iterator end() noexcept;
294    const_iterator end()   const noexcept;
295
296          reverse_iterator rbegin() noexcept;
297    const_reverse_iterator rbegin() const noexcept;
298          reverse_iterator rend() noexcept;
299    const_reverse_iterator rend()   const noexcept;
300
301    const_iterator         cbegin()  const noexcept;
302    const_iterator         cend()    const noexcept;
303    const_reverse_iterator crbegin() const noexcept;
304    const_reverse_iterator crend()   const noexcept;
305
306    // capacity:
307    bool      empty()    const noexcept;
308    size_type size()     const noexcept;
309    size_type max_size() const noexcept;
310
311    // modifiers:
312    template <class... Args>
313        iterator emplace(Args&&... args);
314    template <class... Args>
315        iterator emplace_hint(const_iterator position, Args&&... args);
316    iterator insert(const value_type& v);
317    iterator insert(value_type&& v);
318    iterator insert(const_iterator position, const value_type& v);
319    iterator insert(const_iterator position, value_type&& v);
320    template <class InputIterator>
321        void insert(InputIterator first, InputIterator last);
322    void insert(initializer_list<value_type> il);
323
324    node_type extract(const_iterator position);                                       // C++17
325    node_type extract(const key_type& x);                                             // C++17
326    iterator insert(node_type&& nh);                                                  // C++17
327    iterator insert(const_iterator hint, node_type&& nh);                             // C++17
328
329    iterator  erase(const_iterator position);
330    iterator  erase(iterator position);  // C++14
331    size_type erase(const key_type& k);
332    iterator  erase(const_iterator first, const_iterator last);
333    void clear() noexcept;
334
335    template<class C2>
336      void merge(multiset<Key, C2, Allocator>& source);    // C++17
337    template<class C2>
338      void merge(multiset<Key, C2, Allocator>&& source);   // C++17
339    template<class C2>
340      void merge(set<Key, C2, Allocator>& source);         // C++17
341    template<class C2>
342      void merge(set<Key, C2, Allocator>&& source);        // C++17
343
344    void swap(multiset& s)
345        noexcept(
346            __is_nothrow_swappable<key_compare>::value &&
347            (!allocator_type::propagate_on_container_swap::value ||
348             __is_nothrow_swappable<allocator_type>::value));
349
350    // observers:
351    allocator_type get_allocator() const noexcept;
352    key_compare    key_comp()      const;
353    value_compare  value_comp()    const;
354
355    // set operations:
356          iterator find(const key_type& k);
357    const_iterator find(const key_type& k) const;
358    template<typename K>
359        iterator find(const K& x);
360    template<typename K>
361        const_iterator find(const K& x) const;  // C++14
362
363    template<typename K>
364        size_type count(const K& x) const;      // C++14
365    size_type      count(const key_type& k) const;
366
367    bool           contains(const key_type& x) const;  // C++20
368    template<class K> bool contains(const K& x) const; // C++20
369
370          iterator lower_bound(const key_type& k);
371    const_iterator lower_bound(const key_type& k) const;
372    template<typename K>
373        iterator lower_bound(const K& x);              // C++14
374    template<typename K>
375        const_iterator lower_bound(const K& x) const;  // C++14
376
377          iterator upper_bound(const key_type& k);
378    const_iterator upper_bound(const key_type& k) const;
379    template<typename K>
380        iterator upper_bound(const K& x);              // C++14
381    template<typename K>
382        const_iterator upper_bound(const K& x) const;  // C++14
383
384    pair<iterator,iterator>             equal_range(const key_type& k);
385    pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
386    template<typename K>
387        pair<iterator,iterator>             equal_range(const K& x);        // C++14
388    template<typename K>
389        pair<const_iterator,const_iterator> equal_range(const K& x) const;  // C++14
390};
391
392template <class Key, class Compare, class Allocator>
393bool
394operator==(const multiset<Key, Compare, Allocator>& x,
395           const multiset<Key, Compare, Allocator>& y);
396
397template <class Key, class Compare, class Allocator>
398bool
399operator< (const multiset<Key, Compare, Allocator>& x,
400           const multiset<Key, Compare, Allocator>& y);
401
402template <class Key, class Compare, class Allocator>
403bool
404operator!=(const multiset<Key, Compare, Allocator>& x,
405           const multiset<Key, Compare, Allocator>& y);
406
407template <class Key, class Compare, class Allocator>
408bool
409operator> (const multiset<Key, Compare, Allocator>& x,
410           const multiset<Key, Compare, Allocator>& y);
411
412template <class Key, class Compare, class Allocator>
413bool
414operator>=(const multiset<Key, Compare, Allocator>& x,
415           const multiset<Key, Compare, Allocator>& y);
416
417template <class Key, class Compare, class Allocator>
418bool
419operator<=(const multiset<Key, Compare, Allocator>& x,
420           const multiset<Key, Compare, Allocator>& y);
421
422// specialized algorithms:
423template <class Key, class Compare, class Allocator>
424void
425swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y)
426    noexcept(noexcept(x.swap(y)));
427
428template <class Key, class Compare, class Allocator, class Predicate>
429typename multiset<Key, Compare, Allocator>::size_type
430erase_if(multiset<Key, Compare, Allocator>& c, Predicate pred);  // C++20
431
432}  // std
433
434*/
435
436#include <__config>
437#include <__debug>
438#include <__node_handle>
439#include <__tree>
440#include <compare>
441#include <functional>
442#include <initializer_list>
443#include <iterator> // __libcpp_erase_if_container
444#include <version>
445
446#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
447#pragma GCC system_header
448#endif
449
450_LIBCPP_BEGIN_NAMESPACE_STD
451
452template <class _Key, class _Compare, class _Allocator>
453class multiset;
454
455template <class _Key, class _Compare = less<_Key>,
456          class _Allocator = allocator<_Key> >
457class _LIBCPP_TEMPLATE_VIS set
458{
459public:
460    // types:
461    typedef _Key                                     key_type;
462    typedef key_type                                 value_type;
463    typedef _Compare                                 key_compare;
464    typedef key_compare                              value_compare;
465    typedef __identity_t<_Allocator>                 allocator_type;
466    typedef value_type&                              reference;
467    typedef const value_type&                        const_reference;
468
469    static_assert((is_same<typename allocator_type::value_type, value_type>::value),
470                  "Allocator::value_type must be same type as value_type");
471
472private:
473    typedef __tree<value_type, value_compare, allocator_type> __base;
474    typedef allocator_traits<allocator_type>                  __alloc_traits;
475    typedef typename __base::__node_holder                    __node_holder;
476
477    __base __tree_;
478
479public:
480    typedef typename __base::pointer               pointer;
481    typedef typename __base::const_pointer         const_pointer;
482    typedef typename __base::size_type             size_type;
483    typedef typename __base::difference_type       difference_type;
484    typedef typename __base::const_iterator        iterator;
485    typedef typename __base::const_iterator        const_iterator;
486    typedef _VSTD::reverse_iterator<iterator>       reverse_iterator;
487    typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
488
489#if _LIBCPP_STD_VER > 14
490    typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
491    typedef __insert_return_type<iterator, node_type> insert_return_type;
492#endif
493
494    template <class _Key2, class _Compare2, class _Alloc2>
495        friend class _LIBCPP_TEMPLATE_VIS set;
496    template <class _Key2, class _Compare2, class _Alloc2>
497        friend class _LIBCPP_TEMPLATE_VIS multiset;
498
499    _LIBCPP_INLINE_VISIBILITY
500    set()
501        _NOEXCEPT_(
502            is_nothrow_default_constructible<allocator_type>::value &&
503            is_nothrow_default_constructible<key_compare>::value &&
504            is_nothrow_copy_constructible<key_compare>::value)
505        : __tree_(value_compare()) {}
506
507    _LIBCPP_INLINE_VISIBILITY
508    explicit set(const value_compare& __comp)
509        _NOEXCEPT_(
510            is_nothrow_default_constructible<allocator_type>::value &&
511            is_nothrow_copy_constructible<key_compare>::value)
512        : __tree_(__comp) {}
513
514    _LIBCPP_INLINE_VISIBILITY
515    explicit set(const value_compare& __comp, const allocator_type& __a)
516        : __tree_(__comp, __a) {}
517    template <class _InputIterator>
518        _LIBCPP_INLINE_VISIBILITY
519        set(_InputIterator __f, _InputIterator __l,
520            const value_compare& __comp = value_compare())
521        : __tree_(__comp)
522        {
523            insert(__f, __l);
524        }
525
526    template <class _InputIterator>
527        _LIBCPP_INLINE_VISIBILITY
528        set(_InputIterator __f, _InputIterator __l, const value_compare& __comp,
529            const allocator_type& __a)
530        : __tree_(__comp, __a)
531        {
532            insert(__f, __l);
533        }
534
535#if _LIBCPP_STD_VER > 11
536        template <class _InputIterator>
537        _LIBCPP_INLINE_VISIBILITY
538        set(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
539            : set(__f, __l, key_compare(), __a) {}
540#endif
541
542    _LIBCPP_INLINE_VISIBILITY
543    set(const set& __s)
544        : __tree_(__s.__tree_)
545        {
546            insert(__s.begin(), __s.end());
547        }
548
549    _LIBCPP_INLINE_VISIBILITY
550    set& operator=(const set& __s)
551        {
552            __tree_ = __s.__tree_;
553            return *this;
554        }
555
556#ifndef _LIBCPP_CXX03_LANG
557    _LIBCPP_INLINE_VISIBILITY
558    set(set&& __s)
559        _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
560        : __tree_(_VSTD::move(__s.__tree_)) {}
561#endif // _LIBCPP_CXX03_LANG
562
563    _LIBCPP_INLINE_VISIBILITY
564    explicit set(const allocator_type& __a)
565        : __tree_(__a) {}
566
567    _LIBCPP_INLINE_VISIBILITY
568    set(const set& __s, const allocator_type& __a)
569        : __tree_(__s.__tree_.value_comp(), __a)
570        {
571            insert(__s.begin(), __s.end());
572        }
573
574#ifndef _LIBCPP_CXX03_LANG
575    set(set&& __s, const allocator_type& __a);
576
577    _LIBCPP_INLINE_VISIBILITY
578    set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
579        : __tree_(__comp)
580        {
581            insert(__il.begin(), __il.end());
582        }
583
584    _LIBCPP_INLINE_VISIBILITY
585    set(initializer_list<value_type> __il, const value_compare& __comp,
586        const allocator_type& __a)
587        : __tree_(__comp, __a)
588        {
589            insert(__il.begin(), __il.end());
590        }
591
592#if _LIBCPP_STD_VER > 11
593    _LIBCPP_INLINE_VISIBILITY
594    set(initializer_list<value_type> __il, const allocator_type& __a)
595        : set(__il, key_compare(), __a) {}
596#endif
597
598    _LIBCPP_INLINE_VISIBILITY
599    set& operator=(initializer_list<value_type> __il)
600        {
601            __tree_.__assign_unique(__il.begin(), __il.end());
602            return *this;
603        }
604
605    _LIBCPP_INLINE_VISIBILITY
606    set& operator=(set&& __s)
607        _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
608        {
609            __tree_ = _VSTD::move(__s.__tree_);
610            return *this;
611        }
612#endif // _LIBCPP_CXX03_LANG
613
614    _LIBCPP_INLINE_VISIBILITY
615    ~set() {
616        static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
617    }
618
619    _LIBCPP_INLINE_VISIBILITY
620          iterator begin() _NOEXCEPT       {return __tree_.begin();}
621    _LIBCPP_INLINE_VISIBILITY
622    const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
623    _LIBCPP_INLINE_VISIBILITY
624          iterator end() _NOEXCEPT         {return __tree_.end();}
625    _LIBCPP_INLINE_VISIBILITY
626    const_iterator end()   const _NOEXCEPT {return __tree_.end();}
627
628    _LIBCPP_INLINE_VISIBILITY
629          reverse_iterator rbegin() _NOEXCEPT
630            {return reverse_iterator(end());}
631    _LIBCPP_INLINE_VISIBILITY
632    const_reverse_iterator rbegin() const _NOEXCEPT
633        {return const_reverse_iterator(end());}
634    _LIBCPP_INLINE_VISIBILITY
635          reverse_iterator rend() _NOEXCEPT
636            {return reverse_iterator(begin());}
637    _LIBCPP_INLINE_VISIBILITY
638    const_reverse_iterator rend() const _NOEXCEPT
639        {return const_reverse_iterator(begin());}
640
641    _LIBCPP_INLINE_VISIBILITY
642    const_iterator cbegin()  const _NOEXCEPT {return begin();}
643    _LIBCPP_INLINE_VISIBILITY
644    const_iterator cend() const _NOEXCEPT {return end();}
645    _LIBCPP_INLINE_VISIBILITY
646    const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
647    _LIBCPP_INLINE_VISIBILITY
648    const_reverse_iterator crend() const _NOEXCEPT {return rend();}
649
650    _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
651    bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
652    _LIBCPP_INLINE_VISIBILITY
653    size_type size() const _NOEXCEPT {return __tree_.size();}
654    _LIBCPP_INLINE_VISIBILITY
655    size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
656
657    // modifiers:
658#ifndef _LIBCPP_CXX03_LANG
659    template <class... _Args>
660        _LIBCPP_INLINE_VISIBILITY
661        pair<iterator, bool> emplace(_Args&&... __args)
662            {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
663    template <class... _Args>
664        _LIBCPP_INLINE_VISIBILITY
665        iterator emplace_hint(const_iterator __p, _Args&&... __args)
666            {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);}
667#endif // _LIBCPP_CXX03_LANG
668
669    _LIBCPP_INLINE_VISIBILITY
670    pair<iterator,bool> insert(const value_type& __v)
671        {return __tree_.__insert_unique(__v);}
672    _LIBCPP_INLINE_VISIBILITY
673    iterator insert(const_iterator __p, const value_type& __v)
674        {return __tree_.__insert_unique(__p, __v);}
675
676    template <class _InputIterator>
677        _LIBCPP_INLINE_VISIBILITY
678        void insert(_InputIterator __f, _InputIterator __l)
679        {
680            for (const_iterator __e = cend(); __f != __l; ++__f)
681                __tree_.__insert_unique(__e, *__f);
682        }
683
684#ifndef _LIBCPP_CXX03_LANG
685    _LIBCPP_INLINE_VISIBILITY
686    pair<iterator,bool> insert(value_type&& __v)
687        {return __tree_.__insert_unique(_VSTD::move(__v));}
688
689    _LIBCPP_INLINE_VISIBILITY
690    iterator insert(const_iterator __p, value_type&& __v)
691        {return __tree_.__insert_unique(__p, _VSTD::move(__v));}
692
693    _LIBCPP_INLINE_VISIBILITY
694    void insert(initializer_list<value_type> __il)
695        {insert(__il.begin(), __il.end());}
696#endif // _LIBCPP_CXX03_LANG
697
698    _LIBCPP_INLINE_VISIBILITY
699    iterator  erase(const_iterator __p) {return __tree_.erase(__p);}
700    _LIBCPP_INLINE_VISIBILITY
701    size_type erase(const key_type& __k)
702        {return __tree_.__erase_unique(__k);}
703    _LIBCPP_INLINE_VISIBILITY
704    iterator  erase(const_iterator __f, const_iterator __l)
705        {return __tree_.erase(__f, __l);}
706    _LIBCPP_INLINE_VISIBILITY
707    void clear() _NOEXCEPT {__tree_.clear();}
708
709#if _LIBCPP_STD_VER > 14
710    _LIBCPP_INLINE_VISIBILITY
711    insert_return_type insert(node_type&& __nh)
712    {
713        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
714            "node_type with incompatible allocator passed to set::insert()");
715        return __tree_.template __node_handle_insert_unique<
716            node_type, insert_return_type>(_VSTD::move(__nh));
717    }
718    _LIBCPP_INLINE_VISIBILITY
719    iterator insert(const_iterator __hint, node_type&& __nh)
720    {
721        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
722            "node_type with incompatible allocator passed to set::insert()");
723        return __tree_.template __node_handle_insert_unique<node_type>(
724            __hint, _VSTD::move(__nh));
725    }
726    _LIBCPP_INLINE_VISIBILITY
727    node_type extract(key_type const& __key)
728    {
729        return __tree_.template __node_handle_extract<node_type>(__key);
730    }
731    _LIBCPP_INLINE_VISIBILITY
732    node_type extract(const_iterator __it)
733    {
734        return __tree_.template __node_handle_extract<node_type>(__it);
735    }
736    template <class _Compare2>
737    _LIBCPP_INLINE_VISIBILITY
738    void merge(set<key_type, _Compare2, allocator_type>& __source)
739    {
740        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
741                       "merging container with incompatible allocator");
742        __tree_.__node_handle_merge_unique(__source.__tree_);
743    }
744    template <class _Compare2>
745    _LIBCPP_INLINE_VISIBILITY
746    void merge(set<key_type, _Compare2, allocator_type>&& __source)
747    {
748        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
749                       "merging container with incompatible allocator");
750        __tree_.__node_handle_merge_unique(__source.__tree_);
751    }
752    template <class _Compare2>
753    _LIBCPP_INLINE_VISIBILITY
754    void merge(multiset<key_type, _Compare2, allocator_type>& __source)
755    {
756        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
757                       "merging container with incompatible allocator");
758        __tree_.__node_handle_merge_unique(__source.__tree_);
759    }
760    template <class _Compare2>
761    _LIBCPP_INLINE_VISIBILITY
762    void merge(multiset<key_type, _Compare2, allocator_type>&& __source)
763    {
764        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
765                       "merging container with incompatible allocator");
766        __tree_.__node_handle_merge_unique(__source.__tree_);
767    }
768#endif
769
770    _LIBCPP_INLINE_VISIBILITY
771    void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
772        {__tree_.swap(__s.__tree_);}
773
774    _LIBCPP_INLINE_VISIBILITY
775    allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
776    _LIBCPP_INLINE_VISIBILITY
777    key_compare    key_comp()      const {return __tree_.value_comp();}
778    _LIBCPP_INLINE_VISIBILITY
779    value_compare  value_comp()    const {return __tree_.value_comp();}
780
781    // set operations:
782    _LIBCPP_INLINE_VISIBILITY
783    iterator find(const key_type& __k)             {return __tree_.find(__k);}
784    _LIBCPP_INLINE_VISIBILITY
785    const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
786#if _LIBCPP_STD_VER > 11
787    template <typename _K2>
788    _LIBCPP_INLINE_VISIBILITY
789    typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
790    find(const _K2& __k)                           {return __tree_.find(__k);}
791    template <typename _K2>
792    _LIBCPP_INLINE_VISIBILITY
793    typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
794    find(const _K2& __k) const                     {return __tree_.find(__k);}
795#endif
796
797    _LIBCPP_INLINE_VISIBILITY
798    size_type      count(const key_type& __k) const
799        {return __tree_.__count_unique(__k);}
800#if _LIBCPP_STD_VER > 11
801    template <typename _K2>
802    _LIBCPP_INLINE_VISIBILITY
803    typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
804    count(const _K2& __k) const                    {return __tree_.__count_multi(__k);}
805#endif
806
807#if _LIBCPP_STD_VER > 17
808    _LIBCPP_INLINE_VISIBILITY
809    bool contains(const key_type& __k) const {return find(__k) != end();}
810    template <typename _K2>
811    _LIBCPP_INLINE_VISIBILITY
812    typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
813    contains(const _K2& __k) const { return find(__k) != end(); }
814#endif // _LIBCPP_STD_VER > 17
815
816    _LIBCPP_INLINE_VISIBILITY
817    iterator lower_bound(const key_type& __k)
818        {return __tree_.lower_bound(__k);}
819    _LIBCPP_INLINE_VISIBILITY
820    const_iterator lower_bound(const key_type& __k) const
821        {return __tree_.lower_bound(__k);}
822#if _LIBCPP_STD_VER > 11
823    template <typename _K2>
824    _LIBCPP_INLINE_VISIBILITY
825    typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
826    lower_bound(const _K2& __k)       {return __tree_.lower_bound(__k);}
827
828    template <typename _K2>
829    _LIBCPP_INLINE_VISIBILITY
830    typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
831    lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
832#endif
833
834    _LIBCPP_INLINE_VISIBILITY
835    iterator upper_bound(const key_type& __k)
836        {return __tree_.upper_bound(__k);}
837    _LIBCPP_INLINE_VISIBILITY
838    const_iterator upper_bound(const key_type& __k) const
839        {return __tree_.upper_bound(__k);}
840#if _LIBCPP_STD_VER > 11
841    template <typename _K2>
842    _LIBCPP_INLINE_VISIBILITY
843    typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
844    upper_bound(const _K2& __k)       {return __tree_.upper_bound(__k);}
845    template <typename _K2>
846    _LIBCPP_INLINE_VISIBILITY
847    typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
848    upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
849#endif
850
851    _LIBCPP_INLINE_VISIBILITY
852    pair<iterator,iterator> equal_range(const key_type& __k)
853        {return __tree_.__equal_range_unique(__k);}
854    _LIBCPP_INLINE_VISIBILITY
855    pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
856        {return __tree_.__equal_range_unique(__k);}
857#if _LIBCPP_STD_VER > 11
858    template <typename _K2>
859    _LIBCPP_INLINE_VISIBILITY
860    typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
861    equal_range(const _K2& __k)       {return __tree_.__equal_range_multi(__k);}
862    template <typename _K2>
863    _LIBCPP_INLINE_VISIBILITY
864    typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
865    equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
866#endif
867};
868
869#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
870template<class _InputIterator,
871         class _Compare = less<__iter_value_type<_InputIterator>>,
872         class _Allocator = allocator<__iter_value_type<_InputIterator>>,
873         class = _EnableIf<__is_allocator<_Allocator>::value, void>,
874         class = _EnableIf<!__is_allocator<_Compare>::value, void>>
875set(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
876  -> set<__iter_value_type<_InputIterator>, _Compare, _Allocator>;
877
878template<class _Key, class _Compare = less<_Key>,
879         class _Allocator = allocator<_Key>,
880         class = _EnableIf<__is_allocator<_Allocator>::value, void>,
881         class = _EnableIf<!__is_allocator<_Compare>::value, void>>
882set(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator())
883  -> set<_Key, _Compare, _Allocator>;
884
885template<class _InputIterator, class _Allocator,
886         class = _EnableIf<__is_allocator<_Allocator>::value, void>>
887set(_InputIterator, _InputIterator, _Allocator)
888  -> set<__iter_value_type<_InputIterator>,
889         less<__iter_value_type<_InputIterator>>, _Allocator>;
890
891template<class _Key, class _Allocator,
892         class = _EnableIf<__is_allocator<_Allocator>::value, void>>
893set(initializer_list<_Key>, _Allocator)
894  -> set<_Key, less<_Key>, _Allocator>;
895#endif
896
897#ifndef _LIBCPP_CXX03_LANG
898
899template <class _Key, class _Compare, class _Allocator>
900set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a)
901    : __tree_(_VSTD::move(__s.__tree_), __a)
902{
903    if (__a != __s.get_allocator())
904    {
905        const_iterator __e = cend();
906        while (!__s.empty())
907            insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
908    }
909}
910
911#endif // _LIBCPP_CXX03_LANG
912
913template <class _Key, class _Compare, class _Allocator>
914inline _LIBCPP_INLINE_VISIBILITY
915bool
916operator==(const set<_Key, _Compare, _Allocator>& __x,
917           const set<_Key, _Compare, _Allocator>& __y)
918{
919    return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
920}
921
922template <class _Key, class _Compare, class _Allocator>
923inline _LIBCPP_INLINE_VISIBILITY
924bool
925operator< (const set<_Key, _Compare, _Allocator>& __x,
926           const set<_Key, _Compare, _Allocator>& __y)
927{
928    return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
929}
930
931template <class _Key, class _Compare, class _Allocator>
932inline _LIBCPP_INLINE_VISIBILITY
933bool
934operator!=(const set<_Key, _Compare, _Allocator>& __x,
935           const set<_Key, _Compare, _Allocator>& __y)
936{
937    return !(__x == __y);
938}
939
940template <class _Key, class _Compare, class _Allocator>
941inline _LIBCPP_INLINE_VISIBILITY
942bool
943operator> (const set<_Key, _Compare, _Allocator>& __x,
944           const set<_Key, _Compare, _Allocator>& __y)
945{
946    return __y < __x;
947}
948
949template <class _Key, class _Compare, class _Allocator>
950inline _LIBCPP_INLINE_VISIBILITY
951bool
952operator>=(const set<_Key, _Compare, _Allocator>& __x,
953           const set<_Key, _Compare, _Allocator>& __y)
954{
955    return !(__x < __y);
956}
957
958template <class _Key, class _Compare, class _Allocator>
959inline _LIBCPP_INLINE_VISIBILITY
960bool
961operator<=(const set<_Key, _Compare, _Allocator>& __x,
962           const set<_Key, _Compare, _Allocator>& __y)
963{
964    return !(__y < __x);
965}
966
967// specialized algorithms:
968template <class _Key, class _Compare, class _Allocator>
969inline _LIBCPP_INLINE_VISIBILITY
970void
971swap(set<_Key, _Compare, _Allocator>& __x,
972     set<_Key, _Compare, _Allocator>& __y)
973    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
974{
975    __x.swap(__y);
976}
977
978#if _LIBCPP_STD_VER > 17
979template <class _Key, class _Compare, class _Allocator, class _Predicate>
980inline _LIBCPP_INLINE_VISIBILITY
981    typename set<_Key, _Compare, _Allocator>::size_type
982    erase_if(set<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {
983  return _VSTD::__libcpp_erase_if_container(__c, __pred);
984}
985#endif
986
987template <class _Key, class _Compare = less<_Key>,
988          class _Allocator = allocator<_Key> >
989class _LIBCPP_TEMPLATE_VIS multiset
990{
991public:
992    // types:
993    typedef _Key                                     key_type;
994    typedef key_type                                 value_type;
995    typedef _Compare                                 key_compare;
996    typedef key_compare                              value_compare;
997    typedef __identity_t<_Allocator>                 allocator_type;
998    typedef value_type&                              reference;
999    typedef const value_type&                        const_reference;
1000
1001    static_assert((is_same<typename allocator_type::value_type, value_type>::value),
1002                  "Allocator::value_type must be same type as value_type");
1003
1004private:
1005    typedef __tree<value_type, value_compare, allocator_type> __base;
1006    typedef allocator_traits<allocator_type>                  __alloc_traits;
1007    typedef typename __base::__node_holder                    __node_holder;
1008
1009    __base __tree_;
1010
1011public:
1012    typedef typename __base::pointer               pointer;
1013    typedef typename __base::const_pointer         const_pointer;
1014    typedef typename __base::size_type             size_type;
1015    typedef typename __base::difference_type       difference_type;
1016    typedef typename __base::const_iterator        iterator;
1017    typedef typename __base::const_iterator        const_iterator;
1018    typedef _VSTD::reverse_iterator<iterator>       reverse_iterator;
1019    typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
1020
1021#if _LIBCPP_STD_VER > 14
1022    typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
1023#endif
1024
1025    template <class _Key2, class _Compare2, class _Alloc2>
1026        friend class _LIBCPP_TEMPLATE_VIS set;
1027    template <class _Key2, class _Compare2, class _Alloc2>
1028        friend class _LIBCPP_TEMPLATE_VIS multiset;
1029
1030    // construct/copy/destroy:
1031    _LIBCPP_INLINE_VISIBILITY
1032    multiset()
1033        _NOEXCEPT_(
1034            is_nothrow_default_constructible<allocator_type>::value &&
1035            is_nothrow_default_constructible<key_compare>::value &&
1036            is_nothrow_copy_constructible<key_compare>::value)
1037        : __tree_(value_compare()) {}
1038
1039    _LIBCPP_INLINE_VISIBILITY
1040    explicit multiset(const value_compare& __comp)
1041        _NOEXCEPT_(
1042            is_nothrow_default_constructible<allocator_type>::value &&
1043            is_nothrow_copy_constructible<key_compare>::value)
1044        : __tree_(__comp) {}
1045
1046    _LIBCPP_INLINE_VISIBILITY
1047    explicit multiset(const value_compare& __comp, const allocator_type& __a)
1048        : __tree_(__comp, __a) {}
1049    template <class _InputIterator>
1050        _LIBCPP_INLINE_VISIBILITY
1051        multiset(_InputIterator __f, _InputIterator __l,
1052                 const value_compare& __comp = value_compare())
1053        : __tree_(__comp)
1054        {
1055            insert(__f, __l);
1056        }
1057
1058#if _LIBCPP_STD_VER > 11
1059        template <class _InputIterator>
1060        _LIBCPP_INLINE_VISIBILITY
1061        multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1062            : multiset(__f, __l, key_compare(), __a) {}
1063#endif
1064
1065    template <class _InputIterator>
1066        _LIBCPP_INLINE_VISIBILITY
1067        multiset(_InputIterator __f, _InputIterator __l,
1068                 const value_compare& __comp, const allocator_type& __a)
1069        : __tree_(__comp, __a)
1070        {
1071            insert(__f, __l);
1072        }
1073
1074    _LIBCPP_INLINE_VISIBILITY
1075    multiset(const multiset& __s)
1076        : __tree_(__s.__tree_.value_comp(),
1077          __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc()))
1078        {
1079            insert(__s.begin(), __s.end());
1080        }
1081
1082    _LIBCPP_INLINE_VISIBILITY
1083    multiset& operator=(const multiset& __s)
1084        {
1085            __tree_ = __s.__tree_;
1086            return *this;
1087        }
1088
1089#ifndef _LIBCPP_CXX03_LANG
1090    _LIBCPP_INLINE_VISIBILITY
1091    multiset(multiset&& __s)
1092        _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1093        : __tree_(_VSTD::move(__s.__tree_)) {}
1094
1095    multiset(multiset&& __s, const allocator_type& __a);
1096#endif // _LIBCPP_CXX03_LANG
1097    _LIBCPP_INLINE_VISIBILITY
1098    explicit multiset(const allocator_type& __a)
1099        : __tree_(__a) {}
1100    _LIBCPP_INLINE_VISIBILITY
1101    multiset(const multiset& __s, const allocator_type& __a)
1102        : __tree_(__s.__tree_.value_comp(), __a)
1103        {
1104            insert(__s.begin(), __s.end());
1105        }
1106
1107#ifndef _LIBCPP_CXX03_LANG
1108    _LIBCPP_INLINE_VISIBILITY
1109    multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
1110        : __tree_(__comp)
1111        {
1112            insert(__il.begin(), __il.end());
1113        }
1114
1115    _LIBCPP_INLINE_VISIBILITY
1116    multiset(initializer_list<value_type> __il, const value_compare& __comp,
1117        const allocator_type& __a)
1118        : __tree_(__comp, __a)
1119        {
1120            insert(__il.begin(), __il.end());
1121        }
1122
1123#if _LIBCPP_STD_VER > 11
1124    _LIBCPP_INLINE_VISIBILITY
1125    multiset(initializer_list<value_type> __il, const allocator_type& __a)
1126        : multiset(__il, key_compare(), __a) {}
1127#endif
1128
1129    _LIBCPP_INLINE_VISIBILITY
1130    multiset& operator=(initializer_list<value_type> __il)
1131        {
1132            __tree_.__assign_multi(__il.begin(), __il.end());
1133            return *this;
1134        }
1135
1136    _LIBCPP_INLINE_VISIBILITY
1137    multiset& operator=(multiset&& __s)
1138        _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1139        {
1140            __tree_ = _VSTD::move(__s.__tree_);
1141            return *this;
1142        }
1143#endif // _LIBCPP_CXX03_LANG
1144
1145    _LIBCPP_INLINE_VISIBILITY
1146    ~multiset() {
1147        static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
1148    }
1149
1150    _LIBCPP_INLINE_VISIBILITY
1151          iterator begin() _NOEXCEPT       {return __tree_.begin();}
1152    _LIBCPP_INLINE_VISIBILITY
1153    const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
1154    _LIBCPP_INLINE_VISIBILITY
1155          iterator end() _NOEXCEPT         {return __tree_.end();}
1156    _LIBCPP_INLINE_VISIBILITY
1157    const_iterator end()   const _NOEXCEPT {return __tree_.end();}
1158
1159    _LIBCPP_INLINE_VISIBILITY
1160          reverse_iterator rbegin() _NOEXCEPT
1161            {return reverse_iterator(end());}
1162    _LIBCPP_INLINE_VISIBILITY
1163    const_reverse_iterator rbegin() const _NOEXCEPT
1164        {return const_reverse_iterator(end());}
1165    _LIBCPP_INLINE_VISIBILITY
1166          reverse_iterator rend() _NOEXCEPT
1167            {return       reverse_iterator(begin());}
1168    _LIBCPP_INLINE_VISIBILITY
1169    const_reverse_iterator rend() const _NOEXCEPT
1170        {return const_reverse_iterator(begin());}
1171
1172    _LIBCPP_INLINE_VISIBILITY
1173    const_iterator cbegin()  const _NOEXCEPT {return begin();}
1174    _LIBCPP_INLINE_VISIBILITY
1175    const_iterator cend() const _NOEXCEPT {return end();}
1176    _LIBCPP_INLINE_VISIBILITY
1177    const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1178    _LIBCPP_INLINE_VISIBILITY
1179    const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1180
1181    _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1182    bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1183    _LIBCPP_INLINE_VISIBILITY
1184    size_type size() const _NOEXCEPT {return __tree_.size();}
1185    _LIBCPP_INLINE_VISIBILITY
1186    size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1187
1188    // modifiers:
1189#ifndef _LIBCPP_CXX03_LANG
1190    template <class... _Args>
1191        _LIBCPP_INLINE_VISIBILITY
1192        iterator emplace(_Args&&... __args)
1193            {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
1194    template <class... _Args>
1195        _LIBCPP_INLINE_VISIBILITY
1196        iterator emplace_hint(const_iterator __p, _Args&&... __args)
1197            {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
1198#endif // _LIBCPP_CXX03_LANG
1199
1200    _LIBCPP_INLINE_VISIBILITY
1201    iterator insert(const value_type& __v)
1202        {return __tree_.__insert_multi(__v);}
1203    _LIBCPP_INLINE_VISIBILITY
1204    iterator insert(const_iterator __p, const value_type& __v)
1205        {return __tree_.__insert_multi(__p, __v);}
1206
1207    template <class _InputIterator>
1208        _LIBCPP_INLINE_VISIBILITY
1209        void insert(_InputIterator __f, _InputIterator __l)
1210        {
1211            for (const_iterator __e = cend(); __f != __l; ++__f)
1212                __tree_.__insert_multi(__e, *__f);
1213        }
1214
1215#ifndef _LIBCPP_CXX03_LANG
1216    _LIBCPP_INLINE_VISIBILITY
1217    iterator insert(value_type&& __v)
1218        {return __tree_.__insert_multi(_VSTD::move(__v));}
1219
1220    _LIBCPP_INLINE_VISIBILITY
1221    iterator insert(const_iterator __p, value_type&& __v)
1222        {return __tree_.__insert_multi(__p, _VSTD::move(__v));}
1223
1224    _LIBCPP_INLINE_VISIBILITY
1225    void insert(initializer_list<value_type> __il)
1226        {insert(__il.begin(), __il.end());}
1227#endif // _LIBCPP_CXX03_LANG
1228
1229    _LIBCPP_INLINE_VISIBILITY
1230    iterator  erase(const_iterator __p) {return __tree_.erase(__p);}
1231    _LIBCPP_INLINE_VISIBILITY
1232    size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1233    _LIBCPP_INLINE_VISIBILITY
1234    iterator  erase(const_iterator __f, const_iterator __l)
1235        {return __tree_.erase(__f, __l);}
1236    _LIBCPP_INLINE_VISIBILITY
1237    void clear() _NOEXCEPT {__tree_.clear();}
1238
1239#if _LIBCPP_STD_VER > 14
1240    _LIBCPP_INLINE_VISIBILITY
1241    iterator insert(node_type&& __nh)
1242    {
1243        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1244            "node_type with incompatible allocator passed to multiset::insert()");
1245        return __tree_.template __node_handle_insert_multi<node_type>(
1246            _VSTD::move(__nh));
1247    }
1248    _LIBCPP_INLINE_VISIBILITY
1249    iterator insert(const_iterator __hint, node_type&& __nh)
1250    {
1251        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1252            "node_type with incompatible allocator passed to multiset::insert()");
1253        return __tree_.template __node_handle_insert_multi<node_type>(
1254            __hint, _VSTD::move(__nh));
1255    }
1256    _LIBCPP_INLINE_VISIBILITY
1257    node_type extract(key_type const& __key)
1258    {
1259        return __tree_.template __node_handle_extract<node_type>(__key);
1260    }
1261    _LIBCPP_INLINE_VISIBILITY
1262    node_type extract(const_iterator __it)
1263    {
1264        return __tree_.template __node_handle_extract<node_type>(__it);
1265    }
1266    template <class _Compare2>
1267    _LIBCPP_INLINE_VISIBILITY
1268    void merge(multiset<key_type, _Compare2, allocator_type>& __source)
1269    {
1270        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1271                       "merging container with incompatible allocator");
1272        __tree_.__node_handle_merge_multi(__source.__tree_);
1273    }
1274    template <class _Compare2>
1275    _LIBCPP_INLINE_VISIBILITY
1276    void merge(multiset<key_type, _Compare2, allocator_type>&& __source)
1277    {
1278        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1279                       "merging container with incompatible allocator");
1280        __tree_.__node_handle_merge_multi(__source.__tree_);
1281    }
1282    template <class _Compare2>
1283    _LIBCPP_INLINE_VISIBILITY
1284    void merge(set<key_type, _Compare2, allocator_type>& __source)
1285    {
1286        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1287                       "merging container with incompatible allocator");
1288        __tree_.__node_handle_merge_multi(__source.__tree_);
1289    }
1290    template <class _Compare2>
1291    _LIBCPP_INLINE_VISIBILITY
1292    void merge(set<key_type, _Compare2, allocator_type>&& __source)
1293    {
1294        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1295                       "merging container with incompatible allocator");
1296        __tree_.__node_handle_merge_multi(__source.__tree_);
1297    }
1298#endif
1299
1300    _LIBCPP_INLINE_VISIBILITY
1301    void swap(multiset& __s)
1302        _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1303        {__tree_.swap(__s.__tree_);}
1304
1305    _LIBCPP_INLINE_VISIBILITY
1306    allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
1307    _LIBCPP_INLINE_VISIBILITY
1308    key_compare    key_comp()      const {return __tree_.value_comp();}
1309    _LIBCPP_INLINE_VISIBILITY
1310    value_compare  value_comp()    const {return __tree_.value_comp();}
1311
1312    // set operations:
1313    _LIBCPP_INLINE_VISIBILITY
1314    iterator find(const key_type& __k)             {return __tree_.find(__k);}
1315    _LIBCPP_INLINE_VISIBILITY
1316    const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1317#if _LIBCPP_STD_VER > 11
1318    template <typename _K2>
1319    _LIBCPP_INLINE_VISIBILITY
1320    typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1321    find(const _K2& __k)                           {return __tree_.find(__k);}
1322    template <typename _K2>
1323    _LIBCPP_INLINE_VISIBILITY
1324    typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1325    find(const _K2& __k) const                     {return __tree_.find(__k);}
1326#endif
1327
1328    _LIBCPP_INLINE_VISIBILITY
1329    size_type      count(const key_type& __k) const
1330        {return __tree_.__count_multi(__k);}
1331#if _LIBCPP_STD_VER > 11
1332    template <typename _K2>
1333    _LIBCPP_INLINE_VISIBILITY
1334    typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1335    count(const _K2& __k) const            {return __tree_.__count_multi(__k);}
1336#endif
1337
1338#if _LIBCPP_STD_VER > 17
1339    _LIBCPP_INLINE_VISIBILITY
1340    bool contains(const key_type& __k) const {return find(__k) != end();}
1341    template <typename _K2>
1342    _LIBCPP_INLINE_VISIBILITY
1343    typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
1344    contains(const _K2& __k) const { return find(__k) != end(); }
1345#endif // _LIBCPP_STD_VER > 17
1346
1347    _LIBCPP_INLINE_VISIBILITY
1348    iterator lower_bound(const key_type& __k)
1349        {return __tree_.lower_bound(__k);}
1350    _LIBCPP_INLINE_VISIBILITY
1351    const_iterator lower_bound(const key_type& __k) const
1352            {return __tree_.lower_bound(__k);}
1353#if _LIBCPP_STD_VER > 11
1354    template <typename _K2>
1355    _LIBCPP_INLINE_VISIBILITY
1356    typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1357    lower_bound(const _K2& __k)       {return __tree_.lower_bound(__k);}
1358
1359    template <typename _K2>
1360    _LIBCPP_INLINE_VISIBILITY
1361    typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1362    lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1363#endif
1364
1365    _LIBCPP_INLINE_VISIBILITY
1366    iterator upper_bound(const key_type& __k)
1367            {return __tree_.upper_bound(__k);}
1368    _LIBCPP_INLINE_VISIBILITY
1369    const_iterator upper_bound(const key_type& __k) const
1370            {return __tree_.upper_bound(__k);}
1371#if _LIBCPP_STD_VER > 11
1372    template <typename _K2>
1373    _LIBCPP_INLINE_VISIBILITY
1374    typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1375    upper_bound(const _K2& __k)       {return __tree_.upper_bound(__k);}
1376    template <typename _K2>
1377    _LIBCPP_INLINE_VISIBILITY
1378    typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1379    upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1380#endif
1381
1382    _LIBCPP_INLINE_VISIBILITY
1383    pair<iterator,iterator>             equal_range(const key_type& __k)
1384            {return __tree_.__equal_range_multi(__k);}
1385    _LIBCPP_INLINE_VISIBILITY
1386    pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1387            {return __tree_.__equal_range_multi(__k);}
1388#if _LIBCPP_STD_VER > 11
1389    template <typename _K2>
1390    _LIBCPP_INLINE_VISIBILITY
1391    typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1392    equal_range(const _K2& __k)       {return __tree_.__equal_range_multi(__k);}
1393    template <typename _K2>
1394    _LIBCPP_INLINE_VISIBILITY
1395    typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1396    equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1397#endif
1398};
1399
1400#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
1401template<class _InputIterator,
1402         class _Compare = less<__iter_value_type<_InputIterator>>,
1403         class _Allocator = allocator<__iter_value_type<_InputIterator>>,
1404         class = _EnableIf<__is_allocator<_Allocator>::value, void>,
1405         class = _EnableIf<!__is_allocator<_Compare>::value, void>>
1406multiset(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1407  -> multiset<__iter_value_type<_InputIterator>, _Compare, _Allocator>;
1408
1409template<class _Key, class _Compare = less<_Key>,
1410         class _Allocator = allocator<_Key>,
1411         class = _EnableIf<__is_allocator<_Allocator>::value, void>,
1412         class = _EnableIf<!__is_allocator<_Compare>::value, void>>
1413multiset(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator())
1414  -> multiset<_Key, _Compare, _Allocator>;
1415
1416template<class _InputIterator, class _Allocator,
1417         class = _EnableIf<__is_allocator<_Allocator>::value, void>>
1418multiset(_InputIterator, _InputIterator, _Allocator)
1419  -> multiset<__iter_value_type<_InputIterator>,
1420         less<__iter_value_type<_InputIterator>>, _Allocator>;
1421
1422template<class _Key, class _Allocator,
1423         class = _EnableIf<__is_allocator<_Allocator>::value, void>>
1424multiset(initializer_list<_Key>, _Allocator)
1425  -> multiset<_Key, less<_Key>, _Allocator>;
1426#endif
1427
1428#ifndef _LIBCPP_CXX03_LANG
1429
1430template <class _Key, class _Compare, class _Allocator>
1431multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a)
1432    : __tree_(_VSTD::move(__s.__tree_), __a)
1433{
1434    if (__a != __s.get_allocator())
1435    {
1436        const_iterator __e = cend();
1437        while (!__s.empty())
1438            insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
1439    }
1440}
1441
1442#endif // _LIBCPP_CXX03_LANG
1443
1444template <class _Key, class _Compare, class _Allocator>
1445inline _LIBCPP_INLINE_VISIBILITY
1446bool
1447operator==(const multiset<_Key, _Compare, _Allocator>& __x,
1448           const multiset<_Key, _Compare, _Allocator>& __y)
1449{
1450    return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1451}
1452
1453template <class _Key, class _Compare, class _Allocator>
1454inline _LIBCPP_INLINE_VISIBILITY
1455bool
1456operator< (const multiset<_Key, _Compare, _Allocator>& __x,
1457           const multiset<_Key, _Compare, _Allocator>& __y)
1458{
1459    return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1460}
1461
1462template <class _Key, class _Compare, class _Allocator>
1463inline _LIBCPP_INLINE_VISIBILITY
1464bool
1465operator!=(const multiset<_Key, _Compare, _Allocator>& __x,
1466           const multiset<_Key, _Compare, _Allocator>& __y)
1467{
1468    return !(__x == __y);
1469}
1470
1471template <class _Key, class _Compare, class _Allocator>
1472inline _LIBCPP_INLINE_VISIBILITY
1473bool
1474operator> (const multiset<_Key, _Compare, _Allocator>& __x,
1475           const multiset<_Key, _Compare, _Allocator>& __y)
1476{
1477    return __y < __x;
1478}
1479
1480template <class _Key, class _Compare, class _Allocator>
1481inline _LIBCPP_INLINE_VISIBILITY
1482bool
1483operator>=(const multiset<_Key, _Compare, _Allocator>& __x,
1484           const multiset<_Key, _Compare, _Allocator>& __y)
1485{
1486    return !(__x < __y);
1487}
1488
1489template <class _Key, class _Compare, class _Allocator>
1490inline _LIBCPP_INLINE_VISIBILITY
1491bool
1492operator<=(const multiset<_Key, _Compare, _Allocator>& __x,
1493           const multiset<_Key, _Compare, _Allocator>& __y)
1494{
1495    return !(__y < __x);
1496}
1497
1498template <class _Key, class _Compare, class _Allocator>
1499inline _LIBCPP_INLINE_VISIBILITY
1500void
1501swap(multiset<_Key, _Compare, _Allocator>& __x,
1502     multiset<_Key, _Compare, _Allocator>& __y)
1503    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1504{
1505    __x.swap(__y);
1506}
1507
1508#if _LIBCPP_STD_VER > 17
1509template <class _Key, class _Compare, class _Allocator, class _Predicate>
1510inline _LIBCPP_INLINE_VISIBILITY
1511    typename multiset<_Key, _Compare, _Allocator>::size_type
1512    erase_if(multiset<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {
1513  return _VSTD::__libcpp_erase_if_container(__c, __pred);
1514}
1515#endif
1516
1517_LIBCPP_END_NAMESPACE_STD
1518
1519#endif // _LIBCPP_SET
1520