CoCalc -- flat

GitHub Repository: freebsd/freebsd-src
Path: blob/main/contrib/llvm-project/libcxx/include/__flat_map/flat_map.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_MAP_FLAT_MAP_H
11
#define _LIBCPP___FLAT_MAP_FLAT_MAP_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/byte.h>
28
#include <__cstddef/ptrdiff_t.h>
29
#include <__flat_map/key_value_iterator.h>
30
#include <__flat_map/sorted_unique.h>
31
#include <__flat_map/utils.h>
32
#include <__functional/invoke.h>
33
#include <__functional/is_transparent.h>
34
#include <__functional/operations.h>
35
#include <__fwd/memory.h>
36
#include <__fwd/vector.h>
37
#include <__iterator/concepts.h>
38
#include <__iterator/distance.h>
39
#include <__iterator/iterator_traits.h>
40
#include <__iterator/next.h>
41
#include <__iterator/ranges_iterator_traits.h>
42
#include <__iterator/reverse_iterator.h>
43
#include <__memory/allocator_traits.h>
44
#include <__memory/uses_allocator.h>
45
#include <__memory/uses_allocator_construction.h>
46
#include <__ranges/access.h>
47
#include <__ranges/concepts.h>
48
#include <__ranges/container_compatible_range.h>
49
#include <__ranges/drop_view.h>
50
#include <__ranges/from_range.h>
51
#include <__ranges/ref_view.h>
52
#include <__ranges/size.h>
53
#include <__ranges/subrange.h>
54
#include <__ranges/zip_view.h>
55
#include <__type_traits/conjunction.h>
56
#include <__type_traits/container_traits.h>
57
#include <__type_traits/invoke.h>
58
#include <__type_traits/is_allocator.h>
59
#include <__type_traits/is_nothrow_constructible.h>
60
#include <__type_traits/is_same.h>
61
#include <__utility/exception_guard.h>
62
#include <__utility/move.h>
63
#include <__utility/pair.h>
64
#include <__utility/scope_guard.h>
65
#include <__vector/vector.h>
66
#include <initializer_list>
67
#include <stdexcept>
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,
81
          class _Tp,
82
          class _Compare         = less<_Key>,
83
          class _KeyContainer    = vector<_Key>,
84
          class _MappedContainer = vector<_Tp>>
85
class flat_map {
86
  template <class, class, class, class, class>
87
  friend class flat_map;
88

89
  static_assert(is_same_v<_Key, typename _KeyContainer::value_type>);
90
  static_assert(is_same_v<_Tp, typename _MappedContainer::value_type>);
91
  static_assert(!is_same_v<_KeyContainer, std::vector<bool>>, "vector<bool> is not a sequence container");
92
  static_assert(!is_same_v<_MappedContainer, std::vector<bool>>, "vector<bool> is not a sequence container");
93

94
  template <bool _Const>
95
  using __iterator _LIBCPP_NODEBUG = __key_value_iterator<flat_map, _KeyContainer, _MappedContainer, _Const>;
96

97
public:
98
  // types
99
  using key_type               = _Key;
100
  using mapped_type            = _Tp;
101
  using value_type             = pair<key_type, mapped_type>;
102
  using key_compare            = __type_identity_t<_Compare>;
103
  using reference              = pair<const key_type&, mapped_type&>;
104
  using const_reference        = pair<const key_type&, const mapped_type&>;
105
  using size_type              = size_t;
106
  using difference_type        = ptrdiff_t;
107
  using iterator               = __iterator<false>; // see [container.requirements]
108
  using const_iterator         = __iterator<true>;  // see [container.requirements]
109
  using reverse_iterator       = std::reverse_iterator<iterator>;
110
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
111
  using key_container_type     = _KeyContainer;
112
  using mapped_container_type  = _MappedContainer;
113

114
  class value_compare {
115
  private:
116
    _LIBCPP_NO_UNIQUE_ADDRESS key_compare __comp_;
117
    _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 value_compare(key_compare __c) : __comp_(__c) {}
118
    friend flat_map;
119

120
  public:
121
    _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
122
    operator()(const_reference __x, const_reference __y) const {
123
      return __comp_(__x.first, __y.first);
124
    }
125
  };
126

127
  struct containers {
128
    key_container_type keys;
129
    mapped_container_type values;
130
  };
131

132
private:
133
  template <class _Allocator>
134
  _LIBCPP_HIDE_FROM_ABI static constexpr bool __allocator_ctor_constraint =
135
      _And<uses_allocator<key_container_type, _Allocator>, uses_allocator<mapped_container_type, _Allocator>>::value;
136

137
  _LIBCPP_HIDE_FROM_ABI static constexpr bool __is_compare_transparent = __is_transparent_v<_Compare>;
138

139
public:
140
  // [flat.map.cons], construct/copy/destroy
141
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map() noexcept(
142
      is_nothrow_default_constructible_v<_KeyContainer> && is_nothrow_default_constructible_v<_MappedContainer> &&
143
      is_nothrow_default_constructible_v<_Compare>)
144
      : __containers_(), __compare_() {}
145

146
  _LIBCPP_HIDE_FROM_ABI flat_map(const flat_map&) = default;
147

148
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(flat_map&& __other) noexcept(
149
      is_nothrow_move_constructible_v<_KeyContainer> && is_nothrow_move_constructible_v<_MappedContainer> &&
150
      is_nothrow_move_constructible_v<_Compare>)
151
#  if _LIBCPP_HAS_EXCEPTIONS
152
      try
153
#  endif // _LIBCPP_HAS_EXCEPTIONS
154
      : __containers_(std::move(__other.__containers_)), __compare_(std::move(__other.__compare_)) {
155
    __other.clear();
156
#  if _LIBCPP_HAS_EXCEPTIONS
157
  } catch (...) {
158
    __other.clear();
159
    // gcc does not like the `throw` keyword in a conditionally noexcept function
160
    if constexpr (!(is_nothrow_move_constructible_v<_KeyContainer> &&
161
                    is_nothrow_move_constructible_v<_MappedContainer> && is_nothrow_move_constructible_v<_Compare>)) {
162
      throw;
163
    }
164
#  endif // _LIBCPP_HAS_EXCEPTIONS
165
  }
166

167
  template <class _Allocator>
168
    requires __allocator_ctor_constraint<_Allocator>
169
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(const flat_map& __other, const _Allocator& __alloc)
170
      : flat_map(__ctor_uses_allocator_tag{},
171
                 __alloc,
172
                 __other.__containers_.keys,
173
                 __other.__containers_.values,
174
                 __other.__compare_) {}
175

176
  template <class _Allocator>
177
    requires __allocator_ctor_constraint<_Allocator>
178
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(flat_map&& __other, const _Allocator& __alloc)
179
#  if _LIBCPP_HAS_EXCEPTIONS
180
      try
181
#  endif // _LIBCPP_HAS_EXCEPTIONS
182
      : flat_map(__ctor_uses_allocator_tag{},
183
                 __alloc,
184
                 std::move(__other.__containers_.keys),
185
                 std::move(__other.__containers_.values),
186
                 std::move(__other.__compare_)) {
187
    __other.clear();
188
#  if _LIBCPP_HAS_EXCEPTIONS
189
  } catch (...) {
190
    __other.clear();
191
    throw;
192
#  endif // _LIBCPP_HAS_EXCEPTIONS
193
  }
194

195
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(
196
      key_container_type __key_cont, mapped_container_type __mapped_cont, const key_compare& __comp = key_compare())
197
      : __containers_{.keys = std::move(__key_cont), .values = std::move(__mapped_cont)}, __compare_(__comp) {
198
    _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
199
                                     "flat_map keys and mapped containers have different size");
200
    __sort_and_unique();
201
  }
