Warning: This file is not a C or C++ file. It does not have highlighting.

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
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 flat_set(const flat_set&) = default;
115
116 _LIBCPP_HIDE_FROM_ABI 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 explicit flat_set(const key_compare& __comp) : __keys_(), __compare_(__comp) {}
134
135 _LIBCPP_HIDE_FROM_ABI explicit flat_set(container_type __keys, const key_compare& __comp = key_compare())
136 : __keys_(std::move(__keys)), __compare_(__comp) {
137 __sort_and_unique();
138 }
139
140 _LIBCPP_HIDE_FROM_ABI flat_set(sorted_unique_t, container_type __keys, const key_compare& __comp = key_compare())
141 : __keys_(std::move(__keys)), __compare_(__comp) {
142 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
143 __is_sorted_and_unique(__keys_), "Either the key container is not sorted or it contains duplicates");
144 }
145
146 template <class _InputIterator>
147 requires __has_input_iterator_category<_InputIterator>::value
148 _LIBCPP_HIDE_FROM_ABI
149 flat_set(_InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare())
150 : __keys_(), __compare_(__comp) {
151 insert(__first, __last);
152 }
153
154 template <class _InputIterator>
155 requires __has_input_iterator_category<_InputIterator>::value
156 _LIBCPP_HIDE_FROM_ABI
157 flat_set(sorted_unique_t, _InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare())
158 : __keys_(__first, __last), __compare_(__comp) {
159 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
160 __is_sorted_and_unique(__keys_), "Either the key container is not sorted or it contains duplicates");
161 }
162
163 template <_ContainerCompatibleRange<value_type> _Range>
164 _LIBCPP_HIDE_FROM_ABI flat_set(from_range_t, _Range&& __rg)
165 : flat_set(from_range, std::forward<_Range>(__rg), key_compare()) {}
166
167 template <_ContainerCompatibleRange<value_type> _Range>
168 _LIBCPP_HIDE_FROM_ABI flat_set(from_range_t, _Range&& __rg, const key_compare& __comp) : flat_set(__comp) {
169 insert_range(std::forward<_Range>(__rg));
170 }
171
172 _LIBCPP_HIDE_FROM_ABI flat_set(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
173 : flat_set(__il.begin(), __il.end(), __comp) {}
174
175 _LIBCPP_HIDE_FROM_ABI
176 flat_set(sorted_unique_t, initializer_list<value_type> __il, const key_compare& __comp = key_compare())
177 : flat_set(sorted_unique, __il.begin(), __il.end(), __comp) {}
178
179 template <class _Allocator>
180 requires uses_allocator<container_type, _Allocator>::value
181 _LIBCPP_HIDE_FROM_ABI explicit flat_set(const _Allocator& __alloc)
182 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_() {}
183
184 template <class _Allocator>
185 requires uses_allocator<container_type, _Allocator>::value
186 _LIBCPP_HIDE_FROM_ABI flat_set(const key_compare& __comp, const _Allocator& __alloc)
187 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_(__comp) {}
188
189 template <class _Allocator>
190 requires uses_allocator<container_type, _Allocator>::value
191 _LIBCPP_HIDE_FROM_ABI flat_set(const container_type& __keys, const _Allocator& __alloc)
192 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __keys)), __compare_() {
193 __sort_and_unique();
194 }
195
196 template <class _Allocator>
197 requires uses_allocator<container_type, _Allocator>::value
198 _LIBCPP_HIDE_FROM_ABI flat_set(const container_type& __keys, const key_compare& __comp, const _Allocator& __alloc)
199 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __keys)), __compare_(__comp) {
200 __sort_and_unique();
201 }
202
203 template <class _Allocator>
204 requires uses_allocator<container_type, _Allocator>::value
205 _LIBCPP_HIDE_FROM_ABI flat_set(sorted_unique_t, const container_type& __keys, const _Allocator& __alloc)
206 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __keys)), __compare_() {
207 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
208 __is_sorted_and_unique(__keys_), "Either the key container is not sorted or it contains duplicates");
209 }
210
211 template <class _Allocator>
212 requires uses_allocator<container_type, _Allocator>::value
213 _LIBCPP_HIDE_FROM_ABI
214 flat_set(sorted_unique_t, const container_type& __keys, const key_compare& __comp, const _Allocator& __alloc)
215 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __keys)), __compare_(__comp) {
216 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
217 __is_sorted_and_unique(__keys_), "Either the key container is not sorted or it contains duplicates");
218 }
219
220 template <class _Allocator>
221 requires uses_allocator<container_type, _Allocator>::value
222 _LIBCPP_HIDE_FROM_ABI flat_set(const flat_set& __other, const _Allocator& __alloc)
223 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __other.__keys_)),
224 __compare_(__other.__compare_) {}
225
226 template <class _Allocator>
227 requires uses_allocator<container_type, _Allocator>::value
228 _LIBCPP_HIDE_FROM_ABI flat_set(flat_set&& __other, const _Allocator& __alloc)
229# if _LIBCPP_HAS_EXCEPTIONS
230 try
231# endif // _LIBCPP_HAS_EXCEPTIONS
232 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, std::move(__other.__keys_))),
233 __compare_(std::move(__other.__compare_)) {
234 __other.clear();
235# if _LIBCPP_HAS_EXCEPTIONS
236 } catch (...) {
237 __other.clear();
238 throw;
239# endif // _LIBCPP_HAS_EXCEPTIONS
240 }
241
242 template <class _InputIterator, class _Allocator>
243 requires(__has_input_iterator_category<_InputIterator>::value && uses_allocator<container_type, _Allocator>::value)
244 _LIBCPP_HIDE_FROM_ABI 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
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
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
269 flat_set(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 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 flat_set(from_range_t, _Range&& __rg, const key_compare& __comp, const _Allocator& __alloc)
289 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_(__comp) {
290 insert_range(std::forward<_Range>(__rg));
291 }
292
293 template <class _Allocator>
294 requires uses_allocator<container_type, _Allocator>::value
295 _LIBCPP_HIDE_FROM_ABI flat_set(initializer_list<value_type> __il, const _Allocator& __alloc)
296 : flat_set(__il.begin(), __il.end(), __alloc) {}
297
298 template <class _Allocator>
299 requires uses_allocator<container_type, _Allocator>::value
300 _LIBCPP_HIDE_FROM_ABI
301 flat_set(initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc)
302 : flat_set(__il.begin(), __il.end(), __comp, __alloc) {}
303
304 template <class _Allocator>
305 requires uses_allocator<container_type, _Allocator>::value
306 _LIBCPP_HIDE_FROM_ABI flat_set(sorted_unique_t, initializer_list<value_type> __il, const _Allocator& __alloc)
307 : flat_set(sorted_unique, __il.begin(), __il.end(), __alloc) {}
308
309 template <class _Allocator>
310 requires uses_allocator<container_type, _Allocator>::value
311 _LIBCPP_HIDE_FROM_ABI
312 flat_set(sorted_unique_t, initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc)
313 : flat_set(sorted_unique, __il.begin(), __il.end(), __comp, __alloc) {}
314
315 _LIBCPP_HIDE_FROM_ABI flat_set& operator=(initializer_list<value_type> __il) {
316 clear();
317 insert(__il);
318 return *this;
319 }
320
321 _LIBCPP_HIDE_FROM_ABI flat_set& operator=(const flat_set&) = default;
322
323 _LIBCPP_HIDE_FROM_ABI flat_set& operator=(flat_set&& __other) noexcept(
324 is_nothrow_move_assignable_v<_KeyContainer> && is_nothrow_move_assignable_v<_Compare>) {
325 // No matter what happens, we always want to clear the other container before returning
326 // since we moved from it
327 auto __clear_other_guard = std::__make_scope_guard([&]() noexcept { __other.clear() /* noexcept */; });
328 {
329 // If an exception is thrown, we have no choice but to clear *this to preserve invariants
330 auto __on_exception = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
331 __keys_ = std::move(__other.__keys_);
332 __compare_ = std::move(__other.__compare_);
333 __on_exception.__complete();
334 }
335 return *this;
336 }
337
338 // iterators
339 _LIBCPP_HIDE_FROM_ABI iterator begin() noexcept { return iterator(std::as_const(__keys_).begin()); }
340 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const noexcept { return const_iterator(__keys_.begin()); }
341 _LIBCPP_HIDE_FROM_ABI iterator end() noexcept { return iterator(std::as_const(__keys_).end()); }
342 _LIBCPP_HIDE_FROM_ABI const_iterator end() const noexcept { return const_iterator(__keys_.end()); }
343
344 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
345 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }
346 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
347 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }
348
349 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const noexcept { return begin(); }
350 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const noexcept { return end(); }
351 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(end()); }
352 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const noexcept { return const_reverse_iterator(begin()); }
353
354 // [flat.set.capacity], capacity
355 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI bool empty() const noexcept { return __keys_.empty(); }
356
357 _LIBCPP_HIDE_FROM_ABI size_type size() const noexcept { return __keys_.size(); }
358
359 _LIBCPP_HIDE_FROM_ABI size_type max_size() const noexcept { return __keys_.max_size(); }
360
361 // [flat.set.modifiers], modifiers
362 template <class... _Args>
363 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {
364 if constexpr (sizeof...(__args) == 1 && (is_same_v<remove_cvref_t<_Args>, _Key> && ...)) {
365 return __emplace(std::forward<_Args>(__args)...);
366 } else {
367 return __emplace(_Key(std::forward<_Args>(__args)...));
368 }
369 }
370
371 template <class... _Args>
372 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __hint, _Args&&... __args) {
373 if constexpr (sizeof...(__args) == 1 && (is_same_v<remove_cvref_t<_Args>, _Key> && ...)) {
374 return __emplace_hint(std::move(__hint), std::forward<_Args>(__args)...);
375 } else {
376 return __emplace_hint(std::move(__hint), _Key(std::forward<_Args>(__args)...));
377 }
378 }
379
380 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return emplace(__x); }
381
382 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __x) { return emplace(std::move(__x)); }
383
384 template <class _Kp>
385 requires(__is_transparent_v<_Compare> && is_constructible_v<value_type, _Kp>)
386 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(_Kp&& __x) {
387 return __emplace(std::forward<_Kp>(__x));
388 }
389 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, const value_type& __x) {
390 return emplace_hint(__hint, __x);
391 }
392
393 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, value_type&& __x) {
394 return emplace_hint(__hint, std::move(__x));
395 }
396
397 template <class _Kp>
398 requires(__is_transparent_v<_Compare> && is_constructible_v<value_type, _Kp>)
399 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, _Kp&& __x) {
400 return __emplace_hint(__hint, std::forward<_Kp>(__x));
401 }
402
403 template <class _InputIterator>
404 requires __has_input_iterator_category<_InputIterator>::value
405 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last) {
406 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) {
407 __reserve(__last - __first);
408 }
409 __append_sort_merge_unique</*WasSorted = */ false>(std::move(__first), std::move(__last));
410 }
411
412 template <class _InputIterator>
413 requires __has_input_iterator_category<_InputIterator>::value
414 _LIBCPP_HIDE_FROM_ABI void insert(sorted_unique_t, _InputIterator __first, _InputIterator __last) {
415 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) {
416 __reserve(__last - __first);
417 }
418
419 __append_sort_merge_unique</*WasSorted = */ true>(std::move(__first), std::move(__last));
420 }
421
422 template <_ContainerCompatibleRange<value_type> _Range>
423 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
424 if constexpr (ranges::sized_range<_Range>) {
425 __reserve(ranges::size(__range));
426 }
427
428 __append_sort_merge_unique</*WasSorted = */ false>(std::forward<_Range>(__range));
429 }
430
431 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
432
433 _LIBCPP_HIDE_FROM_ABI void insert(sorted_unique_t, initializer_list<value_type> __il) {
434 insert(sorted_unique, __il.begin(), __il.end());
435 }
436
437 _LIBCPP_HIDE_FROM_ABI container_type extract() && {
438 auto __guard = std::__make_scope_guard([&]() noexcept { clear() /* noexcept */; });
439 auto __ret = std::move(__keys_);
440 return __ret;
441 }
442
443 _LIBCPP_HIDE_FROM_ABI void replace(container_type&& __keys) {
444 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
445 __is_sorted_and_unique(__keys), "Either the key container is not sorted or it contains duplicates");
446 auto __guard = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
447 __keys_ = std::move(__keys);
448 __guard.__complete();
449 }
450
451 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __position) {
452 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
453 auto __key_iter = __keys_.erase(__position.__base());
454 __on_failure.__complete();
455 return iterator(__key_iter);
456 }
457
458 // The following overload is the same as the iterator overload
459 // iterator erase(const_iterator __position);
460
461 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __x) {
462 auto __iter = find(__x);
463 if (__iter != end()) {
464 erase(__iter);
465 return 1;
466 }
467 return 0;
468 }
469
470 template <class _Kp>
471 requires(__is_transparent_v<_Compare> && !is_convertible_v<_Kp &&, iterator> &&
472 !is_convertible_v<_Kp &&, const_iterator>)
473 _LIBCPP_HIDE_FROM_ABI size_type erase(_Kp&& __x) {
474 auto [__first, __last] = equal_range(__x);
475 auto __res = __last - __first;
476 erase(__first, __last);
477 return __res;
478 }
479
480 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
481 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
482 auto __key_it = __keys_.erase(__first.__base(), __last.__base());
483 __on_failure.__complete();
484 return iterator(std::move(__key_it));
485 }
486
487 _LIBCPP_HIDE_FROM_ABI void swap(flat_set& __y) noexcept {
488 // warning: The spec has unconditional noexcept, which means that
489 // if any of the following functions throw an exception,
490 // std::terminate will be called.
491 // This is discussed in P2767, which hasn't been voted on yet.
492 ranges::swap(__compare_, __y.__compare_);
493 ranges::swap(__keys_, __y.__keys_);
494 }
495
496 _LIBCPP_HIDE_FROM_ABI void clear() noexcept { __keys_.clear(); }
497
498 // observers
499 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __compare_; }
500 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return __compare_; }
501
502 // set operations
503 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __x) { return __find_impl(*this, __x); }
504
505 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __x) const { return __find_impl(*this, __x); }
506
507 template <class _Kp>
508 requires __is_transparent_v<_Compare>
509 _LIBCPP_HIDE_FROM_ABI iterator find(const _Kp& __x) {
510 return __find_impl(*this, __x);
511 }
512
513 template <class _Kp>
514 requires __is_transparent_v<_Compare>
515 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _Kp& __x) const {
516 return __find_impl(*this, __x);
517 }
518
519 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __x) const { return contains(__x) ? 1 : 0; }
520
521 template <class _Kp>
522 requires __is_transparent_v<_Compare>
523 _LIBCPP_HIDE_FROM_ABI size_type count(const _Kp& __x) const {
524 return contains(__x) ? 1 : 0;
525 }
526
527 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __x) const { return find(__x) != end(); }
528
529 template <class _Kp>
530 requires __is_transparent_v<_Compare>
531 _LIBCPP_HIDE_FROM_ABI bool contains(const _Kp& __x) const {
532 return find(__x) != end();
533 }
534
535 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __x) {
536 const auto& __keys = __keys_;
537 return iterator(std::lower_bound(__keys.begin(), __keys.end(), __x, __compare_));
538 }
539
540 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __x) const {
541 return const_iterator(std::lower_bound(__keys_.begin(), __keys_.end(), __x, __compare_));
542 }
543
544 template <class _Kp>
545 requires __is_transparent_v<_Compare>
546 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _Kp& __x) {
547 const auto& __keys = __keys_;
548 return iterator(std::lower_bound(__keys.begin(), __keys.end(), __x, __compare_));
549 }
550
551 template <class _Kp>
552 requires __is_transparent_v<_Compare>
553 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _Kp& __x) const {
554 return const_iterator(std::lower_bound(__keys_.begin(), __keys_.end(), __x, __compare_));
555 }
556
557 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __x) {
558 const auto& __keys = __keys_;
559 return iterator(std::upper_bound(__keys.begin(), __keys.end(), __x, __compare_));
560 }
561
562 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __x) const {
563 return const_iterator(std::upper_bound(__keys_.begin(), __keys_.end(), __x, __compare_));
564 }
565
566 template <class _Kp>
567 requires __is_transparent_v<_Compare>
568 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _Kp& __x) {
569 const auto& __keys = __keys_;
570 return iterator(std::upper_bound(__keys.begin(), __keys.end(), __x, __compare_));
571 }
572
573 template <class _Kp>
574 requires __is_transparent_v<_Compare>
575 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _Kp& __x) const {
576 return const_iterator(std::upper_bound(__keys_.begin(), __keys_.end(), __x, __compare_));
577 }
578
579 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __x) {
580 return __equal_range_impl(*this, __x);
581 }
582
583 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __x) const {
584 return __equal_range_impl(*this, __x);
585 }
586
587 template <class _Kp>
588 requires __is_transparent_v<_Compare>
589 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _Kp& __x) {
590 return __equal_range_impl(*this, __x);
591 }
592 template <class _Kp>
593 requires __is_transparent_v<_Compare>
594 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _Kp& __x) const {
595 return __equal_range_impl(*this, __x);
596 }
597
598 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const flat_set& __x, const flat_set& __y) {
599 return ranges::equal(__x, __y);
600 }
601
602 friend _LIBCPP_HIDE_FROM_ABI auto operator<=>(const flat_set& __x, const flat_set& __y) {
603 return std::lexicographical_compare_three_way(
604 __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
605 }
606
607 friend _LIBCPP_HIDE_FROM_ABI void swap(flat_set& __x, flat_set& __y) noexcept { __x.swap(__y); }
608
609private:
610 _LIBCPP_HIDE_FROM_ABI bool __is_sorted_and_unique(auto&& __key_container) const {
611 auto __greater_or_equal_to = [this](const auto& __x, const auto& __y) { return !__compare_(__x, __y); };
612 return ranges::adjacent_find(__key_container, __greater_or_equal_to) == ranges::end(__key_container);
613 }
614
615 // This function is only used in constructors. So there is not exception handling in this function.
616 // If the function exits via an exception, there will be no flat_set object constructed, thus, there
617 // is no invariant state to preserve
618 _LIBCPP_HIDE_FROM_ABI void __sort_and_unique() {
619 ranges::sort(__keys_, __compare_);
620 auto __dup_start = ranges::unique(__keys_, __key_equiv(__compare_)).begin();
621 __keys_.erase(__dup_start, __keys_.end());
622 }
623
624 template <bool _WasSorted, class... _Args>
625 _LIBCPP_HIDE_FROM_ABI void __append_sort_merge_unique(_Args&&... __args) {
626 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
627 size_type __old_size = size();
628 __flat_set_utils::__append(*this, std::forward<_Args>(__args)...);
629 if (size() != __old_size) {
630 if constexpr (!_WasSorted) {
631 ranges::sort(__keys_.begin() + __old_size, __keys_.end(), __compare_);
632 } else {
633 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(__is_sorted_and_unique(__keys_ | ranges::views::drop(__old_size)),
634 "Either the key container is not sorted or it contains duplicates");
635 }
636 ranges::inplace_merge(__keys_.begin(), __keys_.begin() + __old_size, __keys_.end(), __compare_);
637
638 auto __dup_start = ranges::unique(__keys_, __key_equiv(__compare_)).begin();
639 __keys_.erase(__dup_start, __keys_.end());
640 }
641 __on_failure.__complete();
642 }
643
644 template <class _Self, class _Kp>
645 _LIBCPP_HIDE_FROM_ABI static auto __find_impl(_Self&& __self, const _Kp& __key) {
646 auto __it = __self.lower_bound(__key);
647 auto __last = __self.end();
648 if (__it == __last || __self.__compare_(__key, *__it)) {
649 return __last;
650 }
651 return __it;
652 }
653
654 template <class _Self, class _Kp>
655 _LIBCPP_HIDE_FROM_ABI static auto __equal_range_impl(_Self&& __self, const _Kp& __key) {
656 using __iter = _If<is_const_v<__libcpp_remove_reference_t<_Self>>, const_iterator, iterator>;
657 auto __it = std::lower_bound(__self.__keys_.begin(), __self.__keys_.end(), __key, __self.__compare_);
658 auto __last = __self.__keys_.end();
659 if (__it == __last || __self.__compare_(__key, *__it)) {
660 return std::make_pair(__iter(__it), __iter(__it));
661 }
662 return std::make_pair(__iter(__it), __iter(std::next(__it)));
663 }
664
665 template <class _Kp>
666 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace(_Kp&& __key) {
667 auto __it = lower_bound(__key);
668 if (__it == end() || __compare_(__key, *__it)) {
669 return pair<iterator, bool>(__flat_set_utils::__emplace_exact_pos(*this, __it, std::forward<_Kp>(__key)), true);
670 } else {
671 return pair<iterator, bool>(std::move(__it), false);
672 }
673 }
674
675 template <class _Kp>
676 _LIBCPP_HIDE_FROM_ABI bool __is_hint_correct(const_iterator __hint, _Kp&& __key) {
677 if (__hint != cbegin() && !__compare_(*std::prev(__hint), __key)) {
678 return false;
679 }
680 if (__hint != cend() && __compare_(*__hint, __key)) {
681 return false;
682 }
683 return true;
684 }
685
686 template <class _Kp>
687 _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint(const_iterator __hint, _Kp&& __key) {
688 if (__is_hint_correct(__hint, __key)) {
689 if (__hint == cend() || __compare_(__key, *__hint)) {
690 return __flat_set_utils::__emplace_exact_pos(*this, __hint, std::forward<_Kp>(__key));
691 } else {
692 // we already have an equal key
693 return __hint;
694 }
695 } else {
696 return __emplace(std::forward<_Kp>(__key)).first;
697 }
698 }
699
700 _LIBCPP_HIDE_FROM_ABI void __reserve(size_t __size) {
701 if constexpr (__container_traits<_KeyContainer>::__reservable) {
702 __keys_.reserve(__size);
703 }
704 }
705
706 template <class _Key2, class _Compare2, class _KeyContainer2, class _Predicate>
707 friend typename flat_set<_Key2, _Compare2, _KeyContainer2>::size_type
708 erase_if(flat_set<_Key2, _Compare2, _KeyContainer2>&, _Predicate);
709
710 _KeyContainer __keys_;
711 _LIBCPP_NO_UNIQUE_ADDRESS key_compare __compare_;
712
713 struct __key_equiv {
714 _LIBCPP_HIDE_FROM_ABI __key_equiv(key_compare __c) : __comp_(__c) {}
715 _LIBCPP_HIDE_FROM_ABI bool operator()(const_reference __x, const_reference __y) const {
716 return !__comp_(__x, __y) && !__comp_(__y, __x);
717 }
718 key_compare __comp_;
719 };
720};
721
722template <class _KeyContainer, class _Compare = less<typename _KeyContainer::value_type>>
723 requires(!__is_allocator<_Compare>::value && !__is_allocator<_KeyContainer>::value &&
724 is_invocable_v<const _Compare&,
725 const typename _KeyContainer::value_type&,
726 const typename _KeyContainer::value_type&>)
727flat_set(_KeyContainer, _Compare = _Compare()) -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
728
729template <class _KeyContainer, class _Allocator>
730 requires(uses_allocator_v<_KeyContainer, _Allocator> && !__is_allocator<_KeyContainer>::value)
731flat_set(_KeyContainer, _Allocator)
732 -> flat_set<typename _KeyContainer::value_type, less<typename _KeyContainer::value_type>, _KeyContainer>;
733
734template <class _KeyContainer, class _Compare, class _Allocator>
735 requires(!__is_allocator<_Compare>::value && !__is_allocator<_KeyContainer>::value &&
736 uses_allocator_v<_KeyContainer, _Allocator> &&
737 is_invocable_v<const _Compare&,
738 const typename _KeyContainer::value_type&,
739 const typename _KeyContainer::value_type&>)
740flat_set(_KeyContainer, _Compare, _Allocator) -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
741
742template <class _KeyContainer, class _Compare = less<typename _KeyContainer::value_type>>
743 requires(!__is_allocator<_Compare>::value && !__is_allocator<_KeyContainer>::value &&
744 is_invocable_v<const _Compare&,
745 const typename _KeyContainer::value_type&,
746 const typename _KeyContainer::value_type&>)
747flat_set(sorted_unique_t, _KeyContainer, _Compare = _Compare())
748 -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
749
750template <class _KeyContainer, class _Allocator>
751 requires(uses_allocator_v<_KeyContainer, _Allocator> && !__is_allocator<_KeyContainer>::value)
752flat_set(sorted_unique_t, _KeyContainer, _Allocator)
753 -> flat_set<typename _KeyContainer::value_type, less<typename _KeyContainer::value_type>, _KeyContainer>;
754
755template <class _KeyContainer, class _Compare, class _Allocator>
756 requires(!__is_allocator<_Compare>::value && !__is_allocator<_KeyContainer>::value &&
757 uses_allocator_v<_KeyContainer, _Allocator> &&
758 is_invocable_v<const _Compare&,
759 const typename _KeyContainer::value_type&,
760 const typename _KeyContainer::value_type&>)
761flat_set(sorted_unique_t, _KeyContainer, _Compare, _Allocator)
762 -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
763
764template <class _InputIterator, class _Compare = less<__iter_value_type<_InputIterator>>>
765 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator<_Compare>::value)
766flat_set(_InputIterator, _InputIterator, _Compare = _Compare())
767 -> flat_set<__iter_value_type<_InputIterator>, _Compare>;
768
769template <class _InputIterator, class _Compare = less<__iter_value_type<_InputIterator>>>
770 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator<_Compare>::value)
771flat_set(sorted_unique_t, _InputIterator, _InputIterator, _Compare = _Compare())
772 -> flat_set<__iter_value_type<_InputIterator>, _Compare>;
773
774template <ranges::input_range _Range,
775 class _Compare = less<ranges::range_value_t<_Range>>,
776 class _Allocator = allocator<ranges::range_value_t<_Range>>,
777 class = __enable_if_t<!__is_allocator<_Compare>::value && __is_allocator<_Allocator>::value>>
778flat_set(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator()) -> flat_set<
779 ranges::range_value_t<_Range>,
780 _Compare,
781 vector<ranges::range_value_t<_Range>, __allocator_traits_rebind_t<_Allocator, ranges::range_value_t<_Range>>>>;
782
783template <ranges::input_range _Range, class _Allocator, class = __enable_if_t<__is_allocator<_Allocator>::value>>
784flat_set(from_range_t, _Range&&, _Allocator) -> flat_set<
785 ranges::range_value_t<_Range>,
786 less<ranges::range_value_t<_Range>>,
787 vector<ranges::range_value_t<_Range>, __allocator_traits_rebind_t<_Allocator, ranges::range_value_t<_Range>>>>;
788
789template <class _Key, class _Compare = less<_Key>>
790 requires(!__is_allocator<_Compare>::value)
791flat_set(initializer_list<_Key>, _Compare = _Compare()) -> flat_set<_Key, _Compare>;
792
793template <class _Key, class _Compare = less<_Key>>
794 requires(!__is_allocator<_Compare>::value)
795flat_set(sorted_unique_t, initializer_list<_Key>, _Compare = _Compare()) -> flat_set<_Key, _Compare>;
796
797template <class _Key, class _Compare, class _KeyContainer, class _Allocator>
798struct uses_allocator<flat_set<_Key, _Compare, _KeyContainer>, _Allocator>
799 : bool_constant<uses_allocator_v<_KeyContainer, _Allocator>> {};
800
801template <class _Key, class _Compare, class _KeyContainer, class _Predicate>
802_LIBCPP_HIDE_FROM_ABI typename flat_set<_Key, _Compare, _KeyContainer>::size_type
803erase_if(flat_set<_Key, _Compare, _KeyContainer>& __flat_set, _Predicate __pred) {
804 auto __guard = std::__make_exception_guard([&] { __flat_set.clear(); });
805 auto __it = std::remove_if(__flat_set.__keys_.begin(), __flat_set.__keys_.end(), [&](const auto& __e) -> bool {
806 return static_cast<bool>(__pred(__e));
807 });
808 auto __res = __flat_set.__keys_.end() - __it;
809 __flat_set.__keys_.erase(__it, __flat_set.__keys_.end());
810 __guard.__complete();
811 return __res;
812}
813
814_LIBCPP_END_NAMESPACE_STD
815
816#endif // _LIBCPP_STD_VER >= 23
817
818_LIBCPP_POP_MACROS
819
820#endif // _LIBCPP___FLAT_SET_FLAT_SET_H
821

Warning: This file is not a C or C++ file. It does not have highlighting.

source code of libcxx/include/__flat_set/flat_set.h