master
1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP___FLAT_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
80template <class _Key,
81 class _Tp,
82 class _Compare = less<_Key>,
83 class _KeyContainer = vector<_Key>,
84 class _MappedContainer = vector<_Tp>>
85class 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
97public:
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
132private:
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
139public:
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
885private:
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
1127template <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&>)
1133flat_map(_KeyContainer, _MappedContainer, _Compare = _Compare())
1134 -> flat_map<typename _KeyContainer::value_type,
1135 typename _MappedContainer::value_type,
1136 _Compare,
1137 _KeyContainer,
1138 _MappedContainer>;
1139
1140template <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)
1143flat_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
1150template <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&>)
1157flat_map(_KeyContainer, _MappedContainer, _Compare, _Allocator)
1158 -> flat_map<typename _KeyContainer::value_type,
1159 typename _MappedContainer::value_type,
1160 _Compare,
1161 _KeyContainer,
1162 _MappedContainer>;
1163
1164template <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&>)
1170flat_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
1177template <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)
1180flat_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
1187template <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&>)
1194flat_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
1201template <class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>>
1202 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator<_Compare>::value)
1203flat_map(_InputIterator, _InputIterator, _Compare = _Compare())
1204 -> flat_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare>;
1205
1206template <class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>>
1207 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator<_Compare>::value)
1208flat_map(sorted_unique_t, _InputIterator, _InputIterator, _Compare = _Compare())
1209 -> flat_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare>;
1210
1211template <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>>
1215flat_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
1222template <ranges::input_range _Range, class _Allocator, class = __enable_if_t<__is_allocator<_Allocator>::value>>
1223flat_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
1230template <class _Key, class _Tp, class _Compare = less<_Key>>
1231 requires(!__is_allocator<_Compare>::value)
1232flat_map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare()) -> flat_map<_Key, _Tp, _Compare>;
1233
1234template <class _Key, class _Tp, class _Compare = less<_Key>>
1235 requires(!__is_allocator<_Compare>::value)
1236flat_map(sorted_unique_t, initializer_list<pair<_Key, _Tp>>, _Compare = _Compare()) -> flat_map<_Key, _Tp, _Compare>;
1237
1238template <class _Key, class _Tp, class _Compare, class _KeyContainer, class _MappedContainer, class _Allocator>
1239struct uses_allocator<flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>, _Allocator>
1240 : bool_constant<uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator>> {};
1241
1242template <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