202

203
  template <class _Allocator>
204
    requires __allocator_ctor_constraint<_Allocator>
205
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
206
  flat_map(const key_container_type& __key_cont, const mapped_container_type& __mapped_cont, const _Allocator& __alloc)
207
      : flat_map(__ctor_uses_allocator_tag{}, __alloc, __key_cont, __mapped_cont) {
208
    _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
209
                                     "flat_map keys and mapped containers have different size");
210
    __sort_and_unique();
211
  }
212

213
  template <class _Allocator>
214
    requires __allocator_ctor_constraint<_Allocator>
215
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
216
  flat_map(const key_container_type& __key_cont,
217
           const mapped_container_type& __mapped_cont,
218
           const key_compare& __comp,
219
           const _Allocator& __alloc)
220
      : flat_map(__ctor_uses_allocator_tag{}, __alloc, __key_cont, __mapped_cont, __comp) {
221
    _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
222
                                     "flat_map keys and mapped containers have different size");
223
    __sort_and_unique();
224
  }
225

226
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
227
  flat_map(sorted_unique_t,
228
           key_container_type __key_cont,
229
           mapped_container_type __mapped_cont,
230
           const key_compare& __comp = key_compare())
231
      : __containers_{.keys = std::move(__key_cont), .values = std::move(__mapped_cont)}, __compare_(__comp) {
232
    _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
233
                                     "flat_map keys and mapped containers have different size");
234
    _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
235
        __is_sorted_and_unique(__containers_.keys), "Either the key container is not sorted or it contains duplicates");
236
  }
237

238
  template <class _Allocator>
239
    requires __allocator_ctor_constraint<_Allocator>
240
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
241
  flat_map(sorted_unique_t,
242
           const key_container_type& __key_cont,
243
           const mapped_container_type& __mapped_cont,
244
           const _Allocator& __alloc)
245
      : flat_map(__ctor_uses_allocator_tag{}, __alloc, __key_cont, __mapped_cont) {
246
    _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
247
                                     "flat_map keys and mapped containers have different size");
248
    _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
249
        __is_sorted_and_unique(__containers_.keys), "Either the key container is not sorted or it contains duplicates");
250
  }
251

252
  template <class _Allocator>
253
    requires __allocator_ctor_constraint<_Allocator>
254
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(
255
      sorted_unique_t,
256
      const key_container_type& __key_cont,
257
      const mapped_container_type& __mapped_cont,
258
      const key_compare& __comp,
259
      const _Allocator& __alloc)
260
      : flat_map(__ctor_uses_allocator_tag{}, __alloc, __key_cont, __mapped_cont, __comp) {
261
    _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
262
                                     "flat_map keys and mapped containers have different size");
263
    _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
264
        __is_sorted_and_unique(__containers_.keys), "Either the key container is not sorted or it contains duplicates");
265
  }
266

267
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit flat_map(const key_compare& __comp)
268
      : __containers_(), __compare_(__comp) {}
269

270
  template <class _Allocator>
271
    requires __allocator_ctor_constraint<_Allocator>
272
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(const key_compare& __comp, const _Allocator& __alloc)
273
      : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) {}
274

275
  template <class _Allocator>
276
    requires __allocator_ctor_constraint<_Allocator>
277
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit flat_map(const _Allocator& __alloc)
278
      : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc) {}
279

280
  template <class _InputIterator>
281
    requires __has_input_iterator_category<_InputIterator>::value
282
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
283
  flat_map(_InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare())
284
      : __containers_(), __compare_(__comp) {
285
    insert(__first, __last);
286
  }
287

288
  template <class _InputIterator, class _Allocator>
289
    requires(__has_input_iterator_category<_InputIterator>::value && __allocator_ctor_constraint<_Allocator>)
290
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
291
  flat_map(_InputIterator __first, _InputIterator __last, const key_compare& __comp, const _Allocator& __alloc)
292
      : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) {
293
    insert(__first, __last);
294
  }
295

296
  template <class _InputIterator, class _Allocator>
297
    requires(__has_input_iterator_category<_InputIterator>::value && __allocator_ctor_constraint<_Allocator>)
298
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
299
  flat_map(_InputIterator __first, _InputIterator __last, const _Allocator& __alloc)
300
      : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc) {
301
    insert(__first, __last);
302
  }
303

304
  template <_ContainerCompatibleRange<value_type> _Range>
305
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(from_range_t __fr, _Range&& __rg)
306
      : flat_map(__fr, std::forward<_Range>(__rg), key_compare()) {}
307

308
  template <_ContainerCompatibleRange<value_type> _Range, class _Allocator>
309
    requires __allocator_ctor_constraint<_Allocator>
310
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(from_range_t, _Range&& __rg, const _Allocator& __alloc)
311
      : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc) {
312
    insert_range(std::forward<_Range>(__rg));
313
  }
314

315
  template <_ContainerCompatibleRange<value_type> _Range>
316
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(from_range_t, _Range&& __rg, const key_compare& __comp)
317
      : flat_map(__comp) {
318
    insert_range(std::forward<_Range>(__rg));
319
  }
320

321
  template <_ContainerCompatibleRange<value_type> _Range, class _Allocator>
322
    requires __allocator_ctor_constraint<_Allocator>
323
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
324
  flat_map(from_range_t, _Range&& __rg, const key_compare& __comp, const _Allocator& __alloc)
325
      : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) {
326
    insert_range(std::forward<_Range>(__rg));
327
  }
328

329
  template <class _InputIterator>
330
    requires __has_input_iterator_category<_InputIterator>::value
331
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
332
  flat_map(sorted_unique_t, _InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare())
333
      : __containers_(), __compare_(__comp) {
334
    insert(sorted_unique, __first, __last);
335
  }
336
  template <class _InputIterator, class _Allocator>
337
    requires(__has_input_iterator_category<_InputIterator>::value && __allocator_ctor_constraint<_Allocator>)
338
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(
339
      sorted_unique_t,
340
      _InputIterator __first,
341
      _InputIterator __last,
342
      const key_compare& __comp,
343
      const _Allocator& __alloc)
