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