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