344
      : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) {
345
    insert(sorted_unique, __first, __last);
346
  }
347

348
  template <class _InputIterator, class _Allocator>
349
    requires(__has_input_iterator_category<_InputIterator>::value && __allocator_ctor_constraint<_Allocator>)
350
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
351
  flat_map(sorted_unique_t, _InputIterator __first, _InputIterator __last, const _Allocator& __alloc)
352
      : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc) {
353
    insert(sorted_unique, __first, __last);
354
  }
355

356
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
357
  flat_map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
358
      : flat_map(__il.begin(), __il.end(), __comp) {}
359

360
  template <class _Allocator>
361
    requires __allocator_ctor_constraint<_Allocator>
362
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
363
  flat_map(initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc)
364
      : flat_map(__il.begin(), __il.end(), __comp, __alloc) {}
365

366
  template <class _Allocator>
367
    requires __allocator_ctor_constraint<_Allocator>
368
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
369
  flat_map(initializer_list<value_type> __il, const _Allocator& __alloc)
370
      : flat_map(__il.begin(), __il.end(), __alloc) {}
371

372
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
373
  flat_map(sorted_unique_t, initializer_list<value_type> __il, const key_compare& __comp = key_compare())
374
      : flat_map(sorted_unique, __il.begin(), __il.end(), __comp) {}
375

376
  template <class _Allocator>
377
    requires __allocator_ctor_constraint<_Allocator>
378
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
379
  flat_map(sorted_unique_t, initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc)
380
      : flat_map(sorted_unique, __il.begin(), __il.end(), __comp, __alloc) {}
381

382
  template <class _Allocator>
383
    requires __allocator_ctor_constraint<_Allocator>
384
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
385
  flat_map(sorted_unique_t, initializer_list<value_type> __il, const _Allocator& __alloc)
386
      : flat_map(sorted_unique, __il.begin(), __il.end(), __alloc) {}
387

388
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map& operator=(initializer_list<value_type> __il) {
389
    clear();
390
    insert(__il);
391
    return *this;
392
  }
393

394
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map& operator=(const flat_map&) = default;
395

396
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map& operator=(flat_map&& __other) noexcept(
397
      is_nothrow_move_assignable_v<_KeyContainer> && is_nothrow_move_assignable_v<_MappedContainer> &&
398
      is_nothrow_move_assignable_v<_Compare>) {
399
    // No matter what happens, we always want to clear the other container before returning
400
    // since we moved from it
401
    auto __clear_other_guard = std::__make_scope_guard([&]() noexcept { __other.clear() /* noexcept */; });
402
    {
403
      // If an exception is thrown, we have no choice but to clear *this to preserve invariants
404
      auto __on_exception = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
405
      __containers_       = std::move(__other.__containers_);
406
      __compare_          = std::move(__other.__compare_);
407
      __on_exception.__complete();
408
    }
409
    return *this;
410
  }
411

412
  // iterators
413
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator begin() noexcept {
414
    return iterator(__containers_.keys.begin(), __containers_.values.begin());
415
  }
416

417
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator begin() const noexcept {
418
    return const_iterator(__containers_.keys.begin(), __containers_.values.begin());
419
  }
420

421
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator end() noexcept {
422
    return iterator(__containers_.keys.end(), __containers_.values.end());
423
  }
424

425
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator end() const noexcept {
426
    return const_iterator(__containers_.keys.end(), __containers_.values.end());
427
  }
428

429
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 reverse_iterator rbegin() noexcept {
430
    return reverse_iterator(end());
431
  }
432
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator rbegin() const noexcept {
433
    return const_reverse_iterator(end());
434
  }
435
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 reverse_iterator rend() noexcept {
436
    return reverse_iterator(begin());
437
  }
438
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator rend() const noexcept {
439
    return const_reverse_iterator(begin());
440
  }
441

442
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator cbegin() const noexcept { return begin(); }
443
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator cend() const noexcept { return end(); }
444
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator crbegin() const noexcept {
445
    return const_reverse_iterator(end());
446
  }
447
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator crend() const noexcept {
448
    return const_reverse_iterator(begin());
449
  }
450

451
  // [flat.map.capacity], capacity
452
  [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool empty() const noexcept {
453
    return __containers_.keys.empty();
454
  }
455

456
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type size() const noexcept {
457
    return __containers_.keys.size();
458
  }
459

460
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type max_size() const noexcept {
461
    return std::min<size_type>(__containers_.keys.max_size(), __containers_.values.max_size());
462
  }
463

464
  // [flat.map.access], element access
465
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 mapped_type& operator[](const key_type& __x)
466
    requires is_constructible_v<mapped_type>
467
  {
468
    return try_emplace(__x).first->second;
469
  }
470

471
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 mapped_type& operator[](key_type&& __x)
472
    requires is_constructible_v<mapped_type>
473
  {
474
    return try_emplace(std::move(__x)).first->second;
475
  }
476

477
  template <class _Kp>
478
    requires(__is_compare_transparent && is_constructible_v<key_type, _Kp> && is_constructible_v<mapped_type> &&
479
             !is_convertible_v<_Kp &&, const_iterator> && !is_convertible_v<_Kp &&, iterator>)
480
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 mapped_type& operator[](_Kp&& __x) {
481
    return try_emplace(std::forward<_Kp>(__x)).first->second;
482
  }
483

484
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 mapped_type& at(const key_type& __x) {
485
    auto __it = find(__x);
486
    if (__it == end()) {
487
      std::__throw_out_of_range("flat_map::at(const key_type&): Key does not exist");
488
    }
489
    return __it->second;
490
  }
491

492
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const mapped_type& at(const key_type& __x) const {
493
    auto __it = find(__x);
494
    if (__it == end()) {
495
      std::__throw_out_of_range("flat_map::at(const key_type&) const: Key does not exist");
496
    }
497
    return __it->second;
498
  }
499

500
  template <class _Kp>
501
    requires __is_compare_transparent
502
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 mapped_type& at(const _Kp& __x) {
503
    auto __it = find(__x);
504
    if (__it == end()) {
505
      std::__throw_out_of_range("flat_map::at(const K&): Key does not exist");
506
    }
507
    return __it->second;
508
  }
509

510
  template <class _Kp>
511
    requires __is_compare_transparent
512
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const mapped_type& at(const _Kp& __x) const {
513
    auto __it = find(__x);
514
    if (__it == end()) {
515
      std::__throw_out_of_range("flat_map::at(const K&) const: Key does not exist");
516
    }
517
    return __it->second;
518
  }
519

520
  // [flat.map.modifiers], modifiers
521
  template <class... _Args>
522
    requires is_constructible_v<pair<key_type, mapped_type>, _Args...>
523
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> emplace(_Args&&... __args) {
524
    std::pair<key_type, mapped_type> __pair(std::forward<_Args>(__args)...);
525
    return __try_emplace(std::move(__pair.first), std::move(__pair.second));
526
  }
527

528
  template <class... _Args>
529
    requires is_constructible_v<pair<key_type, mapped_type>, _Args...>
530
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator emplace_hint(const_iterator __hint, _Args&&... __args) {
531
    std::pair<key_type, mapped_type> __pair(std::forward<_Args>(__args)...);
532
    return __try_emplace_hint(__hint, std::move(__pair.first), std::move(__pair.second)).first;
533
  }
534

535
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> insert(const value_type& __x) {
536
    return emplace(__x);
537
  }
538

539
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> insert(value_type&& __x) {
540
    return emplace(std::move(__x));
541
  }
542

543
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __hint, const value_type& __x) {
544
    return emplace_hint(__hint, __x);
545
  }
