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