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

1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP___FLAT_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 value_compare(key_compare __c) : __comp_(__c) {}
118 friend flat_map;
119
120 public:
121 _LIBCPP_HIDE_FROM_ABI bool 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 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 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 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 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 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
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
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
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
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
254 flat_map(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 explicit flat_map(const key_compare& __comp) : __containers_(), __compare_(__comp) {}
267
268 template <class _Allocator>
269 requires __allocator_ctor_constraint<_Allocator>
270 _LIBCPP_HIDE_FROM_ABI flat_map(const key_compare& __comp, const _Allocator& __alloc)
271 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) {}
272
273 template <class _Allocator>
274 requires __allocator_ctor_constraint<_Allocator>
275 _LIBCPP_HIDE_FROM_ABI explicit flat_map(const _Allocator& __alloc)
276 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc) {}
277
278 template <class _InputIterator>
279 requires __has_input_iterator_category<_InputIterator>::value
280 _LIBCPP_HIDE_FROM_ABI
281 flat_map(_InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare())
282 : __containers_(), __compare_(__comp) {
283 insert(__first, __last);
284 }
285
286 template <class _InputIterator, class _Allocator>
287 requires(__has_input_iterator_category<_InputIterator>::value && __allocator_ctor_constraint<_Allocator>)
288 _LIBCPP_HIDE_FROM_ABI
289 flat_map(_InputIterator __first, _InputIterator __last, const key_compare& __comp, const _Allocator& __alloc)
290 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) {
291 insert(__first, __last);
292 }
293
294 template <class _InputIterator, class _Allocator>
295 requires(__has_input_iterator_category<_InputIterator>::value && __allocator_ctor_constraint<_Allocator>)
296 _LIBCPP_HIDE_FROM_ABI flat_map(_InputIterator __first, _InputIterator __last, const _Allocator& __alloc)
297 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc) {
298 insert(__first, __last);
299 }
300
301 template <_ContainerCompatibleRange<value_type> _Range>
302 _LIBCPP_HIDE_FROM_ABI flat_map(from_range_t __fr, _Range&& __rg)
303 : flat_map(__fr, std::forward<_Range>(__rg), key_compare()) {}
304
305 template <_ContainerCompatibleRange<value_type> _Range, class _Allocator>
306 requires __allocator_ctor_constraint<_Allocator>
307 _LIBCPP_HIDE_FROM_ABI flat_map(from_range_t, _Range&& __rg, const _Allocator& __alloc)
308 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc) {
309 insert_range(std::forward<_Range>(__rg));
310 }
311
312 template <_ContainerCompatibleRange<value_type> _Range>
313 _LIBCPP_HIDE_FROM_ABI flat_map(from_range_t, _Range&& __rg, const key_compare& __comp) : flat_map(__comp) {
314 insert_range(std::forward<_Range>(__rg));
315 }
316
317 template <_ContainerCompatibleRange<value_type> _Range, class _Allocator>
318 requires __allocator_ctor_constraint<_Allocator>
319 _LIBCPP_HIDE_FROM_ABI flat_map(from_range_t, _Range&& __rg, const key_compare& __comp, const _Allocator& __alloc)
320 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) {
321 insert_range(std::forward<_Range>(__rg));
322 }
323
324 template <class _InputIterator>
325 requires __has_input_iterator_category<_InputIterator>::value
326 _LIBCPP_HIDE_FROM_ABI
327 flat_map(sorted_unique_t, _InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare())
328 : __containers_(), __compare_(__comp) {
329 insert(sorted_unique, __first, __last);
330 }
331 template <class _InputIterator, class _Allocator>
332 requires(__has_input_iterator_category<_InputIterator>::value && __allocator_ctor_constraint<_Allocator>)
333 _LIBCPP_HIDE_FROM_ABI
334 flat_map(sorted_unique_t,
335 _InputIterator __first,
336 _InputIterator __last,
337 const key_compare& __comp,
338 const _Allocator& __alloc)
339 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) {
340 insert(sorted_unique, __first, __last);
341 }
342
343 template <class _InputIterator, class _Allocator>
344 requires(__has_input_iterator_category<_InputIterator>::value && __allocator_ctor_constraint<_Allocator>)
345 _LIBCPP_HIDE_FROM_ABI
346 flat_map(sorted_unique_t, _InputIterator __first, _InputIterator __last, const _Allocator& __alloc)
347 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc) {
348 insert(sorted_unique, __first, __last);
349 }
350
351 _LIBCPP_HIDE_FROM_ABI flat_map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
352 : flat_map(__il.begin(), __il.end(), __comp) {}
353
354 template <class _Allocator>
355 requires __allocator_ctor_constraint<_Allocator>
356 _LIBCPP_HIDE_FROM_ABI
357 flat_map(initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc)
358 : flat_map(__il.begin(), __il.end(), __comp, __alloc) {}
359
360 template <class _Allocator>
361 requires __allocator_ctor_constraint<_Allocator>
362 _LIBCPP_HIDE_FROM_ABI flat_map(initializer_list<value_type> __il, const _Allocator& __alloc)
363 : flat_map(__il.begin(), __il.end(), __alloc) {}
364
365 _LIBCPP_HIDE_FROM_ABI
366 flat_map(sorted_unique_t, initializer_list<value_type> __il, const key_compare& __comp = key_compare())
367 : flat_map(sorted_unique, __il.begin(), __il.end(), __comp) {}
368
369 template <class _Allocator>
370 requires __allocator_ctor_constraint<_Allocator>
371 _LIBCPP_HIDE_FROM_ABI
372 flat_map(sorted_unique_t, initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc)
373 : flat_map(sorted_unique, __il.begin(), __il.end(), __comp, __alloc) {}
374
375 template <class _Allocator>
376 requires __allocator_ctor_constraint<_Allocator>
377 _LIBCPP_HIDE_FROM_ABI flat_map(sorted_unique_t, initializer_list<value_type> __il, const _Allocator& __alloc)
378 : flat_map(sorted_unique, __il.begin(), __il.end(), __alloc) {}
379
380 _LIBCPP_HIDE_FROM_ABI flat_map& operator=(initializer_list<value_type> __il) {
381 clear();
382 insert(__il);
383 return *this;
384 }
385
386 _LIBCPP_HIDE_FROM_ABI flat_map& operator=(const flat_map&) = default;
387
388 _LIBCPP_HIDE_FROM_ABI flat_map& operator=(flat_map&& __other) noexcept(
389 is_nothrow_move_assignable_v<_KeyContainer> && is_nothrow_move_assignable_v<_MappedContainer> &&
390 is_nothrow_move_assignable_v<_Compare>) {
391 // No matter what happens, we always want to clear the other container before returning
392 // since we moved from it
393 auto __clear_other_guard = std::__make_scope_guard([&]() noexcept { __other.clear() /* noexcept */; });
394 {
395 // If an exception is thrown, we have no choice but to clear *this to preserve invariants
396 auto __on_exception = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
397 __containers_ = std::move(__other.__containers_);
398 __compare_ = std::move(__other.__compare_);
399 __on_exception.__complete();
400 }
401 return *this;
402 }
403
404 // iterators
405 _LIBCPP_HIDE_FROM_ABI iterator begin() noexcept {
406 return iterator(__containers_.keys.begin(), __containers_.values.begin());
407 }
408
409 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const noexcept {
410 return const_iterator(__containers_.keys.begin(), __containers_.values.begin());
411 }
412
413 _LIBCPP_HIDE_FROM_ABI iterator end() noexcept {
414 return iterator(__containers_.keys.end(), __containers_.values.end());
415 }
416
417 _LIBCPP_HIDE_FROM_ABI const_iterator end() const noexcept {
418 return const_iterator(__containers_.keys.end(), __containers_.values.end());
419 }
420
421 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
422 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }
423 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
424 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }
425
426 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const noexcept { return begin(); }
427 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const noexcept { return end(); }
428 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(end()); }
429 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const noexcept { return const_reverse_iterator(begin()); }
430
431 // [flat.map.capacity], capacity
432 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI bool empty() const noexcept { return __containers_.keys.empty(); }
433
434 _LIBCPP_HIDE_FROM_ABI size_type size() const noexcept { return __containers_.keys.size(); }
435
436 _LIBCPP_HIDE_FROM_ABI size_type max_size() const noexcept {
437 return std::min<size_type>(__containers_.keys.max_size(), __containers_.values.max_size());
438 }
439
440 // [flat.map.access], element access
441 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __x)
442 requires is_constructible_v<mapped_type>
443 {
444 return try_emplace(__x).first->second;
445 }
446
447 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](key_type&& __x)
448 requires is_constructible_v<mapped_type>
449 {
450 return try_emplace(std::move(__x)).first->second;
451 }
452
453 template <class _Kp>
454 requires(__is_compare_transparent && is_constructible_v<key_type, _Kp> && is_constructible_v<mapped_type> &&
455 !is_convertible_v<_Kp &&, const_iterator> && !is_convertible_v<_Kp &&, iterator>)
456 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](_Kp&& __x) {
457 return try_emplace(std::forward<_Kp>(__x)).first->second;
458 }
459
460 _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __x) {
461 auto __it = find(__x);
462 if (__it == end()) {
463 std::__throw_out_of_range("flat_map::at(const key_type&): Key does not exist");
464 }
465 return __it->second;
466 }
467
468 _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __x) const {
469 auto __it = find(__x);
470 if (__it == end()) {
471 std::__throw_out_of_range("flat_map::at(const key_type&) const: Key does not exist");
472 }
473 return __it->second;
474 }
475
476 template <class _Kp>
477 requires __is_compare_transparent
478 _LIBCPP_HIDE_FROM_ABI mapped_type& at(const _Kp& __x) {
479 auto __it = find(__x);
480 if (__it == end()) {
481 std::__throw_out_of_range("flat_map::at(const K&): Key does not exist");
482 }
483 return __it->second;
484 }
485
486 template <class _Kp>
487 requires __is_compare_transparent
488 _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const _Kp& __x) const {
489 auto __it = find(__x);
490 if (__it == end()) {
491 std::__throw_out_of_range("flat_map::at(const K&) const: Key does not exist");
492 }
493 return __it->second;
494 }
495
496 // [flat.map.modifiers], modifiers
497 template <class... _Args>
498 requires is_constructible_v<pair<key_type, mapped_type>, _Args...>
499 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {
500 std::pair<key_type, mapped_type> __pair(std::forward<_Args>(__args)...);
501 return __try_emplace(std::move(__pair.first), std::move(__pair.second));
502 }
503
504 template <class... _Args>
505 requires is_constructible_v<pair<key_type, mapped_type>, _Args...>
506 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __hint, _Args&&... __args) {
507 std::pair<key_type, mapped_type> __pair(std::forward<_Args>(__args)...);
508 return __try_emplace_hint(__hint, std::move(__pair.first), std::move(__pair.second)).first;
509 }
510
511 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return emplace(__x); }
512
513 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __x) { return emplace(std::move(__x)); }
514
515 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, const value_type& __x) {
516 return emplace_hint(__hint, __x);
517 }
518
519 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, value_type&& __x) {
520 return emplace_hint(__hint, std::move(__x));
521 }
522
523 template <class _PairLike>
524 requires is_constructible_v<pair<key_type, mapped_type>, _PairLike>
525 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(_PairLike&& __x) {
526 return emplace(std::forward<_PairLike>(__x));
527 }
528
529 template <class _PairLike>
530 requires is_constructible_v<pair<key_type, mapped_type>, _PairLike>
531 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, _PairLike&& __x) {
532 return emplace_hint(__hint, std::forward<_PairLike>(__x));
533 }
534
535 template <class _InputIterator>
536 requires __has_input_iterator_category<_InputIterator>::value
537 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last) {
538 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) {
539 __reserve(__last - __first);
540 }
541 __append_sort_merge_unique</*WasSorted = */ false>(std::move(__first), std::move(__last));
542 }
543
544 template <class _InputIterator>
545 requires __has_input_iterator_category<_InputIterator>::value
546 _LIBCPP_HIDE_FROM_ABI void insert(sorted_unique_t, _InputIterator __first, _InputIterator __last) {
547 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) {
548 __reserve(__last - __first);
549 }
550
551 __append_sort_merge_unique</*WasSorted = */ true>(std::move(__first), std::move(__last));
552 }
553
554 template <_ContainerCompatibleRange<value_type> _Range>
555 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
556 if constexpr (ranges::sized_range<_Range>) {
557 __reserve(ranges::size(__range));
558 }
559
560 __append_sort_merge_unique</*WasSorted = */ false>(ranges::begin(__range), ranges::end(__range));
561 }
562
563 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
564
565 _LIBCPP_HIDE_FROM_ABI void insert(sorted_unique_t, initializer_list<value_type> __il) {
566 insert(sorted_unique, __il.begin(), __il.end());
567 }
568
569 _LIBCPP_HIDE_FROM_ABI containers extract() && {
570 auto __guard = std::__make_scope_guard([&]() noexcept { clear() /* noexcept */; });
571 auto __ret = std::move(__containers_);
572 return __ret;
573 }
574
575 _LIBCPP_HIDE_FROM_ABI void replace(key_container_type&& __key_cont, mapped_container_type&& __mapped_cont) {
576 _LIBCPP_ASSERT_VALID_INPUT_RANGE(
577 __key_cont.size() == __mapped_cont.size(), "flat_map keys and mapped containers have different size");
578
579 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
580 __is_sorted_and_unique(__key_cont), "Either the key container is not sorted or it contains duplicates");
581 auto __guard = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
582 __containers_.keys = std::move(__key_cont);
583 __containers_.values = std::move(__mapped_cont);
584 __guard.__complete();
585 }
586
587 template <class... _Args>
588 requires is_constructible_v<mapped_type, _Args...>
589 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(const key_type& __key, _Args&&... __args) {
590 return __try_emplace(__key, std::forward<_Args>(__args)...);
591 }
592
593 template <class... _Args>
594 requires is_constructible_v<mapped_type, _Args...>
595 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(key_type&& __key, _Args&&... __args) {
596 return __try_emplace(std::move(__key), std::forward<_Args>(__args)...);
597 }
598
599 template <class _Kp, class... _Args>
600 requires(__is_compare_transparent && is_constructible_v<key_type, _Kp> &&
601 is_constructible_v<mapped_type, _Args...> && !is_convertible_v<_Kp &&, const_iterator> &&
602 !is_convertible_v<_Kp &&, iterator>)
603 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(_Kp&& __key, _Args&&... __args) {
604 return __try_emplace(std::forward<_Kp>(__key), std::forward<_Args>(__args)...);
605 }
606
607 template <class... _Args>
608 requires is_constructible_v<mapped_type, _Args...>
609 _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __hint, const key_type& __key, _Args&&... __args) {
610 return __try_emplace_hint(__hint, __key, std::forward<_Args>(__args)...).first;
611 }
612
613 template <class... _Args>
614 requires is_constructible_v<mapped_type, _Args...>
615 _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __hint, key_type&& __key, _Args&&... __args) {
616 return __try_emplace_hint(__hint, std::move(__key), std::forward<_Args>(__args)...).first;
617 }
618
619 template <class _Kp, class... _Args>
620 requires __is_compare_transparent && is_constructible_v<key_type, _Kp> && is_constructible_v<mapped_type, _Args...>
621 _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __hint, _Kp&& __key, _Args&&... __args) {
622 return __try_emplace_hint(__hint, std::forward<_Kp>(__key), std::forward<_Args>(__args)...).first;
623 }
624
625 template <class _Mapped>
626 requires is_assignable_v<mapped_type&, _Mapped> && is_constructible_v<mapped_type, _Mapped>
627 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(const key_type& __key, _Mapped&& __obj) {
628 return __insert_or_assign(__key, std::forward<_Mapped>(__obj));
629 }
630
631 template <class _Mapped>
632 requires is_assignable_v<mapped_type&, _Mapped> && is_constructible_v<mapped_type, _Mapped>
633 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(key_type&& __key, _Mapped&& __obj) {
634 return __insert_or_assign(std::move(__key), std::forward<_Mapped>(__obj));
635 }
636
637 template <class _Kp, class _Mapped>
638 requires __is_compare_transparent && is_constructible_v<key_type, _Kp> && is_assignable_v<mapped_type&, _Mapped> &&
639 is_constructible_v<mapped_type, _Mapped>
640 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(_Kp&& __key, _Mapped&& __obj) {
641 return __insert_or_assign(std::forward<_Kp>(__key), std::forward<_Mapped>(__obj));
642 }
643
644 template <class _Mapped>
645 requires is_assignable_v<mapped_type&, _Mapped> && is_constructible_v<mapped_type, _Mapped>
646 _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __hint, const key_type& __key, _Mapped&& __obj) {
647 return __insert_or_assign(__hint, __key, std::forward<_Mapped>(__obj));
648 }
649
650 template <class _Mapped>
651 requires is_assignable_v<mapped_type&, _Mapped> && is_constructible_v<mapped_type, _Mapped>
652 _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __hint, key_type&& __key, _Mapped&& __obj) {
653 return __insert_or_assign(__hint, std::move(__key), std::forward<_Mapped>(__obj));
654 }
655
656 template <class _Kp, class _Mapped>
657 requires __is_compare_transparent && is_constructible_v<key_type, _Kp> && is_assignable_v<mapped_type&, _Mapped> &&
658 is_constructible_v<mapped_type, _Mapped>
659 _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __hint, _Kp&& __key, _Mapped&& __obj) {
660 return __insert_or_assign(__hint, std::forward<_Kp>(__key), std::forward<_Mapped>(__obj));
661 }
662
663 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __position) {
664 return __erase(__position.__key_iter_, __position.__mapped_iter_);
665 }
666
667 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __position) {
668 return __erase(__position.__key_iter_, __position.__mapped_iter_);
669 }
670
671 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __x) {
672 auto __iter = find(__x);
673 if (__iter != end()) {
674 erase(__iter);
675 return 1;
676 }
677 return 0;
678 }
679
680 template <class _Kp>
681 requires(__is_compare_transparent && !is_convertible_v<_Kp &&, iterator> &&
682 !is_convertible_v<_Kp &&, const_iterator>)
683 _LIBCPP_HIDE_FROM_ABI size_type erase(_Kp&& __x) {
684 auto [__first, __last] = equal_range(__x);
685 auto __res = __last - __first;
686 erase(__first, __last);
687 return __res;
688 }
689
690 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
691 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
692 auto __key_it = __containers_.keys.erase(__first.__key_iter_, __last.__key_iter_);
693 auto __mapped_it = __containers_.values.erase(__first.__mapped_iter_, __last.__mapped_iter_);
694 __on_failure.__complete();
695 return iterator(std::move(__key_it), std::move(__mapped_it));
696 }
697
698 _LIBCPP_HIDE_FROM_ABI void swap(flat_map& __y) noexcept {
699 // warning: The spec has unconditional noexcept, which means that
700 // if any of the following functions throw an exception,
701 // std::terminate will be called.
702 // This is discussed in P2767, which hasn't been voted on yet.
703 ranges::swap(__compare_, __y.__compare_);
704 ranges::swap(__containers_.keys, __y.__containers_.keys);
705 ranges::swap(__containers_.values, __y.__containers_.values);
706 }
707
708 _LIBCPP_HIDE_FROM_ABI void clear() noexcept {
709 __containers_.keys.clear();
710 __containers_.values.clear();
711 }
712
713 // observers
714 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __compare_; }
715 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return value_compare(__compare_); }
716
717 _LIBCPP_HIDE_FROM_ABI const key_container_type& keys() const noexcept { return __containers_.keys; }
718 _LIBCPP_HIDE_FROM_ABI const mapped_container_type& values() const noexcept { return __containers_.values; }
719
720 // map operations
721 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __x) { return __find_impl(*this, __x); }
722
723 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __x) const { return __find_impl(*this, __x); }
724
725 template <class _Kp>
726 requires __is_compare_transparent
727 _LIBCPP_HIDE_FROM_ABI iterator find(const _Kp& __x) {
728 return __find_impl(*this, __x);
729 }
730
731 template <class _Kp>
732 requires __is_compare_transparent
733 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _Kp& __x) const {
734 return __find_impl(*this, __x);
735 }
736
737 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __x) const { return contains(__x) ? 1 : 0; }
738
739 template <class _Kp>
740 requires __is_compare_transparent
741 _LIBCPP_HIDE_FROM_ABI size_type count(const _Kp& __x) const {
742 return contains(__x) ? 1 : 0;
743 }
744
745 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __x) const { return find(__x) != end(); }
746
747 template <class _Kp>
748 requires __is_compare_transparent
749 _LIBCPP_HIDE_FROM_ABI bool contains(const _Kp& __x) const {
750 return find(__x) != end();
751 }
752
753 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __x) { return __lower_bound<iterator>(*this, __x); }
754
755 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __x) const {
756 return __lower_bound<const_iterator>(*this, __x);
757 }
758
759 template <class _Kp>
760 requires __is_compare_transparent
761 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _Kp& __x) {
762 return __lower_bound<iterator>(*this, __x);
763 }
764
765 template <class _Kp>
766 requires __is_compare_transparent
767 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _Kp& __x) const {
768 return __lower_bound<const_iterator>(*this, __x);
769 }
770
771 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __x) { return __upper_bound<iterator>(*this, __x); }
772
773 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __x) const {
774 return __upper_bound<const_iterator>(*this, __x);
775 }
776
777 template <class _Kp>
778 requires __is_compare_transparent
779 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _Kp& __x) {
780 return __upper_bound<iterator>(*this, __x);
781 }
782
783 template <class _Kp>
784 requires __is_compare_transparent
785 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _Kp& __x) const {
786 return __upper_bound<const_iterator>(*this, __x);
787 }
788
789 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __x) {
790 return __equal_range_impl(*this, __x);
791 }
792
793 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __x) const {
794 return __equal_range_impl(*this, __x);
795 }
796
797 template <class _Kp>
798 requires __is_compare_transparent
799 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _Kp& __x) {
800 return __equal_range_impl(*this, __x);
801 }
802 template <class _Kp>
803 requires __is_compare_transparent
804 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _Kp& __x) const {
805 return __equal_range_impl(*this, __x);
806 }
807
808 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const flat_map& __x, const flat_map& __y) {
809 return ranges::equal(__x, __y);
810 }
811
812 friend _LIBCPP_HIDE_FROM_ABI auto operator<=>(const flat_map& __x, const flat_map& __y) {
813 return std::lexicographical_compare_three_way(
814 __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
815 }
816
817 friend _LIBCPP_HIDE_FROM_ABI void swap(flat_map& __x, flat_map& __y) noexcept { __x.swap(__y); }
818
819private:
820 struct __ctor_uses_allocator_tag {
821 explicit _LIBCPP_HIDE_FROM_ABI __ctor_uses_allocator_tag() = default;
822 };
823 struct __ctor_uses_allocator_empty_tag {
824 explicit _LIBCPP_HIDE_FROM_ABI __ctor_uses_allocator_empty_tag() = default;
825 };
826
827 template <class _Allocator, class _KeyCont, class _MappedCont, class... _CompArg>
828 requires __allocator_ctor_constraint<_Allocator>
829 _LIBCPP_HIDE_FROM_ABI
830 flat_map(__ctor_uses_allocator_tag,
831 const _Allocator& __alloc,
832 _KeyCont&& __key_cont,
833 _MappedCont&& __mapped_cont,
834 _CompArg&&... __comp)
835 : __containers_{.keys = std::make_obj_using_allocator<key_container_type>(
836 __alloc, std::forward<_KeyCont>(__key_cont)),
837 .values = std::make_obj_using_allocator<mapped_container_type>(
838 __alloc, std::forward<_MappedCont>(__mapped_cont))},
839 __compare_(std::forward<_CompArg>(__comp)...) {}
840
841 template <class _Allocator, class... _CompArg>
842 requires __allocator_ctor_constraint<_Allocator>
843 _LIBCPP_HIDE_FROM_ABI flat_map(__ctor_uses_allocator_empty_tag, const _Allocator& __alloc, _CompArg&&... __comp)
844 : __containers_{.keys = std::make_obj_using_allocator<key_container_type>(__alloc),
845 .values = std::make_obj_using_allocator<mapped_container_type>(__alloc)},
846 __compare_(std::forward<_CompArg>(__comp)...) {}
847
848 _LIBCPP_HIDE_FROM_ABI bool __is_sorted_and_unique(auto&& __key_container) const {
849 auto __greater_or_equal_to = [this](const auto& __x, const auto& __y) { return !__compare_(__x, __y); };
850 return ranges::adjacent_find(__key_container, __greater_or_equal_to) == ranges::end(__key_container);
851 }
852
853 // This function is only used in constructors. So there is not exception handling in this function.
854 // If the function exits via an exception, there will be no flat_map object constructed, thus, there
855 // is no invariant state to preserve
856 _LIBCPP_HIDE_FROM_ABI void __sort_and_unique() {
857 auto __zv = ranges::views::zip(__containers_.keys, __containers_.values);
858 ranges::sort(__zv, __compare_, [](const auto& __p) -> decltype(auto) { return std::get<0>(__p); });
859 auto __dup_start = ranges::unique(__zv, __key_equiv(__compare_)).begin();
860 auto __dist = ranges::distance(__zv.begin(), __dup_start);
861 __containers_.keys.erase(__containers_.keys.begin() + __dist, __containers_.keys.end());
862 __containers_.values.erase(__containers_.values.begin() + __dist, __containers_.values.end());
863 }
864
865 template <class _Self, class _KeyIter>
866 _LIBCPP_HIDE_FROM_ABI static auto __corresponding_mapped_it(_Self&& __self, _KeyIter&& __key_iter) {
867 return __self.__containers_.values.begin() +
868 static_cast<ranges::range_difference_t<mapped_container_type>>(
869 ranges::distance(__self.__containers_.keys.begin(), __key_iter));
870 }
871
872 template <bool _WasSorted, class _InputIterator, class _Sentinel>
873 _LIBCPP_HIDE_FROM_ABI void __append_sort_merge_unique(_InputIterator __first, _Sentinel __last) {
874 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
875 size_t __num_of_appended = __flat_map_utils::__append(*this, std::move(__first), std::move(__last));
876 if (__num_of_appended != 0) {
877 auto __zv = ranges::views::zip(__containers_.keys, __containers_.values);
878 auto __append_start_offset = __containers_.keys.size() - __num_of_appended;
879 auto __end = __zv.end();
880 auto __compare_key = [this](const auto& __p1, const auto& __p2) {
881 return __compare_(std::get<0>(__p1), std::get<0>(__p2));
882 };
883 if constexpr (!_WasSorted) {
884 ranges::sort(__zv.begin() + __append_start_offset, __end, __compare_key);
885 } else {
886 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
887 __is_sorted_and_unique(__containers_.keys | ranges::views::drop(__append_start_offset)),
888 "Either the key container is not sorted or it contains duplicates");
889 }
890 ranges::inplace_merge(__zv.begin(), __zv.begin() + __append_start_offset, __end, __compare_key);
891
892 auto __dup_start = ranges::unique(__zv, __key_equiv(__compare_)).begin();
893 auto __dist = ranges::distance(__zv.begin(), __dup_start);
894 __containers_.keys.erase(__containers_.keys.begin() + __dist, __containers_.keys.end());
895 __containers_.values.erase(__containers_.values.begin() + __dist, __containers_.values.end());
896 }
897 __on_failure.__complete();
898 }
899
900 template <class _Self, class _Kp>
901 _LIBCPP_HIDE_FROM_ABI static auto __find_impl(_Self&& __self, const _Kp& __key) {
902 auto __it = __self.lower_bound(__key);
903 auto __last = __self.end();
904 if (__it == __last || __self.__compare_(__key, __it->first)) {
905 return __last;
906 }
907 return __it;
908 }
909
910 template <class _Self, class _Kp>
911 _LIBCPP_HIDE_FROM_ABI static auto __key_equal_range(_Self&& __self, const _Kp& __key) {
912 auto __it =
913 std::lower_bound(__self.__containers_.keys.begin(), __self.__containers_.keys.end(), __key, __self.__compare_);
914 auto __last = __self.__containers_.keys.end();
915 if (__it == __last || __self.__compare_(__key, *__it)) {
916 return std::make_pair(__it, __it);
917 }
918 return std::make_pair(__it, std::next(__it));
919 }
920
921 template <class _Self, class _Kp>
922 _LIBCPP_HIDE_FROM_ABI static auto __equal_range_impl(_Self&& __self, const _Kp& __key) {
923 auto [__key_first, __key_last] = __key_equal_range(__self, __key);
924 using __iterator_type = ranges::iterator_t<decltype(__self)>;
925 return std::make_pair(__iterator_type(__key_first, __corresponding_mapped_it(__self, __key_first)),
926 __iterator_type(__key_last, __corresponding_mapped_it(__self, __key_last)));
927 }
928
929 template <class _Res, class _Self, class _Kp>
930 _LIBCPP_HIDE_FROM_ABI static _Res __lower_bound(_Self&& __self, _Kp& __x) {
931 auto __key_iter =
932 std::lower_bound(__self.__containers_.keys.begin(), __self.__containers_.keys.end(), __x, __self.__compare_);
933 auto __mapped_iter = __corresponding_mapped_it(__self, __key_iter);
934 return _Res(std::move(__key_iter), std::move(__mapped_iter));
935 }
936
937 template <class _Res, class _Self, class _Kp>
938 _LIBCPP_HIDE_FROM_ABI static _Res __upper_bound(_Self&& __self, _Kp& __x) {
939 auto __key_iter =
940 std::upper_bound(__self.__containers_.keys.begin(), __self.__containers_.keys.end(), __x, __self.__compare_);
941 auto __mapped_iter = __corresponding_mapped_it(__self, __key_iter);
942 return _Res(std::move(__key_iter), std::move(__mapped_iter));
943 }
944
945 template <class _KeyArg, class... _MArgs>
946 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __try_emplace(_KeyArg&& __key, _MArgs&&... __mapped_args) {
947 auto __key_it = std::lower_bound(__containers_.keys.begin(), __containers_.keys.end(), __key, __compare_);
948 auto __mapped_it = __containers_.values.begin() + ranges::distance(__containers_.keys.begin(), __key_it);
949
950 if (__key_it == __containers_.keys.end() || __compare_(__key, *__key_it)) {
951 return pair<iterator, bool>(
952 __flat_map_utils::__emplace_exact_pos(
953 *this,
954 std::move(__key_it),
955 std::move(__mapped_it),
956 std::forward<_KeyArg>(__key),
957 std::forward<_MArgs>(__mapped_args)...),
958 true);
959 } else {
960 return pair<iterator, bool>(iterator(std::move(__key_it), std::move(__mapped_it)), false);
961 }
962 }
963
964 template <class _Kp>
965 _LIBCPP_HIDE_FROM_ABI bool __is_hint_correct(const_iterator __hint, _Kp&& __key) {
966 if (__hint != cbegin() && !__compare_((__hint - 1)->first, __key)) {
967 return false;
968 }
969 if (__hint != cend() && __compare_(__hint->first, __key)) {
970 return false;
971 }
972 return true;
973 }
974
975 template <class _Kp, class... _Args>
976 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __try_emplace_hint(const_iterator __hint, _Kp&& __key, _Args&&... __args) {
977 if (__is_hint_correct(__hint, __key)) {
978 if (__hint == cend() || __compare_(__key, __hint->first)) {
979 return {__flat_map_utils::__emplace_exact_pos(
980 *this,
981 __hint.__key_iter_,
982 __hint.__mapped_iter_,
983 std::forward<_Kp>(__key),
984 std::forward<_Args>(__args)...),
985 true};
986 } else {
987 // key equals
988 auto __dist = __hint - cbegin();
989 return {iterator(__containers_.keys.begin() + __dist, __containers_.values.begin() + __dist), false};
990 }
991 } else {
992 return __try_emplace(std::forward<_Kp>(__key), std::forward<_Args>(__args)...);
993 }
994 }
995
996 template <class _Kp, class _Mapped>
997 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_or_assign(_Kp&& __key, _Mapped&& __mapped) {
998 auto __r = try_emplace(std::forward<_Kp>(__key), std::forward<_Mapped>(__mapped));
999 if (!__r.second) {
1000 __r.first->second = std::forward<_Mapped>(__mapped);
1001 }
1002 return __r;
1003 }
1004
1005 template <class _Kp, class _Mapped>
1006 _LIBCPP_HIDE_FROM_ABI iterator __insert_or_assign(const_iterator __hint, _Kp&& __key, _Mapped&& __mapped) {
1007 auto __r = __try_emplace_hint(__hint, std::forward<_Kp>(__key), std::forward<_Mapped>(__mapped));
1008 if (!__r.second) {
1009 __r.first->second = std::forward<_Mapped>(__mapped);
1010 }
1011 return __r.first;
1012 }
1013
1014 _LIBCPP_HIDE_FROM_ABI void __reserve(size_t __size) {
1015 if constexpr (__container_traits<_KeyContainer>::__reservable) {
1016 __containers_.keys.reserve(__size);
1017 }
1018
1019 if constexpr (__container_traits<_MappedContainer>::__reservable) {
1020 __containers_.values.reserve(__size);
1021 }
1022 }
1023
1024 template <class _KIter, class _MIter>
1025 _LIBCPP_HIDE_FROM_ABI iterator __erase(_KIter __key_iter_to_remove, _MIter __mapped_iter_to_remove) {
1026 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
1027 auto __key_iter = __containers_.keys.erase(__key_iter_to_remove);
1028 auto __mapped_iter = __containers_.values.erase(__mapped_iter_to_remove);
1029 __on_failure.__complete();
1030 return iterator(std::move(__key_iter), std::move(__mapped_iter));
1031 }
1032
1033 template <class _Key2, class _Tp2, class _Compare2, class _KeyContainer2, class _MappedContainer2, class _Predicate>
1034 friend typename flat_map<_Key2, _Tp2, _Compare2, _KeyContainer2, _MappedContainer2>::size_type
1035 erase_if(flat_map<_Key2, _Tp2, _Compare2, _KeyContainer2, _MappedContainer2>&, _Predicate);
1036
1037 friend __flat_map_utils;
1038
1039 containers __containers_;
1040 _LIBCPP_NO_UNIQUE_ADDRESS key_compare __compare_;
1041
1042 struct __key_equiv {
1043 _LIBCPP_HIDE_FROM_ABI __key_equiv(key_compare __c) : __comp_(__c) {}
1044 _LIBCPP_HIDE_FROM_ABI bool operator()(const_reference __x, const_reference __y) const {
1045 return !__comp_(std::get<0>(__x), std::get<0>(__y)) && !__comp_(std::get<0>(__y), std::get<0>(__x));
1046 }
1047 key_compare __comp_;
1048 };
1049};
1050
1051template <class _KeyContainer, class _MappedContainer, class _Compare = less<typename _KeyContainer::value_type>>
1052 requires(!__is_allocator<_Compare>::value && !__is_allocator<_KeyContainer>::value &&
1053 !__is_allocator<_MappedContainer>::value &&
1054 is_invocable_v<const _Compare&,
1055 const typename _KeyContainer::value_type&,
1056 const typename _KeyContainer::value_type&>)
1057flat_map(_KeyContainer, _MappedContainer, _Compare = _Compare())
1058 -> flat_map<typename _KeyContainer::value_type,
1059 typename _MappedContainer::value_type,
1060 _Compare,
1061 _KeyContainer,
1062 _MappedContainer>;
1063
1064template <class _KeyContainer, class _MappedContainer, class _Allocator>
1065 requires(uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator> &&
1066 !__is_allocator<_KeyContainer>::value && !__is_allocator<_MappedContainer>::value)
1067flat_map(_KeyContainer, _MappedContainer, _Allocator)
1068 -> flat_map<typename _KeyContainer::value_type,
1069 typename _MappedContainer::value_type,
1070 less<typename _KeyContainer::value_type>,
1071 _KeyContainer,
1072 _MappedContainer>;
1073
1074template <class _KeyContainer, class _MappedContainer, class _Compare, class _Allocator>
1075 requires(!__is_allocator<_Compare>::value && !__is_allocator<_KeyContainer>::value &&
1076 !__is_allocator<_MappedContainer>::value && uses_allocator_v<_KeyContainer, _Allocator> &&
1077 uses_allocator_v<_MappedContainer, _Allocator> &&
1078 is_invocable_v<const _Compare&,
1079 const typename _KeyContainer::value_type&,
1080 const typename _KeyContainer::value_type&>)
1081flat_map(_KeyContainer, _MappedContainer, _Compare, _Allocator)
1082 -> flat_map<typename _KeyContainer::value_type,
1083 typename _MappedContainer::value_type,
1084 _Compare,
1085 _KeyContainer,
1086 _MappedContainer>;
1087
1088template <class _KeyContainer, class _MappedContainer, class _Compare = less<typename _KeyContainer::value_type>>
1089 requires(!__is_allocator<_Compare>::value && !__is_allocator<_KeyContainer>::value &&
1090 !__is_allocator<_MappedContainer>::value &&
1091 is_invocable_v<const _Compare&,
1092 const typename _KeyContainer::value_type&,
1093 const typename _KeyContainer::value_type&>)
1094flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Compare = _Compare())
1095 -> flat_map<typename _KeyContainer::value_type,
1096 typename _MappedContainer::value_type,
1097 _Compare,
1098 _KeyContainer,
1099 _MappedContainer>;
1100
1101template <class _KeyContainer, class _MappedContainer, class _Allocator>
1102 requires(uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator> &&
1103 !__is_allocator<_KeyContainer>::value && !__is_allocator<_MappedContainer>::value)
1104flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Allocator)
1105 -> flat_map<typename _KeyContainer::value_type,
1106 typename _MappedContainer::value_type,
1107 less<typename _KeyContainer::value_type>,
1108 _KeyContainer,
1109 _MappedContainer>;
1110
1111template <class _KeyContainer, class _MappedContainer, class _Compare, class _Allocator>
1112 requires(!__is_allocator<_Compare>::value && !__is_allocator<_KeyContainer>::value &&
1113 !__is_allocator<_MappedContainer>::value && uses_allocator_v<_KeyContainer, _Allocator> &&
1114 uses_allocator_v<_MappedContainer, _Allocator> &&
1115 is_invocable_v<const _Compare&,
1116 const typename _KeyContainer::value_type&,
1117 const typename _KeyContainer::value_type&>)
1118flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Compare, _Allocator)
1119 -> flat_map<typename _KeyContainer::value_type,
1120 typename _MappedContainer::value_type,
1121 _Compare,
1122 _KeyContainer,
1123 _MappedContainer>;
1124
1125template <class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>>
1126 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator<_Compare>::value)
1127flat_map(_InputIterator, _InputIterator, _Compare = _Compare())
1128 -> flat_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare>;
1129
1130template <class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>>
1131 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator<_Compare>::value)
1132flat_map(sorted_unique_t, _InputIterator, _InputIterator, _Compare = _Compare())
1133 -> flat_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare>;
1134
1135template <ranges::input_range _Range,
1136 class _Compare = less<__range_key_type<_Range>>,
1137 class _Allocator = allocator<byte>,
1138 class = __enable_if_t<!__is_allocator<_Compare>::value && __is_allocator<_Allocator>::value>>
1139flat_map(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator()) -> flat_map<
1140 __range_key_type<_Range>,
1141 __range_mapped_type<_Range>,
1142 _Compare,
1143 vector<__range_key_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_key_type<_Range>>>,
1144 vector<__range_mapped_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_mapped_type<_Range>>>>;
1145
1146template <ranges::input_range _Range, class _Allocator, class = __enable_if_t<__is_allocator<_Allocator>::value>>
1147flat_map(from_range_t, _Range&&, _Allocator) -> flat_map<
1148 __range_key_type<_Range>,
1149 __range_mapped_type<_Range>,
1150 less<__range_key_type<_Range>>,
1151 vector<__range_key_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_key_type<_Range>>>,
1152 vector<__range_mapped_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_mapped_type<_Range>>>>;
1153
1154template <class _Key, class _Tp, class _Compare = less<_Key>>
1155 requires(!__is_allocator<_Compare>::value)
1156flat_map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare()) -> flat_map<_Key, _Tp, _Compare>;
1157
1158template <class _Key, class _Tp, class _Compare = less<_Key>>
1159 requires(!__is_allocator<_Compare>::value)
1160flat_map(sorted_unique_t, initializer_list<pair<_Key, _Tp>>, _Compare = _Compare()) -> flat_map<_Key, _Tp, _Compare>;
1161
1162template <class _Key, class _Tp, class _Compare, class _KeyContainer, class _MappedContainer, class _Allocator>
1163struct uses_allocator<flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>, _Allocator>
1164 : bool_constant<uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator>> {};
1165
1166template <class _Key, class _Tp, class _Compare, class _KeyContainer, class _MappedContainer, class _Predicate>
1167_LIBCPP_HIDE_FROM_ABI typename flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>::size_type
1168erase_if(flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>& __flat_map, _Predicate __pred) {
1169 auto __zv = ranges::views::zip(__flat_map.__containers_.keys, __flat_map.__containers_.values);
1170 auto __first = __zv.begin();
1171 auto __last = __zv.end();
1172 auto __guard = std::__make_exception_guard([&] { __flat_map.clear(); });
1173 auto __it = std::remove_if(__first, __last, [&](auto&& __zipped) -> bool {
1174 using _Ref = typename flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>::const_reference;
1175 return __pred(_Ref(std::get<0>(__zipped), std::get<1>(__zipped)));
1176 });
1177 auto __res = __last - __it;
1178 auto __offset = __it - __first;
1179
1180 const auto __erase_container = [&](auto& __cont) { __cont.erase(__cont.begin() + __offset, __cont.end()); };
1181
1182 __erase_container(__flat_map.__containers_.keys);
1183 __erase_container(__flat_map.__containers_.values);
1184
1185 __guard.__complete();
1186 return __res;
1187}
1188
1189_LIBCPP_END_NAMESPACE_STD
1190
1191#endif // _LIBCPP_STD_VER >= 23
1192
1193_LIBCPP_POP_MACROS
1194
1195#endif // _LIBCPP___FLAT_MAP_FLAT_MAP_H
1196

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

source code of libcxx/include/__flat_map/flat_map.h