546

547
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __hint, value_type&& __x) {
548
    return emplace_hint(__hint, std::move(__x));
549
  }
550

551
  template <class _PairLike>
552
    requires is_constructible_v<pair<key_type, mapped_type>, _PairLike>
553
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> insert(_PairLike&& __x) {
554
    return emplace(std::forward<_PairLike>(__x));
555
  }
556

557
  template <class _PairLike>
558
    requires is_constructible_v<pair<key_type, mapped_type>, _PairLike>
559
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __hint, _PairLike&& __x) {
560
    return emplace_hint(__hint, std::forward<_PairLike>(__x));
561
  }
562

563
  template <class _InputIterator>
564
    requires __has_input_iterator_category<_InputIterator>::value
565
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(_InputIterator __first, _InputIterator __last) {
566
    if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) {
567
      __reserve(__last - __first);
568
    }
569
    __append_sort_merge_unique</*WasSorted = */ false>(std::move(__first), std::move(__last));
570
  }
571

572
  template <class _InputIterator>
573
    requires __has_input_iterator_category<_InputIterator>::value
574
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
575
  insert(sorted_unique_t, _InputIterator __first, _InputIterator __last) {
576
    if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) {
577
      __reserve(__last - __first);
578
    }
579

580
    __append_sort_merge_unique</*WasSorted = */ true>(std::move(__first), std::move(__last));
581
  }
582

583
  template <_ContainerCompatibleRange<value_type> _Range>
584
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert_range(_Range&& __range) {
585
    if constexpr (ranges::sized_range<_Range>) {
586
      __reserve(ranges::size(__range));
587
    }
588

589
    __append_sort_merge_unique</*WasSorted = */ false>(ranges::begin(__range), ranges::end(__range));
590
  }
591

592
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(initializer_list<value_type> __il) {
593
    insert(__il.begin(), __il.end());
594
  }
595

596
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(sorted_unique_t, initializer_list<value_type> __il) {
597
    insert(sorted_unique, __il.begin(), __il.end());
598
  }
599

600
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 containers extract() && {
601
    auto __guard = std::__make_scope_guard([&]() noexcept { clear() /* noexcept */; });
602
    auto __ret   = std::move(__containers_);
603
    return __ret;
604
  }
605

606
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
607
  replace(key_container_type&& __key_cont, mapped_container_type&& __mapped_cont) {
608
    _LIBCPP_ASSERT_VALID_INPUT_RANGE(
609
        __key_cont.size() == __mapped_cont.size(), "flat_map keys and mapped containers have different size");
610

611
    _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
612
        __is_sorted_and_unique(__key_cont), "Either the key container is not sorted or it contains duplicates");
613
    auto __guard         = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
614
    __containers_.keys   = std::move(__key_cont);
615
    __containers_.values = std::move(__mapped_cont);
616
    __guard.__complete();
617
  }
618

619
  template <class... _Args>
620
    requires is_constructible_v<mapped_type, _Args...>
621
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool>
622
  try_emplace(const key_type& __key, _Args&&... __args) {
623
    return __try_emplace(__key, std::forward<_Args>(__args)...);
624
  }
625

626
  template <class... _Args>
627
    requires is_constructible_v<mapped_type, _Args...>
628
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool>
629
  try_emplace(key_type&& __key, _Args&&... __args) {
630
    return __try_emplace(std::move(__key), std::forward<_Args>(__args)...);
631
  }
632

633
  template <class _Kp, class... _Args>
634
    requires(__is_compare_transparent && is_constructible_v<key_type, _Kp> &&
635
             is_constructible_v<mapped_type, _Args...> && !is_convertible_v<_Kp &&, const_iterator> &&
636
             !is_convertible_v<_Kp &&, iterator>)
637
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> try_emplace(_Kp&& __key, _Args&&... __args) {
638
    return __try_emplace(std::forward<_Kp>(__key), std::forward<_Args>(__args)...);
639
  }
640

641
  template <class... _Args>
642
    requires is_constructible_v<mapped_type, _Args...>
643
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator
644
  try_emplace(const_iterator __hint, const key_type& __key, _Args&&... __args) {
645
    return __try_emplace_hint(__hint, __key, std::forward<_Args>(__args)...).first;
646
  }
647

648
  template <class... _Args>
649
    requires is_constructible_v<mapped_type, _Args...>
650
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator
651
  try_emplace(const_iterator __hint, key_type&& __key, _Args&&... __args) {
652
    return __try_emplace_hint(__hint, std::move(__key), std::forward<_Args>(__args)...).first;
653
  }
654

655
  template <class _Kp, class... _Args>
656
    requires __is_compare_transparent && is_constructible_v<key_type, _Kp> && is_constructible_v<mapped_type, _Args...>
657
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator
658
  try_emplace(const_iterator __hint, _Kp&& __key, _Args&&... __args) {
659
    return __try_emplace_hint(__hint, std::forward<_Kp>(__key), std::forward<_Args>(__args)...).first;
660
  }
661

662
  template <class _Mapped>
663
    requires is_assignable_v<mapped_type&, _Mapped> && is_constructible_v<mapped_type, _Mapped>
664
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool>
665
  insert_or_assign(const key_type& __key, _Mapped&& __obj) {
666
    return __insert_or_assign(__key, std::forward<_Mapped>(__obj));
667
  }
668

669
  template <class _Mapped>
670
    requires is_assignable_v<mapped_type&, _Mapped> && is_constructible_v<mapped_type, _Mapped>
671
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool>
672
  insert_or_assign(key_type&& __key, _Mapped&& __obj) {
673
    return __insert_or_assign(std::move(__key), std::forward<_Mapped>(__obj));
674
  }
675

676
  template <class _Kp, class _Mapped>
677
    requires __is_compare_transparent && is_constructible_v<key_type, _Kp> && is_assignable_v<mapped_type&, _Mapped> &&
678
             is_constructible_v<mapped_type, _Mapped>
679
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool>
680
  insert_or_assign(_Kp&& __key, _Mapped&& __obj) {
681
    return __insert_or_assign(std::forward<_Kp>(__key), std::forward<_Mapped>(__obj));
682
  }
683

684
  template <class _Mapped>
