master
1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP___FLAT_MAP_FLAT_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/convertible_to.h>
26#include <__concepts/swappable.h>
27#include <__config>
28#include <__cstddef/byte.h>
29#include <__cstddef/ptrdiff_t.h>
30#include <__flat_map/key_value_iterator.h>
31#include <__flat_map/sorted_equivalent.h>
32#include <__flat_map/utils.h>
33#include <__functional/invoke.h>
34#include <__functional/is_transparent.h>
35#include <__functional/operations.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/ranges_iterator_traits.h>
41#include <__iterator/reverse_iterator.h>
42#include <__memory/allocator_traits.h>
43#include <__memory/uses_allocator.h>
44#include <__memory/uses_allocator_construction.h>
45#include <__ranges/access.h>
46#include <__ranges/concepts.h>
47#include <__ranges/container_compatible_range.h>
48#include <__ranges/drop_view.h>
49#include <__ranges/from_range.h>
50#include <__ranges/ref_view.h>
51#include <__ranges/size.h>
52#include <__ranges/subrange.h>
53#include <__ranges/zip_view.h>
54#include <__type_traits/conjunction.h>
55#include <__type_traits/container_traits.h>
56#include <__type_traits/invoke.h>
57#include <__type_traits/is_allocator.h>
58#include <__type_traits/is_nothrow_constructible.h>
59#include <__type_traits/is_same.h>
60#include <__type_traits/maybe_const.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_multimap {
86 template <class, class, class, class, class>
87 friend class flat_multimap;
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_multimap, _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_multimap;
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_multimap() 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_multimap(const flat_multimap&) = default;
146
147 // The copy/move constructors are not specified in the spec, which means they should be defaulted.
148 // However, the move constructor can potentially leave a moved-from object in an inconsistent
149 // state if an exception is thrown.
150 _LIBCPP_HIDE_FROM_ABI flat_multimap(flat_multimap&& __other) noexcept(
151 is_nothrow_move_constructible_v<_KeyContainer> && is_nothrow_move_constructible_v<_MappedContainer> &&
152 is_nothrow_move_constructible_v<_Compare>)
153# if _LIBCPP_HAS_EXCEPTIONS
154 try
155# endif // _LIBCPP_HAS_EXCEPTIONS
156 : __containers_(std::move(__other.__containers_)), __compare_(std::move(__other.__compare_)) {
157 __other.clear();
158# if _LIBCPP_HAS_EXCEPTIONS
159 } catch (...) {
160 __other.clear();
161 // gcc does not like the `throw` keyword in a conditionally noexcept function
162 if constexpr (!(is_nothrow_move_constructible_v<_KeyContainer> &&
163 is_nothrow_move_constructible_v<_MappedContainer> && is_nothrow_move_constructible_v<_Compare>)) {
164 throw;
165 }
166# endif // _LIBCPP_HAS_EXCEPTIONS
167 }
168
169 template <class _Allocator>
170 requires __allocator_ctor_constraint<_Allocator>
171 _LIBCPP_HIDE_FROM_ABI flat_multimap(const flat_multimap& __other, const _Allocator& __alloc)
172 : flat_multimap(__ctor_uses_allocator_tag{},
173 __alloc,
174 __other.__containers_.keys,
175 __other.__containers_.values,
176 __other.__compare_) {}
177
178 template <class _Allocator>
179 requires __allocator_ctor_constraint<_Allocator>
180 _LIBCPP_HIDE_FROM_ABI flat_multimap(flat_multimap&& __other, const _Allocator& __alloc)
181# if _LIBCPP_HAS_EXCEPTIONS
182 try
183# endif // _LIBCPP_HAS_EXCEPTIONS
184 : flat_multimap(__ctor_uses_allocator_tag{},
185 __alloc,
186 std::move(__other.__containers_.keys),
187 std::move(__other.__containers_.values),
188 std::move(__other.__compare_)) {
189 __other.clear();
190# if _LIBCPP_HAS_EXCEPTIONS
191 } catch (...) {
192 __other.clear();
193 throw;
194# endif // _LIBCPP_HAS_EXCEPTIONS
195 }
196
197 _LIBCPP_HIDE_FROM_ABI flat_multimap(
198 key_container_type __key_cont, mapped_container_type __mapped_cont, const key_compare& __comp = key_compare())
199 : __containers_{.keys = std::move(__key_cont), .values = std::move(__mapped_cont)}, __compare_(__comp) {
200 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
201 "flat_multimap keys and mapped containers have different size");
202 __sort();
203 }
204
205 template <class _Allocator>
206 requires __allocator_ctor_constraint<_Allocator>
207 _LIBCPP_HIDE_FROM_ABI flat_multimap(
208 const key_container_type& __key_cont, const mapped_container_type& __mapped_cont, const _Allocator& __alloc)
209 : flat_multimap(__ctor_uses_allocator_tag{}, __alloc, __key_cont, __mapped_cont) {
210 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
211 "flat_multimap keys and mapped containers have different size");
212 __sort();
213 }
214
215 template <class _Allocator>
216 requires __allocator_ctor_constraint<_Allocator>
217 _LIBCPP_HIDE_FROM_ABI
218 flat_multimap(const key_container_type& __key_cont,
219 const mapped_container_type& __mapped_cont,
220 const key_compare& __comp,
221 const _Allocator& __alloc)
222 : flat_multimap(__ctor_uses_allocator_tag{}, __alloc, __key_cont, __mapped_cont, __comp) {
223 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
224 "flat_multimap keys and mapped containers have different size");
225 __sort();
226 }
227
228 _LIBCPP_HIDE_FROM_ABI
229 flat_multimap(sorted_equivalent_t,
230 key_container_type __key_cont,
231 mapped_container_type __mapped_cont,
232 const key_compare& __comp = key_compare())
233 : __containers_{.keys = std::move(__key_cont), .values = std::move(__mapped_cont)}, __compare_(__comp) {
234 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
235 "flat_multimap keys and mapped containers have different size");
236 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(__is_sorted(__containers_.keys), "Key container is not sorted");
237 }
238
239 template <class _Allocator>
240 requires __allocator_ctor_constraint<_Allocator>
241 _LIBCPP_HIDE_FROM_ABI
242 flat_multimap(sorted_equivalent_t,
243 const key_container_type& __key_cont,
244 const mapped_container_type& __mapped_cont,
245 const _Allocator& __alloc)
246 : flat_multimap(__ctor_uses_allocator_tag{}, __alloc, __key_cont, __mapped_cont) {
247 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
248 "flat_multimap keys and mapped containers have different size");
249 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(__is_sorted(__containers_.keys), "Key container is not sorted");
250 }
251
252 template <class _Allocator>
253 requires __allocator_ctor_constraint<_Allocator>
254 _LIBCPP_HIDE_FROM_ABI
255 flat_multimap(sorted_equivalent_t,
256 const key_container_type& __key_cont,
257 const mapped_container_type& __mapped_cont,
258 const key_compare& __comp,
259 const _Allocator& __alloc)
260 : flat_multimap(__ctor_uses_allocator_tag{}, __alloc, __key_cont, __mapped_cont, __comp) {
261 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
262 "flat_multimap keys and mapped containers have different size");
263 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(__is_sorted(__containers_.keys), "Key container is not sorted");
264 }
265
266 _LIBCPP_HIDE_FROM_ABI explicit flat_multimap(const key_compare& __comp) : __containers_(), __compare_(__comp) {}
267
268 template <class _Allocator>
269 requires __allocator_ctor_constraint<_Allocator>
270 _LIBCPP_HIDE_FROM_ABI 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 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
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
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 flat_multimap(_InputIterator __first, _InputIterator __last, const _Allocator& __alloc)
297 : flat_multimap(__ctor_uses_allocator_empty_tag{}, __alloc) {
298 insert(__first, __last);
299 }
300
301 template <_ContainerCompatibleRange<value_type> _Range>
302 _LIBCPP_HIDE_FROM_ABI flat_multimap(from_range_t __fr, _Range&& __rg)
303 : flat_multimap(__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_multimap(from_range_t, _Range&& __rg, const _Allocator& __alloc)
308 : flat_multimap(__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_multimap(from_range_t, _Range&& __rg, const key_compare& __comp) : flat_multimap(__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_multimap(from_range_t, _Range&& __rg, const key_compare& __comp, const _Allocator& __alloc)
320 : flat_multimap(__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 flat_multimap(
327 sorted_equivalent_t, _InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare())
328 : __containers_(), __compare_(__comp) {
329 insert(sorted_equivalent, __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_multimap(sorted_equivalent_t,
335 _InputIterator __first,
336 _InputIterator __last,
337 const key_compare& __comp,
338 const _Allocator& __alloc)
339 : flat_multimap(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) {
340 insert(sorted_equivalent, __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_multimap(sorted_equivalent_t, _InputIterator __first, _InputIterator __last, const _Allocator& __alloc)
347 : flat_multimap(__ctor_uses_allocator_empty_tag{}, __alloc) {
348 insert(sorted_equivalent, __first, __last);
349 }
350
351 _LIBCPP_HIDE_FROM_ABI flat_multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
352 : flat_multimap(__il.begin(), __il.end(), __comp) {}
353
354 template <class _Allocator>
355 requires __allocator_ctor_constraint<_Allocator>
356 _LIBCPP_HIDE_FROM_ABI
357 flat_multimap(initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc)
358 : flat_multimap(__il.begin(), __il.end(), __comp, __alloc) {}
359
360 template <class _Allocator>
361 requires __allocator_ctor_constraint<_Allocator>
362 _LIBCPP_HIDE_FROM_ABI flat_multimap(initializer_list<value_type> __il, const _Allocator& __alloc)
363 : flat_multimap(__il.begin(), __il.end(), __alloc) {}
364
365 _LIBCPP_HIDE_FROM_ABI
366 flat_multimap(sorted_equivalent_t, initializer_list<value_type> __il, const key_compare& __comp = key_compare())
367 : flat_multimap(sorted_equivalent, __il.begin(), __il.end(), __comp) {}
368
369 template <class _Allocator>
370 requires __allocator_ctor_constraint<_Allocator>
371 _LIBCPP_HIDE_FROM_ABI flat_multimap(
372 sorted_equivalent_t, initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc)
373 : flat_multimap(sorted_equivalent, __il.begin(), __il.end(), __comp, __alloc) {}
374
375 template <class _Allocator>
376 requires __allocator_ctor_constraint<_Allocator>
377 _LIBCPP_HIDE_FROM_ABI flat_multimap(sorted_equivalent_t, initializer_list<value_type> __il, const _Allocator& __alloc)
378 : flat_multimap(sorted_equivalent, __il.begin(), __il.end(), __alloc) {}
379
380 _LIBCPP_HIDE_FROM_ABI flat_multimap& operator=(initializer_list<value_type> __il) {
381 clear();
382 insert(__il);
383 return *this;
384 }
385
386 // copy/move assignment are not specified in the spec (defaulted)
387 // but move assignment can potentially leave moved from object in an inconsistent
388 // state if an exception is thrown
389 _LIBCPP_HIDE_FROM_ABI flat_multimap& operator=(const flat_multimap&) = default;
390
391 _LIBCPP_HIDE_FROM_ABI flat_multimap& operator=(flat_multimap&& __other) noexcept(
392 is_nothrow_move_assignable_v<_KeyContainer> && is_nothrow_move_assignable_v<_MappedContainer> &&
393 is_nothrow_move_assignable_v<_Compare>) {
394 auto __clear_other_guard = std::__make_scope_guard([&]() noexcept { __other.clear() /* noexcept */; });
395 auto __clear_self_guard = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
396 __containers_ = std::move(__other.__containers_);
397 __compare_ = std::move(__other.__compare_);
398 __clear_self_guard.__complete();
399 return *this;
400 }
401
402 // iterators
403 _LIBCPP_HIDE_FROM_ABI iterator begin() noexcept {
404 return iterator(__containers_.keys.begin(), __containers_.values.begin());
405 }
406
407 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const noexcept {
408 return const_iterator(__containers_.keys.begin(), __containers_.values.begin());
409 }
410
411 _LIBCPP_HIDE_FROM_ABI iterator end() noexcept {
412 return iterator(__containers_.keys.end(), __containers_.values.end());
413 }
414
415 _LIBCPP_HIDE_FROM_ABI const_iterator end() const noexcept {
416 return const_iterator(__containers_.keys.end(), __containers_.values.end());
417 }
418
419 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
420 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }
421 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
422 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }
423
424 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const noexcept { return begin(); }
425 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const noexcept { return end(); }
426 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(end()); }
427 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const noexcept { return const_reverse_iterator(begin()); }
428
429 // [flat.map.capacity], capacity
430 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI bool empty() const noexcept { return __containers_.keys.empty(); }
431
432 _LIBCPP_HIDE_FROM_ABI size_type size() const noexcept { return __containers_.keys.size(); }
433
434 _LIBCPP_HIDE_FROM_ABI size_type max_size() const noexcept {
435 return std::min<size_type>(__containers_.keys.max_size(), __containers_.values.max_size());
436 }
437
438 // [flat.map.modifiers], modifiers
439 template <class... _Args>
440 requires is_constructible_v<pair<key_type, mapped_type>, _Args...> && is_move_constructible_v<key_type> &&
441 is_move_constructible_v<mapped_type>
442 _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) {
443 std::pair<key_type, mapped_type> __pair(std::forward<_Args>(__args)...);
444 auto __key_it = std::upper_bound(__containers_.keys.begin(), __containers_.keys.end(), __pair.first, __compare_);
445 auto __mapped_it = __corresponding_mapped_it(*this, __key_it);
446
447 return __flat_map_utils::__emplace_exact_pos(
448 *this, std::move(__key_it), std::move(__mapped_it), std::move(__pair.first), std::move(__pair.second));
449 }
450
451 template <class... _Args>
452 requires is_constructible_v<pair<key_type, mapped_type>, _Args...>
453 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __hint, _Args&&... __args) {
454 std::pair<key_type, mapped_type> __pair(std::forward<_Args>(__args)...);
455
456 auto __prev_larger = __hint != cbegin() && __compare_(__pair.first, (__hint - 1)->first);
457 auto __next_smaller = __hint != cend() && __compare_(__hint->first, __pair.first);
458
459 auto __hint_distance = __hint.__key_iter_ - __containers_.keys.cbegin();
460 auto __key_iter = __containers_.keys.begin() + __hint_distance;
461 auto __mapped_iter = __containers_.values.begin() + __hint_distance;
462
463 if (!__prev_larger && !__next_smaller) [[likely]] {
464 // hint correct, just use exact hint iterators
465 } else if (__prev_larger && !__next_smaller) {
466 // the hint position is more to the right than the key should have been.
467 // we want to emplace the element to a position as right as possible
468 // e.g. Insert new element "2" in the following range
469 // 1, 1, 2, 2, 2, 3, 4, 6
470 // ^
471 // |
472 // hint
473 // We want to insert "2" after the last existing "2"
474 __key_iter = std::upper_bound(__containers_.keys.begin(), __key_iter, __pair.first, __compare_);
475 __mapped_iter = __corresponding_mapped_it(*this, __key_iter);
476 } else {
477 _LIBCPP_ASSERT_INTERNAL(!__prev_larger && __next_smaller, "this means that the multimap is not sorted");
478
479 // the hint position is more to the left than the key should have been.
480 // we want to emplace the element to a position as left as possible
481 // 1, 1, 2, 2, 2, 3, 4, 6
482 // ^
483 // |
484 // hint
485 // We want to insert "2" before the first existing "2"
486 __key_iter = std::lower_bound(__key_iter, __containers_.keys.end(), __pair.first, __compare_);
487 __mapped_iter = __corresponding_mapped_it(*this, __key_iter);
488 }
489 return __flat_map_utils::__emplace_exact_pos(
490 *this, __key_iter, __mapped_iter, std::move(__pair.first), std::move(__pair.second));
491 }
492
493 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return emplace(__x); }
494
495 _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __x) { return emplace(std::move(__x)); }
496
497 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, const value_type& __x) {
498 return emplace_hint(__hint, __x);
499 }
500
501 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, value_type&& __x) {
502 return emplace_hint(__hint, std::move(__x));
503 }
504
505 template <class _PairLike>
506 requires is_constructible_v<pair<key_type, mapped_type>, _PairLike>
507 _LIBCPP_HIDE_FROM_ABI iterator insert(_PairLike&& __x) {
508 return emplace(std::forward<_PairLike>(__x));
509 }
510
511 template <class _PairLike>
512 requires is_constructible_v<pair<key_type, mapped_type>, _PairLike>
513 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, _PairLike&& __x) {
514 return emplace_hint(__hint, std::forward<_PairLike>(__x));
515 }
516
517 template <class _InputIterator>
518 requires __has_input_iterator_category<_InputIterator>::value
519 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last) {
520 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) {
521 __reserve(__last - __first);
522 }
523 __append_sort_merge</*WasSorted = */ false>(std::move(__first), std::move(__last));
524 }
525
526 template <class _InputIterator>
527 requires __has_input_iterator_category<_InputIterator>::value
528 _LIBCPP_HIDE_FROM_ABI void insert(sorted_equivalent_t, _InputIterator __first, _InputIterator __last) {
529 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) {
530 __reserve(__last - __first);
531 }
532
533 __append_sort_merge</*WasSorted = */ true>(std::move(__first), std::move(__last));
534 }
535
536 template <_ContainerCompatibleRange<value_type> _Range>
537 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
538 if constexpr (ranges::sized_range<_Range>) {
539 __reserve(ranges::size(__range));
540 }
541
542 __append_sort_merge</*WasSorted = */ false>(ranges::begin(__range), ranges::end(__range));
543 }
544
545 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
546
547 _LIBCPP_HIDE_FROM_ABI void insert(sorted_equivalent_t, initializer_list<value_type> __il) {
548 insert(sorted_equivalent, __il.begin(), __il.end());
549 }
550
551 _LIBCPP_HIDE_FROM_ABI containers extract() && {
552 auto __guard = std::__make_scope_guard([&]() noexcept { clear() /* noexcept */; });
553 auto __ret = std::move(__containers_);
554 return __ret;
555 }
556
557 _LIBCPP_HIDE_FROM_ABI void replace(key_container_type&& __key_cont, mapped_container_type&& __mapped_cont) {
558 _LIBCPP_ASSERT_VALID_INPUT_RANGE(
559 __key_cont.size() == __mapped_cont.size(), "flat_multimap keys and mapped containers have different size");
560
561 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(__is_sorted(__key_cont), "Key container is not sorted");
562 auto __guard = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
563 __containers_.keys = std::move(__key_cont);
564 __containers_.values = std::move(__mapped_cont);
565 __guard.__complete();
566 }
567
568 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __position) {
569 return __erase(__position.__key_iter_, __position.__mapped_iter_);
570 }
571
572 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __position) {
573 return __erase(__position.__key_iter_, __position.__mapped_iter_);
574 }
575
576 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __x) {
577 auto [__first, __last] = equal_range(__x);
578 auto __res = __last - __first;
579 erase(__first, __last);
580 return __res;
581 }
582
583 template <class _Kp>
584 requires(__is_compare_transparent && !is_convertible_v<_Kp &&, iterator> &&
585 !is_convertible_v<_Kp &&, const_iterator>)
586 _LIBCPP_HIDE_FROM_ABI size_type erase(_Kp&& __x) {
587 auto [__first, __last] = equal_range(__x);
588 auto __res = __last - __first;
589 erase(__first, __last);
590 return __res;
591 }
592
593 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
594 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
595 auto __key_it = __containers_.keys.erase(__first.__key_iter_, __last.__key_iter_);
596 auto __mapped_it = __containers_.values.erase(__first.__mapped_iter_, __last.__mapped_iter_);
597 __on_failure.__complete();
598 return iterator(std::move(__key_it), std::move(__mapped_it));
599 }
600
601 _LIBCPP_HIDE_FROM_ABI void swap(flat_multimap& __y) noexcept {
602 // warning: The spec has unconditional noexcept, which means that
603 // if any of the following functions throw an exception,
604 // std::terminate will be called
605 ranges::swap(__compare_, __y.__compare_);
606 ranges::swap(__containers_.keys, __y.__containers_.keys);
607 ranges::swap(__containers_.values, __y.__containers_.values);
608 }
609
610 _LIBCPP_HIDE_FROM_ABI void clear() noexcept {
611 __containers_.keys.clear();
612 __containers_.values.clear();
613 }
614
615 // observers
616 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __compare_; }
617 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return value_compare(__compare_); }
618
619 _LIBCPP_HIDE_FROM_ABI const key_container_type& keys() const noexcept { return __containers_.keys; }
620 _LIBCPP_HIDE_FROM_ABI const mapped_container_type& values() const noexcept { return __containers_.values; }
621
622 // map operations
623 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __x) { return __find_impl(*this, __x); }
624
625 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __x) const { return __find_impl(*this, __x); }
626
627 template <class _Kp>
628 requires __is_compare_transparent
629 _LIBCPP_HIDE_FROM_ABI iterator find(const _Kp& __x) {
630 return __find_impl(*this, __x);
631 }
632
633 template <class _Kp>
634 requires __is_compare_transparent
635 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _Kp& __x) const {
636 return __find_impl(*this, __x);
637 }
638
639 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __x) const {
640 auto [__first, __last] = equal_range(__x);
641 return __last - __first;
642 }
643
644 template <class _Kp>
645 requires __is_compare_transparent
646 _LIBCPP_HIDE_FROM_ABI size_type count(const _Kp& __x) const {
647 auto [__first, __last] = equal_range(__x);
648 return __last - __first;
649 }
650
651 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __x) const { return find(__x) != end(); }
652
653 template <class _Kp>
654 requires __is_compare_transparent
655 _LIBCPP_HIDE_FROM_ABI bool contains(const _Kp& __x) const {
656 return find(__x) != end();
657 }
658
659 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __x) { return __lower_bound<iterator>(*this, __x); }
660
661 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __x) const {
662 return __lower_bound<const_iterator>(*this, __x);
663 }
664
665 template <class _Kp>
666 requires __is_compare_transparent
667 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _Kp& __x) {
668 return __lower_bound<iterator>(*this, __x);
669 }
670
671 template <class _Kp>
672 requires __is_compare_transparent
673 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _Kp& __x) const {
674 return __lower_bound<const_iterator>(*this, __x);
675 }
676
677 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __x) { return __upper_bound<iterator>(*this, __x); }
678
679 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __x) const {
680 return __upper_bound<const_iterator>(*this, __x);
681 }
682
683 template <class _Kp>
684 requires __is_compare_transparent
685 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _Kp& __x) {
686 return __upper_bound<iterator>(*this, __x);
687 }
688
689 template <class _Kp>
690 requires __is_compare_transparent
691 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _Kp& __x) const {
692 return __upper_bound<const_iterator>(*this, __x);
693 }
694
695 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __x) {
696 return __equal_range_impl(*this, __x);
697 }
698
699 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __x) const {
700 return __equal_range_impl(*this, __x);
701 }
702
703 template <class _Kp>
704 requires __is_compare_transparent
705 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _Kp& __x) {
706 return __equal_range_impl(*this, __x);
707 }
708 template <class _Kp>
709 requires __is_compare_transparent
710 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _Kp& __x) const {
711 return __equal_range_impl(*this, __x);
712 }
713
714 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const flat_multimap& __x, const flat_multimap& __y) {
715 return ranges::equal(__x, __y);
716 }
717
718 friend _LIBCPP_HIDE_FROM_ABI auto operator<=>(const flat_multimap& __x, const flat_multimap& __y) {
719 return std::lexicographical_compare_three_way(
720 __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
721 }
722
723 friend _LIBCPP_HIDE_FROM_ABI void swap(flat_multimap& __x, flat_multimap& __y) noexcept { __x.swap(__y); }
724
725private:
726 struct __ctor_uses_allocator_tag {
727 explicit _LIBCPP_HIDE_FROM_ABI __ctor_uses_allocator_tag() = default;
728 };
729 struct __ctor_uses_allocator_empty_tag {
730 explicit _LIBCPP_HIDE_FROM_ABI __ctor_uses_allocator_empty_tag() = default;
731 };
732
733 template <class _Allocator, class _KeyCont, class _MappedCont, class... _CompArg>
734 requires __allocator_ctor_constraint<_Allocator>
735 _LIBCPP_HIDE_FROM_ABI
736 flat_multimap(__ctor_uses_allocator_tag,
737 const _Allocator& __alloc,
738 _KeyCont&& __key_cont,
739 _MappedCont&& __mapped_cont,
740 _CompArg&&... __comp)
741 : __containers_{.keys = std::make_obj_using_allocator<key_container_type>(
742 __alloc, std::forward<_KeyCont>(__key_cont)),
743 .values = std::make_obj_using_allocator<mapped_container_type>(
744 __alloc, std::forward<_MappedCont>(__mapped_cont))},
745 __compare_(std::forward<_CompArg>(__comp)...) {}
746
747 template <class _Allocator, class... _CompArg>
748 requires __allocator_ctor_constraint<_Allocator>
749 _LIBCPP_HIDE_FROM_ABI flat_multimap(__ctor_uses_allocator_empty_tag, const _Allocator& __alloc, _CompArg&&... __comp)
750 : __containers_{.keys = std::make_obj_using_allocator<key_container_type>(__alloc),
751 .values = std::make_obj_using_allocator<mapped_container_type>(__alloc)},
752 __compare_(std::forward<_CompArg>(__comp)...) {}
753
754 _LIBCPP_HIDE_FROM_ABI bool __is_sorted(auto&& __key_container) const {
755 return ranges::is_sorted(__key_container, __compare_);
756 }
757
758 _LIBCPP_HIDE_FROM_ABI void __sort() {
759 auto __zv = ranges::views::zip(__containers_.keys, __containers_.values);
760 ranges::sort(__zv, __compare_, [](const auto& __p) -> decltype(auto) { return std::get<0>(__p); });
761 }
762
763 template <class _Self, class _KeyIter>
764 _LIBCPP_HIDE_FROM_ABI static auto __corresponding_mapped_it(_Self&& __self, _KeyIter&& __key_iter) {
765 return __self.__containers_.values.begin() +
766 static_cast<ranges::range_difference_t<mapped_container_type>>(
767 ranges::distance(__self.__containers_.keys.begin(), __key_iter));
768 }
769
770 template <bool _WasSorted, class _InputIterator, class _Sentinel>
771 _LIBCPP_HIDE_FROM_ABI void __append_sort_merge(_InputIterator __first, _Sentinel __last) {
772 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
773 size_t __num_appended = __flat_map_utils::__append(*this, std::move(__first), std::move(__last));
774 if (__num_appended != 0) {
775 auto __zv = ranges::views::zip(__containers_.keys, __containers_.values);
776 auto __append_start_offset = __containers_.keys.size() - __num_appended;
777 auto __end = __zv.end();
778 auto __compare_key = [this](const auto& __p1, const auto& __p2) {
779 return __compare_(std::get<0>(__p1), std::get<0>(__p2));
780 };
781 if constexpr (!_WasSorted) {
782 ranges::sort(__zv.begin() + __append_start_offset, __end, __compare_key);
783 } else {
784 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
785 __is_sorted(__containers_.keys | ranges::views::drop(__append_start_offset)),
786 "Key container is not sorted");
787 }
788 ranges::inplace_merge(__zv.begin(), __zv.begin() + __append_start_offset, __end, __compare_key);
789 }
790 __on_failure.__complete();
791 }
792
793 template <class _Self, class _Kp>
794 _LIBCPP_HIDE_FROM_ABI static auto __find_impl(_Self&& __self, const _Kp& __key) {
795 auto __it = __self.lower_bound(__key);
796 auto __last = __self.end();
797 if (__it == __last || __self.__compare_(__key, __it->first)) {
798 return __last;
799 }
800 return __it;
801 }
802
803 template <class _Self, class _Kp>
804 _LIBCPP_HIDE_FROM_ABI static auto __equal_range_impl(_Self&& __self, const _Kp& __key) {
805 auto [__key_first, __key_last] =
806 std::equal_range(__self.__containers_.keys.begin(), __self.__containers_.keys.end(), __key, __self.__compare_);
807
808 using __iterator_type = ranges::iterator_t<decltype(__self)>;
809 return std::make_pair(__iterator_type(__key_first, __corresponding_mapped_it(__self, __key_first)),
810 __iterator_type(__key_last, __corresponding_mapped_it(__self, __key_last)));
811 }
812
813 template <class _Res, class _Self, class _Kp>
814 _LIBCPP_HIDE_FROM_ABI static _Res __lower_bound(_Self&& __self, _Kp& __x) {
815 auto __key_iter =
816 std::lower_bound(__self.__containers_.keys.begin(), __self.__containers_.keys.end(), __x, __self.__compare_);
817 auto __mapped_iter = __corresponding_mapped_it(__self, __key_iter);
818 return _Res(std::move(__key_iter), std::move(__mapped_iter));
819 }
820
821 template <class _Res, class _Self, class _Kp>
822 _LIBCPP_HIDE_FROM_ABI static _Res __upper_bound(_Self&& __self, _Kp& __x) {
823 auto __key_iter =
824 std::upper_bound(__self.__containers_.keys.begin(), __self.__containers_.keys.end(), __x, __self.__compare_);
825 auto __mapped_iter = __corresponding_mapped_it(__self, __key_iter);
826 return _Res(std::move(__key_iter), std::move(__mapped_iter));
827 }
828
829 _LIBCPP_HIDE_FROM_ABI void __reserve(size_t __size) {
830 if constexpr (__container_traits<_KeyContainer>::__reservable) {
831 __containers_.keys.reserve(__size);
832 }
833
834 if constexpr (__container_traits<_MappedContainer>::__reservable) {
835 __containers_.values.reserve(__size);
836 }
837 }
838
839 template <class _KIter, class _MIter>
840 _LIBCPP_HIDE_FROM_ABI iterator __erase(_KIter __key_iter_to_remove, _MIter __mapped_iter_to_remove) {
841 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
842 auto __key_iter = __containers_.keys.erase(__key_iter_to_remove);
843 auto __mapped_iter = __containers_.values.erase(__mapped_iter_to_remove);
844 __on_failure.__complete();
845 return iterator(std::move(__key_iter), std::move(__mapped_iter));
846 }
847
848 template <class _Key2, class _Tp2, class _Compare2, class _KeyContainer2, class _MappedContainer2, class _Predicate>
849 friend typename flat_multimap<_Key2, _Tp2, _Compare2, _KeyContainer2, _MappedContainer2>::size_type
850 erase_if(flat_multimap<_Key2, _Tp2, _Compare2, _KeyContainer2, _MappedContainer2>&, _Predicate);
851
852 friend __flat_map_utils;
853
854 containers __containers_;
855 _LIBCPP_NO_UNIQUE_ADDRESS key_compare __compare_;
856
857 struct __key_equiv {
858 _LIBCPP_HIDE_FROM_ABI __key_equiv(key_compare __c) : __comp_(__c) {}
859 _LIBCPP_HIDE_FROM_ABI bool operator()(const_reference __x, const_reference __y) const {
860 return !__comp_(std::get<0>(__x), std::get<0>(__y)) && !__comp_(std::get<0>(__y), std::get<0>(__x));
861 }
862 key_compare __comp_;
863 };
864};
865
866template <class _KeyContainer, class _MappedContainer, class _Compare = less<typename _KeyContainer::value_type>>
867 requires(!__is_allocator<_Compare>::value && !__is_allocator<_KeyContainer>::value &&
868 !__is_allocator<_MappedContainer>::value &&
869 is_invocable_v<const _Compare&,
870 const typename _KeyContainer::value_type&,
871 const typename _KeyContainer::value_type&>)
872flat_multimap(_KeyContainer, _MappedContainer, _Compare = _Compare())
873 -> flat_multimap<typename _KeyContainer::value_type,
874 typename _MappedContainer::value_type,
875 _Compare,
876 _KeyContainer,
877 _MappedContainer>;
878
879template <class _KeyContainer, class _MappedContainer, class _Allocator>
880 requires(uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator> &&
881 !__is_allocator<_KeyContainer>::value && !__is_allocator<_MappedContainer>::value)
882flat_multimap(_KeyContainer, _MappedContainer, _Allocator)
883 -> flat_multimap<typename _KeyContainer::value_type,
884 typename _MappedContainer::value_type,
885 less<typename _KeyContainer::value_type>,
886 _KeyContainer,
887 _MappedContainer>;
888
889template <class _KeyContainer, class _MappedContainer, class _Compare, class _Allocator>
890 requires(!__is_allocator<_Compare>::value && !__is_allocator<_KeyContainer>::value &&
891 !__is_allocator<_MappedContainer>::value && uses_allocator_v<_KeyContainer, _Allocator> &&
892 uses_allocator_v<_MappedContainer, _Allocator> &&
893 is_invocable_v<const _Compare&,
894 const typename _KeyContainer::value_type&,
895 const typename _KeyContainer::value_type&>)
896flat_multimap(_KeyContainer, _MappedContainer, _Compare, _Allocator)
897 -> flat_multimap<typename _KeyContainer::value_type,
898 typename _MappedContainer::value_type,
899 _Compare,
900 _KeyContainer,
901 _MappedContainer>;
902
903template <class _KeyContainer, class _MappedContainer, class _Compare = less<typename _KeyContainer::value_type>>
904 requires(!__is_allocator<_Compare>::value && !__is_allocator<_KeyContainer>::value &&
905 !__is_allocator<_MappedContainer>::value &&
906 is_invocable_v<const _Compare&,
907 const typename _KeyContainer::value_type&,
908 const typename _KeyContainer::value_type&>)
909flat_multimap(sorted_equivalent_t, _KeyContainer, _MappedContainer, _Compare = _Compare())
910 -> flat_multimap<typename _KeyContainer::value_type,
911 typename _MappedContainer::value_type,
912 _Compare,
913 _KeyContainer,
914 _MappedContainer>;
915
916template <class _KeyContainer, class _MappedContainer, class _Allocator>
917 requires(uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator> &&
918 !__is_allocator<_KeyContainer>::value && !__is_allocator<_MappedContainer>::value)
919flat_multimap(sorted_equivalent_t, _KeyContainer, _MappedContainer, _Allocator)
920 -> flat_multimap<typename _KeyContainer::value_type,
921 typename _MappedContainer::value_type,
922 less<typename _KeyContainer::value_type>,
923 _KeyContainer,
924 _MappedContainer>;
925
926template <class _KeyContainer, class _MappedContainer, class _Compare, class _Allocator>
927 requires(!__is_allocator<_Compare>::value && !__is_allocator<_KeyContainer>::value &&
928 !__is_allocator<_MappedContainer>::value && uses_allocator_v<_KeyContainer, _Allocator> &&
929 uses_allocator_v<_MappedContainer, _Allocator> &&
930 is_invocable_v<const _Compare&,
931 const typename _KeyContainer::value_type&,
932 const typename _KeyContainer::value_type&>)
933flat_multimap(sorted_equivalent_t, _KeyContainer, _MappedContainer, _Compare, _Allocator)
934 -> flat_multimap<typename _KeyContainer::value_type,
935 typename _MappedContainer::value_type,
936 _Compare,
937 _KeyContainer,
938 _MappedContainer>;
939
940template <class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>>
941 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator<_Compare>::value)
942flat_multimap(_InputIterator, _InputIterator, _Compare = _Compare())
943 -> flat_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare>;
944
945template <class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>>
946 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator<_Compare>::value)
947flat_multimap(sorted_equivalent_t, _InputIterator, _InputIterator, _Compare = _Compare())
948 -> flat_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare>;
949
950template <ranges::input_range _Range,
951 class _Compare = less<__range_key_type<_Range>>,
952 class _Allocator = allocator<byte>,
953 class = __enable_if_t<!__is_allocator<_Compare>::value && __is_allocator<_Allocator>::value>>
954flat_multimap(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator()) -> flat_multimap<
955 __range_key_type<_Range>,
956 __range_mapped_type<_Range>,
957 _Compare,
958 vector<__range_key_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_key_type<_Range>>>,
959 vector<__range_mapped_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_mapped_type<_Range>>>>;
960
961template <ranges::input_range _Range, class _Allocator, class = __enable_if_t<__is_allocator<_Allocator>::value>>
962flat_multimap(from_range_t, _Range&&, _Allocator) -> flat_multimap<
963 __range_key_type<_Range>,
964 __range_mapped_type<_Range>,
965 less<__range_key_type<_Range>>,
966 vector<__range_key_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_key_type<_Range>>>,
967 vector<__range_mapped_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_mapped_type<_Range>>>>;
968
969template <class _Key, class _Tp, class _Compare = less<_Key>>
970 requires(!__is_allocator<_Compare>::value)
971flat_multimap(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare()) -> flat_multimap<_Key, _Tp, _Compare>;
972
973template <class _Key, class _Tp, class _Compare = less<_Key>>
974 requires(!__is_allocator<_Compare>::value)
975flat_multimap(sorted_equivalent_t, initializer_list<pair<_Key, _Tp>>, _Compare = _Compare())
976 -> flat_multimap<_Key, _Tp, _Compare>;
977
978template <class _Key, class _Tp, class _Compare, class _KeyContainer, class _MappedContainer, class _Allocator>
979struct uses_allocator<flat_multimap<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>, _Allocator>
980 : bool_constant<uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator>> {};
981
982template <class _Key, class _Tp, class _Compare, class _KeyContainer, class _MappedContainer, class _Predicate>
983_LIBCPP_HIDE_FROM_ABI typename flat_multimap<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>::size_type
984erase_if(flat_multimap<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>& __flat_multimap, _Predicate __pred) {
985 auto __zv = ranges::views::zip(__flat_multimap.__containers_.keys, __flat_multimap.__containers_.values);
986 auto __first = __zv.begin();
987 auto __last = __zv.end();
988 auto __guard = std::__make_exception_guard([&] { __flat_multimap.clear(); });
989 auto __it = std::remove_if(__first, __last, [&](auto&& __zipped) -> bool {
990 using _Ref = typename flat_multimap<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>::const_reference;
991 return __pred(_Ref(std::get<0>(__zipped), std::get<1>(__zipped)));
992 });
993 auto __res = __last - __it;
994 auto __offset = __it - __first;
995
996 const auto __erase_container = [&](auto& __cont) { __cont.erase(__cont.begin() + __offset, __cont.end()); };
997
998 __erase_container(__flat_multimap.__containers_.keys);
999 __erase_container(__flat_multimap.__containers_.values);
1000
1001 __guard.__complete();
1002 return __res;
1003}
1004
1005_LIBCPP_END_NAMESPACE_STD
1006
1007#endif // _LIBCPP_STD_VER >= 23
1008
1009_LIBCPP_POP_MACROS
1010
1011#endif // _LIBCPP___FLAT_MAP_FLAT_MULTIMAP_H