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_MULTIMAP_H
11#define _LIBCPP___FLAT_MAP_FLAT_MULTIMAP_H
12
13#include <__algorithm/equal_range.h>
14#include <__algorithm/lexicographical_compare_three_way.h>
15#include <__algorithm/lower_bound.h>
16#include <__algorithm/min.h>
17#include <__algorithm/ranges_equal.h>
18#include <__algorithm/ranges_inplace_merge.h>
19#include <__algorithm/ranges_is_sorted.h>
20#include <__algorithm/ranges_sort.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_equivalent.h>
31#include <__flat_map/utils.h>
32#include <__functional/is_transparent.h>
33#include <__functional/operations.h>
34#include <__fwd/vector.h>
35#include <__iterator/concepts.h>
36#include <__iterator/distance.h>
37#include <__iterator/iterator_traits.h>
38#include <__iterator/ranges_iterator_traits.h>
39#include <__iterator/reverse_iterator.h>
40#include <__memory/allocator_traits.h>
41#include <__memory/uses_allocator.h>
42#include <__memory/uses_allocator_construction.h>
43#include <__ranges/access.h>
44#include <__ranges/concepts.h>
45#include <__ranges/container_compatible_range.h>
46#include <__ranges/drop_view.h>
47#include <__ranges/from_range.h>
48#include <__ranges/range_adaptor.h>
49#include <__ranges/size.h>
50#include <__ranges/subrange.h>
51#include <__ranges/zip_view.h>
52#include <__type_traits/conjunction.h>
53#include <__type_traits/container_traits.h>
54#include <__type_traits/invoke.h>
55#include <__type_traits/is_allocator.h>
56#include <__type_traits/is_nothrow_constructible.h>
57#include <__type_traits/is_same.h>
58#include <__utility/exception_guard.h>
59#include <__utility/move.h>
60#include <__utility/pair.h>
61#include <__utility/scope_guard.h>
62#include <__vector/vector.h>
63#include <initializer_list>
64
65#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
66# pragma GCC system_header
67#endif
68
69_LIBCPP_PUSH_MACROS
70#include <__undef_macros>
71
72#if _LIBCPP_STD_VER >= 23
73
74_LIBCPP_BEGIN_NAMESPACE_STD
75
76template <class _Key,
77 class _Tp,
78 class _Compare = less<_Key>,
79 class _KeyContainer = vector<_Key>,
80 class _MappedContainer = vector<_Tp>>
81class flat_multimap {
82 template <class, class, class, class, class>
83 friend class flat_multimap;
84
85 static_assert(is_same_v<_Key, typename _KeyContainer::value_type>);
86 static_assert(is_same_v<_Tp, typename _MappedContainer::value_type>);
87 static_assert(!is_same_v<_KeyContainer, std::vector<bool>>, "vector<bool> is not a sequence container");
88 static_assert(!is_same_v<_MappedContainer, std::vector<bool>>, "vector<bool> is not a sequence container");
89
90 template <bool _Const>
91 using __iterator _LIBCPP_NODEBUG = __key_value_iterator<flat_multimap, _KeyContainer, _MappedContainer, _Const>;
92
93public:
94 // types
95 using key_type = _Key;
96 using mapped_type = _Tp;
97 using value_type = pair<key_type, mapped_type>;
98 using key_compare = __type_identity_t<_Compare>;
99 using reference = pair<const key_type&, mapped_type&>;
100 using const_reference = pair<const key_type&, const mapped_type&>;
101 using size_type = size_t;
102 using difference_type = ptrdiff_t;
103 using iterator = __iterator<false>; // see [container.requirements]
104 using const_iterator = __iterator<true>; // see [container.requirements]
105 using reverse_iterator = std::reverse_iterator<iterator>;
106 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
107 using key_container_type = _KeyContainer;
108 using mapped_container_type = _MappedContainer;
109
110 class value_compare {
111 private:
112 _LIBCPP_NO_UNIQUE_ADDRESS key_compare __comp_;
113 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 value_compare(key_compare __c) : __comp_(__c) {}
114 friend flat_multimap;
115
116 public:
117 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
118 operator()(const_reference __x, const_reference __y) const {
119 return __comp_(__x.first, __y.first);
120 }
121 };
122
123 struct containers {
124 key_container_type keys;
125 mapped_container_type values;
126 };
127
128private:
129 template <class _Allocator>
130 _LIBCPP_HIDE_FROM_ABI static constexpr bool __allocator_ctor_constraint =
131 _And<uses_allocator<key_container_type, _Allocator>, uses_allocator<mapped_container_type, _Allocator>>::value;
132
133 _LIBCPP_HIDE_FROM_ABI static constexpr bool __is_compare_transparent = __is_transparent_v<_Compare>;
134
135public:
136 // [flat.map.cons], construct/copy/destroy
137 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multimap() noexcept(
138 is_nothrow_default_constructible_v<_KeyContainer> && is_nothrow_default_constructible_v<_MappedContainer> &&
139 is_nothrow_default_constructible_v<_Compare>)
140 : __containers_(), __compare_() {}
141
142 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multimap(const flat_multimap&) = default;
143
144 // The copy/move constructors are not specified in the spec, which means they should be defaulted.
145 // However, the move constructor can potentially leave a moved-from object in an inconsistent
146 // state if an exception is thrown.
147 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multimap(flat_multimap&& __other) noexcept(
148 is_nothrow_move_constructible_v<_KeyContainer> && is_nothrow_move_constructible_v<_MappedContainer> &&
149 is_nothrow_move_constructible_v<_Compare>)
150# if _LIBCPP_HAS_EXCEPTIONS
151 try
152# endif // _LIBCPP_HAS_EXCEPTIONS
153 : __containers_(std::move(__other.__containers_)), __compare_(std::move(__other.__compare_)) {
154 __other.clear();
155# if _LIBCPP_HAS_EXCEPTIONS
156 } catch (...) {
157 __other.clear();
158 // gcc does not like the `throw` keyword in a conditionally noexcept function
159 if constexpr (!(is_nothrow_move_constructible_v<_KeyContainer> &&
160 is_nothrow_move_constructible_v<_MappedContainer> && is_nothrow_move_constructible_v<_Compare>)) {
161 throw;
162 }
163# endif // _LIBCPP_HAS_EXCEPTIONS
164 }
165
166 template <class _Allocator>
167 requires __allocator_ctor_constraint<_Allocator>
168 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
169 flat_multimap(const flat_multimap& __other, const _Allocator& __alloc)
170 : flat_multimap(__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_multimap(flat_multimap&& __other, const _Allocator& __alloc)
179# if _LIBCPP_HAS_EXCEPTIONS
180 try
181# endif // _LIBCPP_HAS_EXCEPTIONS
182 : flat_multimap(__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_multimap(
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_multimap keys and mapped containers have different size");
200 __sort();
201 }
202
203 template <class _Allocator>
204 requires __allocator_ctor_constraint<_Allocator>
205 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multimap(
206 const key_container_type& __key_cont, const mapped_container_type& __mapped_cont, const _Allocator& __alloc)
207 : flat_multimap(__ctor_uses_allocator_tag{}, __alloc, __key_cont, __mapped_cont) {
208 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
209 "flat_multimap keys and mapped containers have different size");
210 __sort();
211 }
212
213 template <class _Allocator>
214 requires __allocator_ctor_constraint<_Allocator>
215 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multimap(
216 const key_container_type& __key_cont,
217 const mapped_container_type& __mapped_cont,
218 const key_compare& __comp,
219 const _Allocator& __alloc)
220 : flat_multimap(__ctor_uses_allocator_tag{}, __alloc, __key_cont, __mapped_cont, __comp) {
221 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
222 "flat_multimap keys and mapped containers have different size");
223 __sort();
224 }
225
226 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multimap(
227 sorted_equivalent_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_multimap keys and mapped containers have different size");
234 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(__is_sorted(__containers_.keys), "Key container is not sorted");
235 }
236
237 template <class _Allocator>
238 requires __allocator_ctor_constraint<_Allocator>
239 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multimap(
240 sorted_equivalent_t,
241 const key_container_type& __key_cont,
242 const mapped_container_type& __mapped_cont,
243 const _Allocator& __alloc)
244 : flat_multimap(__ctor_uses_allocator_tag{}, __alloc, __key_cont, __mapped_cont) {
245 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
246 "flat_multimap keys and mapped containers have different size");
247 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(__is_sorted(__containers_.keys), "Key container is not sorted");
248 }
249
250 template <class _Allocator>
251 requires __allocator_ctor_constraint<_Allocator>
252 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multimap(
253 sorted_equivalent_t,
254 const key_container_type& __key_cont,
255 const mapped_container_type& __mapped_cont,
256 const key_compare& __comp,
257 const _Allocator& __alloc)
258 : flat_multimap(__ctor_uses_allocator_tag{}, __alloc, __key_cont, __mapped_cont, __comp) {
259 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
260 "flat_multimap keys and mapped containers have different size");
261 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(__is_sorted(__containers_.keys), "Key container is not sorted");
262 }
263
264 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit flat_multimap(const key_compare& __comp)
265 : __containers_(), __compare_(__comp) {}
266
267 template <class _Allocator>
268 requires __allocator_ctor_constraint<_Allocator>
269 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
270 flat_multimap(const key_compare& __comp, const _Allocator& __alloc)
271 : flat_multimap(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) {}
272
273 template <class _Allocator>
274 requires __allocator_ctor_constraint<_Allocator>
275 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit flat_multimap(const _Allocator& __alloc)
276 : flat_multimap(__ctor_uses_allocator_empty_tag{}, __alloc) {}
277
278 template <class _InputIterator>
279 requires __has_input_iterator_category<_InputIterator>::value
280 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
281 flat_multimap(_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 _LIBCPP_CONSTEXPR_SINCE_CXX26
289 flat_multimap(_InputIterator __first, _InputIterator __last, const key_compare& __comp, const _Allocator& __alloc)
290 : flat_multimap(__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 _LIBCPP_CONSTEXPR_SINCE_CXX26
297 flat_multimap(_InputIterator __first, _InputIterator __last, const _Allocator& __alloc)
298 : flat_multimap(__ctor_uses_allocator_empty_tag{}, __alloc) {
299 insert(__first, __last);
300 }
301
302 template <_ContainerCompatibleRange<value_type> _Range>
303 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multimap(from_range_t __fr, _Range&& __rg)
304 : flat_multimap(__fr, std::forward<_Range>(__rg), key_compare()) {}
305
306 template <_ContainerCompatibleRange<value_type> _Range, class _Allocator>
307 requires __allocator_ctor_constraint<_Allocator>
308 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
309 flat_multimap(from_range_t, _Range&& __rg, const _Allocator& __alloc)
310 : flat_multimap(__ctor_uses_allocator_empty_tag{}, __alloc) {
311 insert_range(std::forward<_Range>(__rg));
312 }
313
314 template <_ContainerCompatibleRange<value_type> _Range>
315 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
316 flat_multimap(from_range_t, _Range&& __rg, const key_compare& __comp)
317 : flat_multimap(__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_multimap(from_range_t, _Range&& __rg, const key_compare& __comp, const _Allocator& __alloc)
325 : flat_multimap(__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 flat_multimap(
332 sorted_equivalent_t, _InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare())
333 : __containers_(), __compare_(__comp) {
334 insert(sorted_equivalent, __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_multimap(
339 sorted_equivalent_t,
340 _InputIterator __first,
341 _InputIterator __last,
342 const key_compare& __comp,
343 const _Allocator& __alloc)
344 : flat_multimap(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) {
345 insert(sorted_equivalent, __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_multimap(sorted_equivalent_t, _InputIterator __first, _InputIterator __last, const _Allocator& __alloc)
352 : flat_multimap(__ctor_uses_allocator_empty_tag{}, __alloc) {
353 insert(sorted_equivalent, __first, __last);
354 }
355
356 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
357 flat_multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
358 : flat_multimap(__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_multimap(initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc)
364 : flat_multimap(__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_multimap(initializer_list<value_type> __il, const _Allocator& __alloc)
370 : flat_multimap(__il.begin(), __il.end(), __alloc) {}
371
372 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
373 flat_multimap(sorted_equivalent_t, initializer_list<value_type> __il, const key_compare& __comp = key_compare())
374 : flat_multimap(sorted_equivalent, __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 flat_multimap(
379 sorted_equivalent_t, initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc)
380 : flat_multimap(sorted_equivalent, __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_multimap(sorted_equivalent_t, initializer_list<value_type> __il, const _Allocator& __alloc)
386 : flat_multimap(sorted_equivalent, __il.begin(), __il.end(), __alloc) {}
387
388 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multimap& operator=(initializer_list<value_type> __il) {
389 clear();
390 insert(__il);
391 return *this;
392 }
393
394 // copy/move assignment are not specified in the spec (defaulted)
395 // but move assignment can potentially leave moved from object in an inconsistent
396 // state if an exception is thrown
397 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multimap& operator=(const flat_multimap&) = default;
398
399 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multimap& operator=(flat_multimap&& __other) noexcept(
400 is_nothrow_move_assignable_v<_KeyContainer> && is_nothrow_move_assignable_v<_MappedContainer> &&
401 is_nothrow_move_assignable_v<_Compare>) {
402 auto __clear_other_guard = std::__make_scope_guard([&]() noexcept { __other.clear() /* noexcept */; });
403 auto __clear_self_guard = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
404 __containers_ = std::move(__other.__containers_);
405 __compare_ = std::move(__other.__compare_);
406 __clear_self_guard.__complete();
407 return *this;
408 }
409
410 // iterators
411 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator begin() noexcept {
412 return iterator(__containers_.keys.begin(), __containers_.values.begin());
413 }
414
415 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator begin() const noexcept {
416 return const_iterator(__containers_.keys.begin(), __containers_.values.begin());
417 }
418
419 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator end() noexcept {
420 return iterator(__containers_.keys.end(), __containers_.values.end());
421 }
422
423 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator end() const noexcept {
424 return const_iterator(__containers_.keys.end(), __containers_.values.end());
425 }
426
427 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 reverse_iterator rbegin() noexcept {
428 return reverse_iterator(end());
429 }
430 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator rbegin() const noexcept {
431 return const_reverse_iterator(end());
432 }
433 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 reverse_iterator rend() noexcept {
434 return reverse_iterator(begin());
435 }
436 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator rend() const noexcept {
437 return const_reverse_iterator(begin());
438 }
439
440 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator cbegin() const noexcept {
441 return begin();
442 }
443 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator cend() const noexcept {
444 return end();
445 }
446 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator crbegin() const noexcept {
447 return const_reverse_iterator(end());
448 }
449 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator crend() const noexcept {
450 return const_reverse_iterator(begin());
451 }
452
453 // [flat.map.capacity], capacity
454 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool empty() const noexcept {
455 return __containers_.keys.empty();
456 }
457
458 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type size() const noexcept {
459 return __containers_.keys.size();
460 }
461
462 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type max_size() const noexcept {
463 return std::min<size_type>(__containers_.keys.max_size(), __containers_.values.max_size());
464 }
465
466 // [flat.map.modifiers], modifiers
467 template <class... _Args>
468 requires is_constructible_v<pair<key_type, mapped_type>, _Args...> && is_move_constructible_v<key_type> &&
469 is_move_constructible_v<mapped_type>
470 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator emplace(_Args&&... __args) {
471 std::pair<key_type, mapped_type> __pair(std::forward<_Args>(__args)...);
472 auto __key_it = std::upper_bound(__containers_.keys.begin(), __containers_.keys.end(), __pair.first, __compare_);
473 auto __mapped_it = __corresponding_mapped_it(*this, __key_it);
474
475 return __flat_map_utils::__emplace_exact_pos(
476 *this, std::move(__key_it), std::move(__mapped_it), std::move(__pair.first), std::move(__pair.second));
477 }
478
479 template <class... _Args>
480 requires is_constructible_v<pair<key_type, mapped_type>, _Args...>
481 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator emplace_hint(const_iterator __hint, _Args&&... __args) {
482 std::pair<key_type, mapped_type> __pair(std::forward<_Args>(__args)...);
483
484 auto __prev_larger = __hint != cbegin() && __compare_(__pair.first, (__hint - 1)->first);
485 auto __next_smaller = __hint != cend() && __compare_(__hint->first, __pair.first);
486
487 auto __hint_distance = __hint.__key_iter_ - __containers_.keys.cbegin();
488 auto __key_iter = __containers_.keys.begin() + __hint_distance;
489 auto __mapped_iter = __containers_.values.begin() + __hint_distance;
490
491 if (!__prev_larger && !__next_smaller) [[likely]] {
492 // hint correct, just use exact hint iterators
493 } else if (__prev_larger && !__next_smaller) {
494 // the hint position is more to the right than the key should have been.
495 // we want to emplace the element to a position as right as possible
496 // e.g. Insert new element "2" in the following range
497 // 1, 1, 2, 2, 2, 3, 4, 6
498 // ^
499 // |
500 // hint
501 // We want to insert "2" after the last existing "2"
502 __key_iter = std::upper_bound(__containers_.keys.begin(), __key_iter, __pair.first, __compare_);
503 __mapped_iter = __corresponding_mapped_it(*this, __key_iter);
504 } else {
505 _LIBCPP_ASSERT_INTERNAL(!__prev_larger && __next_smaller, "this means that the multimap is not sorted");
506
507 // the hint position is more to the left than the key should have been.
508 // we want to emplace the element to a position as left as possible
509 // 1, 1, 2, 2, 2, 3, 4, 6
510 // ^
511 // |
512 // hint
513 // We want to insert "2" before the first existing "2"
514 __key_iter = std::lower_bound(__key_iter, __containers_.keys.end(), __pair.first, __compare_);
515 __mapped_iter = __corresponding_mapped_it(*this, __key_iter);
516 }
517 return __flat_map_utils::__emplace_exact_pos(
518 *this, __key_iter, __mapped_iter, std::move(__pair.first), std::move(__pair.second));
519 }
520
521 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const value_type& __x) { return emplace(__x); }
522
523 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(value_type&& __x) {
524 return emplace(std::move(__x));
525 }
526
527 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __hint, const value_type& __x) {
528 return emplace_hint(__hint, __x);
529 }
530
531 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __hint, value_type&& __x) {
532 return emplace_hint(__hint, std::move(__x));
533 }
534
535 template <class _PairLike>
536 requires is_constructible_v<pair<key_type, mapped_type>, _PairLike>
537 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(_PairLike&& __x) {
538 return emplace(std::forward<_PairLike>(__x));
539 }
540
541 template <class _PairLike>
542 requires is_constructible_v<pair<key_type, mapped_type>, _PairLike>
543 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __hint, _PairLike&& __x) {
544 return emplace_hint(__hint, std::forward<_PairLike>(__x));
545 }
546
547 template <class _InputIterator>
548 requires __has_input_iterator_category<_InputIterator>::value
549 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(_InputIterator __first, _InputIterator __last) {
550 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) {
551 __reserve(__last - __first);
552 }
553 __append_sort_merge</*WasSorted = */ false>(std::move(__first), std::move(__last));
554 }
555
556 template <class _InputIterator>
557 requires __has_input_iterator_category<_InputIterator>::value
558 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
559 insert(sorted_equivalent_t, _InputIterator __first, _InputIterator __last) {
560 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) {
561 __reserve(__last - __first);
562 }
563
564 __append_sort_merge</*WasSorted = */ true>(std::move(__first), std::move(__last));
565 }
566
567 template <_ContainerCompatibleRange<value_type> _Range>
568 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert_range(_Range&& __range) {
569 if constexpr (ranges::sized_range<_Range>) {
570 __reserve(ranges::size(__range));
571 }
572
573 __append_sort_merge</*WasSorted = */ false>(ranges::begin(__range), ranges::end(__range));
574 }
575
576 template <_ContainerCompatibleRange<value_type> _Range>
577 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert_range(sorted_equivalent_t, _Range&& __range) {
578 if constexpr (ranges::sized_range<_Range>) {
579 __reserve(ranges::size(__range));
580 }
581
582 __append_sort_merge</*WasSorted = */ true>(ranges::begin(__range), ranges::end(__range));
583 }
584
585 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(initializer_list<value_type> __il) {
586 insert(__il.begin(), __il.end());
587 }
588
589 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
590 insert(sorted_equivalent_t, initializer_list<value_type> __il) {
591 insert(sorted_equivalent, __il.begin(), __il.end());
592 }
593
594 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 containers extract() && {
595 auto __guard = std::__make_scope_guard([&]() noexcept { clear() /* noexcept */; });
596 auto __ret = std::move(__containers_);
597 return __ret;
598 }
599
600 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
601 replace(key_container_type&& __key_cont, mapped_container_type&& __mapped_cont) {
602 _LIBCPP_ASSERT_VALID_INPUT_RANGE(
603 __key_cont.size() == __mapped_cont.size(), "flat_multimap keys and mapped containers have different size");
604
605 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(__is_sorted(__key_cont), "Key container is not sorted");
606 auto __guard = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
607 __containers_.keys = std::move(__key_cont);
608 __containers_.values = std::move(__mapped_cont);
609 __guard.__complete();
610 }
611
612 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator erase(iterator __position) {
613 return __erase(__position.__key_iter_, __position.__mapped_iter_);
614 }
615
616 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator erase(const_iterator __position) {
617 return __erase(__position.__key_iter_, __position.__mapped_iter_);
618 }
619
620 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type erase(const key_type& __x) {
621 auto [__first, __last] = equal_range(__x);
622 auto __res = __last - __first;
623 erase(__first, __last);
624 return __res;
625 }
626
627 template <class _Kp>
628 requires(__is_compare_transparent && !is_convertible_v<_Kp &&, iterator> &&
629 !is_convertible_v<_Kp &&, const_iterator>)
630 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type erase(_Kp&& __x) {
631 auto [__first, __last] = equal_range(__x);
632 auto __res = __last - __first;
633 erase(__first, __last);
634 return __res;
635 }
636
637 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator erase(const_iterator __first, const_iterator __last) {
638 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
639 auto __key_it = __containers_.keys.erase(__first.__key_iter_, __last.__key_iter_);
640 auto __mapped_it = __containers_.values.erase(__first.__mapped_iter_, __last.__mapped_iter_);
641 __on_failure.__complete();
642 return iterator(std::move(__key_it), std::move(__mapped_it));
643 }
644
645 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void swap(flat_multimap& __y) noexcept(
646 is_nothrow_swappable_v<key_container_type> && is_nothrow_swappable_v<mapped_container_type> &&
647 is_nothrow_swappable_v<key_compare>) {
648 auto __on_failure = std::__make_exception_guard([&]() noexcept {
649 clear() /* noexcept */;
650 __y.clear() /* noexcept */;
651 });
652 ranges::swap(__compare_, __y.__compare_);
653 ranges::swap(__containers_.keys, __y.__containers_.keys);
654 ranges::swap(__containers_.values, __y.__containers_.values);
655 __on_failure.__complete();
656 }
657
658 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void clear() noexcept {
659 __containers_.keys.clear();
660 __containers_.values.clear();
661 }
662
663 // observers
664 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 key_compare key_comp() const { return __compare_; }
665 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 value_compare value_comp() const {
666 return value_compare(__compare_);
667 }
668
669 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const key_container_type& keys() const noexcept {
670 return __containers_.keys;
671 }
672 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const mapped_container_type&
673 values() const noexcept {
674 return __containers_.values;
675 }
676
677 // map operations
678 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator find(const key_type& __x) {
679 return __find_impl(*this, __x);
680 }
681
682 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator find(const key_type& __x) const {
683 return __find_impl(*this, __x);
684 }
685
686 template <class _Kp>
687 requires __is_compare_transparent
688 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator find(const _Kp& __x) {
689 return __find_impl(*this, __x);
690 }
691
692 template <class _Kp>
693 requires __is_compare_transparent
694 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator find(const _Kp& __x) const {
695 return __find_impl(*this, __x);
696 }
697
698 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type count(const key_type& __x) const {
699 auto [__first, __last] = equal_range(__x);
700 return __last - __first;
701 }
702
703 template <class _Kp>
704 requires __is_compare_transparent
705 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type count(const _Kp& __x) const {
706 auto [__first, __last] = equal_range(__x);
707 return __last - __first;
708 }
709
710 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool contains(const key_type& __x) const {
711 return find(__x) != end();
712 }
713
714 template <class _Kp>
715 requires __is_compare_transparent
716 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool contains(const _Kp& __x) const {
717 return find(__x) != end();
718 }
719
720 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator lower_bound(const key_type& __x) {
721 return __lower_bound<iterator>(*this, __x);
722 }
723
724 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator
725 lower_bound(const key_type& __x) const {
726 return __lower_bound<const_iterator>(*this, __x);
727 }
728
729 template <class _Kp>
730 requires __is_compare_transparent
731 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator lower_bound(const _Kp& __x) {
732 return __lower_bound<iterator>(*this, __x);
733 }
734
735 template <class _Kp>
736 requires __is_compare_transparent
737 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator lower_bound(const _Kp& __x) const {
738 return __lower_bound<const_iterator>(*this, __x);
739 }
740
741 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator upper_bound(const key_type& __x) {
742 return __upper_bound<iterator>(*this, __x);
743 }
744
745 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator
746 upper_bound(const key_type& __x) const {
747 return __upper_bound<const_iterator>(*this, __x);
748 }
749
750 template <class _Kp>
751 requires __is_compare_transparent
752 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator upper_bound(const _Kp& __x) {
753 return __upper_bound<iterator>(*this, __x);
754 }
755
756 template <class _Kp>
757 requires __is_compare_transparent
758 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator upper_bound(const _Kp& __x) const {
759 return __upper_bound<const_iterator>(*this, __x);
760 }
761
762 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, iterator>
763 equal_range(const key_type& __x) {
764 return __equal_range_impl(*this, __x);
765 }
766
767 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<const_iterator, const_iterator>
768 equal_range(const key_type& __x) const {
769 return __equal_range_impl(*this, __x);
770 }
771
772 template <class _Kp>
773 requires __is_compare_transparent
774 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, iterator>
775 equal_range(const _Kp& __x) {
776 return __equal_range_impl(*this, __x);
777 }
778 template <class _Kp>
779 requires __is_compare_transparent
780 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<const_iterator, const_iterator>
781 equal_range(const _Kp& __x) const {
782 return __equal_range_impl(*this, __x);
783 }
784
785 friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
786 operator==(const flat_multimap& __x, const flat_multimap& __y) {
787 return ranges::equal(__x, __y);
788 }
789
790 friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 auto
791 operator<=>(const flat_multimap& __x, const flat_multimap& __y) {
792 return std::lexicographical_compare_three_way(
793 __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
794 }
795
796 friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
797 swap(flat_multimap& __x, flat_multimap& __y) noexcept(noexcept(__x.swap(__y))) {
798 __x.swap(__y);
799 }
800
801private:
802 struct __ctor_uses_allocator_tag {
803 explicit _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __ctor_uses_allocator_tag() = default;
804 };
805 struct __ctor_uses_allocator_empty_tag {
806 explicit _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __ctor_uses_allocator_empty_tag() = default;
807 };
808
809 template <class _Allocator, class _KeyCont, class _MappedCont, class... _CompArg>
810 requires __allocator_ctor_constraint<_Allocator>
811 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multimap(
812 __ctor_uses_allocator_tag,
813 const _Allocator& __alloc,
814 _KeyCont&& __key_cont,
815 _MappedCont&& __mapped_cont,
816 _CompArg&&... __comp)
817 : __containers_{.keys = std::make_obj_using_allocator<key_container_type>(
818 __alloc, std::forward<_KeyCont>(__key_cont)),
819 .values = std::make_obj_using_allocator<mapped_container_type>(
820 __alloc, std::forward<_MappedCont>(__mapped_cont))},
821 __compare_(std::forward<_CompArg>(__comp)...) {}
822
823 template <class _Allocator, class... _CompArg>
824 requires __allocator_ctor_constraint<_Allocator>
825 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
826 flat_multimap(__ctor_uses_allocator_empty_tag, const _Allocator& __alloc, _CompArg&&... __comp)
827 : __containers_{.keys = std::make_obj_using_allocator<key_container_type>(__alloc),
828 .values = std::make_obj_using_allocator<mapped_container_type>(__alloc)},
829 __compare_(std::forward<_CompArg>(__comp)...) {}
830
831 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool __is_sorted(auto&& __key_container) const {
832 return ranges::is_sorted(__key_container, __compare_);
833 }
834
835 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __sort() {
836 auto __zv = ranges::views::zip(__containers_.keys, __containers_.values);
837 ranges::sort(__zv, __compare_, [](const auto& __p) -> decltype(auto) { return std::get<0>(__p); });
838 }
839
840 template <class _Self, class _KeyIter>
841 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto
842 __corresponding_mapped_it(_Self&& __self, _KeyIter&& __key_iter) {
843 return __self.__containers_.values.begin() +
844 static_cast<ranges::range_difference_t<mapped_container_type>>(
845 ranges::distance(__self.__containers_.keys.begin(), __key_iter));
846 }
847
848 template <bool _WasSorted, class _InputIterator, class _Sentinel>
849 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
850 __append_sort_merge(_InputIterator __first, _Sentinel __last) {
851 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
852 size_t __num_appended = __flat_map_utils::__append(*this, std::move(__first), std::move(__last));
853 if (__num_appended != 0) {
854 auto __zv = ranges::views::zip(__containers_.keys, __containers_.values);
855 auto __append_start_offset = __containers_.keys.size() - __num_appended;
856 auto __end = __zv.end();
857 auto __compare_key = [this](const auto& __p1, const auto& __p2) -> bool {
858 return __compare_(std::get<0>(__p1), std::get<0>(__p2));
859 };
860 if constexpr (!_WasSorted) {
861 ranges::sort(__zv.begin() + __append_start_offset, __end, __compare_key);
862 } else {
863 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
864 __is_sorted(__containers_.keys | ranges::views::drop(__append_start_offset)),
865 "Key container is not sorted");
866 }
867 ranges::inplace_merge(__zv.begin(), __zv.begin() + __append_start_offset, __end, __compare_key);
868 }
869 __on_failure.__complete();
870 }
871
872 template <class _Self, class _Kp>
873 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto __find_impl(_Self&& __self, const _Kp& __key) {
874 auto __it = __self.lower_bound(__key);
875 auto __last = __self.end();
876 if (__it == __last || __self.__compare_(__key, __it->first)) {
877 return __last;
878 }
879 return __it;
880 }
881
882 template <class _Self, class _Kp>
883 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto __equal_range_impl(_Self&& __self, const _Kp& __key) {
884 auto [__key_first, __key_last] =
885 std::equal_range(__self.__containers_.keys.begin(), __self.__containers_.keys.end(), __key, __self.__compare_);
886
887 using __iterator_type = ranges::iterator_t<decltype(__self)>;
888 return std::make_pair(__iterator_type(__key_first, __corresponding_mapped_it(__self, __key_first)),
889 __iterator_type(__key_last, __corresponding_mapped_it(__self, __key_last)));
890 }
891
892 template <class _Res, class _Self, class _Kp>
893 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static _Res __lower_bound(_Self&& __self, _Kp& __x) {
894 auto __key_iter =
895 std::lower_bound(__self.__containers_.keys.begin(), __self.__containers_.keys.end(), __x, __self.__compare_);
896 auto __mapped_iter = __corresponding_mapped_it(__self, __key_iter);
897 return _Res(std::move(__key_iter), std::move(__mapped_iter));
898 }
899
900 template <class _Res, class _Self, class _Kp>
901 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static _Res __upper_bound(_Self&& __self, _Kp& __x) {
902 auto __key_iter =
903 std::upper_bound(__self.__containers_.keys.begin(), __self.__containers_.keys.end(), __x, __self.__compare_);
904 auto __mapped_iter = __corresponding_mapped_it(__self, __key_iter);
905 return _Res(std::move(__key_iter), std::move(__mapped_iter));
906 }
907
908 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __reserve(size_t __size) {
909 if constexpr (__container_traits<_KeyContainer>::__reservable) {
910 __containers_.keys.reserve(__size);
911 }
912
913 if constexpr (__container_traits<_MappedContainer>::__reservable) {
914 __containers_.values.reserve(__size);
915 }
916 }
917
918 template <class _KIter, class _MIter>
919 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator
920 __erase(_KIter __key_iter_to_remove, _MIter __mapped_iter_to_remove) {
921 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
922 auto __key_iter = __containers_.keys.erase(__key_iter_to_remove);
923 auto __mapped_iter = __containers_.values.erase(__mapped_iter_to_remove);
924 __on_failure.__complete();
925 return iterator(std::move(__key_iter), std::move(__mapped_iter));
926 }
927
928 template <class _Key2, class _Tp2, class _Compare2, class _KeyContainer2, class _MappedContainer2, class _Predicate>
929 friend typename flat_multimap<_Key2, _Tp2, _Compare2, _KeyContainer2, _MappedContainer2>::size_type
930 _LIBCPP_CONSTEXPR_SINCE_CXX26
931 erase_if(flat_multimap<_Key2, _Tp2, _Compare2, _KeyContainer2, _MappedContainer2>&, _Predicate);
932
933 friend __flat_map_utils;
934
935 containers __containers_;
936 _LIBCPP_NO_UNIQUE_ADDRESS key_compare __compare_;
937
938 struct __key_equiv {
939 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_equiv(key_compare __c) : __comp_(__c) {}
940 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
941 operator()(const_reference __x, const_reference __y) const {
942 return !__comp_(std::get<0>(__x), std::get<0>(__y)) && !__comp_(std::get<0>(__y), std::get<0>(__x));
943 }
944 key_compare __comp_;
945 };
946};
947
948template <class _KeyContainer, class _MappedContainer, class _Compare = less<typename _KeyContainer::value_type>>
949 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> && !__is_allocator_v<_MappedContainer> &&
950 is_invocable_v<const _Compare&,
951 const typename _KeyContainer::value_type&,
952 const typename _KeyContainer::value_type&>)
953flat_multimap(_KeyContainer, _MappedContainer, _Compare = _Compare())
954 -> flat_multimap<typename _KeyContainer::value_type,
955 typename _MappedContainer::value_type,
956 _Compare,
957 _KeyContainer,
958 _MappedContainer>;
959
960template <class _KeyContainer, class _MappedContainer, class _Allocator>
961 requires(uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator> &&
962 !__is_allocator_v<_KeyContainer> && !__is_allocator_v<_MappedContainer>)
963flat_multimap(_KeyContainer, _MappedContainer, _Allocator)
964 -> flat_multimap<typename _KeyContainer::value_type,
965 typename _MappedContainer::value_type,
966 less<typename _KeyContainer::value_type>,
967 _KeyContainer,
968 _MappedContainer>;
969
970template <class _KeyContainer, class _MappedContainer, class _Compare, class _Allocator>
971 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> && !__is_allocator_v<_MappedContainer> &&
972 uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator> &&
973 is_invocable_v<const _Compare&,
974 const typename _KeyContainer::value_type&,
975 const typename _KeyContainer::value_type&>)
976flat_multimap(_KeyContainer, _MappedContainer, _Compare, _Allocator)
977 -> flat_multimap<typename _KeyContainer::value_type,
978 typename _MappedContainer::value_type,
979 _Compare,
980 _KeyContainer,
981 _MappedContainer>;
982
983template <class _KeyContainer, class _MappedContainer, class _Compare = less<typename _KeyContainer::value_type>>
984 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> && !__is_allocator_v<_MappedContainer> &&
985 is_invocable_v<const _Compare&,
986 const typename _KeyContainer::value_type&,
987 const typename _KeyContainer::value_type&>)
988flat_multimap(sorted_equivalent_t, _KeyContainer, _MappedContainer, _Compare = _Compare())
989 -> flat_multimap<typename _KeyContainer::value_type,
990 typename _MappedContainer::value_type,
991 _Compare,
992 _KeyContainer,
993 _MappedContainer>;
994
995template <class _KeyContainer, class _MappedContainer, class _Allocator>
996 requires(uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator> &&
997 !__is_allocator_v<_KeyContainer> && !__is_allocator_v<_MappedContainer>)
998flat_multimap(sorted_equivalent_t, _KeyContainer, _MappedContainer, _Allocator)
999 -> flat_multimap<typename _KeyContainer::value_type,
1000 typename _MappedContainer::value_type,
1001 less<typename _KeyContainer::value_type>,
1002 _KeyContainer,
1003 _MappedContainer>;
1004
1005template <class _KeyContainer, class _MappedContainer, class _Compare, class _Allocator>
1006 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> && !__is_allocator_v<_MappedContainer> &&
1007 uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator> &&
1008 is_invocable_v<const _Compare&,
1009 const typename _KeyContainer::value_type&,
1010 const typename _KeyContainer::value_type&>)
1011flat_multimap(sorted_equivalent_t, _KeyContainer, _MappedContainer, _Compare, _Allocator)
1012 -> flat_multimap<typename _KeyContainer::value_type,
1013 typename _MappedContainer::value_type,
1014 _Compare,
1015 _KeyContainer,
1016 _MappedContainer>;
1017
1018template <class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>>
1019 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator_v<_Compare>)
1020flat_multimap(_InputIterator, _InputIterator, _Compare = _Compare())
1021 -> flat_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare>;
1022
1023template <class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>>
1024 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator_v<_Compare>)
1025flat_multimap(sorted_equivalent_t, _InputIterator, _InputIterator, _Compare = _Compare())
1026 -> flat_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare>;
1027
1028template <ranges::input_range _Range,
1029 class _Compare = less<__range_key_type<_Range>>,
1030 class _Allocator = allocator<byte>,
1031 class = __enable_if_t<!__is_allocator_v<_Compare> && __is_allocator_v<_Allocator>>>
1032flat_multimap(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator()) -> flat_multimap<
1033 __range_key_type<_Range>,
1034 __range_mapped_type<_Range>,
1035 _Compare,
1036 vector<__range_key_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_key_type<_Range>>>,
1037 vector<__range_mapped_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_mapped_type<_Range>>>>;
1038
1039template <ranges::input_range _Range, class _Allocator, class = __enable_if_t<__is_allocator_v<_Allocator>>>
1040flat_multimap(from_range_t, _Range&&, _Allocator) -> flat_multimap<
1041 __range_key_type<_Range>,
1042 __range_mapped_type<_Range>,
1043 less<__range_key_type<_Range>>,
1044 vector<__range_key_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_key_type<_Range>>>,
1045 vector<__range_mapped_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_mapped_type<_Range>>>>;
1046
1047template <class _Key, class _Tp, class _Compare = less<_Key>>
1048 requires(!__is_allocator_v<_Compare>)
1049flat_multimap(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare()) -> flat_multimap<_Key, _Tp, _Compare>;
1050
1051template <class _Key, class _Tp, class _Compare = less<_Key>>
1052 requires(!__is_allocator_v<_Compare>)
1053flat_multimap(sorted_equivalent_t, initializer_list<pair<_Key, _Tp>>, _Compare = _Compare())
1054 -> flat_multimap<_Key, _Tp, _Compare>;
1055
1056template <class _Key, class _Tp, class _Compare, class _KeyContainer, class _MappedContainer, class _Allocator>
1057struct uses_allocator<flat_multimap<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>, _Allocator>
1058 : bool_constant<uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator>> {};
1059
1060template <class _Key, class _Tp, class _Compare, class _KeyContainer, class _MappedContainer, class _Predicate>
1061_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
1062 typename flat_multimap<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>::size_type
1063 erase_if(flat_multimap<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>& __flat_multimap, _Predicate __pred) {
1064 auto __zv = ranges::views::zip(__flat_multimap.__containers_.keys, __flat_multimap.__containers_.values);
1065 auto __first = __zv.begin();
1066 auto __last = __zv.end();
1067 auto __guard = std::__make_exception_guard([&] { __flat_multimap.clear(); });
1068 auto __it = std::remove_if(__first, __last, [&](auto&& __zipped) -> bool {
1069 using _Ref = typename flat_multimap<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>::const_reference;
1070 return __pred(_Ref(std::get<0>(__zipped), std::get<1>(__zipped)));
1071 });
1072 auto __res = __last - __it;
1073 auto __offset = __it - __first;
1074
1075 const auto __erase_container = [&](auto& __cont) { __cont.erase(__cont.begin() + __offset, __cont.end()); };
1076
1077 __erase_container(__flat_multimap.__containers_.keys);
1078 __erase_container(__flat_multimap.__containers_.values);
1079
1080 __guard.__complete();
1081 return __res;
1082}
1083
1084_LIBCPP_END_NAMESPACE_STD
1085
1086#endif // _LIBCPP_STD_VER >= 23
1087
1088_LIBCPP_POP_MACROS
1089
1090#endif // _LIBCPP___FLAT_MAP_FLAT_MULTIMAP_H