685
    requires is_assignable_v<mapped_type&, _Mapped> && is_constructible_v<mapped_type, _Mapped>
686
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator
687
  insert_or_assign(const_iterator __hint, const key_type& __key, _Mapped&& __obj) {
688
    return __insert_or_assign(__hint, __key, std::forward<_Mapped>(__obj));
689
  }
690

691
  template <class _Mapped>
692
    requires is_assignable_v<mapped_type&, _Mapped> && is_constructible_v<mapped_type, _Mapped>
693
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator
694
  insert_or_assign(const_iterator __hint, key_type&& __key, _Mapped&& __obj) {
695
    return __insert_or_assign(__hint, std::move(__key), std::forward<_Mapped>(__obj));
696
  }
697

698
  template <class _Kp, class _Mapped>
699
    requires __is_compare_transparent && is_constructible_v<key_type, _Kp> && is_assignable_v<mapped_type&, _Mapped> &&
700
             is_constructible_v<mapped_type, _Mapped>
701
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator
702
  insert_or_assign(const_iterator __hint, _Kp&& __key, _Mapped&& __obj) {
703
    return __insert_or_assign(__hint, std::forward<_Kp>(__key), std::forward<_Mapped>(__obj));
704
  }
705

706
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator erase(iterator __position) {
707
    return __erase(__position.__key_iter_, __position.__mapped_iter_);
708
  }
709

710
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator erase(const_iterator __position) {
711
    return __erase(__position.__key_iter_, __position.__mapped_iter_);
712
  }
713

714
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type erase(const key_type& __x) {
715
    auto __iter = find(__x);
716
    if (__iter != end()) {
717
      erase(__iter);
718
      return 1;
719
    }
720
    return 0;
721
  }
722

723
  template <class _Kp>
724
    requires(__is_compare_transparent && !is_convertible_v<_Kp &&, iterator> &&
725
             !is_convertible_v<_Kp &&, const_iterator>)
726
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type erase(_Kp&& __x) {
727
    auto [__first, __last] = equal_range(__x);
728
    auto __res             = __last - __first;
729
    erase(__first, __last);
730
    return __res;
731
  }
732

733
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator erase(const_iterator __first, const_iterator __last) {
734
    auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
735
    auto __key_it     = __containers_.keys.erase(__first.__key_iter_, __last.__key_iter_);
736
    auto __mapped_it  = __containers_.values.erase(__first.__mapped_iter_, __last.__mapped_iter_);
737
    __on_failure.__complete();
738
    return iterator(std::move(__key_it), std::move(__mapped_it));
739
  }
740

741
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void swap(flat_map& __y) noexcept {
742
    // warning: The spec has unconditional noexcept, which means that
743
    // if any of the following functions throw an exception,
744
    // std::terminate will be called.
745
    // This is discussed in P2767, which hasn't been voted on yet.
746
    ranges::swap(__compare_, __y.__compare_);
747
    ranges::swap(__containers_.keys, __y.__containers_.keys);
748
    ranges::swap(__containers_.values, __y.__containers_.values);
749
  }
750

751
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void clear() noexcept {
752
    __containers_.keys.clear();
753
    __containers_.values.clear();
754
  }
755

756
  // observers
757
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 key_compare key_comp() const { return __compare_; }
758
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 value_compare value_comp() const {
759
    return value_compare(__compare_);
760
  }
761

762
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const key_container_type& keys() const noexcept {
763
    return __containers_.keys;
764
  }
765
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const mapped_container_type& values() const noexcept {
766
    return __containers_.values;
767
  }
768

769
  // map operations
770
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator find(const key_type& __x) {
771
    return __find_impl(*this, __x);
772
  }
773

774
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator find(const key_type& __x) const {
775
    return __find_impl(*this, __x);
776
  }
777

778
  template <class _Kp>
779
    requires __is_compare_transparent
780
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator find(const _Kp& __x) {
781
    return __find_impl(*this, __x);
782
  }
783

784
  template <class _Kp>
785
    requires __is_compare_transparent
786
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator find(const _Kp& __x) const {
787
    return __find_impl(*this, __x);
788
  }
789

790
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type count(const key_type& __x) const {
791
    return contains(__x) ? 1 : 0;
792
  }
793

794
  template <class _Kp>
795
    requires __is_compare_transparent
796
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type count(const _Kp& __x) const {
797
    return contains(__x) ? 1 : 0;
798
  }
799

800
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool contains(const key_type& __x) const {
801
    return find(__x) != end();
802
  }
803

804
  template <class _Kp>
805
    requires __is_compare_transparent
806
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool contains(const _Kp& __x) const {
807
    return find(__x) != end();
808
  }
809

810
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator lower_bound(const key_type& __x) {
811
    return __lower_bound<iterator>(*this, __x);
812
  }
813

814
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator lower_bound(const key_type& __x) const {
815
    return __lower_bound<const_iterator>(*this, __x);
816
  }
817

818
  template <class _Kp>
819
    requires __is_compare_transparent
820
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator lower_bound(const _Kp& __x) {
821
    return __lower_bound<iterator>(*this, __x);
822
  }
823

824
  template <class _Kp>
825
    requires __is_compare_transparent
826
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator lower_bound(const _Kp& __x) const {
827
    return __lower_bound<const_iterator>(*this, __x);
828
  }
829

830
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator upper_bound(const key_type& __x) {
831
    return __upper_bound<iterator>(*this, __x);
832
  }
833

834
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator upper_bound(const key_type& __x) const {
835
    return __upper_bound<const_iterator>(*this, __x);
836
  }
837

838
  template <class _Kp>
839
    requires __is_compare_transparent
840
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator upper_bound(const _Kp& __x) {
841
    return __upper_bound<iterator>(*this, __x);
842
  }
843

844
  template <class _Kp>
845
    requires __is_compare_transparent
846
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator upper_bound(const _Kp& __x) const {
847
    return __upper_bound<const_iterator>(*this, __x);
848
  }
849

850
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, iterator> equal_range(const key_type& __x) {
851
    return __equal_range_impl(*this, __x);
852
  }
853

854
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<const_iterator, const_iterator>
855
  equal_range(const key_type& __x) const {
856
    return __equal_range_impl(*this, __x);
857
  }
858

859
  template <class _Kp>
860
    requires __is_compare_transparent
861
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, iterator> equal_range(const _Kp& __x) {
862
    return __equal_range_impl(*this, __x);
863
  }
864
  template <class _Kp>
865
    requires __is_compare_transparent
866
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<const_iterator, const_iterator>
867
  equal_range(const _Kp& __x) const {
868
    return __equal_range_impl(*this, __x);
869
  }
870

871
  friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool operator==(const flat_map& __x, const flat_map& __y) {
872
    return ranges::equal(__x, __y);
873
  }
874

875
  friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 auto
