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___FLAT_SET_FLAT_SET_H
11#define _LIBCPP___FLAT_SET_FLAT_SET_H
12
13#include <__algorithm/lexicographical_compare_three_way.h>
14#include <__algorithm/lower_bound.h>
15#include <__algorithm/ranges_adjacent_find.h>
16#include <__algorithm/ranges_equal.h>
17#include <__algorithm/ranges_inplace_merge.h>
18#include <__algorithm/ranges_sort.h>
19#include <__algorithm/ranges_unique.h>
20#include <__algorithm/remove_if.h>
21#include <__algorithm/upper_bound.h>
22#include <__assert>
23#include <__compare/synth_three_way.h>
24#include <__concepts/swappable.h>
25#include <__config>
26#include <__flat_map/sorted_unique.h>
27#include <__flat_set/ra_iterator.h>
28#include <__flat_set/utils.h>
29#include <__functional/is_transparent.h>
30#include <__functional/operations.h>
31#include <__fwd/vector.h>
32#include <__iterator/concepts.h>
33#include <__iterator/iterator_traits.h>
34#include <__iterator/next.h>
35#include <__iterator/prev.h>
36#include <__iterator/reverse_iterator.h>
37#include <__memory/allocator_traits.h>
38#include <__memory/uses_allocator.h>
39#include <__memory/uses_allocator_construction.h>
40#include <__ranges/access.h>
41#include <__ranges/concepts.h>
42#include <__ranges/container_compatible_range.h>
43#include <__ranges/drop_view.h>
44#include <__ranges/from_range.h>
45#include <__ranges/size.h>
46#include <__type_traits/container_traits.h>
47#include <__type_traits/invoke.h>
48#include <__type_traits/is_allocator.h>
49#include <__type_traits/is_const.h>
50#include <__type_traits/is_nothrow_constructible.h>
51#include <__type_traits/is_same.h>
52#include <__type_traits/remove_reference.h>
53#include <__utility/as_const.h>
54#include <__utility/exception_guard.h>
55#include <__utility/move.h>
56#include <__utility/pair.h>
57#include <__utility/scope_guard.h>
58#include <__vector/vector.h>
59#include <initializer_list>
60
61#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
62# pragma GCC system_header
63#endif
64
65_LIBCPP_PUSH_MACROS
66#include <__undef_macros>
67
68#if _LIBCPP_STD_VER >= 23
69
70_LIBCPP_BEGIN_NAMESPACE_STD
71
72template <class _Key, class _Compare = less<_Key>, class _KeyContainer = vector<_Key>>
73class flat_set {
74 template <class, class, class>
75 friend class flat_set;
76
77 friend __flat_set_utils;
78
79 static_assert(is_same_v<_Key, typename _KeyContainer::value_type>);
80 static_assert(!is_same_v<_KeyContainer, std::vector<bool>>, "vector<bool> is not a sequence container");
81
82 using __key_iterator _LIBCPP_NODEBUG = typename _KeyContainer::const_iterator;
83
84public:
85 // types
86 using key_type = _Key;
87 using value_type = _Key;
88 using key_compare = __type_identity_t<_Compare>;
89 using value_compare = _Compare;
90 using reference = value_type&;
91 using const_reference = const value_type&;
92 using size_type = typename _KeyContainer::size_type;
93 using difference_type = typename _KeyContainer::difference_type;
94 using iterator = __ra_iterator<flat_set, typename _KeyContainer::const_iterator>;
95 using const_iterator = iterator;
96 using reverse_iterator = std::reverse_iterator<iterator>;
97 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
98 using container_type = _KeyContainer;
99
100public:
101 // [flat.set.cons], construct/copy/destroy
102 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
103 flat_set() noexcept(is_nothrow_default_constructible_v<_KeyContainer> && is_nothrow_default_constructible_v<_Compare>)
104 : __keys_(), __compare_() {}
105
106 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(const flat_set&) = default;
107
108 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(flat_set&& __other) noexcept(
109 is_nothrow_move_constructible_v<_KeyContainer> && is_nothrow_move_constructible_v<_Compare>)
110# if _LIBCPP_HAS_EXCEPTIONS
111 try
112# endif // _LIBCPP_HAS_EXCEPTIONS
113 : __keys_(std::move(__other.__keys_)), __compare_(std::move(__other.__compare_)) {
114 __other.clear();
115# if _LIBCPP_HAS_EXCEPTIONS
116 } catch (...) {
117 __other.clear();
118 // gcc does not like the `throw` keyword in a conditionally noexcept function
119 if constexpr (!(is_nothrow_move_constructible_v<_KeyContainer> && is_nothrow_move_constructible_v<_Compare>)) {
120 throw;
121 }
122# endif // _LIBCPP_HAS_EXCEPTIONS
123 }
124
125 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit flat_set(const key_compare& __comp)
126 : __keys_(), __compare_(__comp) {}
127
128 _LIBCPP_HIDE_FROM_ABI
129 _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit flat_set(container_type __keys, const key_compare& __comp = key_compare())
130 : __keys_(std::move(__keys)), __compare_(__comp) {
131 __sort_and_unique();
132 }
133
134 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
135 flat_set(sorted_unique_t, container_type __keys, const key_compare& __comp = key_compare())
136 : __keys_(std::move(__keys)), __compare_(__comp) {
137 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
138 __is_sorted_and_unique(__keys_), "Either the key container is not sorted or it contains duplicates");
139 }
140
141 template <class _InputIterator>
142 requires __has_input_iterator_category<_InputIterator>::value
143 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
144 flat_set(_InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare())
145 : __keys_(), __compare_(__comp) {
146 insert(__first, __last);
147 }
148
149 template <class _InputIterator>
150 requires __has_input_iterator_category<_InputIterator>::value
151 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
152 flat_set(sorted_unique_t, _InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare())
153 : __keys_(__first, __last), __compare_(__comp) {
154 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
155 __is_sorted_and_unique(__keys_), "Either the key container is not sorted or it contains duplicates");
156 }
157
158 template <_ContainerCompatibleRange<value_type> _Range>
159 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(from_range_t, _Range&& __rg)
160 : flat_set(from_range, std::forward<_Range>(__rg), key_compare()) {}
161
162 template <_ContainerCompatibleRange<value_type> _Range>
163 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(from_range_t, _Range&& __rg, const key_compare& __comp)
164 : flat_set(__comp) {
165 insert_range(std::forward<_Range>(__rg));
166 }
167
168 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
169 flat_set(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
170 : flat_set(__il.begin(), __il.end(), __comp) {}
171
172 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
173 flat_set(sorted_unique_t, initializer_list<value_type> __il, const key_compare& __comp = key_compare())
174 : flat_set(sorted_unique, __il.begin(), __il.end(), __comp) {}
175
176 template <class _Allocator>
177 requires uses_allocator<container_type, _Allocator>::value
178 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit flat_set(const _Allocator& __alloc)
179 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_() {}
180
181 template <class _Allocator>
182 requires uses_allocator<container_type, _Allocator>::value
183 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(const key_compare& __comp, const _Allocator& __alloc)
184 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_(__comp) {}
185
186 template <class _Allocator>
187 requires uses_allocator<container_type, _Allocator>::value
188 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(const container_type& __keys, const _Allocator& __alloc)
189 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __keys)), __compare_() {
190 __sort_and_unique();
191 }
192
193 template <class _Allocator>
194 requires uses_allocator<container_type, _Allocator>::value
195 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
196 flat_set(const container_type& __keys, const key_compare& __comp, const _Allocator& __alloc)
197 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __keys)), __compare_(__comp) {
198 __sort_and_unique();
199 }
200
201 template <class _Allocator>
202 requires uses_allocator<container_type, _Allocator>::value
203 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
204 flat_set(sorted_unique_t, const container_type& __keys, const _Allocator& __alloc)
205 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __keys)), __compare_() {
206 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
207 __is_sorted_and_unique(__keys_), "Either the key container is not sorted or it contains duplicates");
208 }
209
210 template <class _Allocator>
211 requires uses_allocator<container_type, _Allocator>::value
212 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
213 flat_set(sorted_unique_t, const container_type& __keys, const key_compare& __comp, const _Allocator& __alloc)
214 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __keys)), __compare_(__comp) {
215 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
216 __is_sorted_and_unique(__keys_), "Either the key container is not sorted or it contains duplicates");
217 }
218
219 template <class _Allocator>
220 requires uses_allocator<container_type, _Allocator>::value
221 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(const flat_set& __other, const _Allocator& __alloc)
222 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __other.__keys_)),
223 __compare_(__other.__compare_) {}
224
225 template <class _Allocator>
226 requires uses_allocator<container_type, _Allocator>::value
227 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(flat_set&& __other, const _Allocator& __alloc)
228# if _LIBCPP_HAS_EXCEPTIONS
229 try
230# endif // _LIBCPP_HAS_EXCEPTIONS
231 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, std::move(__other.__keys_))),
232 __compare_(std::move(__other.__compare_)) {
233 __other.clear();
234# if _LIBCPP_HAS_EXCEPTIONS
235 } catch (...) {
236 __other.clear();
237 throw;
238# endif // _LIBCPP_HAS_EXCEPTIONS
239 }
240
241 template <class _InputIterator, class _Allocator>
242 requires(__has_input_iterator_category<_InputIterator>::value && uses_allocator<container_type, _Allocator>::value)
243 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
244 flat_set(_InputIterator __first, _InputIterator __last, const _Allocator& __alloc)
245 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_() {
246 insert(__first, __last);
247 }
248
249 template <class _InputIterator, class _Allocator>
250 requires(__has_input_iterator_category<_InputIterator>::value && uses_allocator<container_type, _Allocator>::value)
251 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
252 flat_set(_InputIterator __first, _InputIterator __last, const key_compare& __comp, const _Allocator& __alloc)
253 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_(__comp) {
254 insert(__first, __last);
255 }
256
257 template <class _InputIterator, class _Allocator>
258 requires(__has_input_iterator_category<_InputIterator>::value && uses_allocator<container_type, _Allocator>::value)
259 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
260 flat_set(sorted_unique_t, _InputIterator __first, _InputIterator __last, const _Allocator& __alloc)
261 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __first, __last)), __compare_() {
262 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
263 __is_sorted_and_unique(__keys_), "Either the key container is not sorted or it contains duplicates");
264 }
265
266 template <class _InputIterator, class _Allocator>
267 requires(__has_input_iterator_category<_InputIterator>::value && uses_allocator<container_type, _Allocator>::value)
268 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(
269 sorted_unique_t,
270 _InputIterator __first,
271 _InputIterator __last,
272 const key_compare& __comp,
273 const _Allocator& __alloc)
274 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __first, __last)), __compare_(__comp) {
275 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
276 __is_sorted_and_unique(__keys_), "Either the key container is not sorted or it contains duplicates");
277 }
278
279 template <_ContainerCompatibleRange<value_type> _Range, class _Allocator>
280 requires uses_allocator<container_type, _Allocator>::value
281 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(from_range_t, _Range&& __rg, const _Allocator& __alloc)
282 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_() {
283 insert_range(std::forward<_Range>(__rg));
284 }
285
286 template <_ContainerCompatibleRange<value_type> _Range, class _Allocator>
287 requires uses_allocator<container_type, _Allocator>::value
288 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
289 flat_set(from_range_t, _Range&& __rg, const key_compare& __comp, const _Allocator& __alloc)
290 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_(__comp) {
291 insert_range(std::forward<_Range>(__rg));
292 }
293
294 template <class _Allocator>
295 requires uses_allocator<container_type, _Allocator>::value
296 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
297 flat_set(initializer_list<value_type> __il, const _Allocator& __alloc)
298 : flat_set(__il.begin(), __il.end(), __alloc) {}
299
300 template <class _Allocator>
301 requires uses_allocator<container_type, _Allocator>::value
302 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
303 flat_set(initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc)
304 : flat_set(__il.begin(), __il.end(), __comp, __alloc) {}
305
306 template <class _Allocator>
307 requires uses_allocator<container_type, _Allocator>::value
308 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
309 flat_set(sorted_unique_t, initializer_list<value_type> __il, const _Allocator& __alloc)
310 : flat_set(sorted_unique, __il.begin(), __il.end(), __alloc) {}
311
312 template <class _Allocator>
313 requires uses_allocator<container_type, _Allocator>::value
314 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
315 flat_set(sorted_unique_t, initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc)
316 : flat_set(sorted_unique, __il.begin(), __il.end(), __comp, __alloc) {}
317
318 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set& operator=(initializer_list<value_type> __il) {
319 clear();
320 insert(__il);
321 return *this;
322 }
323
324 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set& operator=(const flat_set&) = default;
325
326 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set& operator=(flat_set&& __other) noexcept(
327 is_nothrow_move_assignable_v<_KeyContainer> && is_nothrow_move_assignable_v<_Compare>) {
328 // No matter what happens, we always want to clear the other container before returning
329 // since we moved from it
330 auto __clear_other_guard = std::__make_scope_guard([&]() noexcept { __other.clear() /* noexcept */; });
331 {
332 // If an exception is thrown, we have no choice but to clear *this to preserve invariants
333 auto __on_exception = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
334 __keys_ = std::move(__other.__keys_);
335 __compare_ = std::move(__other.__compare_);
336 __on_exception.__complete();
337 }
338 return *this;
339 }
340
341 // iterators
342 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator begin() noexcept {
343 return iterator(std::as_const(__keys_).begin());
344 }
345 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator begin() const noexcept {
346 return const_iterator(__keys_.begin());
347 }
348 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator end() noexcept {
349 return iterator(std::as_const(__keys_).end());
350 }
351 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator end() const noexcept {
352 return const_iterator(__keys_.end());
353 }
354
355 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 reverse_iterator rbegin() noexcept {
356 return reverse_iterator(end());
357 }
358 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator rbegin() const noexcept {
359 return const_reverse_iterator(end());
360 }
361 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 reverse_iterator rend() noexcept {
362 return reverse_iterator(begin());
363 }
364 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator rend() const noexcept {
365 return const_reverse_iterator(begin());
366 }
367
368 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator cbegin() const noexcept {
369 return begin();
370 }
371 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator cend() const noexcept {
372 return end();
373 }
374 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator crbegin() const noexcept {
375 return const_reverse_iterator(end());
376 }
377 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator crend() const noexcept {
378 return const_reverse_iterator(begin());
379 }
380
381 // [flat.set.capacity], capacity
382 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool empty() const noexcept {
383 return __keys_.empty();
384 }
385
386 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type size() const noexcept {
387 return __keys_.size();
388 }
389
390 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type max_size() const noexcept {
391 return __keys_.max_size();
392 }
393
394 // [flat.set.modifiers], modifiers
395 template <class... _Args>
396 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> emplace(_Args&&... __args) {
397 if constexpr (sizeof...(__args) == 1 && (is_same_v<remove_cvref_t<_Args>, _Key> && ...)) {
398 return __emplace(std::forward<_Args>(__args)...);
399 } else {
400 return __emplace(_Key(std::forward<_Args>(__args)...));
401 }
402 }
403
404 template <class... _Args>
405 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator emplace_hint(const_iterator __hint, _Args&&... __args) {
406 if constexpr (sizeof...(__args) == 1 && (is_same_v<remove_cvref_t<_Args>, _Key> && ...)) {
407 return __emplace_hint(std::move(__hint), std::forward<_Args>(__args)...);
408 } else {
409 return __emplace_hint(std::move(__hint), _Key(std::forward<_Args>(__args)...));
410 }
411 }
412
413 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> insert(const value_type& __x) {
414 return emplace(__x);
415 }
416
417 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> insert(value_type&& __x) {
418 return emplace(std::move(__x));
419 }
420
421 template <class _Kp>
422 requires(__is_transparent_v<_Compare> && is_constructible_v<value_type, _Kp>)
423 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> insert(_Kp&& __x) {
424 return __emplace(std::forward<_Kp>(__x));
425 }
426 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __hint, const value_type& __x) {
427 return emplace_hint(__hint, __x);
428 }
429
430 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __hint, value_type&& __x) {
431 return emplace_hint(__hint, std::move(__x));
432 }
433
434 template <class _Kp>
435 requires(__is_transparent_v<_Compare> && is_constructible_v<value_type, _Kp>)
436 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __hint, _Kp&& __x) {
437 return __emplace_hint(__hint, std::forward<_Kp>(__x));
438 }
439
440 template <class _InputIterator>
441 requires __has_input_iterator_category<_InputIterator>::value
442 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(_InputIterator __first, _InputIterator __last) {
443 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) {
444 __reserve(__last - __first);
445 }
446 __append_sort_merge_unique</*WasSorted = */ false>(std::move(__first), std::move(__last));
447 }
448
449 template <class _InputIterator>
450 requires __has_input_iterator_category<_InputIterator>::value
451 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
452 insert(sorted_unique_t, _InputIterator __first, _InputIterator __last) {
453 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) {
454 __reserve(__last - __first);
455 }
456
457 __append_sort_merge_unique</*WasSorted = */ true>(std::move(__first), std::move(__last));
458 }
459
460 template <_ContainerCompatibleRange<value_type> _Range>
461 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert_range(_Range&& __range) {
462 if constexpr (ranges::sized_range<_Range>) {
463 __reserve(ranges::size(__range));
464 }
465
466 __append_sort_merge_unique</*WasSorted = */ false>(std::forward<_Range>(__range));
467 }
468
469 template <_ContainerCompatibleRange<value_type> _Range>
470 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert_range(std::sorted_unique_t, _Range&& __range) {
471 if constexpr (ranges::sized_range<_Range>) {
472 __reserve(ranges::size(__range));
473 }
474
475 __append_sort_merge_unique</*WasSorted = */ true>(std::forward<_Range>(__range));
476 }
477
478 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(initializer_list<value_type> __il) {
479 insert(__il.begin(), __il.end());
480 }
481
482 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(sorted_unique_t, initializer_list<value_type> __il) {
483 insert(sorted_unique, __il.begin(), __il.end());
484 }
485
486 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 container_type extract() && {
487 auto __guard = std::__make_scope_guard([&]() noexcept { clear() /* noexcept */; });
488 auto __ret = std::move(__keys_);
489 return __ret;
490 }
491
492 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void replace(container_type&& __keys) {
493 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
494 __is_sorted_and_unique(__keys), "Either the key container is not sorted or it contains duplicates");
495 auto __guard = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
496 __keys_ = std::move(__keys);
497 __guard.__complete();
498 }
499
500 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator erase(iterator __position) {
501 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
502 auto __key_iter = __keys_.erase(__position.__base());
503 __on_failure.__complete();
504 return iterator(__key_iter);
505 }
506
507 // The following overload is the same as the iterator overload
508 // iterator erase(const_iterator __position);
509
510 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type erase(const key_type& __x) {
511 auto __iter = find(__x);
512 if (__iter != end()) {
513 erase(__iter);
514 return 1;
515 }
516 return 0;
517 }
518
519 template <class _Kp>
520 requires(__is_transparent_v<_Compare> && !is_convertible_v<_Kp &&, iterator> &&
521 !is_convertible_v<_Kp &&, const_iterator>)
522 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type erase(_Kp&& __x) {
523 auto [__first, __last] = equal_range(__x);
524 auto __res = __last - __first;
525 erase(__first, __last);
526 return __res;
527 }
528
529 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator erase(const_iterator __first, const_iterator __last) {
530 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
531 auto __key_it = __keys_.erase(__first.__base(), __last.__base());
532 __on_failure.__complete();
533 return iterator(std::move(__key_it));
534 }
535
536 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
537 swap(flat_set& __y) noexcept(is_nothrow_swappable_v<container_type> && is_nothrow_swappable_v<key_compare>) {
538 auto __on_failure = std::__make_exception_guard([&]() noexcept {
539 clear() /* noexcept */;
540 __y.clear() /* noexcept */;
541 });
542 ranges::swap(__compare_, __y.__compare_);
543 ranges::swap(__keys_, __y.__keys_);
544 __on_failure.__complete();
545 }
546
547 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void clear() noexcept { __keys_.clear(); }
548
549 // observers
550 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 key_compare key_comp() const { return __compare_; }
551 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 value_compare value_comp() const {
552 return __compare_;
553 }
554
555 // set operations
556 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator find(const key_type& __x) {
557 return __find_impl(*this, __x);
558 }
559
560 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator find(const key_type& __x) const {
561 return __find_impl(*this, __x);
562 }
563
564 template <class _Kp>
565 requires __is_transparent_v<_Compare>
566 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator find(const _Kp& __x) {
567 return __find_impl(*this, __x);
568 }
569
570 template <class _Kp>
571 requires __is_transparent_v<_Compare>
572 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator find(const _Kp& __x) const {
573 return __find_impl(*this, __x);
574 }
575
576 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type count(const key_type& __x) const {
577 return contains(__x) ? 1 : 0;
578 }
579
580 template <class _Kp>
581 requires __is_transparent_v<_Compare>
582 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type count(const _Kp& __x) const {
583 return contains(__x) ? 1 : 0;
584 }
585
586 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool contains(const key_type& __x) const {
587 return find(__x) != end();
588 }
589
590 template <class _Kp>
591 requires __is_transparent_v<_Compare>
592 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool contains(const _Kp& __x) const {
593 return find(__x) != end();
594 }
595
596 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator lower_bound(const key_type& __x) {
597 const auto& __keys = __keys_;
598 return iterator(std::lower_bound(__keys.begin(), __keys.end(), __x, __compare_));
599 }
600
601 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator
602 lower_bound(const key_type& __x) const {
603 return const_iterator(std::lower_bound(__keys_.begin(), __keys_.end(), __x, __compare_));
604 }
605
606 template <class _Kp>
607 requires __is_transparent_v<_Compare>
608 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator lower_bound(const _Kp& __x) {
609 const auto& __keys = __keys_;
610 return iterator(std::lower_bound(__keys.begin(), __keys.end(), __x, __compare_));
611 }
612
613 template <class _Kp>
614 requires __is_transparent_v<_Compare>
615 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator lower_bound(const _Kp& __x) const {
616 return const_iterator(std::lower_bound(__keys_.begin(), __keys_.end(), __x, __compare_));
617 }
618
619 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator upper_bound(const key_type& __x) {
620 const auto& __keys = __keys_;
621 return iterator(std::upper_bound(__keys.begin(), __keys.end(), __x, __compare_));
622 }
623
624 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator
625 upper_bound(const key_type& __x) const {
626 return const_iterator(std::upper_bound(__keys_.begin(), __keys_.end(), __x, __compare_));
627 }
628
629 template <class _Kp>
630 requires __is_transparent_v<_Compare>
631 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator upper_bound(const _Kp& __x) {
632 const auto& __keys = __keys_;
633 return iterator(std::upper_bound(__keys.begin(), __keys.end(), __x, __compare_));
634 }
635
636 template <class _Kp>
637 requires __is_transparent_v<_Compare>
638 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator upper_bound(const _Kp& __x) const {
639 return const_iterator(std::upper_bound(__keys_.begin(), __keys_.end(), __x, __compare_));
640 }
641
642 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, iterator>
643 equal_range(const key_type& __x) {
644 return __equal_range_impl(*this, __x);
645 }
646
647 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<const_iterator, const_iterator>
648 equal_range(const key_type& __x) const {
649 return __equal_range_impl(*this, __x);
650 }
651
652 template <class _Kp>
653 requires __is_transparent_v<_Compare>
654 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, iterator>
655 equal_range(const _Kp& __x) {
656 return __equal_range_impl(*this, __x);
657 }
658 template <class _Kp>
659 requires __is_transparent_v<_Compare>
660 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<const_iterator, const_iterator>
661 equal_range(const _Kp& __x) const {
662 return __equal_range_impl(*this, __x);
663 }
664
665 friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool operator==(const flat_set& __x, const flat_set& __y) {
666 return ranges::equal(__x, __y);
667 }
668
669 friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 auto
670 operator<=>(const flat_set& __x, const flat_set& __y) {
671 return std::lexicographical_compare_three_way(
672 __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
673 }
674
675 friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
676 swap(flat_set& __x, flat_set& __y) noexcept(noexcept(__x.swap(__y))) {
677 __x.swap(__y);
678 }
679
680private:
681 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool __is_sorted_and_unique(auto&& __key_container) const {
682 auto __greater_or_equal_to = [this](const auto& __x, const auto& __y) -> bool { return !__compare_(__x, __y); };
683 return ranges::adjacent_find(__key_container, __greater_or_equal_to) == ranges::end(__key_container);
684 }
685
686 // This function is only used in constructors. So there is not exception handling in this function.
687 // If the function exits via an exception, there will be no flat_set object constructed, thus, there
688 // is no invariant state to preserve
689 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __sort_and_unique() {
690 ranges::sort(__keys_, __compare_);
691 auto __dup_start = ranges::unique(__keys_, __key_equiv(__compare_)).begin();
692 __keys_.erase(__dup_start, __keys_.end());
693 }
694
695 template <bool _WasSorted, class... _Args>
696 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __append_sort_merge_unique(_Args&&... __args) {
697 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
698 size_type __old_size = size();
699 __flat_set_utils::__append(*this, std::forward<_Args>(__args)...);
700 if (size() != __old_size) {
701 if constexpr (!_WasSorted) {
702 ranges::sort(__keys_.begin() + __old_size, __keys_.end(), __compare_);
703 } else {
704 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(__is_sorted_and_unique(__keys_ | ranges::views::drop(__old_size)),
705 "Either the key container is not sorted or it contains duplicates");
706 }
707 ranges::inplace_merge(__keys_.begin(), __keys_.begin() + __old_size, __keys_.end(), __compare_);
708
709 auto __dup_start = ranges::unique(__keys_, __key_equiv(__compare_)).begin();
710 __keys_.erase(__dup_start, __keys_.end());
711 }
712 __on_failure.__complete();
713 }
714
715 template <class _Self, class _Kp>
716 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto __find_impl(_Self&& __self, const _Kp& __key) {
717 auto __it = __self.lower_bound(__key);
718 auto __last = __self.end();
719 if (__it == __last || __self.__compare_(__key, *__it)) {
720 return __last;
721 }
722 return __it;
723 }
724
725 template <class _Self, class _Kp>
726 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto __equal_range_impl(_Self&& __self, const _Kp& __key) {
727 using __iter = _If<is_const_v<__libcpp_remove_reference_t<_Self>>, const_iterator, iterator>;
728 auto __it = std::lower_bound(__self.__keys_.begin(), __self.__keys_.end(), __key, __self.__compare_);
729 auto __last = __self.__keys_.end();
730 if (__it == __last || __self.__compare_(__key, *__it)) {
731 return std::make_pair(__iter(__it), __iter(__it));
732 }
733 return std::make_pair(__iter(__it), __iter(std::next(__it)));
734 }
735
736 template <class _Kp>
737 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> __emplace(_Kp&& __key) {
738 auto __it = lower_bound(__key);
739 if (__it == end() || __compare_(__key, *__it)) {
740 return pair<iterator, bool>(__flat_set_utils::__emplace_exact_pos(*this, __it, std::forward<_Kp>(__key)), true);
741 } else {
742 return pair<iterator, bool>(std::move(__it), false);
743 }
744 }
745
746 template <class _Kp>
747 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool __is_hint_correct(const_iterator __hint, _Kp&& __key) {
748 if (__hint != cbegin() && !__compare_(*std::prev(__hint), __key)) {
749 return false;
750 }
751 if (__hint != cend() && __compare_(*__hint, __key)) {
752 return false;
753 }
754 return true;
755 }
756
757 template <class _Kp>
758 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator __emplace_hint(const_iterator __hint, _Kp&& __key) {
759 if (__is_hint_correct(__hint, __key)) {
760 if (__hint == cend() || __compare_(__key, *__hint)) {
761 return __flat_set_utils::__emplace_exact_pos(*this, __hint, std::forward<_Kp>(__key));
762 } else {
763 // we already have an equal key
764 return __hint;
765 }
766 } else {
767 return __emplace(std::forward<_Kp>(__key)).first;
768 }
769 }
770
771 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __reserve(size_t __size) {
772 if constexpr (__container_traits<_KeyContainer>::__reservable) {
773 __keys_.reserve(__size);
774 }
775 }
776
777 template <class _Key2, class _Compare2, class _KeyContainer2, class _Predicate>
778 friend typename flat_set<_Key2, _Compare2, _KeyContainer2>::size_type _LIBCPP_CONSTEXPR_SINCE_CXX26
779 erase_if(flat_set<_Key2, _Compare2, _KeyContainer2>&, _Predicate);
780
781 _KeyContainer __keys_;
782 _LIBCPP_NO_UNIQUE_ADDRESS key_compare __compare_;
783
784 struct __key_equiv {
785 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_equiv(key_compare __c) : __comp_(__c) {}
786 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
787 operator()(const_reference __x, const_reference __y) const {
788 return !__comp_(__x, __y) && !__comp_(__y, __x);
789 }
790 key_compare __comp_;
791 };
792};
793
794template <class _KeyContainer, class _Compare = less<typename _KeyContainer::value_type>>
795 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> &&
796 is_invocable_v<const _Compare&,
797 const typename _KeyContainer::value_type&,
798 const typename _KeyContainer::value_type&>)
799flat_set(_KeyContainer, _Compare = _Compare()) -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
800
801template <class _KeyContainer, class _Allocator>
802 requires(uses_allocator_v<_KeyContainer, _Allocator> && !__is_allocator_v<_KeyContainer>)
803flat_set(_KeyContainer, _Allocator)
804 -> flat_set<typename _KeyContainer::value_type, less<typename _KeyContainer::value_type>, _KeyContainer>;
805
806template <class _KeyContainer, class _Compare, class _Allocator>
807 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> &&
808 uses_allocator_v<_KeyContainer, _Allocator> &&
809 is_invocable_v<const _Compare&,
810 const typename _KeyContainer::value_type&,
811 const typename _KeyContainer::value_type&>)
812flat_set(_KeyContainer, _Compare, _Allocator) -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
813
814template <class _KeyContainer, class _Compare = less<typename _KeyContainer::value_type>>
815 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> &&
816 is_invocable_v<const _Compare&,
817 const typename _KeyContainer::value_type&,
818 const typename _KeyContainer::value_type&>)
819flat_set(sorted_unique_t, _KeyContainer, _Compare = _Compare())
820 -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
821
822template <class _KeyContainer, class _Allocator>
823 requires(uses_allocator_v<_KeyContainer, _Allocator> && !__is_allocator_v<_KeyContainer>)
824flat_set(sorted_unique_t, _KeyContainer, _Allocator)
825 -> flat_set<typename _KeyContainer::value_type, less<typename _KeyContainer::value_type>, _KeyContainer>;
826
827template <class _KeyContainer, class _Compare, class _Allocator>
828 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> &&
829 uses_allocator_v<_KeyContainer, _Allocator> &&
830 is_invocable_v<const _Compare&,
831 const typename _KeyContainer::value_type&,
832 const typename _KeyContainer::value_type&>)
833flat_set(sorted_unique_t, _KeyContainer, _Compare, _Allocator)
834 -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
835
836template <class _InputIterator, class _Compare = less<__iterator_value_type<_InputIterator>>>
837 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator_v<_Compare>)
838flat_set(_InputIterator, _InputIterator, _Compare = _Compare())
839 -> flat_set<__iterator_value_type<_InputIterator>, _Compare>;
840
841template <class _InputIterator, class _Compare = less<__iterator_value_type<_InputIterator>>>
842 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator_v<_Compare>)
843flat_set(sorted_unique_t, _InputIterator, _InputIterator, _Compare = _Compare())
844 -> flat_set<__iterator_value_type<_InputIterator>, _Compare>;
845
846template <ranges::input_range _Range,
847 class _Compare = less<ranges::range_value_t<_Range>>,
848 class _Allocator = allocator<ranges::range_value_t<_Range>>,
849 class = __enable_if_t<!__is_allocator_v<_Compare> && __is_allocator_v<_Allocator>>>
850flat_set(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator()) -> flat_set<
851 ranges::range_value_t<_Range>,
852 _Compare,
853 vector<ranges::range_value_t<_Range>, __allocator_traits_rebind_t<_Allocator, ranges::range_value_t<_Range>>>>;
854
855template <ranges::input_range _Range, class _Allocator, class = __enable_if_t<__is_allocator_v<_Allocator>>>
856flat_set(from_range_t, _Range&&, _Allocator) -> flat_set<
857 ranges::range_value_t<_Range>,
858 less<ranges::range_value_t<_Range>>,
859 vector<ranges::range_value_t<_Range>, __allocator_traits_rebind_t<_Allocator, ranges::range_value_t<_Range>>>>;
860
861template <class _Key, class _Compare = less<_Key>>
862 requires(!__is_allocator_v<_Compare>)
863flat_set(initializer_list<_Key>, _Compare = _Compare()) -> flat_set<_Key, _Compare>;
864
865template <class _Key, class _Compare = less<_Key>>
866 requires(!__is_allocator_v<_Compare>)
867flat_set(sorted_unique_t, initializer_list<_Key>, _Compare = _Compare()) -> flat_set<_Key, _Compare>;
868
869template <class _Key, class _Compare, class _KeyContainer, class _Allocator>
870struct uses_allocator<flat_set<_Key, _Compare, _KeyContainer>, _Allocator>
871 : bool_constant<uses_allocator_v<_KeyContainer, _Allocator>> {};
872
873template <class _Key, class _Compare, class _KeyContainer, class _Predicate>
874_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 typename flat_set<_Key, _Compare, _KeyContainer>::size_type
875erase_if(flat_set<_Key, _Compare, _KeyContainer>& __flat_set, _Predicate __pred) {
876 auto __guard = std::__make_exception_guard([&] { __flat_set.clear(); });
877 auto __it = std::remove_if(__flat_set.__keys_.begin(), __flat_set.__keys_.end(), [&](const auto& __e) -> bool {
878 return static_cast<bool>(__pred(__e));
879 });
880 auto __res = __flat_set.__keys_.end() - __it;
881 __flat_set.__keys_.erase(__it, __flat_set.__keys_.end());
882 __guard.__complete();
883 return __res;
884}
885
886_LIBCPP_END_NAMESPACE_STD
887
888#endif // _LIBCPP_STD_VER >= 23
889
890_LIBCPP_POP_MACROS
891
892#endif // _LIBCPP___FLAT_SET_FLAT_SET_H