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/is_transparent.h>
33#include <__functional/operations.h>
34#include <__fwd/memory.h>
35#include <__fwd/vector.h>
36#include <__iterator/concepts.h>
37#include <__iterator/distance.h>
38#include <__iterator/iterator_traits.h>
39#include <__iterator/next.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/range_adaptor.h>
51#include <__ranges/size.h>
52#include <__ranges/subrange.h>
53#include <__ranges/zip_view.h>
54#include <__type_traits/conjunction.h>
55#include <__type_traits/container_traits.h>
56#include <__type_traits/invoke.h>
57#include <__type_traits/is_allocator.h>
58#include <__type_traits/is_nothrow_constructible.h>
59#include <__type_traits/is_same.h>
60#include <__utility/exception_guard.h>
61#include <__utility/move.h>
62#include <__utility/pair.h>
63#include <__utility/scope_guard.h>
64#include <__vector/vector.h>
65#include <initializer_list>
66#include <stdexcept>
67
68#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
69# pragma GCC system_header
70#endif
71
72_LIBCPP_PUSH_MACROS
73#include <__undef_macros>
74
75#if _LIBCPP_STD_VER >= 23
76
77_LIBCPP_BEGIN_NAMESPACE_STD
78
79template <class _Key,
80 class _Tp,
81 class _Compare = less<_Key>,
82 class _KeyContainer = vector<_Key>,
83 class _MappedContainer = vector<_Tp>>
84class flat_map {
85 template <class, class, class, class, class>
86 friend class flat_map;
87
88 static_assert(is_same_v<_Key, typename _KeyContainer::value_type>);
89 static_assert(is_same_v<_Tp, typename _MappedContainer::value_type>);
90 static_assert(!is_same_v<_KeyContainer, std::vector<bool>>, "vector<bool> is not a sequence container");
91 static_assert(!is_same_v<_MappedContainer, std::vector<bool>>, "vector<bool> is not a sequence container");
92
93 template <bool _Const>
94 using __iterator _LIBCPP_NODEBUG = __key_value_iterator<flat_map, _KeyContainer, _MappedContainer, _Const>;
95
96public:
97 // types
98 using key_type = _Key;
99 using mapped_type = _Tp;
100 using value_type = pair<key_type, mapped_type>;
101 using key_compare = __type_identity_t<_Compare>;
102 using reference = pair<const key_type&, mapped_type&>;
103 using const_reference = pair<const key_type&, const mapped_type&>;
104 using size_type = size_t;
105 using difference_type = ptrdiff_t;
106 using iterator = __iterator<false>; // see [container.requirements]
107 using const_iterator = __iterator<true>; // see [container.requirements]
108 using reverse_iterator = std::reverse_iterator<iterator>;
109 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
110 using key_container_type = _KeyContainer;
111 using mapped_container_type = _MappedContainer;
112
113 class value_compare {
114 private:
115 _LIBCPP_NO_UNIQUE_ADDRESS key_compare __comp_;
116 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 value_compare(key_compare __c) : __comp_(__c) {}
117 friend flat_map;
118
119 public:
120 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
121 operator()(const_reference __x, const_reference __y) const {
122 return __comp_(__x.first, __y.first);
123 }
124 };
125
126 struct containers {
127 key_container_type keys;
128 mapped_container_type values;
129 };
130
131private:
132 template <class _Allocator>
133 _LIBCPP_HIDE_FROM_ABI static constexpr bool __allocator_ctor_constraint =
134 _And<uses_allocator<key_container_type, _Allocator>, uses_allocator<mapped_container_type, _Allocator>>::value;
135
136 _LIBCPP_HIDE_FROM_ABI static constexpr bool __is_compare_transparent = __is_transparent_v<_Compare>;
137
138public:
139 // [flat.map.cons], construct/copy/destroy
140 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map() noexcept(
141 is_nothrow_default_constructible_v<_KeyContainer> && is_nothrow_default_constructible_v<_MappedContainer> &&
142 is_nothrow_default_constructible_v<_Compare>)
143 : __containers_(), __compare_() {}
144
145 _LIBCPP_HIDE_FROM_ABI flat_map(const flat_map&) = default;
146
147 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(flat_map&& __other) noexcept(
148 is_nothrow_move_constructible_v<_KeyContainer> && is_nothrow_move_constructible_v<_MappedContainer> &&
149 is_nothrow_move_constructible_v<_Compare>)
150# if _LIBCPP_HAS_EXCEPTIONS
151 try
152# endif // _LIBCPP_HAS_EXCEPTIONS
153 : __containers_(std::move(__other.__containers_)), __compare_(std::move(__other.__compare_)) {
154 __other.clear();
155# if _LIBCPP_HAS_EXCEPTIONS
156 } catch (...) {
157 __other.clear();
158 // gcc does not like the `throw` keyword in a conditionally noexcept function
159 if constexpr (!(is_nothrow_move_constructible_v<_KeyContainer> &&
160 is_nothrow_move_constructible_v<_MappedContainer> && is_nothrow_move_constructible_v<_Compare>)) {
161 throw;
162 }
163# endif // _LIBCPP_HAS_EXCEPTIONS
164 }
165
166 template <class _Allocator>
167 requires __allocator_ctor_constraint<_Allocator>
168 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(const flat_map& __other, const _Allocator& __alloc)
169 : flat_map(__ctor_uses_allocator_tag{},
170 __alloc,
171 __other.__containers_.keys,
172 __other.__containers_.values,
173 __other.__compare_) {}
174
175 template <class _Allocator>
176 requires __allocator_ctor_constraint<_Allocator>
177 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(flat_map&& __other, const _Allocator& __alloc)
178# if _LIBCPP_HAS_EXCEPTIONS
179 try
180# endif // _LIBCPP_HAS_EXCEPTIONS
181 : flat_map(__ctor_uses_allocator_tag{},
182 __alloc,
183 std::move(__other.__containers_.keys),
184 std::move(__other.__containers_.values),
185 std::move(__other.__compare_)) {
186 __other.clear();
187# if _LIBCPP_HAS_EXCEPTIONS
188 } catch (...) {
189 __other.clear();
190 throw;
191# endif // _LIBCPP_HAS_EXCEPTIONS
192 }
193
194 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(
195 key_container_type __key_cont, mapped_container_type __mapped_cont, const key_compare& __comp = key_compare())
196 : __containers_{.keys = std::move(__key_cont), .values = std::move(__mapped_cont)}, __compare_(__comp) {
197 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
198 "flat_map keys and mapped containers have different size");
199 __sort_and_unique();
200 }
201
202 template <class _Allocator>
203 requires __allocator_ctor_constraint<_Allocator>
204 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
205 flat_map(const key_container_type& __key_cont, const mapped_container_type& __mapped_cont, const _Allocator& __alloc)
206 : flat_map(__ctor_uses_allocator_tag{}, __alloc, __key_cont, __mapped_cont) {
207 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
208 "flat_map keys and mapped containers have different size");
209 __sort_and_unique();
210 }
211
212 template <class _Allocator>
213 requires __allocator_ctor_constraint<_Allocator>
214 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
215 flat_map(const key_container_type& __key_cont,
216 const mapped_container_type& __mapped_cont,
217 const key_compare& __comp,
218 const _Allocator& __alloc)
219 : flat_map(__ctor_uses_allocator_tag{}, __alloc, __key_cont, __mapped_cont, __comp) {
220 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
221 "flat_map keys and mapped containers have different size");
222 __sort_and_unique();
223 }
224
225 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
226 flat_map(sorted_unique_t,
227 key_container_type __key_cont,
228 mapped_container_type __mapped_cont,
229 const key_compare& __comp = key_compare())
230 : __containers_{.keys = std::move(__key_cont), .values = std::move(__mapped_cont)}, __compare_(__comp) {
231 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
232 "flat_map keys and mapped containers have different size");
233 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
234 __is_sorted_and_unique(__containers_.keys), "Either the key container is not sorted or it contains duplicates");
235 }
236
237 template <class _Allocator>
238 requires __allocator_ctor_constraint<_Allocator>
239 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
240 flat_map(sorted_unique_t,
241 const key_container_type& __key_cont,
242 const mapped_container_type& __mapped_cont,
243 const _Allocator& __alloc)
244 : flat_map(__ctor_uses_allocator_tag{}, __alloc, __key_cont, __mapped_cont) {
245 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
246 "flat_map keys and mapped containers have different size");
247 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
248 __is_sorted_and_unique(__containers_.keys), "Either the key container is not sorted or it contains duplicates");
249 }
250
251 template <class _Allocator>
252 requires __allocator_ctor_constraint<_Allocator>
253 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(
254 sorted_unique_t,
255 const key_container_type& __key_cont,
256 const mapped_container_type& __mapped_cont,
257 const key_compare& __comp,
258 const _Allocator& __alloc)
259 : flat_map(__ctor_uses_allocator_tag{}, __alloc, __key_cont, __mapped_cont, __comp) {
260 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
261 "flat_map keys and mapped containers have different size");
262 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
263 __is_sorted_and_unique(__containers_.keys), "Either the key container is not sorted or it contains duplicates");
264 }
265
266 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit flat_map(const key_compare& __comp)
267 : __containers_(), __compare_(__comp) {}
268
269 template <class _Allocator>
270 requires __allocator_ctor_constraint<_Allocator>
271 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(const key_compare& __comp, const _Allocator& __alloc)
272 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) {}
273
274 template <class _Allocator>
275 requires __allocator_ctor_constraint<_Allocator>
276 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit flat_map(const _Allocator& __alloc)
277 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc) {}
278
279 template <class _InputIterator>
280 requires __has_input_iterator_category<_InputIterator>::value
281 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
282 flat_map(_InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare())
283 : __containers_(), __compare_(__comp) {
284 insert(__first, __last);
285 }
286
287 template <class _InputIterator, class _Allocator>
288 requires(__has_input_iterator_category<_InputIterator>::value && __allocator_ctor_constraint<_Allocator>)
289 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
290 flat_map(_InputIterator __first, _InputIterator __last, const key_compare& __comp, const _Allocator& __alloc)
291 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) {
292 insert(__first, __last);
293 }
294
295 template <class _InputIterator, class _Allocator>
296 requires(__has_input_iterator_category<_InputIterator>::value && __allocator_ctor_constraint<_Allocator>)
297 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
298 flat_map(_InputIterator __first, _InputIterator __last, const _Allocator& __alloc)
299 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc) {
300 insert(__first, __last);
301 }
302
303 template <_ContainerCompatibleRange<value_type> _Range>
304 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(from_range_t __fr, _Range&& __rg)
305 : flat_map(__fr, std::forward<_Range>(__rg), key_compare()) {}
306
307 template <_ContainerCompatibleRange<value_type> _Range, class _Allocator>
308 requires __allocator_ctor_constraint<_Allocator>
309 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(from_range_t, _Range&& __rg, const _Allocator& __alloc)
310 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc) {
311 insert_range(std::forward<_Range>(__rg));
312 }
313
314 template <_ContainerCompatibleRange<value_type> _Range>
315 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(from_range_t, _Range&& __rg, const key_compare& __comp)
316 : flat_map(__comp) {
317 insert_range(std::forward<_Range>(__rg));
318 }
319
320 template <_ContainerCompatibleRange<value_type> _Range, class _Allocator>
321 requires __allocator_ctor_constraint<_Allocator>
322 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
323 flat_map(from_range_t, _Range&& __rg, const key_compare& __comp, const _Allocator& __alloc)
324 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) {
325 insert_range(std::forward<_Range>(__rg));
326 }
327
328 template <class _InputIterator>
329 requires __has_input_iterator_category<_InputIterator>::value
330 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
331 flat_map(sorted_unique_t, _InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare())
332 : __containers_(), __compare_(__comp) {
333 insert(sorted_unique, __first, __last);
334 }
335 template <class _InputIterator, class _Allocator>
336 requires(__has_input_iterator_category<_InputIterator>::value && __allocator_ctor_constraint<_Allocator>)
337 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(
338 sorted_unique_t,
339 _InputIterator __first,
340 _InputIterator __last,
341 const key_compare& __comp,
342 const _Allocator& __alloc)
343 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) {
344 insert(sorted_unique, __first, __last);
345 }
346
347 template <class _InputIterator, class _Allocator>
348 requires(__has_input_iterator_category<_InputIterator>::value && __allocator_ctor_constraint<_Allocator>)
349 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
350 flat_map(sorted_unique_t, _InputIterator __first, _InputIterator __last, const _Allocator& __alloc)
351 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc) {
352 insert(sorted_unique, __first, __last);
353 }
354
355 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
356 flat_map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
357 : flat_map(__il.begin(), __il.end(), __comp) {}
358
359 template <class _Allocator>
360 requires __allocator_ctor_constraint<_Allocator>
361 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
362 flat_map(initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc)
363 : flat_map(__il.begin(), __il.end(), __comp, __alloc) {}
364
365 template <class _Allocator>
366 requires __allocator_ctor_constraint<_Allocator>
367 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
368 flat_map(initializer_list<value_type> __il, const _Allocator& __alloc)
369 : flat_map(__il.begin(), __il.end(), __alloc) {}
370
371 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
372 flat_map(sorted_unique_t, initializer_list<value_type> __il, const key_compare& __comp = key_compare())
373 : flat_map(sorted_unique, __il.begin(), __il.end(), __comp) {}
374
375 template <class _Allocator>
376 requires __allocator_ctor_constraint<_Allocator>
377 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
378 flat_map(sorted_unique_t, initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc)
379 : flat_map(sorted_unique, __il.begin(), __il.end(), __comp, __alloc) {}
380
381 template <class _Allocator>
382 requires __allocator_ctor_constraint<_Allocator>
383 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
384 flat_map(sorted_unique_t, initializer_list<value_type> __il, const _Allocator& __alloc)
385 : flat_map(sorted_unique, __il.begin(), __il.end(), __alloc) {}
386
387 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map& operator=(initializer_list<value_type> __il) {
388 clear();
389 insert(__il);
390 return *this;
391 }
392
393 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map& operator=(const flat_map&) = default;
394
395 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map& operator=(flat_map&& __other) noexcept(
396 is_nothrow_move_assignable_v<_KeyContainer> && is_nothrow_move_assignable_v<_MappedContainer> &&
397 is_nothrow_move_assignable_v<_Compare>) {
398 // No matter what happens, we always want to clear the other container before returning
399 // since we moved from it
400 auto __clear_other_guard = std::__make_scope_guard([&]() noexcept { __other.clear() /* noexcept */; });
401 {
402 // If an exception is thrown, we have no choice but to clear *this to preserve invariants
403 auto __on_exception = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
404 __containers_ = std::move(__other.__containers_);
405 __compare_ = std::move(__other.__compare_);
406 __on_exception.__complete();
407 }
408 return *this;
409 }
410
411 // iterators
412 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator begin() noexcept {
413 return iterator(__containers_.keys.begin(), __containers_.values.begin());
414 }
415
416 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator begin() const noexcept {
417 return const_iterator(__containers_.keys.begin(), __containers_.values.begin());
418 }
419
420 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator end() noexcept {
421 return iterator(__containers_.keys.end(), __containers_.values.end());
422 }
423
424 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator end() const noexcept {
425 return const_iterator(__containers_.keys.end(), __containers_.values.end());
426 }
427
428 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 reverse_iterator rbegin() noexcept {
429 return reverse_iterator(end());
430 }
431 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator rbegin() const noexcept {
432 return const_reverse_iterator(end());
433 }
434 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 reverse_iterator rend() noexcept {
435 return reverse_iterator(begin());
436 }
437 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator rend() const noexcept {
438 return const_reverse_iterator(begin());
439 }
440
441 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator cbegin() const noexcept {
442 return begin();
443 }
444 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator cend() const noexcept {
445 return end();
446 }
447 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator crbegin() const noexcept {
448 return const_reverse_iterator(end());
449 }
450 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator crend() const noexcept {
451 return const_reverse_iterator(begin());
452 }
453
454 // [flat.map.capacity], capacity
455 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool empty() const noexcept {
456 return __containers_.keys.empty();
457 }
458
459 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type size() const noexcept {
460 return __containers_.keys.size();
461 }
462
463 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type max_size() const noexcept {
464 return std::min<size_type>(__containers_.keys.max_size(), __containers_.values.max_size());
465 }
466
467 // [flat.map.access], element access
468 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 mapped_type& operator[](const key_type& __x)
469 requires is_constructible_v<mapped_type>
470 {
471 return try_emplace(__x).first->second;
472 }
473
474 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 mapped_type& operator[](key_type&& __x)
475 requires is_constructible_v<mapped_type>
476 {
477 return try_emplace(std::move(__x)).first->second;
478 }
479
480 template <class _Kp>
481 requires(__is_compare_transparent && is_constructible_v<key_type, _Kp> && is_constructible_v<mapped_type> &&
482 !is_convertible_v<_Kp &&, const_iterator> && !is_convertible_v<_Kp &&, iterator>)
483 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 mapped_type& operator[](_Kp&& __x) {
484 return try_emplace(std::forward<_Kp>(__x)).first->second;
485 }
486
487 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 mapped_type& at(const key_type& __x) {
488 auto __it = find(__x);
489 if (__it == end()) {
490 std::__throw_out_of_range("flat_map::at(const key_type&): Key does not exist");
491 }
492 return __it->second;
493 }
494
495 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const mapped_type& at(const key_type& __x) const {
496 auto __it = find(__x);
497 if (__it == end()) {
498 std::__throw_out_of_range("flat_map::at(const key_type&) const: Key does not exist");
499 }
500 return __it->second;
501 }
502
503 template <class _Kp>
504 requires __is_compare_transparent
505 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 mapped_type& at(const _Kp& __x) {
506 auto __it = find(__x);
507 if (__it == end()) {
508 std::__throw_out_of_range("flat_map::at(const K&): Key does not exist");
509 }
510 return __it->second;
511 }
512
513 template <class _Kp>
514 requires __is_compare_transparent
515 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const mapped_type& at(const _Kp& __x) const {
516 auto __it = find(__x);
517 if (__it == end()) {
518 std::__throw_out_of_range("flat_map::at(const K&) const: Key does not exist");
519 }
520 return __it->second;
521 }
522
523 // [flat.map.modifiers], modifiers
524 template <class... _Args>
525 requires is_constructible_v<pair<key_type, mapped_type>, _Args...>
526 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> emplace(_Args&&... __args) {
527 std::pair<key_type, mapped_type> __pair(std::forward<_Args>(__args)...);
528 return __try_emplace(std::move(__pair.first), std::move(__pair.second));
529 }
530
531 template <class... _Args>
532 requires is_constructible_v<pair<key_type, mapped_type>, _Args...>
533 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator emplace_hint(const_iterator __hint, _Args&&... __args) {
534 std::pair<key_type, mapped_type> __pair(std::forward<_Args>(__args)...);
535 return __try_emplace_hint(__hint, std::move(__pair.first), std::move(__pair.second)).first;
536 }
537
538 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> insert(const value_type& __x) {
539 return emplace(__x);
540 }
541
542 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> insert(value_type&& __x) {
543 return emplace(std::move(__x));
544 }
545
546 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __hint, const value_type& __x) {
547 return emplace_hint(__hint, __x);
548 }
549
550 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __hint, value_type&& __x) {
551 return emplace_hint(__hint, std::move(__x));
552 }
553
554 template <class _PairLike>
555 requires is_constructible_v<pair<key_type, mapped_type>, _PairLike>
556 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> insert(_PairLike&& __x) {
557 return emplace(std::forward<_PairLike>(__x));
558 }
559
560 template <class _PairLike>
561 requires is_constructible_v<pair<key_type, mapped_type>, _PairLike>
562 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __hint, _PairLike&& __x) {
563 return emplace_hint(__hint, std::forward<_PairLike>(__x));
564 }
565
566 template <class _InputIterator>
567 requires __has_input_iterator_category<_InputIterator>::value
568 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(_InputIterator __first, _InputIterator __last) {
569 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) {
570 __reserve(__last - __first);
571 }
572 __append_sort_merge_unique</*WasSorted = */ false>(std::move(__first), std::move(__last));
573 }
574
575 template <class _InputIterator>
576 requires __has_input_iterator_category<_InputIterator>::value
577 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
578 insert(sorted_unique_t, _InputIterator __first, _InputIterator __last) {
579 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) {
580 __reserve(__last - __first);
581 }
582
583 __append_sort_merge_unique</*WasSorted = */ true>(std::move(__first), std::move(__last));
584 }
585
586 template <_ContainerCompatibleRange<value_type> _Range>
587 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert_range(_Range&& __range) {
588 if constexpr (ranges::sized_range<_Range>) {
589 __reserve(ranges::size(__range));
590 }
591
592 __append_sort_merge_unique</*WasSorted = */ false>(ranges::begin(__range), ranges::end(__range));
593 }
594
595 template <_ContainerCompatibleRange<value_type> _Range>
596 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert_range(sorted_unique_t, _Range&& __range) {
597 if constexpr (ranges::sized_range<_Range>) {
598 __reserve(ranges::size(__range));
599 }
600
601 __append_sort_merge_unique</*WasSorted = */ true>(ranges::begin(__range), ranges::end(__range));
602 }
603
604 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(initializer_list<value_type> __il) {
605 insert(__il.begin(), __il.end());
606 }
607
608 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(sorted_unique_t, initializer_list<value_type> __il) {
609 insert(sorted_unique, __il.begin(), __il.end());
610 }
611
612 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 containers extract() && {
613 auto __guard = std::__make_scope_guard([&]() noexcept { clear() /* noexcept */; });
614 auto __ret = std::move(__containers_);
615 return __ret;
616 }
617
618 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
619 replace(key_container_type&& __key_cont, mapped_container_type&& __mapped_cont) {
620 _LIBCPP_ASSERT_VALID_INPUT_RANGE(
621 __key_cont.size() == __mapped_cont.size(), "flat_map keys and mapped containers have different size");
622
623 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
624 __is_sorted_and_unique(__key_cont), "Either the key container is not sorted or it contains duplicates");
625 auto __guard = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
626 __containers_.keys = std::move(__key_cont);
627 __containers_.values = std::move(__mapped_cont);
628 __guard.__complete();
629 }
630
631 template <class... _Args>
632 requires is_constructible_v<mapped_type, _Args...>
633 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool>
634 try_emplace(const key_type& __key, _Args&&... __args) {
635 return __try_emplace(__key, std::forward<_Args>(__args)...);
636 }
637
638 template <class... _Args>
639 requires is_constructible_v<mapped_type, _Args...>
640 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool>
641 try_emplace(key_type&& __key, _Args&&... __args) {
642 return __try_emplace(std::move(__key), std::forward<_Args>(__args)...);
643 }
644
645 template <class _Kp, class... _Args>
646 requires(__is_compare_transparent && is_constructible_v<key_type, _Kp> &&
647 is_constructible_v<mapped_type, _Args...> && !is_convertible_v<_Kp &&, const_iterator> &&
648 !is_convertible_v<_Kp &&, iterator>)
649 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> try_emplace(_Kp&& __key, _Args&&... __args) {
650 return __try_emplace(std::forward<_Kp>(__key), std::forward<_Args>(__args)...);
651 }
652
653 template <class... _Args>
654 requires is_constructible_v<mapped_type, _Args...>
655 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator
656 try_emplace(const_iterator __hint, const key_type& __key, _Args&&... __args) {
657 return __try_emplace_hint(__hint, __key, std::forward<_Args>(__args)...).first;
658 }
659
660 template <class... _Args>
661 requires is_constructible_v<mapped_type, _Args...>
662 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator
663 try_emplace(const_iterator __hint, key_type&& __key, _Args&&... __args) {
664 return __try_emplace_hint(__hint, std::move(__key), std::forward<_Args>(__args)...).first;
665 }
666
667 template <class _Kp, class... _Args>
668 requires __is_compare_transparent && is_constructible_v<key_type, _Kp> && is_constructible_v<mapped_type, _Args...>
669 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator
670 try_emplace(const_iterator __hint, _Kp&& __key, _Args&&... __args) {
671 return __try_emplace_hint(__hint, std::forward<_Kp>(__key), std::forward<_Args>(__args)...).first;
672 }
673
674 template <class _Mapped>
675 requires is_assignable_v<mapped_type&, _Mapped> && is_constructible_v<mapped_type, _Mapped>
676 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool>
677 insert_or_assign(const key_type& __key, _Mapped&& __obj) {
678 return __insert_or_assign(__key, std::forward<_Mapped>(__obj));
679 }
680
681 template <class _Mapped>
682 requires is_assignable_v<mapped_type&, _Mapped> && is_constructible_v<mapped_type, _Mapped>
683 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool>
684 insert_or_assign(key_type&& __key, _Mapped&& __obj) {
685 return __insert_or_assign(std::move(__key), std::forward<_Mapped>(__obj));
686 }
687
688 template <class _Kp, class _Mapped>
689 requires __is_compare_transparent && is_constructible_v<key_type, _Kp> && is_assignable_v<mapped_type&, _Mapped> &&
690 is_constructible_v<mapped_type, _Mapped>
691 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool>
692 insert_or_assign(_Kp&& __key, _Mapped&& __obj) {
693 return __insert_or_assign(std::forward<_Kp>(__key), std::forward<_Mapped>(__obj));
694 }
695
696 template <class _Mapped>
697 requires is_assignable_v<mapped_type&, _Mapped> && is_constructible_v<mapped_type, _Mapped>
698 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator
699 insert_or_assign(const_iterator __hint, const key_type& __key, _Mapped&& __obj) {
700 return __insert_or_assign(__hint, __key, std::forward<_Mapped>(__obj));
701 }
702
703 template <class _Mapped>
704 requires is_assignable_v<mapped_type&, _Mapped> && is_constructible_v<mapped_type, _Mapped>
705 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator
706 insert_or_assign(const_iterator __hint, key_type&& __key, _Mapped&& __obj) {
707 return __insert_or_assign(__hint, std::move(__key), std::forward<_Mapped>(__obj));
708 }
709
710 template <class _Kp, class _Mapped>
711 requires __is_compare_transparent && is_constructible_v<key_type, _Kp> && is_assignable_v<mapped_type&, _Mapped> &&
712 is_constructible_v<mapped_type, _Mapped>
713 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator
714 insert_or_assign(const_iterator __hint, _Kp&& __key, _Mapped&& __obj) {
715 return __insert_or_assign(__hint, std::forward<_Kp>(__key), std::forward<_Mapped>(__obj));
716 }
717
718 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator erase(iterator __position) {
719 return __erase(__position.__key_iter_, __position.__mapped_iter_);
720 }
721
722 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator erase(const_iterator __position) {
723 return __erase(__position.__key_iter_, __position.__mapped_iter_);
724 }
725
726 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type erase(const key_type& __x) {
727 auto __iter = find(__x);
728 if (__iter != end()) {
729 erase(__iter);
730 return 1;
731 }
732 return 0;
733 }
734
735 template <class _Kp>
736 requires(__is_compare_transparent && !is_convertible_v<_Kp &&, iterator> &&
737 !is_convertible_v<_Kp &&, const_iterator>)
738 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type erase(_Kp&& __x) {
739 auto [__first, __last] = equal_range(__x);
740 auto __res = __last - __first;
741 erase(__first, __last);
742 return __res;
743 }
744
745 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator erase(const_iterator __first, const_iterator __last) {
746 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
747 auto __key_it = __containers_.keys.erase(__first.__key_iter_, __last.__key_iter_);
748 auto __mapped_it = __containers_.values.erase(__first.__mapped_iter_, __last.__mapped_iter_);
749 __on_failure.__complete();
750 return iterator(std::move(__key_it), std::move(__mapped_it));
751 }
752
753 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
754 swap(flat_map& __y) noexcept(is_nothrow_swappable_v<key_container_type> &&
755 is_nothrow_swappable_v<mapped_container_type> && is_nothrow_swappable_v<key_compare>) {
756 auto __on_failure = std::__make_exception_guard([&]() noexcept {
757 clear() /* noexcept */;
758 __y.clear() /* noexcept */;
759 });
760 ranges::swap(__compare_, __y.__compare_);
761 ranges::swap(__containers_.keys, __y.__containers_.keys);
762 ranges::swap(__containers_.values, __y.__containers_.values);
763 __on_failure.__complete();
764 }
765
766 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void clear() noexcept {
767 __containers_.keys.clear();
768 __containers_.values.clear();
769 }
770
771 // observers
772 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 key_compare key_comp() const { return __compare_; }
773 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 value_compare value_comp() const {
774 return value_compare(__compare_);
775 }
776
777 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const key_container_type& keys() const noexcept {
778 return __containers_.keys;
779 }
780 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const mapped_container_type&
781 values() const noexcept {
782 return __containers_.values;
783 }
784
785 // map operations
786 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator find(const key_type& __x) {
787 return __find_impl(*this, __x);
788 }
789
790 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator find(const key_type& __x) const {
791 return __find_impl(*this, __x);
792 }
793
794 template <class _Kp>
795 requires __is_compare_transparent
796 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator find(const _Kp& __x) {
797 return __find_impl(*this, __x);
798 }
799
800 template <class _Kp>
801 requires __is_compare_transparent
802 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator find(const _Kp& __x) const {
803 return __find_impl(*this, __x);
804 }
805
806 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type count(const key_type& __x) const {
807 return contains(__x) ? 1 : 0;
808 }
809
810 template <class _Kp>
811 requires __is_compare_transparent
812 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type count(const _Kp& __x) const {
813 return contains(__x) ? 1 : 0;
814 }
815
816 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool contains(const key_type& __x) const {
817 return find(__x) != end();
818 }
819
820 template <class _Kp>
821 requires __is_compare_transparent
822 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool contains(const _Kp& __x) const {
823 return find(__x) != end();
824 }
825
826 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator lower_bound(const key_type& __x) {
827 return __lower_bound<iterator>(*this, __x);
828 }
829
830 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator
831 lower_bound(const key_type& __x) const {
832 return __lower_bound<const_iterator>(*this, __x);
833 }
834
835 template <class _Kp>
836 requires __is_compare_transparent
837 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator lower_bound(const _Kp& __x) {
838 return __lower_bound<iterator>(*this, __x);
839 }
840
841 template <class _Kp>
842 requires __is_compare_transparent
843 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator lower_bound(const _Kp& __x) const {
844 return __lower_bound<const_iterator>(*this, __x);
845 }
846
847 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator upper_bound(const key_type& __x) {
848 return __upper_bound<iterator>(*this, __x);
849 }
850
851 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator
852 upper_bound(const key_type& __x) const {
853 return __upper_bound<const_iterator>(*this, __x);
854 }
855
856 template <class _Kp>
857 requires __is_compare_transparent
858 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator upper_bound(const _Kp& __x) {
859 return __upper_bound<iterator>(*this, __x);
860 }
861
862 template <class _Kp>
863 requires __is_compare_transparent
864 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator upper_bound(const _Kp& __x) const {
865 return __upper_bound<const_iterator>(*this, __x);
866 }
867
868 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, iterator>
869 equal_range(const key_type& __x) {
870 return __equal_range_impl(*this, __x);
871 }
872
873 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<const_iterator, const_iterator>
874 equal_range(const key_type& __x) const {
875 return __equal_range_impl(*this, __x);
876 }
877
878 template <class _Kp>
879 requires __is_compare_transparent
880 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, iterator>
881 equal_range(const _Kp& __x) {
882 return __equal_range_impl(*this, __x);
883 }
884 template <class _Kp>
885 requires __is_compare_transparent
886 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<const_iterator, const_iterator>
887 equal_range(const _Kp& __x) const {
888 return __equal_range_impl(*this, __x);
889 }
890
891 friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool operator==(const flat_map& __x, const flat_map& __y) {
892 return ranges::equal(__x, __y);
893 }
894
895 friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 auto
896 operator<=>(const flat_map& __x, const flat_map& __y) {
897 return std::lexicographical_compare_three_way(
898 __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
899 }
900
901 friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
902 swap(flat_map& __x, flat_map& __y) noexcept(noexcept(__x.swap(__y))) {
903 __x.swap(__y);
904 }
905
906private:
907 struct __ctor_uses_allocator_tag {
908 explicit _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __ctor_uses_allocator_tag() = default;
909 };
910 struct __ctor_uses_allocator_empty_tag {
911 explicit _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __ctor_uses_allocator_empty_tag() = default;
912 };
913
914 template <class _Allocator, class _KeyCont, class _MappedCont, class... _CompArg>
915 requires __allocator_ctor_constraint<_Allocator>
916 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(
917 __ctor_uses_allocator_tag,
918 const _Allocator& __alloc,
919 _KeyCont&& __key_cont,
920 _MappedCont&& __mapped_cont,
921 _CompArg&&... __comp)
922 : __containers_{.keys = std::make_obj_using_allocator<key_container_type>(
923 __alloc, std::forward<_KeyCont>(__key_cont)),
924 .values = std::make_obj_using_allocator<mapped_container_type>(
925 __alloc, std::forward<_MappedCont>(__mapped_cont))},
926 __compare_(std::forward<_CompArg>(__comp)...) {}
927
928 template <class _Allocator, class... _CompArg>
929 requires __allocator_ctor_constraint<_Allocator>
930 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
931 flat_map(__ctor_uses_allocator_empty_tag, const _Allocator& __alloc, _CompArg&&... __comp)
932 : __containers_{.keys = std::make_obj_using_allocator<key_container_type>(__alloc),
933 .values = std::make_obj_using_allocator<mapped_container_type>(__alloc)},
934 __compare_(std::forward<_CompArg>(__comp)...) {}
935
936 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool __is_sorted_and_unique(auto&& __key_container) const {
937 auto __greater_or_equal_to = [this](const auto& __x, const auto& __y) -> bool { return !__compare_(__x, __y); };
938 return ranges::adjacent_find(__key_container, __greater_or_equal_to) == ranges::end(__key_container);
939 }
940
941 // This function is only used in constructors. So there is not exception handling in this function.
942 // If the function exits via an exception, there will be no flat_map object constructed, thus, there
943 // is no invariant state to preserve
944 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __sort_and_unique() {
945 auto __zv = ranges::views::zip(__containers_.keys, __containers_.values);
946 ranges::sort(__zv, __compare_, [](const auto& __p) -> decltype(auto) { return std::get<0>(__p); });
947 auto __dup_start = ranges::unique(__zv, __key_equiv(__compare_)).begin();
948 auto __dist = ranges::distance(__zv.begin(), __dup_start);
949 __containers_.keys.erase(__containers_.keys.begin() + __dist, __containers_.keys.end());
950 __containers_.values.erase(__containers_.values.begin() + __dist, __containers_.values.end());
951 }
952
953 template <class _Self, class _KeyIter>
954 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto
955 __corresponding_mapped_it(_Self&& __self, _KeyIter&& __key_iter) {
956 return __self.__containers_.values.begin() +
957 static_cast<ranges::range_difference_t<mapped_container_type>>(
958 ranges::distance(__self.__containers_.keys.begin(), __key_iter));
959 }
960
961 template <bool _WasSorted, class _InputIterator, class _Sentinel>
962 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
963 __append_sort_merge_unique(_InputIterator __first, _Sentinel __last) {
964 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
965 size_t __num_of_appended = __flat_map_utils::__append(*this, std::move(__first), std::move(__last));
966 if (__num_of_appended != 0) {
967 auto __zv = ranges::views::zip(__containers_.keys, __containers_.values);
968 auto __append_start_offset = __containers_.keys.size() - __num_of_appended;
969 auto __end = __zv.end();
970 auto __compare_key = [this](const auto& __p1, const auto& __p2) -> bool {
971 return __compare_(std::get<0>(__p1), std::get<0>(__p2));
972 };
973 if constexpr (!_WasSorted) {
974 ranges::sort(__zv.begin() + __append_start_offset, __end, __compare_key);
975 } else {
976 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
977 __is_sorted_and_unique(__containers_.keys | ranges::views::drop(__append_start_offset)),
978 "Either the key container is not sorted or it contains duplicates");
979 }
980 ranges::inplace_merge(__zv.begin(), __zv.begin() + __append_start_offset, __end, __compare_key);
981
982 auto __dup_start = ranges::unique(__zv, __key_equiv(__compare_)).begin();
983 auto __dist = ranges::distance(__zv.begin(), __dup_start);
984 __containers_.keys.erase(__containers_.keys.begin() + __dist, __containers_.keys.end());
985 __containers_.values.erase(__containers_.values.begin() + __dist, __containers_.values.end());
986 }
987 __on_failure.__complete();
988 }
989
990 template <class _Self, class _Kp>
991 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto __find_impl(_Self&& __self, const _Kp& __key) {
992 auto __it = __self.lower_bound(__key);
993 auto __last = __self.end();
994 if (__it == __last || __self.__compare_(__key, __it->first)) {
995 return __last;
996 }
997 return __it;
998 }
999
1000 template <class _Self, class _Kp>
1001 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto __key_equal_range(_Self&& __self, const _Kp& __key) {
1002 auto __it =
1003 std::lower_bound(__self.__containers_.keys.begin(), __self.__containers_.keys.end(), __key, __self.__compare_);
1004 auto __last = __self.__containers_.keys.end();
1005 if (__it == __last || __self.__compare_(__key, *__it)) {
1006 return std::make_pair(__it, __it);
1007 }
1008 return std::make_pair(__it, std::next(__it));
1009 }
1010
1011 template <class _Self, class _Kp>
1012 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto __equal_range_impl(_Self&& __self, const _Kp& __key) {
1013 auto [__key_first, __key_last] = __key_equal_range(__self, __key);
1014 using __iterator_type = ranges::iterator_t<decltype(__self)>;
1015 return std::make_pair(__iterator_type(__key_first, __corresponding_mapped_it(__self, __key_first)),
1016 __iterator_type(__key_last, __corresponding_mapped_it(__self, __key_last)));
1017 }
1018
1019 template <class _Res, class _Self, class _Kp>
1020 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static _Res __lower_bound(_Self&& __self, _Kp& __x) {
1021 auto __key_iter =
1022 std::lower_bound(__self.__containers_.keys.begin(), __self.__containers_.keys.end(), __x, __self.__compare_);
1023 auto __mapped_iter = __corresponding_mapped_it(__self, __key_iter);
1024 return _Res(std::move(__key_iter), std::move(__mapped_iter));
1025 }
1026
1027 template <class _Res, class _Self, class _Kp>
1028 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static _Res __upper_bound(_Self&& __self, _Kp& __x) {
1029 auto __key_iter =
1030 std::upper_bound(__self.__containers_.keys.begin(), __self.__containers_.keys.end(), __x, __self.__compare_);
1031 auto __mapped_iter = __corresponding_mapped_it(__self, __key_iter);
1032 return _Res(std::move(__key_iter), std::move(__mapped_iter));
1033 }
1034
1035 template <class _KeyArg, class... _MArgs>
1036 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool>
1037 __try_emplace(_KeyArg&& __key, _MArgs&&... __mapped_args) {
1038 auto __key_it = std::lower_bound(__containers_.keys.begin(), __containers_.keys.end(), __key, __compare_);
1039 auto __mapped_it = __containers_.values.begin() + ranges::distance(__containers_.keys.begin(), __key_it);
1040
1041 if (__key_it == __containers_.keys.end() || __compare_(__key, *__key_it)) {
1042 return pair<iterator, bool>(
1043 __flat_map_utils::__emplace_exact_pos(
1044 *this,
1045 std::move(__key_it),
1046 std::move(__mapped_it),
1047 std::forward<_KeyArg>(__key),
1048 std::forward<_MArgs>(__mapped_args)...),
1049 true);
1050 } else {
1051 return pair<iterator, bool>(iterator(std::move(__key_it), std::move(__mapped_it)), false);
1052 }
1053 }
1054
1055 template <class _Kp>
1056 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool __is_hint_correct(const_iterator __hint, _Kp&& __key) {
1057 if (__hint != cbegin() && !__compare_((__hint - 1)->first, __key)) {
1058 return false;
1059 }
1060 if (__hint != cend() && __compare_(__hint->first, __key)) {
1061 return false;
1062 }
1063 return true;
1064 }
1065
1066 template <class _Kp, class... _Args>
1067 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool>
1068 __try_emplace_hint(const_iterator __hint, _Kp&& __key, _Args&&... __args) {
1069 if (__is_hint_correct(__hint, __key)) {
1070 if (__hint == cend() || __compare_(__key, __hint->first)) {
1071 return {__flat_map_utils::__emplace_exact_pos(
1072 *this,
1073 __hint.__key_iter_,
1074 __hint.__mapped_iter_,
1075 std::forward<_Kp>(__key),
1076 std::forward<_Args>(__args)...),
1077 true};
1078 } else {
1079 // key equals
1080 auto __dist = __hint - cbegin();
1081 return {iterator(__containers_.keys.begin() + __dist, __containers_.values.begin() + __dist), false};
1082 }
1083 } else {
1084 return __try_emplace(std::forward<_Kp>(__key), std::forward<_Args>(__args)...);
1085 }
1086 }
1087
1088 template <class _Kp, class _Mapped>
1089 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool>
1090 __insert_or_assign(_Kp&& __key, _Mapped&& __mapped) {
1091 auto __r = try_emplace(std::forward<_Kp>(__key), std::forward<_Mapped>(__mapped));
1092 if (!__r.second) {
1093 __r.first->second = std::forward<_Mapped>(__mapped);
1094 }
1095 return __r;
1096 }
1097
1098 template <class _Kp, class _Mapped>
1099 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator
1100 __insert_or_assign(const_iterator __hint, _Kp&& __key, _Mapped&& __mapped) {
1101 auto __r = __try_emplace_hint(__hint, std::forward<_Kp>(__key), std::forward<_Mapped>(__mapped));
1102 if (!__r.second) {
1103 __r.first->second = std::forward<_Mapped>(__mapped);
1104 }
1105 return __r.first;
1106 }
1107
1108 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __reserve(size_t __size) {
1109 if constexpr (__container_traits<_KeyContainer>::__reservable) {
1110 __containers_.keys.reserve(__size);
1111 }
1112
1113 if constexpr (__container_traits<_MappedContainer>::__reservable) {
1114 __containers_.values.reserve(__size);
1115 }
1116 }
1117
1118 template <class _KIter, class _MIter>
1119 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator
1120 __erase(_KIter __key_iter_to_remove, _MIter __mapped_iter_to_remove) {
1121 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
1122 auto __key_iter = __containers_.keys.erase(__key_iter_to_remove);
1123 auto __mapped_iter = __containers_.values.erase(__mapped_iter_to_remove);
1124 __on_failure.__complete();
1125 return iterator(std::move(__key_iter), std::move(__mapped_iter));
1126 }
1127
1128 template <class _Key2, class _Tp2, class _Compare2, class _KeyContainer2, class _MappedContainer2, class _Predicate>
1129 friend typename flat_map<_Key2, _Tp2, _Compare2, _KeyContainer2, _MappedContainer2>::size_type
1130 _LIBCPP_CONSTEXPR_SINCE_CXX26
1131 erase_if(flat_map<_Key2, _Tp2, _Compare2, _KeyContainer2, _MappedContainer2>&, _Predicate);
1132
1133 friend __flat_map_utils;
1134
1135 containers __containers_;
1136 _LIBCPP_NO_UNIQUE_ADDRESS key_compare __compare_;
1137
1138 struct __key_equiv {
1139 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_equiv(key_compare __c) : __comp_(__c) {}
1140 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
1141 operator()(const_reference __x, const_reference __y) const {
1142 return !__comp_(std::get<0>(__x), std::get<0>(__y)) && !__comp_(std::get<0>(__y), std::get<0>(__x));
1143 }
1144 key_compare __comp_;
1145 };
1146};
1147
1148template <class _KeyContainer, class _MappedContainer, class _Compare = less<typename _KeyContainer::value_type>>
1149 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> && !__is_allocator_v<_MappedContainer> &&
1150 is_invocable_v<const _Compare&,
1151 const typename _KeyContainer::value_type&,
1152 const typename _KeyContainer::value_type&>)
1153flat_map(_KeyContainer, _MappedContainer, _Compare = _Compare())
1154 -> flat_map<typename _KeyContainer::value_type,
1155 typename _MappedContainer::value_type,
1156 _Compare,
1157 _KeyContainer,
1158 _MappedContainer>;
1159
1160template <class _KeyContainer, class _MappedContainer, class _Allocator>
1161 requires(uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator> &&
1162 !__is_allocator_v<_KeyContainer> && !__is_allocator_v<_MappedContainer>)
1163flat_map(_KeyContainer, _MappedContainer, _Allocator)
1164 -> flat_map<typename _KeyContainer::value_type,
1165 typename _MappedContainer::value_type,
1166 less<typename _KeyContainer::value_type>,
1167 _KeyContainer,
1168 _MappedContainer>;
1169
1170template <class _KeyContainer, class _MappedContainer, class _Compare, class _Allocator>
1171 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> && !__is_allocator_v<_MappedContainer> &&
1172 uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator> &&
1173 is_invocable_v<const _Compare&,
1174 const typename _KeyContainer::value_type&,
1175 const typename _KeyContainer::value_type&>)
1176flat_map(_KeyContainer, _MappedContainer, _Compare, _Allocator)
1177 -> flat_map<typename _KeyContainer::value_type,
1178 typename _MappedContainer::value_type,
1179 _Compare,
1180 _KeyContainer,
1181 _MappedContainer>;
1182
1183template <class _KeyContainer, class _MappedContainer, class _Compare = less<typename _KeyContainer::value_type>>
1184 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> && !__is_allocator_v<_MappedContainer> &&
1185 is_invocable_v<const _Compare&,
1186 const typename _KeyContainer::value_type&,
1187 const typename _KeyContainer::value_type&>)
1188flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Compare = _Compare())
1189 -> flat_map<typename _KeyContainer::value_type,
1190 typename _MappedContainer::value_type,
1191 _Compare,
1192 _KeyContainer,
1193 _MappedContainer>;
1194
1195template <class _KeyContainer, class _MappedContainer, class _Allocator>
1196 requires(uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator> &&
1197 !__is_allocator_v<_KeyContainer> && !__is_allocator_v<_MappedContainer>)
1198flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Allocator)
1199 -> flat_map<typename _KeyContainer::value_type,
1200 typename _MappedContainer::value_type,
1201 less<typename _KeyContainer::value_type>,
1202 _KeyContainer,
1203 _MappedContainer>;
1204
1205template <class _KeyContainer, class _MappedContainer, class _Compare, class _Allocator>
1206 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> && !__is_allocator_v<_MappedContainer> &&
1207 uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator> &&
1208 is_invocable_v<const _Compare&,
1209 const typename _KeyContainer::value_type&,
1210 const typename _KeyContainer::value_type&>)
1211flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Compare, _Allocator)
1212 -> flat_map<typename _KeyContainer::value_type,
1213 typename _MappedContainer::value_type,
1214 _Compare,
1215 _KeyContainer,
1216 _MappedContainer>;
1217
1218template <class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>>
1219 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator_v<_Compare>)
1220flat_map(_InputIterator, _InputIterator, _Compare = _Compare())
1221 -> flat_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare>;
1222
1223template <class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>>
1224 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator_v<_Compare>)
1225flat_map(sorted_unique_t, _InputIterator, _InputIterator, _Compare = _Compare())
1226 -> flat_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare>;
1227
1228template <ranges::input_range _Range,
1229 class _Compare = less<__range_key_type<_Range>>,
1230 class _Allocator = allocator<byte>,
1231 class = __enable_if_t<!__is_allocator_v<_Compare> && __is_allocator_v<_Allocator>>>
1232flat_map(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator()) -> flat_map<
1233 __range_key_type<_Range>,
1234 __range_mapped_type<_Range>,
1235 _Compare,
1236 vector<__range_key_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_key_type<_Range>>>,
1237 vector<__range_mapped_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_mapped_type<_Range>>>>;
1238
1239template <ranges::input_range _Range, class _Allocator, class = __enable_if_t<__is_allocator_v<_Allocator>>>
1240flat_map(from_range_t, _Range&&, _Allocator) -> flat_map<
1241 __range_key_type<_Range>,
1242 __range_mapped_type<_Range>,
1243 less<__range_key_type<_Range>>,
1244 vector<__range_key_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_key_type<_Range>>>,
1245 vector<__range_mapped_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_mapped_type<_Range>>>>;
1246
1247template <class _Key, class _Tp, class _Compare = less<_Key>>
1248 requires(!__is_allocator_v<_Compare>)
1249flat_map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare()) -> flat_map<_Key, _Tp, _Compare>;
1250
1251template <class _Key, class _Tp, class _Compare = less<_Key>>
1252 requires(!__is_allocator_v<_Compare>)
1253flat_map(sorted_unique_t, initializer_list<pair<_Key, _Tp>>, _Compare = _Compare()) -> flat_map<_Key, _Tp, _Compare>;
1254
1255template <class _Key, class _Tp, class _Compare, class _KeyContainer, class _MappedContainer, class _Allocator>
1256struct uses_allocator<flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>, _Allocator>
1257 : bool_constant<uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator>> {};
1258
1259template <class _Key, class _Tp, class _Compare, class _KeyContainer, class _MappedContainer, class _Predicate>
1260_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
1261 typename flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>::size_type
1262 erase_if(flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>& __flat_map, _Predicate __pred) {
1263 auto __zv = ranges::views::zip(__flat_map.__containers_.keys, __flat_map.__containers_.values);
1264 auto __first = __zv.begin();
1265 auto __last = __zv.end();
1266 auto __guard = std::__make_exception_guard([&] { __flat_map.clear(); });
1267 auto __it = std::remove_if(__first, __last, [&](auto&& __zipped) -> bool {
1268 using _Ref = typename flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>::const_reference;
1269 return __pred(_Ref(std::get<0>(__zipped), std::get<1>(__zipped)));
1270 });
1271 auto __res = __last - __it;
1272 auto __offset = __it - __first;
1273
1274 const auto __erase_container = [&](auto& __cont) { __cont.erase(__cont.begin() + __offset, __cont.end()); };
1275
1276 __erase_container(__flat_map.__containers_.keys);
1277 __erase_container(__flat_map.__containers_.values);
1278
1279 __guard.__complete();
1280 return __res;
1281}
1282
1283_LIBCPP_END_NAMESPACE_STD
1284
1285#endif // _LIBCPP_STD_VER >= 23
1286
1287_LIBCPP_POP_MACROS
1288
1289#endif // _LIBCPP___FLAT_MAP_FLAT_MAP_H