876
  operator<=>(const flat_map& __x, const flat_map& __y) {
877
    return std::lexicographical_compare_three_way(
878
        __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
879
  }
880

881
  friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void swap(flat_map& __x, flat_map& __y) noexcept {
882
    __x.swap(__y);
883
  }
884

885
private:
886
  struct __ctor_uses_allocator_tag {
887
    explicit _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __ctor_uses_allocator_tag() = default;
888
  };
889
  struct __ctor_uses_allocator_empty_tag {
890
    explicit _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __ctor_uses_allocator_empty_tag() = default;
891
  };
892

893
  template <class _Allocator, class _KeyCont, class _MappedCont, class... _CompArg>
894
    requires __allocator_ctor_constraint<_Allocator>
895
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(
896
      __ctor_uses_allocator_tag,
897
      const _Allocator& __alloc,
898
      _KeyCont&& __key_cont,
899
      _MappedCont&& __mapped_cont,
900
      _CompArg&&... __comp)
901
      : __containers_{.keys = std::make_obj_using_allocator<key_container_type>(
902
                          __alloc, std::forward<_KeyCont>(__key_cont)),
903
                      .values = std::make_obj_using_allocator<mapped_container_type>(
904
                          __alloc, std::forward<_MappedCont>(__mapped_cont))},
905
        __compare_(std::forward<_CompArg>(__comp)...) {}
906

907
  template <class _Allocator, class... _CompArg>
908
    requires __allocator_ctor_constraint<_Allocator>
909
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
910
  flat_map(__ctor_uses_allocator_empty_tag, const _Allocator& __alloc, _CompArg&&... __comp)
911
      : __containers_{.keys   = std::make_obj_using_allocator<key_container_type>(__alloc),
912
                      .values = std::make_obj_using_allocator<mapped_container_type>(__alloc)},
913
        __compare_(std::forward<_CompArg>(__comp)...) {}
914

915
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool __is_sorted_and_unique(auto&& __key_container) const {
916
    auto __greater_or_equal_to = [this](const auto& __x, const auto& __y) { return !__compare_(__x, __y); };
917
    return ranges::adjacent_find(__key_container, __greater_or_equal_to) == ranges::end(__key_container);
918
  }
919

920
  // This function is only used in constructors. So there is not exception handling in this function.
921
  // If the function exits via an exception, there will be no flat_map object constructed, thus, there
922
  // is no invariant state to preserve
923
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __sort_and_unique() {
924
    auto __zv = ranges::views::zip(__containers_.keys, __containers_.values);
925
    ranges::sort(__zv, __compare_, [](const auto& __p) -> decltype(auto) { return std::get<0>(__p); });
926
    auto __dup_start = ranges::unique(__zv, __key_equiv(__compare_)).begin();
927
    auto __dist      = ranges::distance(__zv.begin(), __dup_start);
928
    __containers_.keys.erase(__containers_.keys.begin() + __dist, __containers_.keys.end());
929
    __containers_.values.erase(__containers_.values.begin() + __dist, __containers_.values.end());
930
  }
931

932
  template <class _Self, class _KeyIter>
933
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto
934
  __corresponding_mapped_it(_Self&& __self, _KeyIter&& __key_iter) {
935
    return __self.__containers_.values.begin() +
936
           static_cast<ranges::range_difference_t<mapped_container_type>>(
937
               ranges::distance(__self.__containers_.keys.begin(), __key_iter));
938
  }
939

940
  template <bool _WasSorted, class _InputIterator, class _Sentinel>
941
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
942
  __append_sort_merge_unique(_InputIterator __first, _Sentinel __last) {
943
    auto __on_failure        = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
944
    size_t __num_of_appended = __flat_map_utils::__append(*this, std::move(__first), std::move(__last));
945
    if (__num_of_appended != 0) {
946
      auto __zv                  = ranges::views::zip(__containers_.keys, __containers_.values);
947
      auto __append_start_offset = __containers_.keys.size() - __num_of_appended;
948
      auto __end                 = __zv.end();
949
      auto __compare_key         = [this](const auto& __p1, const auto& __p2) {
950
        return __compare_(std::get<0>(__p1), std::get<0>(__p2));
951
      };
952
      if constexpr (!_WasSorted) {
953
        ranges::sort(__zv.begin() + __append_start_offset, __end, __compare_key);
954
      } else {
955
        _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
956
            __is_sorted_and_unique(__containers_.keys | ranges::views::drop(__append_start_offset)),
957
            "Either the key container is not sorted or it contains duplicates");
958
      }
959
      ranges::inplace_merge(__zv.begin(), __zv.begin() + __append_start_offset, __end, __compare_key);
960

961
      auto __dup_start = ranges::unique(__zv, __key_equiv(__compare_)).begin();
962
      auto __dist      = ranges::distance(__zv.begin(), __dup_start);
963
      __containers_.keys.erase(__containers_.keys.begin() + __dist, __containers_.keys.end());
964
      __containers_.values.erase(__containers_.values.begin() + __dist, __containers_.values.end());
965
    }
966
    __on_failure.__complete();
967
  }
968

969
  template <class _Self, class _Kp>
970
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto __find_impl(_Self&& __self, const _Kp& __key) {
971
    auto __it   = __self.lower_bound(__key);
972
    auto __last = __self.end();
973
    if (__it == __last || __self.__compare_(__key, __it->first)) {
974
      return __last;
975
    }
976
    return __it;
977
  }
978

979
  template <class _Self, class _Kp>
980
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto __key_equal_range(_Self&& __self, const _Kp& __key) {
981
    auto __it =
982
        std::lower_bound(__self.__containers_.keys.begin(), __self.__containers_.keys.end(), __key, __self.__compare_);
983
    auto __last = __self.__containers_.keys.end();
984
    if (__it == __last || __self.__compare_(__key, *__it)) {
985
      return std::make_pair(__it, __it);
986
    }
987
    return std::make_pair(__it, std::next(__it));
988
  }
989

990
  template <class _Self, class _Kp>
991
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto __equal_range_impl(_Self&& __self, const _Kp& __key) {
992
    auto [__key_first, __key_last] = __key_equal_range(__self, __key);
993
    using __iterator_type          = ranges::iterator_t<decltype(__self)>;
994
    return std::make_pair(__iterator_type(__key_first, __corresponding_mapped_it(__self, __key_first)),
995
                          __iterator_type(__key_last, __corresponding_mapped_it(__self, __key_last)));
996
  }
997

998
  template <class _Res, class _Self, class _Kp>
999
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static _Res __lower_bound(_Self&& __self, _Kp& __x) {
1000
    auto __key_iter =
1001
        std::lower_bound(__self.__containers_.keys.begin(), __self.__containers_.keys.end(), __x, __self.__compare_);
1002
    auto __mapped_iter = __corresponding_mapped_it(__self, __key_iter);
1003
    return _Res(std::move(__key_iter), std::move(__mapped_iter));
1004
  }
1005

1006
  template <class _Res, class _Self, class _Kp>
