xref: /freebsd/contrib/llvm-project/libcxx/include/set (revision 06c3fb2749bda94cb5201f81ffdb8fa6c3161b2e)
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    template<container-compatible-range<value_type> R>
60      set(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23
61    set(const set& s);
62    set(set&& s)
63        noexcept(
64            is_nothrow_move_constructible<allocator_type>::value &&
65            is_nothrow_move_constructible<key_compare>::value);
66    explicit set(const allocator_type& a);
67    set(const set& s, const allocator_type& a);
68    set(set&& s, const allocator_type& a);
69    set(initializer_list<value_type> il, const value_compare& comp = value_compare());
70    set(initializer_list<value_type> il, const value_compare& comp,
71        const allocator_type& a);
72    template <class InputIterator>
73        set(InputIterator first, InputIterator last, const allocator_type& a)
74            : set(first, last, Compare(), a) {}  // C++14
75    template<container-compatible-range<value_type> R>
76      set(from_range_t, R&& rg, const Allocator& a))
77        : set(from_range, std::forward<R>(rg), Compare(), a) { } // C++23
78    set(initializer_list<value_type> il, const allocator_type& a)
79        : set(il, Compare(), a) {}  // C++14
80    ~set();
81
82    set& operator=(const set& s);
83    set& operator=(set&& s)
84        noexcept(
85            allocator_type::propagate_on_container_move_assignment::value &&
86            is_nothrow_move_assignable<allocator_type>::value &&
87            is_nothrow_move_assignable<key_compare>::value);
88    set& operator=(initializer_list<value_type> il);
89
90    // iterators:
91          iterator begin() noexcept;
92    const_iterator begin() const noexcept;
93          iterator end() noexcept;
94    const_iterator end()   const noexcept;
95
96          reverse_iterator rbegin() noexcept;
97    const_reverse_iterator rbegin() const noexcept;
98          reverse_iterator rend() noexcept;
99    const_reverse_iterator rend()   const noexcept;
100
101    const_iterator         cbegin()  const noexcept;
102    const_iterator         cend()    const noexcept;
103    const_reverse_iterator crbegin() const noexcept;
104    const_reverse_iterator crend()   const noexcept;
105
106    // capacity:
107    bool      empty()    const noexcept;
108    size_type size()     const noexcept;
109    size_type max_size() const noexcept;
110
111    // modifiers:
112    template <class... Args>
113        pair<iterator, bool> emplace(Args&&... args);
114    template <class... Args>
115        iterator emplace_hint(const_iterator position, Args&&... args);
116    pair<iterator,bool> insert(const value_type& v);
117    pair<iterator,bool> insert(value_type&& v);
118    iterator insert(const_iterator position, const value_type& v);
119    iterator insert(const_iterator position, value_type&& v);
120    template <class InputIterator>
121        void insert(InputIterator first, InputIterator last);
122    template<container-compatible-range<value_type> R>
123      void insert_range(R&& rg);                                                      // C++23
124    void insert(initializer_list<value_type> il);
125
126    node_type extract(const_iterator position);                                       // C++17
127    node_type extract(const key_type& x);                                             // C++17
128    insert_return_type insert(node_type&& nh);                                        // C++17
129    iterator insert(const_iterator hint, node_type&& nh);                             // C++17
130
131    iterator  erase(const_iterator position);
132    iterator  erase(iterator position);  // C++14
133    size_type erase(const key_type& k);
134    iterator  erase(const_iterator first, const_iterator last);
135    void clear() noexcept;
136
137    template<class C2>
138      void merge(set<Key, C2, Allocator>& source);         // C++17
139    template<class C2>
140      void merge(set<Key, C2, Allocator>&& source);        // C++17
141    template<class C2>
142      void merge(multiset<Key, C2, Allocator>& source);    // C++17
143    template<class C2>
144      void merge(multiset<Key, C2, Allocator>&& source);   // C++17
145
146    void swap(set& s)
147        noexcept(
148            __is_nothrow_swappable<key_compare>::value &&
149            (!allocator_type::propagate_on_container_swap::value ||
150             __is_nothrow_swappable<allocator_type>::value));
151
152    // observers:
153    allocator_type get_allocator() const noexcept;
154    key_compare    key_comp()      const;
155    value_compare  value_comp()    const;
156
157    // set operations:
158          iterator find(const key_type& k);
159    const_iterator find(const key_type& k) const;
160    template<typename K>
161        iterator find(const K& x);
162    template<typename K>
163        const_iterator find(const K& x) const;  // C++14
164
165    template<typename K>
166        size_type count(const K& x) const;        // C++14
167    size_type      count(const key_type& k) const;
168
169    bool           contains(const key_type& x) const;  // C++20
170    template<class K> bool contains(const K& x) const; // C++20
171
172          iterator lower_bound(const key_type& k);
173    const_iterator lower_bound(const key_type& k) const;
174    template<typename K>
175        iterator lower_bound(const K& x);              // C++14
176    template<typename K>
177        const_iterator lower_bound(const K& x) const;  // C++14
178
179          iterator upper_bound(const key_type& k);
180    const_iterator upper_bound(const key_type& k) const;
181    template<typename K>
182        iterator upper_bound(const K& x);              // C++14
183    template<typename K>
184        const_iterator upper_bound(const K& x) const;  // C++14
185    pair<iterator,iterator>             equal_range(const key_type& k);
186    pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
187    template<typename K>
188        pair<iterator,iterator>             equal_range(const K& x);        // C++14
189    template<typename K>
190        pair<const_iterator,const_iterator> equal_range(const K& x) const;  // C++14
191};
192
193template <class InputIterator,
194      class Compare = less<typename iterator_traits<InputIterator>::value_type>,
195      class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
196set(InputIterator, InputIterator,
197    Compare = Compare(), Allocator = Allocator())
198  -> set<typename iterator_traits<InputIterator>::value_type, Compare, Allocator>; // C++17
199
200template<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>,
201         class Allocator = allocator<ranges::range_value_t<R>>>
202  set(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
203    -> set<ranges::range_value_t<R>, Compare, Allocator>; // C++23
204
205template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
206set(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
207  -> set<Key, Compare, Allocator>; // C++17
208
209template<class InputIterator, class Allocator>
210set(InputIterator, InputIterator, Allocator)
211  -> set<typename iterator_traits<InputIterator>::value_type,
212          less<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17
213
214template<ranges::input_range R, class Allocator>
215  set(from_range_t, R&&, Allocator)
216    -> set<ranges::range_value_t<R>, less<ranges::range_value_t<R>>, Allocator>; // C++23
217
218template<class Key, class Allocator>
219set(initializer_list<Key>, Allocator) -> set<Key, less<Key>, Allocator>; // C++17
220
221template <class Key, class Compare, class Allocator>
222bool
223operator==(const set<Key, Compare, Allocator>& x,
224           const set<Key, Compare, Allocator>& y);
225
226template <class Key, class Compare, class Allocator>
227bool
228operator< (const set<Key, Compare, Allocator>& x,
229           const set<Key, Compare, Allocator>& y);                                // removed in C++20
230
231template <class Key, class Compare, class Allocator>
232bool
233operator!=(const set<Key, Compare, Allocator>& x,
234           const set<Key, Compare, Allocator>& y);                                // removed in C++20
235
236template <class Key, class Compare, class Allocator>
237bool
238operator> (const set<Key, Compare, Allocator>& x,
239           const set<Key, Compare, Allocator>& y);                                // removed in C++20
240
241template <class Key, class Compare, class Allocator>
242bool
243operator>=(const set<Key, Compare, Allocator>& x,
244           const set<Key, Compare, Allocator>& y);                                // removed in C++20
245
246template <class Key, class Compare, class Allocator>
247bool
248operator<=(const set<Key, Compare, Allocator>& x,
249           const set<Key, Compare, Allocator>& y);                                // removed in C++20
250
251template<class Key, class Compare, class Allocator>
252  synth-three-way-result<Key> operator<=>(const set<Key, Compare, Allocator>& x,
253                                          const set<Key, Compare, Allocator>& y); // since C++20
254
255// specialized algorithms:
256template <class Key, class Compare, class Allocator>
257void
258swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y)
259    noexcept(noexcept(x.swap(y)));
260
261template <class Key, class Compare, class Allocator, class Predicate>
262typename set<Key, Compare, Allocator>::size_type
263erase_if(set<Key, Compare, Allocator>& c, Predicate pred);  // C++20
264
265template <class Key, class Compare = less<Key>,
266          class Allocator = allocator<Key>>
267class multiset
268{
269public:
270    // types:
271    typedef Key                                      key_type;
272    typedef key_type                                 value_type;
273    typedef Compare                                  key_compare;
274    typedef key_compare                              value_compare;
275    typedef Allocator                                allocator_type;
276    typedef typename allocator_type::reference       reference;
277    typedef typename allocator_type::const_reference const_reference;
278    typedef typename allocator_type::size_type       size_type;
279    typedef typename allocator_type::difference_type difference_type;
280    typedef typename allocator_type::pointer         pointer;
281    typedef typename allocator_type::const_pointer   const_pointer;
282
283    typedef implementation-defined                   iterator;
284    typedef implementation-defined                   const_iterator;
285    typedef std::reverse_iterator<iterator>          reverse_iterator;
286    typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
287    typedef unspecified                              node_type;               // C++17
288
289    // construct/copy/destroy:
290    multiset()
291        noexcept(
292            is_nothrow_default_constructible<allocator_type>::value &&
293            is_nothrow_default_constructible<key_compare>::value &&
294            is_nothrow_copy_constructible<key_compare>::value);
295    explicit multiset(const value_compare& comp);
296    multiset(const value_compare& comp, const allocator_type& a);
297    template <class InputIterator>
298        multiset(InputIterator first, InputIterator last,
299                 const value_compare& comp = value_compare());
300    template <class InputIterator>
301        multiset(InputIterator first, InputIterator last,
302                 const value_compare& comp, const allocator_type& a);
303    template<container-compatible-range<value_type> R>
304      multiset(from_range_t, R&& rg,
305               const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23
306    multiset(const multiset& s);
307    multiset(multiset&& s)
308        noexcept(
309            is_nothrow_move_constructible<allocator_type>::value &&
310            is_nothrow_move_constructible<key_compare>::value);
311    explicit multiset(const allocator_type& a);
312    multiset(const multiset& s, const allocator_type& a);
313    multiset(multiset&& s, const allocator_type& a);
314    multiset(initializer_list<value_type> il, const value_compare& comp = value_compare());
315    multiset(initializer_list<value_type> il, const value_compare& comp,
316             const allocator_type& a);
317    template <class InputIterator>
318        multiset(InputIterator first, InputIterator last, const allocator_type& a)
319            : set(first, last, Compare(), a) {}  // C++14
320    template<container-compatible-range<value_type> R>
321      multiset(from_range_t, R&& rg, const Allocator& a))
322        : multiset(from_range, std::forward<R>(rg), Compare(), a) { } // C++23
323    multiset(initializer_list<value_type> il, const allocator_type& a)
324        : set(il, Compare(), a) {}  // C++14
325    ~multiset();
326
327    multiset& operator=(const multiset& s);
328    multiset& operator=(multiset&& s)
329        noexcept(
330            allocator_type::propagate_on_container_move_assignment::value &&
331            is_nothrow_move_assignable<allocator_type>::value &&
332            is_nothrow_move_assignable<key_compare>::value);
333    multiset& operator=(initializer_list<value_type> il);
334
335    // iterators:
336          iterator begin() noexcept;
337    const_iterator begin() const noexcept;
338          iterator end() noexcept;
339    const_iterator end()   const noexcept;
340
341          reverse_iterator rbegin() noexcept;
342    const_reverse_iterator rbegin() const noexcept;
343          reverse_iterator rend() noexcept;
344    const_reverse_iterator rend()   const noexcept;
345
346    const_iterator         cbegin()  const noexcept;
347    const_iterator         cend()    const noexcept;
348    const_reverse_iterator crbegin() const noexcept;
349    const_reverse_iterator crend()   const noexcept;
350
351    // capacity:
352    bool      empty()    const noexcept;
353    size_type size()     const noexcept;
354    size_type max_size() const noexcept;
355
356    // modifiers:
357    template <class... Args>
358        iterator emplace(Args&&... args);
359    template <class... Args>
360        iterator emplace_hint(const_iterator position, Args&&... args);
361    iterator insert(const value_type& v);
362    iterator insert(value_type&& v);
363    iterator insert(const_iterator position, const value_type& v);
364    iterator insert(const_iterator position, value_type&& v);
365    template <class InputIterator>
366        void insert(InputIterator first, InputIterator last);
367    template<container-compatible-range<value_type> R>
368      void insert_range(R&& rg);                                                      // C++23
369    void insert(initializer_list<value_type> il);
370
371    node_type extract(const_iterator position);                                       // C++17
372    node_type extract(const key_type& x);                                             // C++17
373    iterator insert(node_type&& nh);                                                  // C++17
374    iterator insert(const_iterator hint, node_type&& nh);                             // C++17
375
376    iterator  erase(const_iterator position);
377    iterator  erase(iterator position);  // C++14
378    size_type erase(const key_type& k);
379    iterator  erase(const_iterator first, const_iterator last);
380    void clear() noexcept;
381
382    template<class C2>
383      void merge(multiset<Key, C2, Allocator>& source);    // C++17
384    template<class C2>
385      void merge(multiset<Key, C2, Allocator>&& source);   // C++17
386    template<class C2>
387      void merge(set<Key, C2, Allocator>& source);         // C++17
388    template<class C2>
389      void merge(set<Key, C2, Allocator>&& source);        // C++17
390
391    void swap(multiset& s)
392        noexcept(
393            __is_nothrow_swappable<key_compare>::value &&
394            (!allocator_type::propagate_on_container_swap::value ||
395             __is_nothrow_swappable<allocator_type>::value));
396
397    // observers:
398    allocator_type get_allocator() const noexcept;
399    key_compare    key_comp()      const;
400    value_compare  value_comp()    const;
401
402    // set operations:
403          iterator find(const key_type& k);
404    const_iterator find(const key_type& k) const;
405    template<typename K>
406        iterator find(const K& x);
407    template<typename K>
408        const_iterator find(const K& x) const;  // C++14
409
410    template<typename K>
411        size_type count(const K& x) const;      // C++14
412    size_type      count(const key_type& k) const;
413
414    bool           contains(const key_type& x) const;  // C++20
415    template<class K> bool contains(const K& x) const; // C++20
416
417          iterator lower_bound(const key_type& k);
418    const_iterator lower_bound(const key_type& k) const;
419    template<typename K>
420        iterator lower_bound(const K& x);              // C++14
421    template<typename K>
422        const_iterator lower_bound(const K& x) const;  // C++14
423
424          iterator upper_bound(const key_type& k);
425    const_iterator upper_bound(const key_type& k) const;
426    template<typename K>
427        iterator upper_bound(const K& x);              // C++14
428    template<typename K>
429        const_iterator upper_bound(const K& x) const;  // C++14
430
431    pair<iterator,iterator>             equal_range(const key_type& k);
432    pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
433    template<typename K>
434        pair<iterator,iterator>             equal_range(const K& x);        // C++14
435    template<typename K>
436        pair<const_iterator,const_iterator> equal_range(const K& x) const;  // C++14
437};
438
439template <class InputIterator,
440      class Compare = less<typename iterator_traits<InputIterator>::value_type>,
441      class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
442multiset(InputIterator, InputIterator,
443    Compare = Compare(), Allocator = Allocator())
444  -> multiset<typename iterator_traits<InputIterator>::value_type, Compare, Allocator>; // C++17
445
446template<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>,
447          class Allocator = allocator<ranges::range_value_t<R>>>
448  multiset(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
449    -> multiset<ranges::range_value_t<R>, Compare, Allocator>;
450
451template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
452multiset(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
453  -> multiset<Key, Compare, Allocator>; // C++17
454
455template<class InputIterator, class Allocator>
456multiset(InputIterator, InputIterator, Allocator)
457  -> multiset<typename iterator_traits<InputIterator>::value_type,
458          less<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17
459
460template<ranges::input_range R, class Allocator>
461  multiset(from_range_t, R&&, Allocator)
462    -> multiset<ranges::range_value_t<R>, less<ranges::range_value_t<R>>, Allocator>;
463
464template<class Key, class Allocator>
465multiset(initializer_list<Key>, Allocator) -> multiset<Key, less<Key>, Allocator>; // C++17
466
467template <class Key, class Compare, class Allocator>
468bool
469operator==(const multiset<Key, Compare, Allocator>& x,
470           const multiset<Key, Compare, Allocator>& y);
471
472template <class Key, class Compare, class Allocator>
473bool
474operator< (const multiset<Key, Compare, Allocator>& x,
475           const multiset<Key, Compare, Allocator>& y);                                // removed in C++20
476
477template <class Key, class Compare, class Allocator>
478bool
479operator!=(const multiset<Key, Compare, Allocator>& x,
480           const multiset<Key, Compare, Allocator>& y);                                // removed in C++20
481
482template <class Key, class Compare, class Allocator>
483bool
484operator> (const multiset<Key, Compare, Allocator>& x,
485           const multiset<Key, Compare, Allocator>& y);                                // removed in C++20
486
487template <class Key, class Compare, class Allocator>
488bool
489operator>=(const multiset<Key, Compare, Allocator>& x,
490           const multiset<Key, Compare, Allocator>& y);                                // removed in C++20
491
492template <class Key, class Compare, class Allocator>
493bool
494operator<=(const multiset<Key, Compare, Allocator>& x,
495           const multiset<Key, Compare, Allocator>& y);                                // removed in C++20
496
497template<class Key, class Compare, class Allocator>
498  synth-three-way-result<Key> operator<=>(const multiset<Key, Compare, Allocator>& x,
499                                          const multiset<Key, Compare, Allocator>& y); // since C++20
500
501// specialized algorithms:
502template <class Key, class Compare, class Allocator>
503void
504swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y)
505    noexcept(noexcept(x.swap(y)));
506
507template <class Key, class Compare, class Allocator, class Predicate>
508typename multiset<Key, Compare, Allocator>::size_type
509erase_if(multiset<Key, Compare, Allocator>& c, Predicate pred);  // C++20
510
511}  // std
512
513*/
514
515#include <__algorithm/equal.h>
516#include <__algorithm/lexicographical_compare.h>
517#include <__algorithm/lexicographical_compare_three_way.h>
518#include <__assert> // all public C++ headers provide the assertion handler
519#include <__availability>
520#include <__config>
521#include <__functional/is_transparent.h>
522#include <__functional/operations.h>
523#include <__iterator/erase_if_container.h>
524#include <__iterator/iterator_traits.h>
525#include <__iterator/ranges_iterator_traits.h>
526#include <__iterator/reverse_iterator.h>
527#include <__memory/allocator.h>
528#include <__memory_resource/polymorphic_allocator.h>
529#include <__node_handle>
530#include <__ranges/concepts.h>
531#include <__ranges/container_compatible_range.h>
532#include <__ranges/from_range.h>
533#include <__tree>
534#include <__type_traits/is_allocator.h>
535#include <__utility/forward.h>
536#include <version>
537
538// standard-mandated includes
539
540// [iterator.range]
541#include <__iterator/access.h>
542#include <__iterator/data.h>
543#include <__iterator/empty.h>
544#include <__iterator/reverse_access.h>
545#include <__iterator/size.h>
546
547// [associative.set.syn]
548#include <compare>
549#include <initializer_list>
550
551#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
552#  pragma GCC system_header
553#endif
554
555_LIBCPP_BEGIN_NAMESPACE_STD
556
557template <class _Key, class _Compare, class _Allocator>
558class multiset;
559
560template <class _Key, class _Compare = less<_Key>,
561          class _Allocator = allocator<_Key> >
562class _LIBCPP_TEMPLATE_VIS set
563{
564public:
565    // types:
566    typedef _Key                                     key_type;
567    typedef key_type                                 value_type;
568    typedef __type_identity_t<_Compare>              key_compare;
569    typedef key_compare                              value_compare;
570    typedef __type_identity_t<_Allocator>            allocator_type;
571    typedef value_type&                              reference;
572    typedef const value_type&                        const_reference;
573
574    static_assert((is_same<typename allocator_type::value_type, value_type>::value),
575                  "Allocator::value_type must be same type as value_type");
576
577private:
578    typedef __tree<value_type, value_compare, allocator_type> __base;
579    typedef allocator_traits<allocator_type>                  __alloc_traits;
580
581    static_assert(is_same<allocator_type, __rebind_alloc<__alloc_traits, value_type> >::value,
582                  "[allocator.requirements] states that rebinding an allocator to the same type should result in the "
583                  "original allocator");
584
585    __base __tree_;
586
587public:
588    typedef typename __base::pointer               pointer;
589    typedef typename __base::const_pointer         const_pointer;
590    typedef typename __base::size_type             size_type;
591    typedef typename __base::difference_type       difference_type;
592    typedef typename __base::const_iterator        iterator;
593    typedef typename __base::const_iterator        const_iterator;
594    typedef _VSTD::reverse_iterator<iterator>       reverse_iterator;
595    typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
596
597#if _LIBCPP_STD_VER >= 17
598    typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
599    typedef __insert_return_type<iterator, node_type> insert_return_type;
600#endif
601
602    template <class _Key2, class _Compare2, class _Alloc2>
603        friend class _LIBCPP_TEMPLATE_VIS set;
604    template <class _Key2, class _Compare2, class _Alloc2>
605        friend class _LIBCPP_TEMPLATE_VIS multiset;
606
607    _LIBCPP_INLINE_VISIBILITY
608    set()
609        _NOEXCEPT_(
610            is_nothrow_default_constructible<allocator_type>::value &&
611            is_nothrow_default_constructible<key_compare>::value &&
612            is_nothrow_copy_constructible<key_compare>::value)
613        : __tree_(value_compare()) {}
614
615    _LIBCPP_INLINE_VISIBILITY
616    explicit set(const value_compare& __comp)
617        _NOEXCEPT_(
618            is_nothrow_default_constructible<allocator_type>::value &&
619            is_nothrow_copy_constructible<key_compare>::value)
620        : __tree_(__comp) {}
621
622    _LIBCPP_INLINE_VISIBILITY
623    explicit set(const value_compare& __comp, const allocator_type& __a)
624        : __tree_(__comp, __a) {}
625    template <class _InputIterator>
626        _LIBCPP_INLINE_VISIBILITY
627        set(_InputIterator __f, _InputIterator __l,
628            const value_compare& __comp = value_compare())
629        : __tree_(__comp)
630        {
631            insert(__f, __l);
632        }
633
634    template <class _InputIterator>
635        _LIBCPP_INLINE_VISIBILITY
636        set(_InputIterator __f, _InputIterator __l, const value_compare& __comp,
637            const allocator_type& __a)
638        : __tree_(__comp, __a)
639        {
640            insert(__f, __l);
641        }
642
643#if _LIBCPP_STD_VER >= 23
644    template <_ContainerCompatibleRange<value_type> _Range>
645    _LIBCPP_HIDE_FROM_ABI
646    set(from_range_t, _Range&& __range, const key_compare& __comp = key_compare(),
647        const allocator_type& __a = allocator_type())
648      : __tree_(__comp, __a) {
649      insert_range(std::forward<_Range>(__range));
650    }
651#endif
652
653#if _LIBCPP_STD_VER >= 14
654        template <class _InputIterator>
655        _LIBCPP_INLINE_VISIBILITY
656        set(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
657            : set(__f, __l, key_compare(), __a) {}
658#endif
659
660#if _LIBCPP_STD_VER >= 23
661    template <_ContainerCompatibleRange<value_type> _Range>
662    _LIBCPP_HIDE_FROM_ABI
663    set(from_range_t, _Range&& __range, const allocator_type& __a)
664      : set(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
665#endif
666
667    _LIBCPP_INLINE_VISIBILITY
668    set(const set& __s)
669        : __tree_(__s.__tree_)
670        {
671            insert(__s.begin(), __s.end());
672        }
673
674    _LIBCPP_INLINE_VISIBILITY
675    set& operator=(const set& __s)
676        {
677            __tree_ = __s.__tree_;
678            return *this;
679        }
680
681#ifndef _LIBCPP_CXX03_LANG
682    _LIBCPP_INLINE_VISIBILITY
683    set(set&& __s)
684        _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
685        : __tree_(_VSTD::move(__s.__tree_)) {}
686#endif // _LIBCPP_CXX03_LANG
687
688    _LIBCPP_INLINE_VISIBILITY
689    explicit set(const allocator_type& __a)
690        : __tree_(__a) {}
691
692    _LIBCPP_INLINE_VISIBILITY
693    set(const set& __s, const allocator_type& __a)
694        : __tree_(__s.__tree_.value_comp(), __a)
695        {
696            insert(__s.begin(), __s.end());
697        }
698
699#ifndef _LIBCPP_CXX03_LANG
700    _LIBCPP_HIDE_FROM_ABI set(set&& __s, const allocator_type& __a);
701
702    _LIBCPP_INLINE_VISIBILITY
703    set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
704        : __tree_(__comp)
705        {
706            insert(__il.begin(), __il.end());
707        }
708
709    _LIBCPP_INLINE_VISIBILITY
710    set(initializer_list<value_type> __il, const value_compare& __comp,
711        const allocator_type& __a)
712        : __tree_(__comp, __a)
713        {
714            insert(__il.begin(), __il.end());
715        }
716
717#if _LIBCPP_STD_VER >= 14
718    _LIBCPP_INLINE_VISIBILITY
719    set(initializer_list<value_type> __il, const allocator_type& __a)
720        : set(__il, key_compare(), __a) {}
721#endif
722
723    _LIBCPP_INLINE_VISIBILITY
724    set& operator=(initializer_list<value_type> __il)
725        {
726            __tree_.__assign_unique(__il.begin(), __il.end());
727            return *this;
728        }
729
730    _LIBCPP_INLINE_VISIBILITY
731    set& operator=(set&& __s)
732        _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
733        {
734            __tree_ = _VSTD::move(__s.__tree_);
735            return *this;
736        }
737#endif // _LIBCPP_CXX03_LANG
738
739    _LIBCPP_INLINE_VISIBILITY
740    ~set() {
741        static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
742    }
743
744    _LIBCPP_INLINE_VISIBILITY
745          iterator begin() _NOEXCEPT       {return __tree_.begin();}
746    _LIBCPP_INLINE_VISIBILITY
747    const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
748    _LIBCPP_INLINE_VISIBILITY
749          iterator end() _NOEXCEPT         {return __tree_.end();}
750    _LIBCPP_INLINE_VISIBILITY
751    const_iterator end()   const _NOEXCEPT {return __tree_.end();}
752
753    _LIBCPP_INLINE_VISIBILITY
754          reverse_iterator rbegin() _NOEXCEPT
755            {return reverse_iterator(end());}
756    _LIBCPP_INLINE_VISIBILITY
757    const_reverse_iterator rbegin() const _NOEXCEPT
758        {return const_reverse_iterator(end());}
759    _LIBCPP_INLINE_VISIBILITY
760          reverse_iterator rend() _NOEXCEPT
761            {return reverse_iterator(begin());}
762    _LIBCPP_INLINE_VISIBILITY
763    const_reverse_iterator rend() const _NOEXCEPT
764        {return const_reverse_iterator(begin());}
765
766    _LIBCPP_INLINE_VISIBILITY
767    const_iterator cbegin()  const _NOEXCEPT {return begin();}
768    _LIBCPP_INLINE_VISIBILITY
769    const_iterator cend() const _NOEXCEPT {return end();}
770    _LIBCPP_INLINE_VISIBILITY
771    const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
772    _LIBCPP_INLINE_VISIBILITY
773    const_reverse_iterator crend() const _NOEXCEPT {return rend();}
774
775    _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
776    bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
777    _LIBCPP_INLINE_VISIBILITY
778    size_type size() const _NOEXCEPT {return __tree_.size();}
779    _LIBCPP_INLINE_VISIBILITY
780    size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
781
782    // modifiers:
783#ifndef _LIBCPP_CXX03_LANG
784    template <class... _Args>
785        _LIBCPP_INLINE_VISIBILITY
786        pair<iterator, bool> emplace(_Args&&... __args)
787            {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
788    template <class... _Args>
789        _LIBCPP_INLINE_VISIBILITY
790        iterator emplace_hint(const_iterator __p, _Args&&... __args)
791            {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);}
792#endif // _LIBCPP_CXX03_LANG
793
794    _LIBCPP_INLINE_VISIBILITY
795    pair<iterator,bool> insert(const value_type& __v)
796        {return __tree_.__insert_unique(__v);}
797    _LIBCPP_INLINE_VISIBILITY
798    iterator insert(const_iterator __p, const value_type& __v)
799        {return __tree_.__insert_unique(__p, __v);}
800
801    template <class _InputIterator>
802        _LIBCPP_INLINE_VISIBILITY
803        void insert(_InputIterator __f, _InputIterator __l)
804        {
805            for (const_iterator __e = cend(); __f != __l; ++__f)
806                __tree_.__insert_unique(__e, *__f);
807        }
808
809#if _LIBCPP_STD_VER >= 23
810    template <_ContainerCompatibleRange<value_type> _Range>
811    _LIBCPP_HIDE_FROM_ABI
812    void insert_range(_Range&& __range) {
813      const_iterator __end = cend();
814      for (auto&& __element : __range) {
815        __tree_.__insert_unique(__end, std::forward<decltype(__element)>(__element));
816      }
817    }
818#endif
819
820#ifndef _LIBCPP_CXX03_LANG
821    _LIBCPP_INLINE_VISIBILITY
822    pair<iterator,bool> insert(value_type&& __v)
823        {return __tree_.__insert_unique(_VSTD::move(__v));}
824
825    _LIBCPP_INLINE_VISIBILITY
826    iterator insert(const_iterator __p, value_type&& __v)
827        {return __tree_.__insert_unique(__p, _VSTD::move(__v));}
828
829    _LIBCPP_INLINE_VISIBILITY
830    void insert(initializer_list<value_type> __il)
831        {insert(__il.begin(), __il.end());}
832#endif // _LIBCPP_CXX03_LANG
833
834    _LIBCPP_INLINE_VISIBILITY
835    iterator  erase(const_iterator __p) {return __tree_.erase(__p);}
836    _LIBCPP_INLINE_VISIBILITY
837    size_type erase(const key_type& __k)
838        {return __tree_.__erase_unique(__k);}
839    _LIBCPP_INLINE_VISIBILITY
840    iterator  erase(const_iterator __f, const_iterator __l)
841        {return __tree_.erase(__f, __l);}
842    _LIBCPP_INLINE_VISIBILITY
843    void clear() _NOEXCEPT {__tree_.clear();}
844
845#if _LIBCPP_STD_VER >= 17
846    _LIBCPP_INLINE_VISIBILITY
847    insert_return_type insert(node_type&& __nh)
848    {
849        _LIBCPP_ASSERT_UNCATEGORIZED(__nh.empty() || __nh.get_allocator() == get_allocator(),
850            "node_type with incompatible allocator passed to set::insert()");
851        return __tree_.template __node_handle_insert_unique<
852            node_type, insert_return_type>(_VSTD::move(__nh));
853    }
854    _LIBCPP_INLINE_VISIBILITY
855    iterator insert(const_iterator __hint, node_type&& __nh)
856    {
857        _LIBCPP_ASSERT_UNCATEGORIZED(__nh.empty() || __nh.get_allocator() == get_allocator(),
858            "node_type with incompatible allocator passed to set::insert()");
859        return __tree_.template __node_handle_insert_unique<node_type>(
860            __hint, _VSTD::move(__nh));
861    }
862    _LIBCPP_INLINE_VISIBILITY
863    node_type extract(key_type const& __key)
864    {
865        return __tree_.template __node_handle_extract<node_type>(__key);
866    }
867    _LIBCPP_INLINE_VISIBILITY
868    node_type extract(const_iterator __it)
869    {
870        return __tree_.template __node_handle_extract<node_type>(__it);
871    }
872    template <class _Compare2>
873    _LIBCPP_INLINE_VISIBILITY
874    void merge(set<key_type, _Compare2, allocator_type>& __source)
875    {
876        _LIBCPP_ASSERT_UNCATEGORIZED(__source.get_allocator() == get_allocator(),
877                       "merging container with incompatible allocator");
878        __tree_.__node_handle_merge_unique(__source.__tree_);
879    }
880    template <class _Compare2>
881    _LIBCPP_INLINE_VISIBILITY
882    void merge(set<key_type, _Compare2, allocator_type>&& __source)
883    {
884        _LIBCPP_ASSERT_UNCATEGORIZED(__source.get_allocator() == get_allocator(),
885                       "merging container with incompatible allocator");
886        __tree_.__node_handle_merge_unique(__source.__tree_);
887    }
888    template <class _Compare2>
889    _LIBCPP_INLINE_VISIBILITY
890    void merge(multiset<key_type, _Compare2, allocator_type>& __source)
891    {
892        _LIBCPP_ASSERT_UNCATEGORIZED(__source.get_allocator() == get_allocator(),
893                       "merging container with incompatible allocator");
894        __tree_.__node_handle_merge_unique(__source.__tree_);
895    }
896    template <class _Compare2>
897    _LIBCPP_INLINE_VISIBILITY
898    void merge(multiset<key_type, _Compare2, allocator_type>&& __source)
899    {
900        _LIBCPP_ASSERT_UNCATEGORIZED(__source.get_allocator() == get_allocator(),
901                       "merging container with incompatible allocator");
902        __tree_.__node_handle_merge_unique(__source.__tree_);
903    }
904#endif
905
906    _LIBCPP_INLINE_VISIBILITY
907    void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
908        {__tree_.swap(__s.__tree_);}
909
910    _LIBCPP_INLINE_VISIBILITY
911    allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
912    _LIBCPP_INLINE_VISIBILITY
913    key_compare    key_comp()      const {return __tree_.value_comp();}
914    _LIBCPP_INLINE_VISIBILITY
915    value_compare  value_comp()    const {return __tree_.value_comp();}
916
917    // set operations:
918    _LIBCPP_INLINE_VISIBILITY
919    iterator find(const key_type& __k)             {return __tree_.find(__k);}
920    _LIBCPP_INLINE_VISIBILITY
921    const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
922#if _LIBCPP_STD_VER >= 14
923    template <typename _K2>
924    _LIBCPP_INLINE_VISIBILITY
925    typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
926    find(const _K2& __k)                           {return __tree_.find(__k);}
927    template <typename _K2>
928    _LIBCPP_INLINE_VISIBILITY
929    typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
930    find(const _K2& __k) const                     {return __tree_.find(__k);}
931#endif
932
933    _LIBCPP_INLINE_VISIBILITY
934    size_type      count(const key_type& __k) const
935        {return __tree_.__count_unique(__k);}
936#if _LIBCPP_STD_VER >= 14
937    template <typename _K2>
938    _LIBCPP_INLINE_VISIBILITY
939    typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
940    count(const _K2& __k) const                    {return __tree_.__count_multi(__k);}
941#endif
942
943#if _LIBCPP_STD_VER >= 20
944    _LIBCPP_INLINE_VISIBILITY
945    bool contains(const key_type& __k) const {return find(__k) != end();}
946    template <typename _K2>
947    _LIBCPP_INLINE_VISIBILITY
948    typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
949    contains(const _K2& __k) const { return find(__k) != end(); }
950#endif // _LIBCPP_STD_VER >= 20
951
952    _LIBCPP_INLINE_VISIBILITY
953    iterator lower_bound(const key_type& __k)
954        {return __tree_.lower_bound(__k);}
955    _LIBCPP_INLINE_VISIBILITY
956    const_iterator lower_bound(const key_type& __k) const
957        {return __tree_.lower_bound(__k);}
958#if _LIBCPP_STD_VER >= 14
959    template <typename _K2>
960    _LIBCPP_INLINE_VISIBILITY
961    typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
962    lower_bound(const _K2& __k)       {return __tree_.lower_bound(__k);}
963
964    template <typename _K2>
965    _LIBCPP_INLINE_VISIBILITY
966    typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
967    lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
968#endif
969
970    _LIBCPP_INLINE_VISIBILITY
971    iterator upper_bound(const key_type& __k)
972        {return __tree_.upper_bound(__k);}
973    _LIBCPP_INLINE_VISIBILITY
974    const_iterator upper_bound(const key_type& __k) const
975        {return __tree_.upper_bound(__k);}
976#if _LIBCPP_STD_VER >= 14
977    template <typename _K2>
978    _LIBCPP_INLINE_VISIBILITY
979    typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
980    upper_bound(const _K2& __k)       {return __tree_.upper_bound(__k);}
981    template <typename _K2>
982    _LIBCPP_INLINE_VISIBILITY
983    typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
984    upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
985#endif
986
987    _LIBCPP_INLINE_VISIBILITY
988    pair<iterator,iterator> equal_range(const key_type& __k)
989        {return __tree_.__equal_range_unique(__k);}
990    _LIBCPP_INLINE_VISIBILITY
991    pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
992        {return __tree_.__equal_range_unique(__k);}
993#if _LIBCPP_STD_VER >= 14
994    template <typename _K2>
995    _LIBCPP_INLINE_VISIBILITY
996    typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
997    equal_range(const _K2& __k)       {return __tree_.__equal_range_multi(__k);}
998    template <typename _K2>
999    _LIBCPP_INLINE_VISIBILITY
1000    typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1001    equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1002#endif
1003};
1004
1005#if _LIBCPP_STD_VER >= 17
1006template<class _InputIterator,
1007         class _Compare = less<__iter_value_type<_InputIterator>>,
1008         class _Allocator = allocator<__iter_value_type<_InputIterator>>,
1009         class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1010         class = enable_if_t<__is_allocator<_Allocator>::value, void>,
1011         class = enable_if_t<!__is_allocator<_Compare>::value, void>>
1012set(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1013  -> set<__iter_value_type<_InputIterator>, _Compare, _Allocator>;
1014
1015#if _LIBCPP_STD_VER >= 23
1016template <ranges::input_range _Range, class _Compare = less<ranges::range_value_t<_Range>>,
1017          class _Allocator = allocator<ranges::range_value_t<_Range>>,
1018          class = enable_if_t<__is_allocator<_Allocator>::value, void>,
1019          class = enable_if_t<!__is_allocator<_Compare>::value, void>>
1020set(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
1021  -> set<ranges::range_value_t<_Range>, _Compare, _Allocator>;
1022#endif
1023
1024template<class _Key, class _Compare = less<_Key>,
1025         class _Allocator = allocator<_Key>,
1026         class = enable_if_t<!__is_allocator<_Compare>::value, void>,
1027         class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1028set(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator())
1029  -> set<_Key, _Compare, _Allocator>;
1030
1031template<class _InputIterator, class _Allocator,
1032         class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1033         class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1034set(_InputIterator, _InputIterator, _Allocator)
1035  -> set<__iter_value_type<_InputIterator>,
1036         less<__iter_value_type<_InputIterator>>, _Allocator>;
1037
1038#if _LIBCPP_STD_VER >= 23
1039template <ranges::input_range _Range, class _Allocator,
1040          class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1041set(from_range_t, _Range&&, _Allocator)
1042  -> set<ranges::range_value_t<_Range>, less<ranges::range_value_t<_Range>>, _Allocator>;
1043#endif
1044
1045template<class _Key, class _Allocator,
1046         class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1047set(initializer_list<_Key>, _Allocator)
1048  -> set<_Key, less<_Key>, _Allocator>;
1049#endif
1050
1051#ifndef _LIBCPP_CXX03_LANG
1052
1053template <class _Key, class _Compare, class _Allocator>
1054set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a)
1055    : __tree_(_VSTD::move(__s.__tree_), __a)
1056{
1057    if (__a != __s.get_allocator())
1058    {
1059        const_iterator __e = cend();
1060        while (!__s.empty())
1061            insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
1062    }
1063}
1064
1065#endif // _LIBCPP_CXX03_LANG
1066
1067template <class _Key, class _Compare, class _Allocator>
1068inline _LIBCPP_INLINE_VISIBILITY
1069bool
1070operator==(const set<_Key, _Compare, _Allocator>& __x,
1071           const set<_Key, _Compare, _Allocator>& __y)
1072{
1073    return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1074}
1075
1076#if _LIBCPP_STD_VER <= 17
1077
1078template <class _Key, class _Compare, class _Allocator>
1079inline _LIBCPP_INLINE_VISIBILITY
1080bool
1081operator< (const set<_Key, _Compare, _Allocator>& __x,
1082           const set<_Key, _Compare, _Allocator>& __y)
1083{
1084    return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1085}
1086
1087template <class _Key, class _Compare, class _Allocator>
1088inline _LIBCPP_INLINE_VISIBILITY
1089bool
1090operator!=(const set<_Key, _Compare, _Allocator>& __x,
1091           const set<_Key, _Compare, _Allocator>& __y)
1092{
1093    return !(__x == __y);
1094}
1095
1096template <class _Key, class _Compare, class _Allocator>
1097inline _LIBCPP_INLINE_VISIBILITY
1098bool
1099operator> (const set<_Key, _Compare, _Allocator>& __x,
1100           const set<_Key, _Compare, _Allocator>& __y)
1101{
1102    return __y < __x;
1103}
1104
1105template <class _Key, class _Compare, class _Allocator>
1106inline _LIBCPP_INLINE_VISIBILITY
1107bool
1108operator>=(const set<_Key, _Compare, _Allocator>& __x,
1109           const set<_Key, _Compare, _Allocator>& __y)
1110{
1111    return !(__x < __y);
1112}
1113
1114template <class _Key, class _Compare, class _Allocator>
1115inline _LIBCPP_INLINE_VISIBILITY
1116bool
1117operator<=(const set<_Key, _Compare, _Allocator>& __x,
1118           const set<_Key, _Compare, _Allocator>& __y)
1119{
1120    return !(__y < __x);
1121}
1122
1123#else // _LIBCPP_STD_VER <= 17
1124
1125template <class _Key, class _Allocator>
1126_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Key>
1127operator<=>(const set<_Key, _Allocator>& __x, const set<_Key, _Allocator>& __y) {
1128    return std::lexicographical_compare_three_way(
1129        __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way<_Key, _Key>);
1130}
1131
1132#endif // _LIBCPP_STD_VER <= 17
1133
1134// specialized algorithms:
1135template <class _Key, class _Compare, class _Allocator>
1136inline _LIBCPP_INLINE_VISIBILITY
1137void
1138swap(set<_Key, _Compare, _Allocator>& __x,
1139     set<_Key, _Compare, _Allocator>& __y)
1140    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1141{
1142    __x.swap(__y);
1143}
1144
1145#if _LIBCPP_STD_VER >= 20
1146template <class _Key, class _Compare, class _Allocator, class _Predicate>
1147inline _LIBCPP_INLINE_VISIBILITY
1148    typename set<_Key, _Compare, _Allocator>::size_type
1149    erase_if(set<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {
1150  return _VSTD::__libcpp_erase_if_container(__c, __pred);
1151}
1152#endif
1153
1154template <class _Key, class _Compare = less<_Key>,
1155          class _Allocator = allocator<_Key> >
1156class _LIBCPP_TEMPLATE_VIS multiset
1157{
1158public:
1159    // types:
1160    typedef _Key                                     key_type;
1161    typedef key_type                                 value_type;
1162    typedef __type_identity_t<_Compare>              key_compare;
1163    typedef key_compare                              value_compare;
1164    typedef __type_identity_t<_Allocator>            allocator_type;
1165    typedef value_type&                              reference;
1166    typedef const value_type&                        const_reference;
1167
1168    static_assert((is_same<typename allocator_type::value_type, value_type>::value),
1169                  "Allocator::value_type must be same type as value_type");
1170
1171private:
1172    typedef __tree<value_type, value_compare, allocator_type> __base;
1173    typedef allocator_traits<allocator_type>                  __alloc_traits;
1174
1175    static_assert(is_same<allocator_type, __rebind_alloc<__alloc_traits, value_type> >::value,
1176                  "[allocator.requirements] states that rebinding an allocator to the same type should result in the "
1177                  "original allocator");
1178
1179    __base __tree_;
1180
1181public:
1182    typedef typename __base::pointer               pointer;
1183    typedef typename __base::const_pointer         const_pointer;
1184    typedef typename __base::size_type             size_type;
1185    typedef typename __base::difference_type       difference_type;
1186    typedef typename __base::const_iterator        iterator;
1187    typedef typename __base::const_iterator        const_iterator;
1188    typedef _VSTD::reverse_iterator<iterator>       reverse_iterator;
1189    typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
1190
1191#if _LIBCPP_STD_VER >= 17
1192    typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
1193#endif
1194
1195    template <class _Key2, class _Compare2, class _Alloc2>
1196        friend class _LIBCPP_TEMPLATE_VIS set;
1197    template <class _Key2, class _Compare2, class _Alloc2>
1198        friend class _LIBCPP_TEMPLATE_VIS multiset;
1199
1200    // construct/copy/destroy:
1201    _LIBCPP_INLINE_VISIBILITY
1202    multiset()
1203        _NOEXCEPT_(
1204            is_nothrow_default_constructible<allocator_type>::value &&
1205            is_nothrow_default_constructible<key_compare>::value &&
1206            is_nothrow_copy_constructible<key_compare>::value)
1207        : __tree_(value_compare()) {}
1208
1209    _LIBCPP_INLINE_VISIBILITY
1210    explicit multiset(const value_compare& __comp)
1211        _NOEXCEPT_(
1212            is_nothrow_default_constructible<allocator_type>::value &&
1213            is_nothrow_copy_constructible<key_compare>::value)
1214        : __tree_(__comp) {}
1215
1216    _LIBCPP_INLINE_VISIBILITY
1217    explicit multiset(const value_compare& __comp, const allocator_type& __a)
1218        : __tree_(__comp, __a) {}
1219    template <class _InputIterator>
1220        _LIBCPP_INLINE_VISIBILITY
1221        multiset(_InputIterator __f, _InputIterator __l,
1222                 const value_compare& __comp = value_compare())
1223        : __tree_(__comp)
1224        {
1225            insert(__f, __l);
1226        }
1227
1228#if _LIBCPP_STD_VER >= 14
1229        template <class _InputIterator>
1230        _LIBCPP_INLINE_VISIBILITY
1231        multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1232            : multiset(__f, __l, key_compare(), __a) {}
1233#endif
1234
1235    template <class _InputIterator>
1236        _LIBCPP_INLINE_VISIBILITY
1237        multiset(_InputIterator __f, _InputIterator __l,
1238                 const value_compare& __comp, const allocator_type& __a)
1239        : __tree_(__comp, __a)
1240        {
1241            insert(__f, __l);
1242        }
1243
1244#if _LIBCPP_STD_VER >= 23
1245    template <_ContainerCompatibleRange<value_type> _Range>
1246    _LIBCPP_HIDE_FROM_ABI
1247    multiset(from_range_t, _Range&& __range, const key_compare& __comp = key_compare(),
1248        const allocator_type& __a = allocator_type())
1249      : __tree_(__comp, __a) {
1250      insert_range(std::forward<_Range>(__range));
1251    }
1252
1253    template <_ContainerCompatibleRange<value_type> _Range>
1254    _LIBCPP_HIDE_FROM_ABI
1255    multiset(from_range_t, _Range&& __range, const allocator_type& __a)
1256      : multiset(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
1257#endif
1258
1259    _LIBCPP_INLINE_VISIBILITY
1260    multiset(const multiset& __s)
1261        : __tree_(__s.__tree_.value_comp(),
1262          __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc()))
1263        {
1264            insert(__s.begin(), __s.end());
1265        }
1266
1267    _LIBCPP_INLINE_VISIBILITY
1268    multiset& operator=(const multiset& __s)
1269        {
1270            __tree_ = __s.__tree_;
1271            return *this;
1272        }
1273
1274#ifndef _LIBCPP_CXX03_LANG
1275    _LIBCPP_INLINE_VISIBILITY
1276    multiset(multiset&& __s)
1277        _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1278        : __tree_(_VSTD::move(__s.__tree_)) {}
1279
1280    _LIBCPP_HIDE_FROM_ABI multiset(multiset&& __s, const allocator_type& __a);
1281#endif // _LIBCPP_CXX03_LANG
1282    _LIBCPP_INLINE_VISIBILITY
1283    explicit multiset(const allocator_type& __a)
1284        : __tree_(__a) {}
1285    _LIBCPP_INLINE_VISIBILITY
1286    multiset(const multiset& __s, const allocator_type& __a)
1287        : __tree_(__s.__tree_.value_comp(), __a)
1288        {
1289            insert(__s.begin(), __s.end());
1290        }
1291
1292#ifndef _LIBCPP_CXX03_LANG
1293    _LIBCPP_INLINE_VISIBILITY
1294    multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
1295        : __tree_(__comp)
1296        {
1297            insert(__il.begin(), __il.end());
1298        }
1299
1300    _LIBCPP_INLINE_VISIBILITY
1301    multiset(initializer_list<value_type> __il, const value_compare& __comp,
1302        const allocator_type& __a)
1303        : __tree_(__comp, __a)
1304        {
1305            insert(__il.begin(), __il.end());
1306        }
1307
1308#if _LIBCPP_STD_VER >= 14
1309    _LIBCPP_INLINE_VISIBILITY
1310    multiset(initializer_list<value_type> __il, const allocator_type& __a)
1311        : multiset(__il, key_compare(), __a) {}
1312#endif
1313
1314    _LIBCPP_INLINE_VISIBILITY
1315    multiset& operator=(initializer_list<value_type> __il)
1316        {
1317            __tree_.__assign_multi(__il.begin(), __il.end());
1318            return *this;
1319        }
1320
1321    _LIBCPP_INLINE_VISIBILITY
1322    multiset& operator=(multiset&& __s)
1323        _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1324        {
1325            __tree_ = _VSTD::move(__s.__tree_);
1326            return *this;
1327        }
1328#endif // _LIBCPP_CXX03_LANG
1329
1330    _LIBCPP_INLINE_VISIBILITY
1331    ~multiset() {
1332        static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
1333    }
1334
1335    _LIBCPP_INLINE_VISIBILITY
1336          iterator begin() _NOEXCEPT       {return __tree_.begin();}
1337    _LIBCPP_INLINE_VISIBILITY
1338    const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
1339    _LIBCPP_INLINE_VISIBILITY
1340          iterator end() _NOEXCEPT         {return __tree_.end();}
1341    _LIBCPP_INLINE_VISIBILITY
1342    const_iterator end()   const _NOEXCEPT {return __tree_.end();}
1343
1344    _LIBCPP_INLINE_VISIBILITY
1345          reverse_iterator rbegin() _NOEXCEPT
1346            {return reverse_iterator(end());}
1347    _LIBCPP_INLINE_VISIBILITY
1348    const_reverse_iterator rbegin() const _NOEXCEPT
1349        {return const_reverse_iterator(end());}
1350    _LIBCPP_INLINE_VISIBILITY
1351          reverse_iterator rend() _NOEXCEPT
1352            {return       reverse_iterator(begin());}
1353    _LIBCPP_INLINE_VISIBILITY
1354    const_reverse_iterator rend() const _NOEXCEPT
1355        {return const_reverse_iterator(begin());}
1356
1357    _LIBCPP_INLINE_VISIBILITY
1358    const_iterator cbegin()  const _NOEXCEPT {return begin();}
1359    _LIBCPP_INLINE_VISIBILITY
1360    const_iterator cend() const _NOEXCEPT {return end();}
1361    _LIBCPP_INLINE_VISIBILITY
1362    const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1363    _LIBCPP_INLINE_VISIBILITY
1364    const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1365
1366    _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1367    bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1368    _LIBCPP_INLINE_VISIBILITY
1369    size_type size() const _NOEXCEPT {return __tree_.size();}
1370    _LIBCPP_INLINE_VISIBILITY
1371    size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1372
1373    // modifiers:
1374#ifndef _LIBCPP_CXX03_LANG
1375    template <class... _Args>
1376        _LIBCPP_INLINE_VISIBILITY
1377        iterator emplace(_Args&&... __args)
1378            {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
1379    template <class... _Args>
1380        _LIBCPP_INLINE_VISIBILITY
1381        iterator emplace_hint(const_iterator __p, _Args&&... __args)
1382            {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
1383#endif // _LIBCPP_CXX03_LANG
1384
1385    _LIBCPP_INLINE_VISIBILITY
1386    iterator insert(const value_type& __v)
1387        {return __tree_.__insert_multi(__v);}
1388    _LIBCPP_INLINE_VISIBILITY
1389    iterator insert(const_iterator __p, const value_type& __v)
1390        {return __tree_.__insert_multi(__p, __v);}
1391
1392    template <class _InputIterator>
1393        _LIBCPP_INLINE_VISIBILITY
1394        void insert(_InputIterator __f, _InputIterator __l)
1395        {
1396            for (const_iterator __e = cend(); __f != __l; ++__f)
1397                __tree_.__insert_multi(__e, *__f);
1398        }
1399
1400#if _LIBCPP_STD_VER >= 23
1401    template <_ContainerCompatibleRange<value_type> _Range>
1402    _LIBCPP_HIDE_FROM_ABI
1403    void insert_range(_Range&& __range) {
1404      const_iterator __end = cend();
1405      for (auto&& __element : __range) {
1406        __tree_.__insert_multi(__end, std::forward<decltype(__element)>(__element));
1407      }
1408    }
1409#endif
1410
1411#ifndef _LIBCPP_CXX03_LANG
1412    _LIBCPP_INLINE_VISIBILITY
1413    iterator insert(value_type&& __v)
1414        {return __tree_.__insert_multi(_VSTD::move(__v));}
1415
1416    _LIBCPP_INLINE_VISIBILITY
1417    iterator insert(const_iterator __p, value_type&& __v)
1418        {return __tree_.__insert_multi(__p, _VSTD::move(__v));}
1419
1420    _LIBCPP_INLINE_VISIBILITY
1421    void insert(initializer_list<value_type> __il)
1422        {insert(__il.begin(), __il.end());}
1423#endif // _LIBCPP_CXX03_LANG
1424
1425    _LIBCPP_INLINE_VISIBILITY
1426    iterator  erase(const_iterator __p) {return __tree_.erase(__p);}
1427    _LIBCPP_INLINE_VISIBILITY
1428    size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1429    _LIBCPP_INLINE_VISIBILITY
1430    iterator  erase(const_iterator __f, const_iterator __l)
1431        {return __tree_.erase(__f, __l);}
1432    _LIBCPP_INLINE_VISIBILITY
1433    void clear() _NOEXCEPT {__tree_.clear();}
1434
1435#if _LIBCPP_STD_VER >= 17
1436    _LIBCPP_INLINE_VISIBILITY
1437    iterator insert(node_type&& __nh)
1438    {
1439        _LIBCPP_ASSERT_UNCATEGORIZED(__nh.empty() || __nh.get_allocator() == get_allocator(),
1440            "node_type with incompatible allocator passed to multiset::insert()");
1441        return __tree_.template __node_handle_insert_multi<node_type>(
1442            _VSTD::move(__nh));
1443    }
1444    _LIBCPP_INLINE_VISIBILITY
1445    iterator insert(const_iterator __hint, node_type&& __nh)
1446    {
1447        _LIBCPP_ASSERT_UNCATEGORIZED(__nh.empty() || __nh.get_allocator() == get_allocator(),
1448            "node_type with incompatible allocator passed to multiset::insert()");
1449        return __tree_.template __node_handle_insert_multi<node_type>(
1450            __hint, _VSTD::move(__nh));
1451    }
1452    _LIBCPP_INLINE_VISIBILITY
1453    node_type extract(key_type const& __key)
1454    {
1455        return __tree_.template __node_handle_extract<node_type>(__key);
1456    }
1457    _LIBCPP_INLINE_VISIBILITY
1458    node_type extract(const_iterator __it)
1459    {
1460        return __tree_.template __node_handle_extract<node_type>(__it);
1461    }
1462    template <class _Compare2>
1463    _LIBCPP_INLINE_VISIBILITY
1464    void merge(multiset<key_type, _Compare2, allocator_type>& __source)
1465    {
1466        _LIBCPP_ASSERT_UNCATEGORIZED(__source.get_allocator() == get_allocator(),
1467                       "merging container with incompatible allocator");
1468        __tree_.__node_handle_merge_multi(__source.__tree_);
1469    }
1470    template <class _Compare2>
1471    _LIBCPP_INLINE_VISIBILITY
1472    void merge(multiset<key_type, _Compare2, allocator_type>&& __source)
1473    {
1474        _LIBCPP_ASSERT_UNCATEGORIZED(__source.get_allocator() == get_allocator(),
1475                       "merging container with incompatible allocator");
1476        __tree_.__node_handle_merge_multi(__source.__tree_);
1477    }
1478    template <class _Compare2>
1479    _LIBCPP_INLINE_VISIBILITY
1480    void merge(set<key_type, _Compare2, allocator_type>& __source)
1481    {
1482        _LIBCPP_ASSERT_UNCATEGORIZED(__source.get_allocator() == get_allocator(),
1483                       "merging container with incompatible allocator");
1484        __tree_.__node_handle_merge_multi(__source.__tree_);
1485    }
1486    template <class _Compare2>
1487    _LIBCPP_INLINE_VISIBILITY
1488    void merge(set<key_type, _Compare2, allocator_type>&& __source)
1489    {
1490        _LIBCPP_ASSERT_UNCATEGORIZED(__source.get_allocator() == get_allocator(),
1491                       "merging container with incompatible allocator");
1492        __tree_.__node_handle_merge_multi(__source.__tree_);
1493    }
1494#endif
1495
1496    _LIBCPP_INLINE_VISIBILITY
1497    void swap(multiset& __s)
1498        _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1499        {__tree_.swap(__s.__tree_);}
1500
1501    _LIBCPP_INLINE_VISIBILITY
1502    allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
1503    _LIBCPP_INLINE_VISIBILITY
1504    key_compare    key_comp()      const {return __tree_.value_comp();}
1505    _LIBCPP_INLINE_VISIBILITY
1506    value_compare  value_comp()    const {return __tree_.value_comp();}
1507
1508    // set operations:
1509    _LIBCPP_INLINE_VISIBILITY
1510    iterator find(const key_type& __k)             {return __tree_.find(__k);}
1511    _LIBCPP_INLINE_VISIBILITY
1512    const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1513#if _LIBCPP_STD_VER >= 14
1514    template <typename _K2>
1515    _LIBCPP_INLINE_VISIBILITY
1516    typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1517    find(const _K2& __k)                           {return __tree_.find(__k);}
1518    template <typename _K2>
1519    _LIBCPP_INLINE_VISIBILITY
1520    typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1521    find(const _K2& __k) const                     {return __tree_.find(__k);}
1522#endif
1523
1524    _LIBCPP_INLINE_VISIBILITY
1525    size_type      count(const key_type& __k) const
1526        {return __tree_.__count_multi(__k);}
1527#if _LIBCPP_STD_VER >= 14
1528    template <typename _K2>
1529    _LIBCPP_INLINE_VISIBILITY
1530    typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1531    count(const _K2& __k) const            {return __tree_.__count_multi(__k);}
1532#endif
1533
1534#if _LIBCPP_STD_VER >= 20
1535    _LIBCPP_INLINE_VISIBILITY
1536    bool contains(const key_type& __k) const {return find(__k) != end();}
1537    template <typename _K2>
1538    _LIBCPP_INLINE_VISIBILITY
1539    typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
1540    contains(const _K2& __k) const { return find(__k) != end(); }
1541#endif // _LIBCPP_STD_VER >= 20
1542
1543    _LIBCPP_INLINE_VISIBILITY
1544    iterator lower_bound(const key_type& __k)
1545        {return __tree_.lower_bound(__k);}
1546    _LIBCPP_INLINE_VISIBILITY
1547    const_iterator lower_bound(const key_type& __k) const
1548            {return __tree_.lower_bound(__k);}
1549#if _LIBCPP_STD_VER >= 14
1550    template <typename _K2>
1551    _LIBCPP_INLINE_VISIBILITY
1552    typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1553    lower_bound(const _K2& __k)       {return __tree_.lower_bound(__k);}
1554
1555    template <typename _K2>
1556    _LIBCPP_INLINE_VISIBILITY
1557    typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1558    lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1559#endif
1560
1561    _LIBCPP_INLINE_VISIBILITY
1562    iterator upper_bound(const key_type& __k)
1563            {return __tree_.upper_bound(__k);}
1564    _LIBCPP_INLINE_VISIBILITY
1565    const_iterator upper_bound(const key_type& __k) const
1566            {return __tree_.upper_bound(__k);}
1567#if _LIBCPP_STD_VER >= 14
1568    template <typename _K2>
1569    _LIBCPP_INLINE_VISIBILITY
1570    typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1571    upper_bound(const _K2& __k)       {return __tree_.upper_bound(__k);}
1572    template <typename _K2>
1573    _LIBCPP_INLINE_VISIBILITY
1574    typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1575    upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1576#endif
1577
1578    _LIBCPP_INLINE_VISIBILITY
1579    pair<iterator,iterator>             equal_range(const key_type& __k)
1580            {return __tree_.__equal_range_multi(__k);}
1581    _LIBCPP_INLINE_VISIBILITY
1582    pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1583            {return __tree_.__equal_range_multi(__k);}
1584#if _LIBCPP_STD_VER >= 14
1585    template <typename _K2>
1586    _LIBCPP_INLINE_VISIBILITY
1587    typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1588    equal_range(const _K2& __k)       {return __tree_.__equal_range_multi(__k);}
1589    template <typename _K2>
1590    _LIBCPP_INLINE_VISIBILITY
1591    typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1592    equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1593#endif
1594};
1595
1596#if _LIBCPP_STD_VER >= 17
1597template<class _InputIterator,
1598         class _Compare = less<__iter_value_type<_InputIterator>>,
1599         class _Allocator = allocator<__iter_value_type<_InputIterator>>,
1600         class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1601         class = enable_if_t<__is_allocator<_Allocator>::value, void>,
1602         class = enable_if_t<!__is_allocator<_Compare>::value, void>>
1603multiset(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1604  -> multiset<__iter_value_type<_InputIterator>, _Compare, _Allocator>;
1605
1606#if _LIBCPP_STD_VER >= 23
1607template <ranges::input_range _Range, class _Compare = less<ranges::range_value_t<_Range>>,
1608          class _Allocator = allocator<ranges::range_value_t<_Range>>,
1609          class = enable_if_t<__is_allocator<_Allocator>::value, void>,
1610          class = enable_if_t<!__is_allocator<_Compare>::value, void>>
1611multiset(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
1612  -> multiset<ranges::range_value_t<_Range>, _Compare, _Allocator>;
1613#endif
1614
1615template<class _Key, class _Compare = less<_Key>,
1616         class _Allocator = allocator<_Key>,
1617         class = enable_if_t<__is_allocator<_Allocator>::value, void>,
1618         class = enable_if_t<!__is_allocator<_Compare>::value, void>>
1619multiset(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator())
1620  -> multiset<_Key, _Compare, _Allocator>;
1621
1622template<class _InputIterator, class _Allocator,
1623         class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1624         class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1625multiset(_InputIterator, _InputIterator, _Allocator)
1626  -> multiset<__iter_value_type<_InputIterator>,
1627         less<__iter_value_type<_InputIterator>>, _Allocator>;
1628
1629#if _LIBCPP_STD_VER >= 23
1630template <ranges::input_range _Range, class _Allocator,
1631          class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1632multiset(from_range_t, _Range&&, _Allocator)
1633  -> multiset<ranges::range_value_t<_Range>, less<ranges::range_value_t<_Range>>, _Allocator>;
1634#endif
1635
1636template<class _Key, class _Allocator,
1637         class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1638multiset(initializer_list<_Key>, _Allocator)
1639  -> multiset<_Key, less<_Key>, _Allocator>;
1640#endif
1641
1642#ifndef _LIBCPP_CXX03_LANG
1643
1644template <class _Key, class _Compare, class _Allocator>
1645multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a)
1646    : __tree_(_VSTD::move(__s.__tree_), __a)
1647{
1648    if (__a != __s.get_allocator())
1649    {
1650        const_iterator __e = cend();
1651        while (!__s.empty())
1652            insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
1653    }
1654}
1655
1656#endif // _LIBCPP_CXX03_LANG
1657
1658template <class _Key, class _Compare, class _Allocator>
1659inline _LIBCPP_INLINE_VISIBILITY
1660bool
1661operator==(const multiset<_Key, _Compare, _Allocator>& __x,
1662           const multiset<_Key, _Compare, _Allocator>& __y)
1663{
1664    return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1665}
1666
1667#if _LIBCPP_STD_VER <= 17
1668
1669template <class _Key, class _Compare, class _Allocator>
1670inline _LIBCPP_INLINE_VISIBILITY
1671bool
1672operator< (const multiset<_Key, _Compare, _Allocator>& __x,
1673           const multiset<_Key, _Compare, _Allocator>& __y)
1674{
1675    return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1676}
1677
1678template <class _Key, class _Compare, class _Allocator>
1679inline _LIBCPP_INLINE_VISIBILITY
1680bool
1681operator!=(const multiset<_Key, _Compare, _Allocator>& __x,
1682           const multiset<_Key, _Compare, _Allocator>& __y)
1683{
1684    return !(__x == __y);
1685}
1686
1687template <class _Key, class _Compare, class _Allocator>
1688inline _LIBCPP_INLINE_VISIBILITY
1689bool
1690operator> (const multiset<_Key, _Compare, _Allocator>& __x,
1691           const multiset<_Key, _Compare, _Allocator>& __y)
1692{
1693    return __y < __x;
1694}
1695
1696template <class _Key, class _Compare, class _Allocator>
1697inline _LIBCPP_INLINE_VISIBILITY
1698bool
1699operator>=(const multiset<_Key, _Compare, _Allocator>& __x,
1700           const multiset<_Key, _Compare, _Allocator>& __y)
1701{
1702    return !(__x < __y);
1703}
1704
1705template <class _Key, class _Compare, class _Allocator>
1706inline _LIBCPP_INLINE_VISIBILITY
1707bool
1708operator<=(const multiset<_Key, _Compare, _Allocator>& __x,
1709           const multiset<_Key, _Compare, _Allocator>& __y)
1710{
1711    return !(__y < __x);
1712}
1713
1714#else // _LIBCPP_STD_VER <= 17
1715
1716template <class _Key, class _Allocator>
1717_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Key>
1718operator<=>(const multiset<_Key, _Allocator>& __x, const multiset<_Key, _Allocator>& __y) {
1719    return std::lexicographical_compare_three_way(
1720        __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way<_Key, _Key>);
1721}
1722
1723#endif // _LIBCPP_STD_VER <= 17
1724
1725template <class _Key, class _Compare, class _Allocator>
1726inline _LIBCPP_INLINE_VISIBILITY
1727void
1728swap(multiset<_Key, _Compare, _Allocator>& __x,
1729     multiset<_Key, _Compare, _Allocator>& __y)
1730    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1731{
1732    __x.swap(__y);
1733}
1734
1735#if _LIBCPP_STD_VER >= 20
1736template <class _Key, class _Compare, class _Allocator, class _Predicate>
1737inline _LIBCPP_INLINE_VISIBILITY
1738    typename multiset<_Key, _Compare, _Allocator>::size_type
1739    erase_if(multiset<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {
1740  return _VSTD::__libcpp_erase_if_container(__c, __pred);
1741}
1742#endif
1743
1744_LIBCPP_END_NAMESPACE_STD
1745
1746#if _LIBCPP_STD_VER >= 17
1747_LIBCPP_BEGIN_NAMESPACE_STD
1748namespace pmr {
1749template <class _KeyT, class _CompareT = std::less<_KeyT>>
1750using set _LIBCPP_AVAILABILITY_PMR = std::set<_KeyT, _CompareT, polymorphic_allocator<_KeyT>>;
1751
1752template <class _KeyT, class _CompareT = std::less<_KeyT>>
1753using multiset _LIBCPP_AVAILABILITY_PMR = std::multiset<_KeyT, _CompareT, polymorphic_allocator<_KeyT>>;
1754} // namespace pmr
1755_LIBCPP_END_NAMESPACE_STD
1756#endif
1757
1758#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
1759#  include <concepts>
1760#  include <cstdlib>
1761#  include <functional>
1762#  include <iterator>
1763#  include <type_traits>
1764#endif
1765
1766#endif // _LIBCPP_SET
1767