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