1007
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static _Res __upper_bound(_Self&& __self, _Kp& __x) {
1008
    auto __key_iter =
1009
        std::upper_bound(__self.__containers_.keys.begin(), __self.__containers_.keys.end(), __x, __self.__compare_);
1010
    auto __mapped_iter = __corresponding_mapped_it(__self, __key_iter);
1011
    return _Res(std::move(__key_iter), std::move(__mapped_iter));
1012
  }
1013

1014
  template <class _KeyArg, class... _MArgs>
1015
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool>
1016
  __try_emplace(_KeyArg&& __key, _MArgs&&... __mapped_args) {
1017
    auto __key_it    = std::lower_bound(__containers_.keys.begin(), __containers_.keys.end(), __key, __compare_);
1018
    auto __mapped_it = __containers_.values.begin() + ranges::distance(__containers_.keys.begin(), __key_it);
1019

1020
    if (__key_it == __containers_.keys.end() || __compare_(__key, *__key_it)) {
1021
      return pair<iterator, bool>(
1022
          __flat_map_utils::__emplace_exact_pos(
1023
              *this,
1024
              std::move(__key_it),
1025
              std::move(__mapped_it),
1026
              std::forward<_KeyArg>(__key),
1027
              std::forward<_MArgs>(__mapped_args)...),
1028
          true);
1029
    } else {
1030
      return pair<iterator, bool>(iterator(std::move(__key_it), std::move(__mapped_it)), false);
1031
    }
1032
  }
1033

1034
  template <class _Kp>
1035
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool __is_hint_correct(const_iterator __hint, _Kp&& __key) {
1036
    if (__hint != cbegin() && !__compare_((__hint - 1)->first, __key)) {
1037
      return false;
1038
    }
1039
    if (__hint != cend() && __compare_(__hint->first, __key)) {
1040
      return false;
1041
    }
1042
    return true;
1043
  }
1044

1045
  template <class _Kp, class... _Args>
1046
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool>
1047
  __try_emplace_hint(const_iterator __hint, _Kp&& __key, _Args&&... __args) {
1048
    if (__is_hint_correct(__hint, __key)) {
1049
      if (__hint == cend() || __compare_(__key, __hint->first)) {
1050
        return {__flat_map_utils::__emplace_exact_pos(
1051
                    *this,
1052
                    __hint.__key_iter_,
1053
                    __hint.__mapped_iter_,
1054
                    std::forward<_Kp>(__key),
1055
                    std::forward<_Args>(__args)...),
1056
                true};
1057
      } else {
1058
        // key equals
1059
        auto __dist = __hint - cbegin();
1060
        return {iterator(__containers_.keys.begin() + __dist, __containers_.values.begin() + __dist), false};
1061
      }
1062
    } else {
1063
      return __try_emplace(std::forward<_Kp>(__key), std::forward<_Args>(__args)...);
1064
    }
1065
  }
1066

1067
  template <class _Kp, class _Mapped>
1068
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool>
1069
  __insert_or_assign(_Kp&& __key, _Mapped&& __mapped) {
1070
    auto __r = try_emplace(std::forward<_Kp>(__key), std::forward<_Mapped>(__mapped));
1071
    if (!__r.second) {
1072
      __r.first->second = std::forward<_Mapped>(__mapped);
1073
    }
1074
    return __r;
1075
  }
1076

1077
  template <class _Kp, class _Mapped>
1078
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator
1079
  __insert_or_assign(const_iterator __hint, _Kp&& __key, _Mapped&& __mapped) {
1080
    auto __r = __try_emplace_hint(__hint, std::forward<_Kp>(__key), std::forward<_Mapped>(__mapped));
1081
    if (!__r.second) {
1082
      __r.first->second = std::forward<_Mapped>(__mapped);
1083
    }
1084
    return __r.first;
1085
  }
1086

1087
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __reserve(size_t __size) {
1088
    if constexpr (__container_traits<_KeyContainer>::__reservable) {
1089
      __containers_.keys.reserve(__size);
1090
    }
1091

1092
    if constexpr (__container_traits<_MappedContainer>::__reservable) {
1093
      __containers_.values.reserve(__size);
1094
    }
1095
  }
1096

1097
  template <class _KIter, class _MIter>
1098
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator
1099
  __erase(_KIter __key_iter_to_remove, _MIter __mapped_iter_to_remove) {
1100
    auto __on_failure  = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
1101
    auto __key_iter    = __containers_.keys.erase(__key_iter_to_remove);
1102
    auto __mapped_iter = __containers_.values.erase(__mapped_iter_to_remove);
1103
    __on_failure.__complete();
1104
    return iterator(std::move(__key_iter), std::move(__mapped_iter));
1105
  }
1106

1107
  template <class _Key2, class _Tp2, class _Compare2, class _KeyContainer2, class _MappedContainer2, class _Predicate>
1108
  friend typename flat_map<_Key2, _Tp2, _Compare2, _KeyContainer2, _MappedContainer2>::size_type
1109
      _LIBCPP_CONSTEXPR_SINCE_CXX26
1110
      erase_if(flat_map<_Key2, _Tp2, _Compare2, _KeyContainer2, _MappedContainer2>&, _Predicate);
1111

1112
  friend __flat_map_utils;
1113

1114
  containers __containers_;
1115
  _LIBCPP_NO_UNIQUE_ADDRESS key_compare __compare_;
1116

1117
  struct __key_equiv {
1118
    _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_equiv(key_compare __c) : __comp_(__c) {}
1119
    _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
1120
    operator()(const_reference __x, const_reference __y) const {
1121
      return !__comp_(std::get<0>(__x), std::get<0>(__y)) && !__comp_(std::get<0>(__y), std::get<0>(__x));
1122
    }
1123
    key_compare __comp_;
1124
  };
1125
};
1126

1127
template <class _KeyContainer, class _MappedContainer, class _Compare = less<typename _KeyContainer::value_type>>
1128
  requires(!__is_allocator<_Compare>::value && !__is_allocator<_KeyContainer>::value &&
1129
           !__is_allocator<_MappedContainer>::value &&
1130
           is_invocable_v<const _Compare&,
1131
                          const typename _KeyContainer::value_type&,
1132
                          const typename _KeyContainer::value_type&>)
1133
flat_map(_KeyContainer, _MappedContainer, _Compare = _Compare())
1134
    -> flat_map<typename _KeyContainer::value_type,
1135
                typename _MappedContainer::value_type,
1136
                _Compare,
1137
                _KeyContainer,
1138
                _MappedContainer>;
1139

1140
template <class _KeyContainer, class _MappedContainer, class _Allocator>
1141
  requires(uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator> &&
1142
           !__is_allocator<_KeyContainer>::value && !__is_allocator<_MappedContainer>::value)
1143
flat_map(_KeyContainer, _MappedContainer, _Allocator)
1144
    -> flat_map<typename _KeyContainer::value_type,
