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