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