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>
519#include <__config>
520#include <__functional/is_transparent.h>
521#include <__functional/operations.h>
522#include <__iterator/erase_if_container.h>
523#include <__iterator/iterator_traits.h>
524#include <__iterator/ranges_iterator_traits.h>
525#include <__iterator/reverse_iterator.h>
526#include <__memory/allocator.h>
527#include <__memory_resource/polymorphic_allocator.h>
528#include <__node_handle>
529#include <__ranges/concepts.h>
530#include <__ranges/container_compatible_range.h>
531#include <__ranges/from_range.h>
532#include <__tree>
533#include <__type_traits/is_allocator.h>
534#include <__utility/forward.h>
535#include <version>
536
537// standard-mandated includes
538
539// [iterator.range]
540#include <__iterator/access.h>
541#include <__iterator/data.h>
542#include <__iterator/empty.h>
543#include <__iterator/reverse_access.h>
544#include <__iterator/size.h>
545
546// [associative.set.syn]
547#include <compare>
548#include <initializer_list>
549
550#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
551# pragma GCC system_header
552#endif
553
554_LIBCPP_PUSH_MACROS
555#include <__undef_macros>
556
557_LIBCPP_BEGIN_NAMESPACE_STD
558
559template <class _Key, class _Compare, class _Allocator>
560class multiset;
561
562template <class _Key, class _Compare = less<_Key>, class _Allocator = allocator<_Key> >
563class _LIBCPP_TEMPLATE_VIS set {
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(__check_valid_allocator<allocator_type>::value, "");
582
583 __base __tree_;
584
585public:
586 typedef typename __base::pointer pointer;
587 typedef typename __base::const_pointer const_pointer;
588 typedef typename __base::size_type size_type;
589 typedef typename __base::difference_type difference_type;
590 typedef typename __base::const_iterator iterator;
591 typedef typename __base::const_iterator const_iterator;
592 typedef std::reverse_iterator<iterator> reverse_iterator;
593 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
594
595#if _LIBCPP_STD_VER >= 17
596 typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
597 typedef __insert_return_type<iterator, node_type> insert_return_type;
598#endif
599
600 template <class _Key2, class _Compare2, class _Alloc2>
601 friend class _LIBCPP_TEMPLATE_VIS set;
602 template <class _Key2, class _Compare2, class _Alloc2>
603 friend class _LIBCPP_TEMPLATE_VIS multiset;
604
605 _LIBCPP_HIDE_FROM_ABI set() _NOEXCEPT_(
606 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&&
607 is_nothrow_copy_constructible<key_compare>::value)
608 : __tree_(value_compare()) {}
609
610 _LIBCPP_HIDE_FROM_ABI explicit set(const value_compare& __comp) _NOEXCEPT_(
611 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value)
612 : __tree_(__comp) {}
613
614 _LIBCPP_HIDE_FROM_ABI explicit set(const value_compare& __comp, const allocator_type& __a) : __tree_(__comp, __a) {}
615 template <class _InputIterator>
616 _LIBCPP_HIDE_FROM_ABI set(_InputIterator __f, _InputIterator __l, const value_compare& __comp = value_compare())
617 : __tree_(__comp) {
618 insert(__f, __l);
619 }
620
621 template <class _InputIterator>
622 _LIBCPP_HIDE_FROM_ABI
623 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, const allocator_type& __a)
624 : __tree_(__comp, __a) {
625 insert(__f, __l);
626 }
627
628#if _LIBCPP_STD_VER >= 23
629 template <_ContainerCompatibleRange<value_type> _Range>
630 _LIBCPP_HIDE_FROM_ABI
631 set(from_range_t,
632 _Range&& __range,
633 const key_compare& __comp = key_compare(),
634 const allocator_type& __a = allocator_type())
635 : __tree_(__comp, __a) {
636 insert_range(std::forward<_Range>(__range));
637 }
638#endif
639
640#if _LIBCPP_STD_VER >= 14
641 template <class _InputIterator>
642 _LIBCPP_HIDE_FROM_ABI set(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
643 : set(__f, __l, key_compare(), __a) {}
644#endif
645
646#if _LIBCPP_STD_VER >= 23
647 template <_ContainerCompatibleRange<value_type> _Range>
648 _LIBCPP_HIDE_FROM_ABI set(from_range_t, _Range&& __range, const allocator_type& __a)
649 : set(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
650#endif
651
652 _LIBCPP_HIDE_FROM_ABI set(const set& __s) : __tree_(__s.__tree_) { insert(__s.begin(), __s.end()); }
653
654 _LIBCPP_HIDE_FROM_ABI set& operator=(const set& __s) {
655 __tree_ = __s.__tree_;
656 return *this;
657 }
658
659#ifndef _LIBCPP_CXX03_LANG
660 _LIBCPP_HIDE_FROM_ABI set(set&& __s) noexcept(is_nothrow_move_constructible<__base>::value)
661 : __tree_(std::move(__s.__tree_)) {}
662#endif // _LIBCPP_CXX03_LANG
663
664 _LIBCPP_HIDE_FROM_ABI explicit set(const allocator_type& __a) : __tree_(__a) {}
665
666 _LIBCPP_HIDE_FROM_ABI set(const set& __s, const allocator_type& __a) : __tree_(__s.__tree_.value_comp(), __a) {
667 insert(__s.begin(), __s.end());
668 }
669
670#ifndef _LIBCPP_CXX03_LANG
671 _LIBCPP_HIDE_FROM_ABI set(set&& __s, const allocator_type& __a);
672
673 _LIBCPP_HIDE_FROM_ABI set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
674 : __tree_(__comp) {
675 insert(__il.begin(), __il.end());
676 }
677
678 _LIBCPP_HIDE_FROM_ABI set(initializer_list<value_type> __il, const value_compare& __comp, const allocator_type& __a)
679 : __tree_(__comp, __a) {
680 insert(__il.begin(), __il.end());
681 }
682
683# if _LIBCPP_STD_VER >= 14
684 _LIBCPP_HIDE_FROM_ABI set(initializer_list<value_type> __il, const allocator_type& __a)
685 : set(__il, key_compare(), __a) {}
686# endif
687
688 _LIBCPP_HIDE_FROM_ABI set& operator=(initializer_list<value_type> __il) {
689 __tree_.__assign_unique(__il.begin(), __il.end());
690 return *this;
691 }
692
693 _LIBCPP_HIDE_FROM_ABI set& operator=(set&& __s) noexcept(is_nothrow_move_assignable<__base>::value) {
694 __tree_ = std::move(__s.__tree_);
695 return *this;
696 }
697#endif // _LIBCPP_CXX03_LANG
698
699 _LIBCPP_HIDE_FROM_ABI ~set() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); }
700
701 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }
702 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }
703 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }
704 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }
705
706 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
707 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
708 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
709 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
710
711 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
712 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
713 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }
714 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
715
716 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }
717 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }
718 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }
719
720 // modifiers:
721#ifndef _LIBCPP_CXX03_LANG
722 template <class... _Args>
723 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {
724 return __tree_.__emplace_unique(std::forward<_Args>(__args)...);
725 }
726 template <class... _Args>
727 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
728 return __tree_.__emplace_hint_unique(__p, std::forward<_Args>(__args)...);
729 }
730#endif // _LIBCPP_CXX03_LANG
731
732 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__insert_unique(__v); }
733 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
734 return __tree_.__insert_unique(__p, __v);
735 }
736
737 template <class _InputIterator>
738 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
739 for (const_iterator __e = cend(); __f != __l; ++__f)
740 __tree_.__insert_unique(__e, *__f);
741 }
742
743#if _LIBCPP_STD_VER >= 23
744 template <_ContainerCompatibleRange<value_type> _Range>
745 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
746 const_iterator __end = cend();
747 for (auto&& __element : __range) {
748 __tree_.__insert_unique(__end, std::forward<decltype(__element)>(__element));
749 }
750 }
751#endif
752
753#ifndef _LIBCPP_CXX03_LANG
754 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __v) {
755 return __tree_.__insert_unique(std::move(__v));
756 }
757
758 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {
759 return __tree_.__insert_unique(__p, std::move(__v));
760 }
761
762 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
763#endif // _LIBCPP_CXX03_LANG
764
765 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p); }
766 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_unique(__k); }
767 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) { return __tree_.erase(__f, __l); }
768 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }
769
770#if _LIBCPP_STD_VER >= 17
771 _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) {
772 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
773 "node_type with incompatible allocator passed to set::insert()");
774 return __tree_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));
775 }
776 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
777 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
778 "node_type with incompatible allocator passed to set::insert()");
779 return __tree_.template __node_handle_insert_unique<node_type>(__hint, std::move(__nh));
780 }
781 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
782 return __tree_.template __node_handle_extract<node_type>(__key);
783 }
784 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
785 return __tree_.template __node_handle_extract<node_type>(__it);
786 }
787 template <class _Compare2>
788 _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>& __source) {
789 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
790 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
791 __tree_.__node_handle_merge_unique(__source.__tree_);
792 }
793 template <class _Compare2>
794 _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>&& __source) {
795 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
796 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
797 __tree_.__node_handle_merge_unique(__source.__tree_);
798 }
799 template <class _Compare2>
800 _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>& __source) {
801 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
802 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
803 __tree_.__node_handle_merge_unique(__source.__tree_);
804 }
805 template <class _Compare2>
806 _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>&& __source) {
807 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
808 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
809 __tree_.__node_handle_merge_unique(__source.__tree_);
810 }
811#endif
812
813 _LIBCPP_HIDE_FROM_ABI void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) { __tree_.swap(__s.__tree_); }
814
815 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return __tree_.__alloc(); }
816 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp(); }
817 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return __tree_.value_comp(); }
818
819 // set operations:
820 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }
821 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }
822#if _LIBCPP_STD_VER >= 14
823 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
824 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
825 return __tree_.find(__k);
826 }
827 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
828 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
829 return __tree_.find(__k);
830 }
831#endif
832
833 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_unique(__k); }
834#if _LIBCPP_STD_VER >= 14
835 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
836 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
837 return __tree_.__count_multi(__k);
838 }
839#endif
840
841#if _LIBCPP_STD_VER >= 20
842 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
843 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
844 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
845 return find(__k) != end();
846 }
847#endif // _LIBCPP_STD_VER >= 20
848
849 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
850 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
851#if _LIBCPP_STD_VER >= 14
852 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
853 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {
854 return __tree_.lower_bound(__k);
855 }
856
857 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
858 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const {
859 return __tree_.lower_bound(__k);
860 }
861#endif
862
863 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
864 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
865#if _LIBCPP_STD_VER >= 14
866 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
867 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {
868 return __tree_.upper_bound(__k);
869 }
870 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
871 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const {
872 return __tree_.upper_bound(__k);
873 }
874#endif
875
876 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
877 return __tree_.__equal_range_unique(__k);
878 }
879 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
880 return __tree_.__equal_range_unique(__k);
881 }
882#if _LIBCPP_STD_VER >= 14
883 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
884 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
885 return __tree_.__equal_range_multi(__k);
886 }
887 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
888 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
889 return __tree_.__equal_range_multi(__k);
890 }
891#endif
892};
893
894#if _LIBCPP_STD_VER >= 17
895template <class _InputIterator,
896 class _Compare = less<__iter_value_type<_InputIterator>>,
897 class _Allocator = allocator<__iter_value_type<_InputIterator>>,
898 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
899 class = enable_if_t<__is_allocator<_Allocator>::value, void>,
900 class = enable_if_t<!__is_allocator<_Compare>::value, void>>
901set(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
902 -> set<__iter_value_type<_InputIterator>, _Compare, _Allocator>;
903
904# if _LIBCPP_STD_VER >= 23
905template <ranges::input_range _Range,
906 class _Compare = less<ranges::range_value_t<_Range>>,
907 class _Allocator = allocator<ranges::range_value_t<_Range>>,
908 class = enable_if_t<__is_allocator<_Allocator>::value, void>,
909 class = enable_if_t<!__is_allocator<_Compare>::value, void>>
910set(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
911 -> set<ranges::range_value_t<_Range>, _Compare, _Allocator>;
912# endif
913
914template <class _Key,
915 class _Compare = less<_Key>,
916 class _Allocator = allocator<_Key>,
917 class = enable_if_t<!__is_allocator<_Compare>::value, void>,
918 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
919set(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator()) -> set<_Key, _Compare, _Allocator>;
920
921template <class _InputIterator,
922 class _Allocator,
923 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
924 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
925set(_InputIterator,
926 _InputIterator,
927 _Allocator) -> set<__iter_value_type<_InputIterator>, less<__iter_value_type<_InputIterator>>, _Allocator>;
928
929# if _LIBCPP_STD_VER >= 23
930template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
931set(from_range_t,
932 _Range&&,
933 _Allocator) -> set<ranges::range_value_t<_Range>, less<ranges::range_value_t<_Range>>, _Allocator>;
934# endif
935
936template <class _Key, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
937set(initializer_list<_Key>, _Allocator) -> set<_Key, less<_Key>, _Allocator>;
938#endif
939
940#ifndef _LIBCPP_CXX03_LANG
941
942template <class _Key, class _Compare, class _Allocator>
943set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a) : __tree_(std::move(__s.__tree_), __a) {
944 if (__a != __s.get_allocator()) {
945 const_iterator __e = cend();
946 while (!__s.empty())
947 insert(__e, std::move(__s.__tree_.remove(__s.begin())->__value_));
948 }
949}
950
951#endif // _LIBCPP_CXX03_LANG
952
953template <class _Key, class _Compare, class _Allocator>
954inline _LIBCPP_HIDE_FROM_ABI bool
955operator==(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
956 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
957}
958
959#if _LIBCPP_STD_VER <= 17
960
961template <class _Key, class _Compare, class _Allocator>
962inline _LIBCPP_HIDE_FROM_ABI bool
963operator<(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
964 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
965}
966
967template <class _Key, class _Compare, class _Allocator>
968inline _LIBCPP_HIDE_FROM_ABI bool
969operator!=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
970 return !(__x == __y);
971}
972
973template <class _Key, class _Compare, class _Allocator>
974inline _LIBCPP_HIDE_FROM_ABI bool
975operator>(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
976 return __y < __x;
977}
978
979template <class _Key, class _Compare, class _Allocator>
980inline _LIBCPP_HIDE_FROM_ABI bool
981operator>=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
982 return !(__x < __y);
983}
984
985template <class _Key, class _Compare, class _Allocator>
986inline _LIBCPP_HIDE_FROM_ABI bool
987operator<=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
988 return !(__y < __x);
989}
990
991#else // _LIBCPP_STD_VER <= 17
992
993template <class _Key, class _Allocator>
994_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Key>
995operator<=>(const set<_Key, _Allocator>& __x, const set<_Key, _Allocator>& __y) {
996 return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
997}
998
999#endif // _LIBCPP_STD_VER <= 17
1000
1001// specialized algorithms:
1002template <class _Key, class _Compare, class _Allocator>
1003inline _LIBCPP_HIDE_FROM_ABI void swap(set<_Key, _Compare, _Allocator>& __x, set<_Key, _Compare, _Allocator>& __y)
1004 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1005 __x.swap(__y);
1006}
1007
1008#if _LIBCPP_STD_VER >= 20
1009template <class _Key, class _Compare, class _Allocator, class _Predicate>
1010inline _LIBCPP_HIDE_FROM_ABI typename set<_Key, _Compare, _Allocator>::size_type
1011erase_if(set<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {
1012 return std::__libcpp_erase_if_container(__c, __pred);
1013}
1014#endif
1015
1016template <class _Key, class _Compare = less<_Key>, class _Allocator = allocator<_Key> >
1017class _LIBCPP_TEMPLATE_VIS multiset {
1018public:
1019 // types:
1020 typedef _Key key_type;
1021 typedef key_type value_type;
1022 typedef __type_identity_t<_Compare> key_compare;
1023 typedef key_compare value_compare;
1024 typedef __type_identity_t<_Allocator> allocator_type;
1025 typedef value_type& reference;
1026 typedef const value_type& const_reference;
1027
1028 static_assert(is_same<typename allocator_type::value_type, value_type>::value,
1029 "Allocator::value_type must be same type as value_type");
1030
1031private:
1032 typedef __tree<value_type, value_compare, allocator_type> __base;
1033 typedef allocator_traits<allocator_type> __alloc_traits;
1034
1035 static_assert(__check_valid_allocator<allocator_type>::value, "");
1036
1037 __base __tree_;
1038
1039public:
1040 typedef typename __base::pointer pointer;
1041 typedef typename __base::const_pointer const_pointer;
1042 typedef typename __base::size_type size_type;
1043 typedef typename __base::difference_type difference_type;
1044 typedef typename __base::const_iterator iterator;
1045 typedef typename __base::const_iterator const_iterator;
1046 typedef std::reverse_iterator<iterator> reverse_iterator;
1047 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1048
1049#if _LIBCPP_STD_VER >= 17
1050 typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
1051#endif
1052
1053 template <class _Key2, class _Compare2, class _Alloc2>
1054 friend class _LIBCPP_TEMPLATE_VIS set;
1055 template <class _Key2, class _Compare2, class _Alloc2>
1056 friend class _LIBCPP_TEMPLATE_VIS multiset;
1057
1058 // construct/copy/destroy:
1059 _LIBCPP_HIDE_FROM_ABI multiset() _NOEXCEPT_(
1060 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&&
1061 is_nothrow_copy_constructible<key_compare>::value)
1062 : __tree_(value_compare()) {}
1063
1064 _LIBCPP_HIDE_FROM_ABI explicit multiset(const value_compare& __comp) _NOEXCEPT_(
1065 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value)
1066 : __tree_(__comp) {}
1067
1068 _LIBCPP_HIDE_FROM_ABI explicit multiset(const value_compare& __comp, const allocator_type& __a)
1069 : __tree_(__comp, __a) {}
1070 template <class _InputIterator>
1071 _LIBCPP_HIDE_FROM_ABI multiset(_InputIterator __f, _InputIterator __l, const value_compare& __comp = value_compare())
1072 : __tree_(__comp) {
1073 insert(__f, __l);
1074 }
1075
1076#if _LIBCPP_STD_VER >= 14
1077 template <class _InputIterator>
1078 _LIBCPP_HIDE_FROM_ABI multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1079 : multiset(__f, __l, key_compare(), __a) {}
1080#endif
1081
1082 template <class _InputIterator>
1083 _LIBCPP_HIDE_FROM_ABI
1084 multiset(_InputIterator __f, _InputIterator __l, const value_compare& __comp, const allocator_type& __a)
1085 : __tree_(__comp, __a) {
1086 insert(__f, __l);
1087 }
1088
1089#if _LIBCPP_STD_VER >= 23
1090 template <_ContainerCompatibleRange<value_type> _Range>
1091 _LIBCPP_HIDE_FROM_ABI
1092 multiset(from_range_t,
1093 _Range&& __range,
1094 const key_compare& __comp = key_compare(),
1095 const allocator_type& __a = allocator_type())
1096 : __tree_(__comp, __a) {
1097 insert_range(std::forward<_Range>(__range));
1098 }
1099
1100 template <_ContainerCompatibleRange<value_type> _Range>
1101 _LIBCPP_HIDE_FROM_ABI multiset(from_range_t, _Range&& __range, const allocator_type& __a)
1102 : multiset(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
1103#endif
1104
1105 _LIBCPP_HIDE_FROM_ABI multiset(const multiset& __s)
1106 : __tree_(__s.__tree_.value_comp(),
1107 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) {
1108 insert(__s.begin(), __s.end());
1109 }
1110
1111 _LIBCPP_HIDE_FROM_ABI multiset& operator=(const multiset& __s) {
1112 __tree_ = __s.__tree_;
1113 return *this;
1114 }
1115
1116#ifndef _LIBCPP_CXX03_LANG
1117 _LIBCPP_HIDE_FROM_ABI multiset(multiset&& __s) noexcept(is_nothrow_move_constructible<__base>::value)
1118 : __tree_(std::move(__s.__tree_)) {}
1119
1120 _LIBCPP_HIDE_FROM_ABI multiset(multiset&& __s, const allocator_type& __a);
1121#endif // _LIBCPP_CXX03_LANG
1122 _LIBCPP_HIDE_FROM_ABI explicit multiset(const allocator_type& __a) : __tree_(__a) {}
1123 _LIBCPP_HIDE_FROM_ABI multiset(const multiset& __s, const allocator_type& __a)
1124 : __tree_(__s.__tree_.value_comp(), __a) {
1125 insert(__s.begin(), __s.end());
1126 }
1127
1128#ifndef _LIBCPP_CXX03_LANG
1129 _LIBCPP_HIDE_FROM_ABI multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
1130 : __tree_(__comp) {
1131 insert(__il.begin(), __il.end());
1132 }
1133
1134 _LIBCPP_HIDE_FROM_ABI
1135 multiset(initializer_list<value_type> __il, const value_compare& __comp, const allocator_type& __a)
1136 : __tree_(__comp, __a) {
1137 insert(__il.begin(), __il.end());
1138 }
1139
1140# if _LIBCPP_STD_VER >= 14
1141 _LIBCPP_HIDE_FROM_ABI multiset(initializer_list<value_type> __il, const allocator_type& __a)
1142 : multiset(__il, key_compare(), __a) {}
1143# endif
1144
1145 _LIBCPP_HIDE_FROM_ABI multiset& operator=(initializer_list<value_type> __il) {
1146 __tree_.__assign_multi(__il.begin(), __il.end());
1147 return *this;
1148 }
1149
1150 _LIBCPP_HIDE_FROM_ABI multiset& operator=(multiset&& __s) _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) {
1151 __tree_ = std::move(__s.__tree_);
1152 return *this;
1153 }
1154#endif // _LIBCPP_CXX03_LANG
1155
1156 _LIBCPP_HIDE_FROM_ABI ~multiset() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); }
1157
1158 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }
1159 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }
1160 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }
1161 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }
1162
1163 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
1164 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
1165 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
1166 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
1167
1168 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
1169 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
1170 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }
1171 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
1172
1173 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }
1174 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }
1175 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }
1176
1177 // modifiers:
1178#ifndef _LIBCPP_CXX03_LANG
1179 template <class... _Args>
1180 _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) {
1181 return __tree_.__emplace_multi(std::forward<_Args>(__args)...);
1182 }
1183 template <class... _Args>
1184 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1185 return __tree_.__emplace_hint_multi(__p, std::forward<_Args>(__args)...);
1186 }
1187#endif // _LIBCPP_CXX03_LANG
1188
1189 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __v) { return __tree_.__insert_multi(__v); }
1190 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
1191 return __tree_.__insert_multi(__p, __v);
1192 }
1193
1194 template <class _InputIterator>
1195 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
1196 for (const_iterator __e = cend(); __f != __l; ++__f)
1197 __tree_.__insert_multi(__e, *__f);
1198 }
1199
1200#if _LIBCPP_STD_VER >= 23
1201 template <_ContainerCompatibleRange<value_type> _Range>
1202 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
1203 const_iterator __end = cend();
1204 for (auto&& __element : __range) {
1205 __tree_.__insert_multi(__end, std::forward<decltype(__element)>(__element));
1206 }
1207 }
1208#endif
1209
1210#ifndef _LIBCPP_CXX03_LANG
1211 _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __v) { return __tree_.__insert_multi(std::move(__v)); }
1212
1213 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {
1214 return __tree_.__insert_multi(__p, std::move(__v));
1215 }
1216
1217 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
1218#endif // _LIBCPP_CXX03_LANG
1219
1220 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p); }
1221 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_multi(__k); }
1222 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) { return __tree_.erase(__f, __l); }
1223 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }
1224
1225#if _LIBCPP_STD_VER >= 17
1226 _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) {
1227 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1228 "node_type with incompatible allocator passed to multiset::insert()");
1229 return __tree_.template __node_handle_insert_multi<node_type>(std::move(__nh));
1230 }
1231 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
1232 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1233 "node_type with incompatible allocator passed to multiset::insert()");
1234 return __tree_.template __node_handle_insert_multi<node_type>(__hint, std::move(__nh));
1235 }
1236 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
1237 return __tree_.template __node_handle_extract<node_type>(__key);
1238 }
1239 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
1240 return __tree_.template __node_handle_extract<node_type>(__it);
1241 }
1242 template <class _Compare2>
1243 _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>& __source) {
1244 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1245 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1246 __tree_.__node_handle_merge_multi(__source.__tree_);
1247 }
1248 template <class _Compare2>
1249 _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>&& __source) {
1250 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1251 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1252 __tree_.__node_handle_merge_multi(__source.__tree_);
1253 }
1254 template <class _Compare2>
1255 _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>& __source) {
1256 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1257 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1258 __tree_.__node_handle_merge_multi(__source.__tree_);
1259 }
1260 template <class _Compare2>
1261 _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>&& __source) {
1262 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1263 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1264 __tree_.__node_handle_merge_multi(__source.__tree_);
1265 }
1266#endif
1267
1268 _LIBCPP_HIDE_FROM_ABI void swap(multiset& __s) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) {
1269 __tree_.swap(__s.__tree_);
1270 }
1271
1272 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return __tree_.__alloc(); }
1273 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp(); }
1274 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return __tree_.value_comp(); }
1275
1276 // set operations:
1277 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }
1278 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }
1279#if _LIBCPP_STD_VER >= 14
1280 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1281 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
1282 return __tree_.find(__k);
1283 }
1284 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1285 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
1286 return __tree_.find(__k);
1287 }
1288#endif
1289
1290 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_multi(__k); }
1291#if _LIBCPP_STD_VER >= 14
1292 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1293 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
1294 return __tree_.__count_multi(__k);
1295 }
1296#endif
1297
1298#if _LIBCPP_STD_VER >= 20
1299 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
1300 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1301 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
1302 return find(__k) != end();
1303 }
1304#endif // _LIBCPP_STD_VER >= 20
1305
1306 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
1307 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
1308#if _LIBCPP_STD_VER >= 14
1309 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1310 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {
1311 return __tree_.lower_bound(__k);
1312 }
1313
1314 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1315 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const {
1316 return __tree_.lower_bound(__k);
1317 }
1318#endif
1319
1320 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
1321 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
1322#if _LIBCPP_STD_VER >= 14
1323 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1324 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {
1325 return __tree_.upper_bound(__k);
1326 }
1327 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1328 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const {
1329 return __tree_.upper_bound(__k);
1330 }
1331#endif
1332
1333 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
1334 return __tree_.__equal_range_multi(__k);
1335 }
1336 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
1337 return __tree_.__equal_range_multi(__k);
1338 }
1339#if _LIBCPP_STD_VER >= 14
1340 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1341 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
1342 return __tree_.__equal_range_multi(__k);
1343 }
1344 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1345 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
1346 return __tree_.__equal_range_multi(__k);
1347 }
1348#endif
1349};
1350
1351#if _LIBCPP_STD_VER >= 17
1352template <class _InputIterator,
1353 class _Compare = less<__iter_value_type<_InputIterator>>,
1354 class _Allocator = allocator<__iter_value_type<_InputIterator>>,
1355 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1356 class = enable_if_t<__is_allocator<_Allocator>::value, void>,
1357 class = enable_if_t<!__is_allocator<_Compare>::value, void>>
1358multiset(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1359 -> multiset<__iter_value_type<_InputIterator>, _Compare, _Allocator>;
1360
1361# if _LIBCPP_STD_VER >= 23
1362template <ranges::input_range _Range,
1363 class _Compare = less<ranges::range_value_t<_Range>>,
1364 class _Allocator = allocator<ranges::range_value_t<_Range>>,
1365 class = enable_if_t<__is_allocator<_Allocator>::value, void>,
1366 class = enable_if_t<!__is_allocator<_Compare>::value, void>>
1367multiset(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
1368 -> multiset<ranges::range_value_t<_Range>, _Compare, _Allocator>;
1369# endif
1370
1371template <class _Key,
1372 class _Compare = less<_Key>,
1373 class _Allocator = allocator<_Key>,
1374 class = enable_if_t<__is_allocator<_Allocator>::value, void>,
1375 class = enable_if_t<!__is_allocator<_Compare>::value, void>>
1376multiset(initializer_list<_Key>,
1377 _Compare = _Compare(),
1378 _Allocator = _Allocator()) -> multiset<_Key, _Compare, _Allocator>;
1379
1380template <class _InputIterator,
1381 class _Allocator,
1382 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1383 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1384multiset(_InputIterator, _InputIterator, _Allocator)
1385 -> multiset<__iter_value_type<_InputIterator>, less<__iter_value_type<_InputIterator>>, _Allocator>;
1386
1387# if _LIBCPP_STD_VER >= 23
1388template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1389multiset(from_range_t,
1390 _Range&&,
1391 _Allocator) -> multiset<ranges::range_value_t<_Range>, less<ranges::range_value_t<_Range>>, _Allocator>;
1392# endif
1393
1394template <class _Key, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1395multiset(initializer_list<_Key>, _Allocator) -> multiset<_Key, less<_Key>, _Allocator>;
1396#endif
1397
1398#ifndef _LIBCPP_CXX03_LANG
1399
1400template <class _Key, class _Compare, class _Allocator>
1401multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a)
1402 : __tree_(std::move(__s.__tree_), __a) {
1403 if (__a != __s.get_allocator()) {
1404 const_iterator __e = cend();
1405 while (!__s.empty())
1406 insert(__e, std::move(__s.__tree_.remove(__s.begin())->__value_));
1407 }
1408}
1409
1410#endif // _LIBCPP_CXX03_LANG
1411
1412template <class _Key, class _Compare, class _Allocator>
1413inline _LIBCPP_HIDE_FROM_ABI bool
1414operator==(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1415 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
1416}
1417
1418#if _LIBCPP_STD_VER <= 17
1419
1420template <class _Key, class _Compare, class _Allocator>
1421inline _LIBCPP_HIDE_FROM_ABI bool
1422operator<(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1423 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1424}
1425
1426template <class _Key, class _Compare, class _Allocator>
1427inline _LIBCPP_HIDE_FROM_ABI bool
1428operator!=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1429 return !(__x == __y);
1430}
1431
1432template <class _Key, class _Compare, class _Allocator>
1433inline _LIBCPP_HIDE_FROM_ABI bool
1434operator>(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1435 return __y < __x;
1436}
1437
1438template <class _Key, class _Compare, class _Allocator>
1439inline _LIBCPP_HIDE_FROM_ABI bool
1440operator>=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1441 return !(__x < __y);
1442}
1443
1444template <class _Key, class _Compare, class _Allocator>
1445inline _LIBCPP_HIDE_FROM_ABI bool
1446operator<=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1447 return !(__y < __x);
1448}
1449
1450#else // _LIBCPP_STD_VER <= 17
1451
1452template <class _Key, class _Allocator>
1453_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Key>
1454operator<=>(const multiset<_Key, _Allocator>& __x, const multiset<_Key, _Allocator>& __y) {
1455 return std::lexicographical_compare_three_way(
1456 __x.begin(), __x.end(), __y.begin(), __y.end(), __synth_three_way);
1457}
1458
1459#endif // _LIBCPP_STD_VER <= 17
1460
1461template <class _Key, class _Compare, class _Allocator>
1462inline _LIBCPP_HIDE_FROM_ABI void
1463swap(multiset<_Key, _Compare, _Allocator>& __x, multiset<_Key, _Compare, _Allocator>& __y)
1464 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1465 __x.swap(__y);
1466}
1467
1468#if _LIBCPP_STD_VER >= 20
1469template <class _Key, class _Compare, class _Allocator, class _Predicate>
1470inline _LIBCPP_HIDE_FROM_ABI typename multiset<_Key, _Compare, _Allocator>::size_type
1471erase_if(multiset<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {
1472 return std::__libcpp_erase_if_container(__c, __pred);
1473}
1474#endif
1475
1476_LIBCPP_END_NAMESPACE_STD
1477
1478#if _LIBCPP_STD_VER >= 17
1479_LIBCPP_BEGIN_NAMESPACE_STD
1480namespace pmr {
1481template <class _KeyT, class _CompareT = std::less<_KeyT>>
1482using set _LIBCPP_AVAILABILITY_PMR = std::set<_KeyT, _CompareT, polymorphic_allocator<_KeyT>>;
1483
1484template <class _KeyT, class _CompareT = std::less<_KeyT>>
1485using multiset _LIBCPP_AVAILABILITY_PMR = std::multiset<_KeyT, _CompareT, polymorphic_allocator<_KeyT>>;
1486} // namespace pmr
1487_LIBCPP_END_NAMESPACE_STD
1488#endif
1489
1490_LIBCPP_POP_MACROS
1491
1492#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
1493# include <concepts>
1494# include <cstdlib>
1495# include <functional>
1496# include <iterator>
1497# include <stdexcept>
1498# include <type_traits>
1499#endif
1500
1501#endif // _LIBCPP_SET
1502