1145
                typename _MappedContainer::value_type,
1146
                less<typename _KeyContainer::value_type>,
1147
                _KeyContainer,
1148
                _MappedContainer>;
1149

1150
template <class _KeyContainer, class _MappedContainer, class _Compare, class _Allocator>
1151
  requires(!__is_allocator<_Compare>::value && !__is_allocator<_KeyContainer>::value &&
1152
           !__is_allocator<_MappedContainer>::value && uses_allocator_v<_KeyContainer, _Allocator> &&
1153
           uses_allocator_v<_MappedContainer, _Allocator> &&
1154
           is_invocable_v<const _Compare&,
1155
                          const typename _KeyContainer::value_type&,
1156
                          const typename _KeyContainer::value_type&>)
1157
flat_map(_KeyContainer, _MappedContainer, _Compare, _Allocator)
1158
    -> flat_map<typename _KeyContainer::value_type,
1159
                typename _MappedContainer::value_type,
1160
                _Compare,
1161
                _KeyContainer,
1162
                _MappedContainer>;
1163

1164
template <class _KeyContainer, class _MappedContainer, class _Compare = less<typename _KeyContainer::value_type>>
1165
  requires(!__is_allocator<_Compare>::value && !__is_allocator<_KeyContainer>::value &&
1166
           !__is_allocator<_MappedContainer>::value &&
1167
           is_invocable_v<const _Compare&,
1168
                          const typename _KeyContainer::value_type&,
1169
                          const typename _KeyContainer::value_type&>)
1170
flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Compare = _Compare())
1171
    -> flat_map<typename _KeyContainer::value_type,
1172
                typename _MappedContainer::value_type,
1173
                _Compare,
1174
                _KeyContainer,
1175
                _MappedContainer>;
1176

1177
template <class _KeyContainer, class _MappedContainer, class _Allocator>
1178
  requires(uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator> &&
1179
           !__is_allocator<_KeyContainer>::value && !__is_allocator<_MappedContainer>::value)
1180
flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Allocator)
1181
    -> flat_map<typename _KeyContainer::value_type,
1182
                typename _MappedContainer::value_type,
1183
                less<typename _KeyContainer::value_type>,
1184
                _KeyContainer,
1185
                _MappedContainer>;
1186

1187
template <class _KeyContainer, class _MappedContainer, class _Compare, class _Allocator>
1188
  requires(!__is_allocator<_Compare>::value && !__is_allocator<_KeyContainer>::value &&
1189
           !__is_allocator<_MappedContainer>::value && uses_allocator_v<_KeyContainer, _Allocator> &&
1190
           uses_allocator_v<_MappedContainer, _Allocator> &&
1191
           is_invocable_v<const _Compare&,
1192
                          const typename _KeyContainer::value_type&,
1193
                          const typename _KeyContainer::value_type&>)
1194
flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Compare, _Allocator)
1195
    -> flat_map<typename _KeyContainer::value_type,
1196
                typename _MappedContainer::value_type,
1197
                _Compare,
1198
                _KeyContainer,
1199
                _MappedContainer>;
1200

1201
template <class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>>
1202
  requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator<_Compare>::value)
1203
flat_map(_InputIterator, _InputIterator, _Compare = _Compare())
1204
    -> flat_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare>;
1205

1206
template <class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>>
1207
  requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator<_Compare>::value)
1208
flat_map(sorted_unique_t, _InputIterator, _InputIterator, _Compare = _Compare())
1209
    -> flat_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare>;
1210

1211
template <ranges::input_range _Range,
1212
          class _Compare   = less<__range_key_type<_Range>>,
1213
          class _Allocator = allocator<byte>,
1214
          class            = __enable_if_t<!__is_allocator<_Compare>::value && __is_allocator<_Allocator>::value>>
1215
flat_map(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator()) -> flat_map<
1216
    __range_key_type<_Range>,
1217
    __range_mapped_type<_Range>,
1218
    _Compare,
1219
    vector<__range_key_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_key_type<_Range>>>,
1220
    vector<__range_mapped_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_mapped_type<_Range>>>>;
1221

1222
template <ranges::input_range _Range, class _Allocator, class = __enable_if_t<__is_allocator<_Allocator>::value>>
1223
flat_map(from_range_t, _Range&&, _Allocator) -> flat_map<
1224
    __range_key_type<_Range>,
1225
    __range_mapped_type<_Range>,
1226
    less<__range_key_type<_Range>>,
1227
    vector<__range_key_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_key_type<_Range>>>,
1228
    vector<__range_mapped_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_mapped_type<_Range>>>>;
1229

1230
template <class _Key, class _Tp, class _Compare = less<_Key>>
1231
  requires(!__is_allocator<_Compare>::value)
1232
flat_map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare()) -> flat_map<_Key, _Tp, _Compare>;
1233

1234
template <class _Key, class _Tp, class _Compare = less<_Key>>
1235
  requires(!__is_allocator<_Compare>::value)
1236
flat_map(sorted_unique_t, initializer_list<pair<_Key, _Tp>>, _Compare = _Compare()) -> flat_map<_Key, _Tp, _Compare>;
1237

1238
template <class _Key, class _Tp, class _Compare, class _KeyContainer, class _MappedContainer, class _Allocator>
1239
struct uses_allocator<flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>, _Allocator>
1240
    : bool_constant<uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator>> {};
1241

1242
template <class _Key, class _Tp, class _Compare, class _KeyContainer, class _MappedContainer, class _Predicate>
1243
_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
1244
    typename flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>::size_type
1245
    erase_if(flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>& __flat_map, _Predicate __pred) {
1246
  auto __zv     = ranges::views::zip(__flat_map.__containers_.keys, __flat_map.__containers_.values);
1247
  auto __first  = __zv.begin();
1248
  auto __last   = __zv.end();
1249
  auto __guard  = std::__make_exception_guard([&] { __flat_map.clear(); });
1250
  auto __it     = std::remove_if(__first, __last, [&](auto&& __zipped) -> bool {
1251
    using _Ref = typename flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>::const_reference;
1252
    return __pred(_Ref(std::get<0>(__zipped), std::get<1>(__zipped)));
1253
  });
1254
  auto __res    = __last - __it;
1255
  auto __offset = __it - __first;
1256

1257
  const auto __erase_container = [&](auto& __cont) { __cont.erase(__cont.begin() + __offset, __cont.end()); };
1258

1259
  __erase_container(__flat_map.__containers_.keys);
1260
  __erase_container(__flat_map.__containers_.values);
1261

1262
  __guard.__complete();
1263
  return __res;
1264
}
1265

1266
_LIBCPP_END_NAMESPACE_STD
1267

1268
#endif // _LIBCPP_STD_VER >= 23
1269

1270
_LIBCPP_POP_MACROS
1271

1272
#endif // _LIBCPP___FLAT_MAP_FLAT_MAP_H
1273

1274
Product

Resources

Company
