CoCalc -- flat

GitHub Repository: freebsd/freebsd-src
Path: blob/main/contrib/llvm-project/libcxx/include/__flat_set/flat_set.h
²¹³⁷⁶⁶ views
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

80
template <class _Key, class _Compare = less<_Key>, class _KeyContainer = vector<_Key>>
81
class 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

92
public:
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

108
public:
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

662
private:
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

776
template <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&>)
781
flat_set(_KeyContainer, _Compare = _Compare()) -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
782

783
template <class _KeyContainer, class _Allocator>
784
  requires(uses_allocator_v<_KeyContainer, _Allocator> && !__is_allocator<_KeyContainer>::value)
785
flat_set(_KeyContainer, _Allocator)
786
    -> flat_set<typename _KeyContainer::value_type, less<typename _KeyContainer::value_type>, _KeyContainer>;
787

788
template <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&>)
794
flat_set(_KeyContainer, _Compare, _Allocator) -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
795

796
template <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&>)
801
flat_set(sorted_unique_t, _KeyContainer, _Compare = _Compare())
802
    -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
803

804
template <class _KeyContainer, class _Allocator>
805
  requires(uses_allocator_v<_KeyContainer, _Allocator> && !__is_allocator<_KeyContainer>::value)
806
flat_set(sorted_unique_t, _KeyContainer, _Allocator)
807
    -> flat_set<typename _KeyContainer::value_type, less<typename _KeyContainer::value_type>, _KeyContainer>;
808

809
template <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&>)
815
flat_set(sorted_unique_t, _KeyContainer, _Compare, _Allocator)
816
    -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
817

818
template <class _InputIterator, class _Compare = less<__iter_value_type<_InputIterator>>>
819
  requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator<_Compare>::value)
820
flat_set(_InputIterator, _InputIterator, _Compare = _Compare())
821
    -> flat_set<__iter_value_type<_InputIterator>, _Compare>;
822

823
template <class _InputIterator, class _Compare = less<__iter_value_type<_InputIterator>>>
824
  requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator<_Compare>::value)
825
flat_set(sorted_unique_t, _InputIterator, _InputIterator, _Compare = _Compare())
826
    -> flat_set<__iter_value_type<_InputIterator>, _Compare>;
827

828
template <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>>
832
flat_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

837
template <ranges::input_range _Range, class _Allocator, class = __enable_if_t<__is_allocator<_Allocator>::value>>
838
flat_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

843
template <class _Key, class _Compare = less<_Key>>
844
  requires(!__is_allocator<_Compare>::value)
845
flat_set(initializer_list<_Key>, _Compare = _Compare()) -> flat_set<_Key, _Compare>;
846

847
template <class _Key, class _Compare = less<_Key>>
848
  requires(!__is_allocator<_Compare>::value)
849
flat_set(sorted_unique_t, initializer_list<_Key>, _Compare = _Compare()) -> flat_set<_Key, _Compare>;
850

851
template <class _Key, class _Compare, class _KeyContainer, class _Allocator>
852
struct uses_allocator<flat_set<_Key, _Compare, _KeyContainer>, _Allocator>
853
    : bool_constant<uses_allocator_v<_KeyContainer, _Allocator>> {};
854

855
template <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
857
erase_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
875

876
Product

Resources

Company
