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) {}
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) {}
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) {}
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) {}
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 _LIBCPP_CONSTEXPR_SINCE_CXX26 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 _LIBCPP_CONSTEXPR_SINCE_CXX26 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
628 _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit set(const value_compare& __comp, const allocator_type& __a)
629 : __tree_(__comp, __a) {}
630 template <class _InputIterator>
631 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
632 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp = value_compare())
633 : __tree_(__comp) {
634 insert(__f, __l);
635 }
636
637 template <class _InputIterator>
638 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
639 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, const allocator_type& __a)
640 : __tree_(__comp, __a) {
641 insert(__f, __l);
642 }
643
644# if _LIBCPP_STD_VER >= 23
645 template <_ContainerCompatibleRange<value_type> _Range>
646 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
647 set(from_range_t,
648 _Range&& __range,
649 const key_compare& __comp = key_compare(),
650 const allocator_type& __a = allocator_type())
651 : __tree_(__comp, __a) {
652 insert_range(std::forward<_Range>(__range));
653 }
654# endif
655
656 template <class _InputIterator>
657 _LIBCPP_HIDE_FROM_ABI
658 _LIBCPP_CONSTEXPR_SINCE_CXX26 set(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
659 : set(__f, __l, key_compare(), __a) {}
660
661# if _LIBCPP_STD_VER >= 23
662 template <_ContainerCompatibleRange<value_type> _Range>
663 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 set(from_range_t, _Range&& __range, const allocator_type& __a)
664 : set(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
665# endif
666
667 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 set(const set& __s) = default;
668
669 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 set& operator=(const set& __s) = default;
670
671# ifndef _LIBCPP_CXX03_LANG
672 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 set(set&& __s) = default;
673# endif // _LIBCPP_CXX03_LANG
674
675 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit set(const allocator_type& __a) : __tree_(__a) {}
676
677 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 set(const set& __s, const allocator_type& __alloc)
678 : __tree_(__s.__tree_, __alloc) {}
679
680# ifndef _LIBCPP_CXX03_LANG
681 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 set(set&& __s, const allocator_type& __alloc)
682 : __tree_(std::move(__s.__tree_), __alloc) {}
683
684 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
685 set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
686 : __tree_(__comp) {
687 insert(__il.begin(), __il.end());
688 }
689
690 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
691 set(initializer_list<value_type> __il, const value_compare& __comp, const allocator_type& __a)
692 : __tree_(__comp, __a) {
693 insert(__il.begin(), __il.end());
694 }
695
696 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 set(initializer_list<value_type> __il, const allocator_type& __a)
697 : set(__il, key_compare(), __a) {}
698
699 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 set& operator=(initializer_list<value_type> __il) {
700 clear();
701 insert(__il.begin(), __il.end());
702 return *this;
703 }
704
705 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 set& operator=(set&& __s) = default;
706# endif // _LIBCPP_CXX03_LANG
707
708 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 ~set() {
709 static_assert(sizeof(std::__diagnose_non_const_comparator<_Key, _Compare>()), "");
710 }
711
712 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator begin() _NOEXCEPT {
713 return __tree_.begin();
714 }
715 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator begin() const _NOEXCEPT {
716 return __tree_.begin();
717 }
718 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator end() _NOEXCEPT {
719 return __tree_.end();
720 }
721 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator end() const _NOEXCEPT {
722 return __tree_.end();
723 }
724
725 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 reverse_iterator rbegin() _NOEXCEPT {
726 return reverse_iterator(end());
727 }
728 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator
729 rbegin() const _NOEXCEPT {
730 return const_reverse_iterator(end());
731 }
732 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 reverse_iterator rend() _NOEXCEPT {
733 return reverse_iterator(begin());
734 }
735 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator rend() const _NOEXCEPT {
736 return const_reverse_iterator(begin());
737 }
738
739 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator cbegin() const _NOEXCEPT {
740 return begin();
741 }
742 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator cend() const _NOEXCEPT {
743 return end();
744 }
745 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator
746 crbegin() const _NOEXCEPT {
747 return rbegin();
748 }
749 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator crend() const _NOEXCEPT {
750 return rend();
751 }
752
753 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool empty() const _NOEXCEPT {
754 return __tree_.size() == 0;
755 }
756 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type size() const _NOEXCEPT {
757 return __tree_.size();
758 }
759 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type max_size() const _NOEXCEPT {
760 return __tree_.max_size();
761 }
762
763 // modifiers:
764# ifndef _LIBCPP_CXX03_LANG
765 template <class... _Args>
766 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> emplace(_Args&&... __args) {
767 return __tree_.__emplace_unique(std::forward<_Args>(__args)...);
768 }
769 template <class... _Args>
770 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator emplace_hint(const_iterator __p, _Args&&... __args) {
771 return __tree_.__emplace_hint_unique(__p, std::forward<_Args>(__args)...).first;
772 }
773# endif // _LIBCPP_CXX03_LANG
774
775 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> insert(const value_type& __v) {
776 return __tree_.__emplace_unique(__v);
777 }
778 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __p, const value_type& __v) {
779 return __tree_.__emplace_hint_unique(__p, __v).first;
780 }
781
782 template <class _InputIterator>
783 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(_InputIterator __first, _InputIterator __last) {
784 __tree_.__insert_range_unique(__first, __last);
785 }
786
787# if _LIBCPP_STD_VER >= 23
788 template <_ContainerCompatibleRange<value_type> _Range>
789 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert_range(_Range&& __range) {
790 __tree_.__insert_range_unique(ranges::begin(__range), ranges::end(__range));
791 }
792# endif
793
794# ifndef _LIBCPP_CXX03_LANG
795 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> insert(value_type&& __v) {
796 return __tree_.__emplace_unique(std::move(__v));
797 }
798
799 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __p, value_type&& __v) {
800 return __tree_.__emplace_hint_unique(__p, std::move(__v)).first;
801 }
802
803 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(initializer_list<value_type> __il) {
804 insert(__il.begin(), __il.end());
805 }
806# endif // _LIBCPP_CXX03_LANG
807
808 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator erase(const_iterator __p) { return __tree_.erase(__p); }
809 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type erase(const key_type& __k) {
810 return __tree_.__erase_unique(__k);
811 }
812 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator erase(const_iterator __f, const_iterator __l) {
813 return __tree_.erase(__f, __l);
814 }
815 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void clear() _NOEXCEPT { __tree_.clear(); }
816
817# if _LIBCPP_STD_VER >= 17
818 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 insert_return_type insert(node_type&& __nh) {
819 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
820 "node_type with incompatible allocator passed to set::insert()");
821 return __tree_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));
822 }
823 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __hint, node_type&& __nh) {
824 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
825 "node_type with incompatible allocator passed to set::insert()");
826 return __tree_.template __node_handle_insert_unique<node_type>(__hint, std::move(__nh));
827 }
828 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 node_type extract(key_type const& __key) {
829 return __tree_.template __node_handle_extract<node_type>(__key);
830 }
831 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 node_type extract(const_iterator __it) {
832 return __tree_.template __node_handle_extract<node_type>(__it);
833 }
834 template <class _Compare2>
835 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void merge(set<key_type, _Compare2, allocator_type>& __source) {
836 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
837 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
838 __tree_.__node_handle_merge_unique(__source.__tree_);
839 }
840 template <class _Compare2>
841 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void merge(set<key_type, _Compare2, allocator_type>&& __source) {
842 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
843 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
844 __tree_.__node_handle_merge_unique(__source.__tree_);
845 }
846 template <class _Compare2>
847 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
848 merge(multiset<key_type, _Compare2, allocator_type>& __source) {
849 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
850 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
851 __tree_.__node_handle_merge_unique(__source.__tree_);
852 }
853 template <class _Compare2>
854 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
855 merge(multiset<key_type, _Compare2, allocator_type>&& __source) {
856 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
857 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
858 __tree_.__node_handle_merge_unique(__source.__tree_);
859 }
860# endif
861
862 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) {
863 __tree_.swap(__s.__tree_);
864 }
865
866 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 allocator_type get_allocator() const _NOEXCEPT {
867 return __tree_.__alloc();
868 }
869 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 key_compare key_comp() const {
870 return __tree_.value_comp();
871 }
872 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 value_compare value_comp() const {
873 return __tree_.value_comp();
874 }
875
876 // set operations:
877 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator find(const key_type& __k) {
878 return __tree_.find(__k);
879 }
880 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator find(const key_type& __k) const {
881 return __tree_.find(__k);
882 }
883# if _LIBCPP_STD_VER >= 14
884 template <typename _K2,
885 class _Comp = _Compare,
886 enable_if_t<__is_transparent_v<_Comp> || __is_transparently_comparable_v<_Comp, key_type, _K2>, int> = 0>
887 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator find(const _K2& __k) {
888 return __tree_.find(__k);
889 }
890 template <typename _K2,
891 class _Comp = _Compare,
892 enable_if_t<__is_transparent_v<_Comp> || __is_transparently_comparable_v<_Comp, key_type, _K2>, int> = 0>
893 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator find(const _K2& __k) const {
894 return __tree_.find(__k);
895 }
896# endif
897
898 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type count(const key_type& __k) const {
899 return __tree_.__count_unique(__k);
900 }
901# if _LIBCPP_STD_VER >= 14
902 template <typename _K2, class _Comp = _Compare, enable_if_t<__is_transparent_v<_Comp>, int> = 0>
903 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type count(const _K2& __k) const {
904 return __tree_.__count_multi(__k);
905 }
906# endif
907
908# if _LIBCPP_STD_VER >= 20
909 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool contains(const key_type& __k) const {
910 return find(__k) != end();
911 }
912 template <typename _K2,
913 class _Comp = _Compare,
914 enable_if_t<__is_transparent_v<_Comp> || __is_transparently_comparable_v<_Comp, key_type, _K2>, int> = 0>
915 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool contains(const _K2& __k) const {
916 return find(__k) != end();
917 }
918# endif // _LIBCPP_STD_VER >= 20
919
920 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator lower_bound(const key_type& __k) {
921 return __tree_.__lower_bound_unique(__k);
922 }
923
924 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator
925 lower_bound(const key_type& __k) const {
926 return __tree_.__lower_bound_unique(__k);
927 }
928
929 // The transparent versions of the lookup functions use the _multi version, since a non-element key is allowed to
930 // match multiple elements.
931# if _LIBCPP_STD_VER >= 14
932 template <typename _K2,
933 class _Comp = _Compare,
934 enable_if_t<__is_transparent_v<_Comp> || __is_transparently_comparable_v<_Comp, key_type, _K2>, int> = 0>
935 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator lower_bound(const _K2& __k) {
936 return __tree_.__lower_bound_multi(__k);
937 }
938
939 template <typename _K2,
940 class _Comp = _Compare,
941 enable_if_t<__is_transparent_v<_Comp> || __is_transparently_comparable_v<_Comp, key_type, _K2>, int> = 0>
942 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator
943 lower_bound(const _K2& __k) const {
944 return __tree_.__lower_bound_multi(__k);
945 }
946# endif
947
948 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator upper_bound(const key_type& __k) {
949 return __tree_.__upper_bound_unique(__k);
950 }
951
952 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator
953 upper_bound(const key_type& __k) const {
954 return __tree_.__upper_bound_unique(__k);
955 }
956
957# if _LIBCPP_STD_VER >= 14
958 template <typename _K2,
959 class _Comp = _Compare,
960 enable_if_t<__is_transparent_v<_Comp> || __is_transparently_comparable_v<_Comp, key_type, _K2>, int> = 0>
961 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator upper_bound(const _K2& __k) {
962 return __tree_.__upper_bound_multi(__k);
963 }
964 template <typename _K2,
965 class _Comp = _Compare,
966 enable_if_t<__is_transparent_v<_Comp> || __is_transparently_comparable_v<_Comp, key_type, _K2>, int> = 0>
967 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator
968 upper_bound(const _K2& __k) const {
969 return __tree_.__upper_bound_multi(__k);
970 }
971# endif
972
973 [[__nodiscard__]]
974 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, iterator> equal_range(const key_type& __k) {
975 return __tree_.__equal_range_unique(__k);
976 }
977 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<const_iterator, const_iterator>
978 equal_range(const key_type& __k) const {
979 return __tree_.__equal_range_unique(__k);
980 }
981# if _LIBCPP_STD_VER >= 14
982 template <typename _K2, class _Comp = _Compare, enable_if_t<__is_transparent_v<_Comp>, int> = 0>
983 [[__nodiscard__]]
984 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, iterator> equal_range(const _K2& __k) {
985 return __tree_.__equal_range_multi(__k);
986 }
987 template <typename _K2, class _Comp = _Compare, enable_if_t<__is_transparent_v<_Comp>, int> = 0>
988 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<const_iterator, const_iterator>
989 equal_range(const _K2& __k) const {
990 return __tree_.__equal_range_multi(__k);
991 }
992# endif
993
994 template <class, class...>
995 friend struct __specialized_algorithm;
996};
997
998# if _LIBCPP_STD_VER >= 17
999template <class _InputIterator,
1000 class _Compare = less<__iterator_value_type<_InputIterator>>,
1001 class _Allocator = allocator<__iterator_value_type<_InputIterator>>,
1002 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1003 class = enable_if_t<__is_allocator_v<_Allocator>>,
1004 class = enable_if_t<!__is_allocator_v<_Compare>>>
1005set(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1006 -> set<__iterator_value_type<_InputIterator>, _Compare, _Allocator>;
1007
1008# if _LIBCPP_STD_VER >= 23
1009template <ranges::input_range _Range,
1010 class _Compare = less<ranges::range_value_t<_Range>>,
1011 class _Allocator = allocator<ranges::range_value_t<_Range>>,
1012 class = enable_if_t<__is_allocator_v<_Allocator>>,
1013 class = enable_if_t<!__is_allocator_v<_Compare>>>
1014set(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
1015 -> set<ranges::range_value_t<_Range>, _Compare, _Allocator>;
1016# endif
1017
1018template <class _Key,
1019 class _Compare = less<_Key>,
1020 class _Allocator = allocator<_Key>,
1021 class = enable_if_t<!__is_allocator_v<_Compare>>,
1022 class = enable_if_t<__is_allocator_v<_Allocator>>>
1023set(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator()) -> set<_Key, _Compare, _Allocator>;
1024
1025template <class _InputIterator,
1026 class _Allocator,
1027 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1028 class = enable_if_t<__is_allocator_v<_Allocator>>>
1029set(_InputIterator, _InputIterator, _Allocator)
1030 -> set<__iterator_value_type<_InputIterator>, less<__iterator_value_type<_InputIterator>>, _Allocator>;
1031
1032# if _LIBCPP_STD_VER >= 23
1033template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>
1034set(from_range_t, _Range&&, _Allocator)
1035 -> set<ranges::range_value_t<_Range>, less<ranges::range_value_t<_Range>>, _Allocator>;
1036# endif
1037
1038template <class _Key, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>
1039set(initializer_list<_Key>, _Allocator) -> set<_Key, less<_Key>, _Allocator>;
1040# endif
1041
1042# if _LIBCPP_STD_VER >= 14
1043template <class _Alg, class _Key, class _Compare, class _Allocator>
1044struct __specialized_algorithm<_Alg, __single_range<set<_Key, _Compare, _Allocator>>> {
1045 using __set _LIBCPP_NODEBUG = set<_Key, _Compare, _Allocator>;
1046
1047 static const bool __has_algorithm =
1048 __specialized_algorithm<_Alg, __single_range<typename __set::__base>>::__has_algorithm;
1049
1050 // set's begin() and end() are identical with and without const qualification
1051 template <class... _Args>
1052 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto operator()(const __set& __set, _Args&&... __args) {
1053 return __specialized_algorithm<_Alg, __single_range<typename __set::__base>>()(
1054 __set.__tree_, std::forward<_Args>(__args)...);
1055 }
1056};
1057# endif
1058
1059template <class _Key, class _Compare, class _Allocator>
1060inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
1061operator==(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
1062 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
1063}
1064
1065# if _LIBCPP_STD_VER <= 17
1066
1067template <class _Key, class _Compare, class _Allocator>
1068inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
1069operator<(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
1070 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1071}
1072
1073template <class _Key, class _Compare, class _Allocator>
1074inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
1075operator!=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
1076 return !(__x == __y);
1077}
1078
1079template <class _Key, class _Compare, class _Allocator>
1080inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
1081operator>(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
1082 return __y < __x;
1083}
1084
1085template <class _Key, class _Compare, class _Allocator>
1086inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
1087operator>=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
1088 return !(__x < __y);
1089}
1090
1091template <class _Key, class _Compare, class _Allocator>
1092inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
1093operator<=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
1094 return !(__y < __x);
1095}
1096
1097# else // _LIBCPP_STD_VER <= 17
1098
1099template <class _Key, class _Compare, class _Allocator>
1100_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __synth_three_way_result<_Key>
1101operator<=>(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
1102 return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
1103}
1104
1105# endif // _LIBCPP_STD_VER <= 17
1106
1107// specialized algorithms:
1108template <class _Key, class _Compare, class _Allocator>
1109inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
1110swap(set<_Key, _Compare, _Allocator>& __x, set<_Key, _Compare, _Allocator>& __y) _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1111 __x.swap(__y);
1112}
1113
1114# if _LIBCPP_STD_VER >= 20
1115template <class _Key, class _Compare, class _Allocator, class _Predicate>
1116inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 typename set<_Key, _Compare, _Allocator>::size_type
1117erase_if(set<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {
1118 return std::__libcpp_erase_if_container(__c, __pred);
1119}
1120# endif
1121
1122template <class _Key, class _Compare, class _Allocator>
1123struct __container_traits<set<_Key, _Compare, _Allocator> > {
1124 // http://eel.is/c++draft/associative.reqmts.except#2
1125 // For associative containers, if an exception is thrown by any operation from within
1126 // an insert or emplace function inserting a single element, the insertion has no effect.
1127 static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee = true;
1128
1129 static _LIBCPP_CONSTEXPR const bool __reservable = false;
1130};
1131
1132template <class _Key, class _Compare, class _Allocator>
1133class multiset {
1134public:
1135 // types:
1136 typedef _Key key_type;
1137 typedef key_type value_type;
1138 typedef __type_identity_t<_Compare> key_compare;
1139 typedef key_compare value_compare;
1140 typedef __type_identity_t<_Allocator> allocator_type;
1141 typedef value_type& reference;
1142 typedef const value_type& const_reference;
1143
1144 static_assert(is_same<typename allocator_type::value_type, value_type>::value,
1145 "Allocator::value_type must be same type as value_type");
1146
1147private:
1148 typedef __tree<value_type, value_compare, allocator_type> __base;
1149 typedef allocator_traits<allocator_type> __alloc_traits;
1150
1151 static_assert(__check_valid_allocator<allocator_type>::value, "");
1152
1153 __base __tree_;
1154
1155public:
1156 typedef typename __base::pointer pointer;
1157 typedef typename __base::const_pointer const_pointer;
1158 typedef typename __base::size_type size_type;
1159 typedef typename __base::difference_type difference_type;
1160 typedef typename __base::const_iterator iterator;
1161 typedef typename __base::const_iterator const_iterator;
1162 typedef std::reverse_iterator<iterator> reverse_iterator;
1163 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1164
1165# if _LIBCPP_STD_VER >= 17
1166 typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
1167# endif
1168
1169 template <class _Key2, class _Compare2, class _Alloc2>
1170 friend class set;
1171 template <class _Key2, class _Compare2, class _Alloc2>
1172 friend class multiset;
1173
1174 // construct/copy/destroy:
1175 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 multiset() _NOEXCEPT_(
1176 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&&
1177 is_nothrow_copy_constructible<key_compare>::value)
1178 : __tree_(value_compare()) {}
1179
1180 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit multiset(const value_compare& __comp) _NOEXCEPT_(
1181 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value)
1182 : __tree_(__comp) {}
1183
1184 _LIBCPP_HIDE_FROM_ABI
1185 _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit multiset(const value_compare& __comp, const allocator_type& __a)
1186 : __tree_(__comp, __a) {}
1187 template <class _InputIterator>
1188 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
1189 multiset(_InputIterator __f, _InputIterator __l, const value_compare& __comp = value_compare())
1190 : __tree_(__comp) {
1191 insert(__f, __l);
1192 }
1193
1194 template <class _InputIterator>
1195 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
1196 multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1197 : multiset(__f, __l, key_compare(), __a) {}
1198
1199 template <class _InputIterator>
1200 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
1201 multiset(_InputIterator __f, _InputIterator __l, const value_compare& __comp, const allocator_type& __a)
1202 : __tree_(__comp, __a) {
1203 insert(__f, __l);
1204 }
1205
1206# if _LIBCPP_STD_VER >= 23
1207 template <_ContainerCompatibleRange<value_type> _Range>
1208 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
1209 multiset(from_range_t,
1210 _Range&& __range,
1211 const key_compare& __comp = key_compare(),
1212 const allocator_type& __a = allocator_type())
1213 : __tree_(__comp, __a) {
1214 insert_range(std::forward<_Range>(__range));
1215 }
1216
1217 template <_ContainerCompatibleRange<value_type> _Range>
1218 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
1219 multiset(from_range_t, _Range&& __range, const allocator_type& __a)
1220 : multiset(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
1221# endif
1222
1223 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 multiset(const multiset& __s) = default;
1224
1225 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 multiset& operator=(const multiset& __s) = default;
1226
1227# ifndef _LIBCPP_CXX03_LANG
1228 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 multiset(multiset&& __s) = default;
1229
1230 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 multiset(multiset&& __s, const allocator_type& __a)
1231 : __tree_(std::move(__s.__tree_), __a) {}
1232# endif // _LIBCPP_CXX03_LANG
1233 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit multiset(const allocator_type& __a) : __tree_(__a) {}
1234 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 multiset(const multiset& __s, const allocator_type& __a)
1235 : __tree_(__s.__tree_, __a) {}
1236
1237# ifndef _LIBCPP_CXX03_LANG
1238 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
1239 multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
1240 : __tree_(__comp) {
1241 insert(__il.begin(), __il.end());
1242 }
1243
1244 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
1245 multiset(initializer_list<value_type> __il, const value_compare& __comp, const allocator_type& __a)
1246 : __tree_(__comp, __a) {
1247 insert(__il.begin(), __il.end());
1248 }
1249
1250 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
1251 multiset(initializer_list<value_type> __il, const allocator_type& __a)
1252 : multiset(__il, key_compare(), __a) {}
1253
1254 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 multiset& operator=(initializer_list<value_type> __il) {
1255 clear();
1256 insert(__il.begin(), __il.end());
1257 return *this;
1258 }
1259
1260 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 multiset& operator=(multiset&& __s) = default;
1261# endif // _LIBCPP_CXX03_LANG
1262
1263 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 ~multiset() {
1264 static_assert(sizeof(std::__diagnose_non_const_comparator<_Key, _Compare>()), "");
1265 }
1266
1267 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator begin() _NOEXCEPT {
1268 return __tree_.begin();
1269 }
1270 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator begin() const _NOEXCEPT {
1271 return __tree_.begin();
1272 }
1273 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator end() _NOEXCEPT {
1274 return __tree_.end();
1275 }
1276 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator end() const _NOEXCEPT {
1277 return __tree_.end();
1278 }
1279
1280 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 reverse_iterator rbegin() _NOEXCEPT {
1281 return reverse_iterator(end());
1282 }
1283 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator
1284 rbegin() const _NOEXCEPT {
1285 return const_reverse_iterator(end());
1286 }
1287 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 reverse_iterator rend() _NOEXCEPT {
1288 return reverse_iterator(begin());
1289 }
1290 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator rend() const _NOEXCEPT {
1291 return const_reverse_iterator(begin());
1292 }
1293
1294 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator cbegin() const _NOEXCEPT {
1295 return begin();
1296 }
1297 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator cend() const _NOEXCEPT {
1298 return end();
1299 }
1300 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator
1301 crbegin() const _NOEXCEPT {
1302 return rbegin();
1303 }
1304 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator crend() const _NOEXCEPT {
1305 return rend();
1306 }
1307
1308 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool empty() const _NOEXCEPT {
1309 return __tree_.size() == 0;
1310 }
1311 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type size() const _NOEXCEPT {
1312 return __tree_.size();
1313 }
1314 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type max_size() const _NOEXCEPT {
1315 return __tree_.max_size();
1316 }
1317
1318 // modifiers:
1319# ifndef _LIBCPP_CXX03_LANG
1320 template <class... _Args>
1321 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator emplace(_Args&&... __args) {
1322 return __tree_.__emplace_multi(std::forward<_Args>(__args)...);
1323 }
1324 template <class... _Args>
1325 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1326 return __tree_.__emplace_hint_multi(__p, std::forward<_Args>(__args)...);
1327 }
1328# endif // _LIBCPP_CXX03_LANG
1329
1330 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const value_type& __v) {
1331 return __tree_.__emplace_multi(__v);
1332 }
1333 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __p, const value_type& __v) {
1334 return __tree_.__emplace_hint_multi(__p, __v);
1335 }
1336
1337 template <class _InputIterator>
1338 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(_InputIterator __first, _InputIterator __last) {
1339 __tree_.__insert_range_multi(__first, __last);
1340 }
1341
1342# if _LIBCPP_STD_VER >= 23
1343 template <_ContainerCompatibleRange<value_type> _Range>
1344 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert_range(_Range&& __range) {
1345 __tree_.__insert_range_multi(ranges::begin(__range), ranges::end(__range));
1346 }
1347# endif
1348
1349# ifndef _LIBCPP_CXX03_LANG
1350 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(value_type&& __v) {
1351 return __tree_.__emplace_multi(std::move(__v));
1352 }
1353
1354 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __p, value_type&& __v) {
1355 return __tree_.__emplace_hint_multi(__p, std::move(__v));
1356 }
1357
1358 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(initializer_list<value_type> __il) {
1359 insert(__il.begin(), __il.end());
1360 }
1361# endif // _LIBCPP_CXX03_LANG
1362
1363 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator erase(const_iterator __p) { return __tree_.erase(__p); }
1364 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type erase(const key_type& __k) {
1365 return __tree_.__erase_multi(__k);
1366 }
1367 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator erase(const_iterator __f, const_iterator __l) {
1368 return __tree_.erase(__f, __l);
1369 }
1370 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void clear() _NOEXCEPT { __tree_.clear(); }
1371
1372# if _LIBCPP_STD_VER >= 17
1373 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(node_type&& __nh) {
1374 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1375 "node_type with incompatible allocator passed to multiset::insert()");
1376 return __tree_.template __node_handle_insert_multi<node_type>(std::move(__nh));
1377 }
1378 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __hint, node_type&& __nh) {
1379 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1380 "node_type with incompatible allocator passed to multiset::insert()");
1381 return __tree_.template __node_handle_insert_multi<node_type>(__hint, std::move(__nh));
1382 }
1383 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 node_type extract(key_type const& __key) {
1384 return __tree_.template __node_handle_extract<node_type>(__key);
1385 }
1386 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 node_type extract(const_iterator __it) {
1387 return __tree_.template __node_handle_extract<node_type>(__it);
1388 }
1389 template <class _Compare2>
1390 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
1391 merge(multiset<key_type, _Compare2, allocator_type>& __source) {
1392 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1393 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1394 __tree_.__node_handle_merge_multi(__source.__tree_);
1395 }
1396 template <class _Compare2>
1397 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
1398 merge(multiset<key_type, _Compare2, allocator_type>&& __source) {
1399 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1400 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1401 __tree_.__node_handle_merge_multi(__source.__tree_);
1402 }
1403 template <class _Compare2>
1404 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void merge(set<key_type, _Compare2, allocator_type>& __source) {
1405 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1406 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1407 __tree_.__node_handle_merge_multi(__source.__tree_);
1408 }
1409 template <class _Compare2>
1410 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void merge(set<key_type, _Compare2, allocator_type>&& __source) {
1411 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1412 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1413 __tree_.__node_handle_merge_multi(__source.__tree_);
1414 }
1415# endif
1416
1417 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void swap(multiset& __s)
1418 _NOEXCEPT_(__is_nothrow_swappable_v<__base>) {
1419 __tree_.swap(__s.__tree_);
1420 }
1421
1422 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 allocator_type get_allocator() const _NOEXCEPT {
1423 return __tree_.__alloc();
1424 }
1425 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 key_compare key_comp() const {
1426 return __tree_.value_comp();
1427 }
1428 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 value_compare value_comp() const {
1429 return __tree_.value_comp();
1430 }
1431
1432 // set operations:
1433 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator find(const key_type& __k) {
1434 return __tree_.find(__k);
1435 }
1436 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator find(const key_type& __k) const {
1437 return __tree_.find(__k);
1438 }
1439# if _LIBCPP_STD_VER >= 14
1440 template <typename _K2,
1441 class _Comp = _Compare,
1442 enable_if_t<__is_transparent_v<_Comp> || __is_transparently_comparable_v<_Comp, key_type, _K2>, int> = 0>
1443 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator find(const _K2& __k) {
1444 return __tree_.find(__k);
1445 }
1446 template <typename _K2,
1447 class _Comp = _Compare,
1448 enable_if_t<__is_transparent_v<_Comp> || __is_transparently_comparable_v<_Comp, key_type, _K2>, int> = 0>
1449 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator find(const _K2& __k) const {
1450 return __tree_.find(__k);
1451 }
1452# endif
1453
1454 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type count(const key_type& __k) const {
1455 return __tree_.__count_multi(__k);
1456 }
1457# if _LIBCPP_STD_VER >= 14
1458 template <typename _K2, class _Comp = _Compare, enable_if_t<__is_transparent_v<_Comp>, int> = 0>
1459 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type count(const _K2& __k) const {
1460 return __tree_.__count_multi(__k);
1461 }
1462# endif
1463
1464# if _LIBCPP_STD_VER >= 20
1465 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool contains(const key_type& __k) const {
1466 return find(__k) != end();
1467 }
1468 template <typename _K2,
1469 class _Comp = _Compare,
1470 enable_if_t<__is_transparent_v<_Comp> || __is_transparently_comparable_v<_Comp, key_type, _K2>, int> = 0>
1471 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool contains(const _K2& __k) const {
1472 return find(__k) != end();
1473 }
1474# endif // _LIBCPP_STD_VER >= 20
1475
1476 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator lower_bound(const key_type& __k) {
1477 return __tree_.__lower_bound_multi(__k);
1478 }
1479
1480 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator
1481 lower_bound(const key_type& __k) const {
1482 return __tree_.__lower_bound_multi(__k);
1483 }
1484
1485# if _LIBCPP_STD_VER >= 14
1486 template <typename _K2,
1487 class _Comp = _Compare,
1488 enable_if_t<__is_transparent_v<_Comp> || __is_transparently_comparable_v<_Comp, key_type, _K2>, int> = 0>
1489 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator lower_bound(const _K2& __k) {
1490 return __tree_.__lower_bound_multi(__k);
1491 }
1492
1493 template <typename _K2,
1494 class _Comp = _Compare,
1495 enable_if_t<__is_transparent_v<_Comp> || __is_transparently_comparable_v<_Comp, key_type, _K2>, int> = 0>
1496 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator
1497 lower_bound(const _K2& __k) const {
1498 return __tree_.__lower_bound_multi(__k);
1499 }
1500# endif
1501
1502 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator upper_bound(const key_type& __k) {
1503 return __tree_.__upper_bound_multi(__k);
1504 }
1505
1506 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator
1507 upper_bound(const key_type& __k) const {
1508 return __tree_.__upper_bound_multi(__k);
1509 }
1510
1511# if _LIBCPP_STD_VER >= 14
1512 template <typename _K2,
1513 class _Comp = _Compare,
1514 enable_if_t<__is_transparent_v<_Comp> || __is_transparently_comparable_v<_Comp, key_type, _K2>, int> = 0>
1515 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator upper_bound(const _K2& __k) {
1516 return __tree_.__upper_bound_multi(__k);
1517 }
1518 template <typename _K2,
1519 class _Comp = _Compare,
1520 enable_if_t<__is_transparent_v<_Comp> || __is_transparently_comparable_v<_Comp, key_type, _K2>, int> = 0>
1521 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator
1522 upper_bound(const _K2& __k) const {
1523 return __tree_.__upper_bound_multi(__k);
1524 }
1525# endif
1526
1527 [[__nodiscard__]]
1528 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, iterator> equal_range(const key_type& __k) {
1529 return __tree_.__equal_range_multi(__k);
1530 }
1531 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<const_iterator, const_iterator>
1532 equal_range(const key_type& __k) const {
1533 return __tree_.__equal_range_multi(__k);
1534 }
1535# if _LIBCPP_STD_VER >= 14
1536 template <typename _K2, class _Comp = _Compare, enable_if_t<__is_transparent_v<_Comp>, int> = 0>
1537 [[__nodiscard__]]
1538 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, iterator> equal_range(const _K2& __k) {
1539 return __tree_.__equal_range_multi(__k);
1540 }
1541 template <typename _K2, class _Comp = _Compare, enable_if_t<__is_transparent_v<_Comp>, int> = 0>
1542 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<const_iterator, const_iterator>
1543 equal_range(const _K2& __k) const {
1544 return __tree_.__equal_range_multi(__k);
1545 }
1546# endif
1547
1548 template <class, class...>
1549 friend struct __specialized_algorithm;
1550};
1551
1552# if _LIBCPP_STD_VER >= 17
1553template <class _InputIterator,
1554 class _Compare = less<__iterator_value_type<_InputIterator>>,
1555 class _Allocator = allocator<__iterator_value_type<_InputIterator>>,
1556 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1557 class = enable_if_t<__is_allocator_v<_Allocator>>,
1558 class = enable_if_t<!__is_allocator_v<_Compare>>>
1559multiset(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1560 -> multiset<__iterator_value_type<_InputIterator>, _Compare, _Allocator>;
1561
1562# if _LIBCPP_STD_VER >= 23
1563template <ranges::input_range _Range,
1564 class _Compare = less<ranges::range_value_t<_Range>>,
1565 class _Allocator = allocator<ranges::range_value_t<_Range>>,
1566 class = enable_if_t<__is_allocator_v<_Allocator>>,
1567 class = enable_if_t<!__is_allocator_v<_Compare>>>
1568multiset(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
1569 -> multiset<ranges::range_value_t<_Range>, _Compare, _Allocator>;
1570# endif
1571
1572template <class _Key,
1573 class _Compare = less<_Key>,
1574 class _Allocator = allocator<_Key>,
1575 class = enable_if_t<__is_allocator_v<_Allocator>>,
1576 class = enable_if_t<!__is_allocator_v<_Compare>>>
1577multiset(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator())
1578 -> multiset<_Key, _Compare, _Allocator>;
1579
1580template <class _InputIterator,
1581 class _Allocator,
1582 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1583 class = enable_if_t<__is_allocator_v<_Allocator>>>
1584multiset(_InputIterator, _InputIterator, _Allocator)
1585 -> multiset<__iterator_value_type<_InputIterator>, less<__iterator_value_type<_InputIterator>>, _Allocator>;
1586
1587# if _LIBCPP_STD_VER >= 23
1588template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>
1589multiset(from_range_t, _Range&&, _Allocator)
1590 -> multiset<ranges::range_value_t<_Range>, less<ranges::range_value_t<_Range>>, _Allocator>;
1591# endif
1592
1593template <class _Key, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>
1594multiset(initializer_list<_Key>, _Allocator) -> multiset<_Key, less<_Key>, _Allocator>;
1595# endif
1596
1597# if _LIBCPP_STD_VER >= 14
1598template <class _Alg, class _Key, class _Compare, class _Allocator>
1599struct __specialized_algorithm<_Alg, __single_range<multiset<_Key, _Compare, _Allocator>>> {
1600 using __set _LIBCPP_NODEBUG = multiset<_Key, _Compare, _Allocator>;
1601
1602 static const bool __has_algorithm =
1603 __specialized_algorithm<_Alg, __single_range<typename __set::__base>>::__has_algorithm;
1604
1605 // set's begin() and end() are identical with and without const qualification
1606 template <class... _Args>
1607 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto operator()(const __set& __set, _Args&&... __args) {
1608 return __specialized_algorithm<_Alg, __single_range<typename __set::__base>>()(
1609 __set.__tree_, std::forward<_Args>(__args)...);
1610 }
1611};
1612# endif
1613
1614template <class _Key, class _Compare, class _Allocator>
1615inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
1616operator==(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1617 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
1618}
1619
1620# if _LIBCPP_STD_VER <= 17
1621
1622template <class _Key, class _Compare, class _Allocator>
1623inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
1624operator<(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1625 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1626}
1627
1628template <class _Key, class _Compare, class _Allocator>
1629inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
1630operator!=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1631 return !(__x == __y);
1632}
1633
1634template <class _Key, class _Compare, class _Allocator>
1635inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
1636operator>(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1637 return __y < __x;
1638}
1639
1640template <class _Key, class _Compare, class _Allocator>
1641inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
1642operator>=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1643 return !(__x < __y);
1644}
1645
1646template <class _Key, class _Compare, class _Allocator>
1647inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
1648operator<=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1649 return !(__y < __x);
1650}
1651
1652# else // _LIBCPP_STD_VER <= 17
1653
1654template <class _Key, class _Compare, class _Allocator>
1655_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __synth_three_way_result<_Key>
1656operator<=>(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1657 return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), __synth_three_way);
1658}
1659
1660# endif // _LIBCPP_STD_VER <= 17
1661
1662template <class _Key, class _Compare, class _Allocator>
1663inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
1664swap(multiset<_Key, _Compare, _Allocator>& __x, multiset<_Key, _Compare, _Allocator>& __y)
1665 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1666 __x.swap(__y);
1667}
1668
1669# if _LIBCPP_STD_VER >= 20
1670template <class _Key, class _Compare, class _Allocator, class _Predicate>
1671inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 typename multiset<_Key, _Compare, _Allocator>::size_type
1672erase_if(multiset<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {
1673 return std::__libcpp_erase_if_container(__c, __pred);
1674}
1675# endif
1676
1677template <class _Key, class _Compare, class _Allocator>
1678struct __container_traits<multiset<_Key, _Compare, _Allocator> > {
1679 // http://eel.is/c++draft/associative.reqmts.except#2
1680 // For associative containers, if an exception is thrown by any operation from within
1681 // an insert or emplace function inserting a single element, the insertion has no effect.
1682 static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee = true;
1683
1684 static _LIBCPP_CONSTEXPR const bool __reservable = false;
1685};
1686
1687_LIBCPP_END_NAMESPACE_STD
1688
1689# if _LIBCPP_STD_VER >= 17
1690_LIBCPP_BEGIN_NAMESPACE_STD
1691namespace pmr {
1692template <class _KeyT, class _CompareT = std::less<_KeyT>>
1693using set _LIBCPP_AVAILABILITY_PMR = std::set<_KeyT, _CompareT, polymorphic_allocator<_KeyT>>;
1694
1695template <class _KeyT, class _CompareT = std::less<_KeyT>>
1696using multiset _LIBCPP_AVAILABILITY_PMR = std::multiset<_KeyT, _CompareT, polymorphic_allocator<_KeyT>>;
1697} // namespace pmr
1698_LIBCPP_END_NAMESPACE_STD
1699# endif
1700
1701_LIBCPP_POP_MACROS
1702
1703# if defined(_LIBCPP_KEEP_TRANSITIVE_INCLUDES_LLVM23) && _LIBCPP_STD_VER <= 20
1704# include <concepts>
1705# include <cstdlib>
1706# include <functional>
1707# include <iterator>
1708# include <stdexcept>
1709# include <type_traits>
1710# endif
1711#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
1712
1713#endif // _LIBCPP_SET