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_MULTISET_H
11#define _LIBCPP___FLAT_MAP_FLAT_MULTISET_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/ranges_equal.h>
17#include <__algorithm/ranges_inplace_merge.h>
18#include <__algorithm/ranges_is_sorted.h>
19#include <__algorithm/ranges_sort.h>
20#include <__algorithm/remove_if.h>
21#include <__algorithm/upper_bound.h>
22#include <__assert>
23#include <__compare/synth_three_way.h>
24#include <__concepts/swappable.h>
25#include <__config>
26#include <__flat_map/sorted_equivalent.h>
27#include <__flat_set/ra_iterator.h>
28#include <__flat_set/utils.h>
29#include <__functional/is_transparent.h>
30#include <__functional/operations.h>
31#include <__fwd/vector.h>
32#include <__iterator/concepts.h>
33#include <__iterator/iterator_traits.h>
34#include <__iterator/prev.h>
35#include <__iterator/reverse_iterator.h>
36#include <__memory/allocator_traits.h>
37#include <__memory/uses_allocator.h>
38#include <__memory/uses_allocator_construction.h>
39#include <__ranges/concepts.h>
40#include <__ranges/container_compatible_range.h>
41#include <__ranges/drop_view.h>
42#include <__ranges/from_range.h>
43#include <__ranges/range_adaptor.h>
44#include <__ranges/size.h>
45#include <__ranges/subrange.h>
46#include <__type_traits/container_traits.h>
47#include <__type_traits/invoke.h>
48#include <__type_traits/is_allocator.h>
49#include <__type_traits/is_nothrow_constructible.h>
50#include <__type_traits/is_same.h>
51#include <__utility/as_const.h>
52#include <__utility/exception_guard.h>
53#include <__utility/move.h>
54#include <__utility/pair.h>
55#include <__utility/scope_guard.h>
56#include <__vector/vector.h>
57#include <initializer_list>
58
59#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
60# pragma GCC system_header
61#endif
62
63_LIBCPP_PUSH_MACROS
64#include <__undef_macros>
65
66#if _LIBCPP_STD_VER >= 23
67
68_LIBCPP_BEGIN_NAMESPACE_STD
69
70template <class _Key, class _Compare = less<_Key>, class _KeyContainer = vector<_Key>>
71class flat_multiset {
72 template <class, class, class>
73 friend class flat_multiset;
74
75 friend __flat_set_utils;
76
77 static_assert(is_same_v<_Key, typename _KeyContainer::value_type>);
78 static_assert(!is_same_v<_KeyContainer, std::vector<bool>>, "vector<bool> is not a sequence container");
79
80public:
81 // types
82 using key_type = _Key;
83 using value_type = _Key;
84 using key_compare = __type_identity_t<_Compare>;
85 using value_compare = _Compare;
86 using reference = value_type&;
87 using const_reference = const value_type&;
88 using size_type = typename _KeyContainer::size_type;
89 using difference_type = typename _KeyContainer::difference_type;
90 using iterator = __ra_iterator<flat_multiset, typename _KeyContainer::const_iterator>;
91 using const_iterator = iterator;
92 using reverse_iterator = std::reverse_iterator<iterator>;
93 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
94 using container_type = _KeyContainer;
95
96public:
97 // [flat.multiset.cons], constructors
98 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multiset() noexcept(
99 is_nothrow_default_constructible_v<_KeyContainer> && is_nothrow_default_constructible_v<_Compare>)
100 : __keys_(), __compare_() {}
101
102 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multiset(const flat_multiset&) = default;
103
104 // The copy/move constructors are not specified in the spec, which means they should be defaulted.
105 // However, the move constructor can potentially leave a moved-from object in an inconsistent
106 // state if an exception is thrown.
107 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multiset(flat_multiset&& __other) noexcept(
108 is_nothrow_move_constructible_v<_KeyContainer> && is_nothrow_move_constructible_v<_Compare>)
109# if _LIBCPP_HAS_EXCEPTIONS
110 try
111# endif // _LIBCPP_HAS_EXCEPTIONS
112 : __keys_(std::move(__other.__keys_)), __compare_(std::move(__other.__compare_)) {
113 __other.clear();
114# if _LIBCPP_HAS_EXCEPTIONS
115 } catch (...) {
116 __other.clear();
117 // gcc does not like the `throw` keyword in a conditionally noexcept function
118 if constexpr (!(is_nothrow_move_constructible_v<_KeyContainer> && is_nothrow_move_constructible_v<_Compare>)) {
119 throw;
120 }
121# endif // _LIBCPP_HAS_EXCEPTIONS
122 }
123
124 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit flat_multiset(const key_compare& __comp)
125 : __keys_(), __compare_(__comp) {}
126
127 _LIBCPP_HIDE_FROM_ABI
128 _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit flat_multiset(container_type __keys, const key_compare& __comp = key_compare())
129 : __keys_(std::move(__keys)), __compare_(__comp) {
130 ranges::sort(__keys_, __compare_);
131 }
132
133 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
134 flat_multiset(sorted_equivalent_t, container_type __keys, const key_compare& __comp = key_compare())
135 : __keys_(std::move(__keys)), __compare_(__comp) {
136 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(ranges::is_sorted(__keys_, __compare_), "Key container is not sorted");
137 }
138
139 template <class _InputIterator>
140 requires __has_input_iterator_category<_InputIterator>::value
141 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
142 flat_multiset(_InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare())
143 : __keys_(), __compare_(__comp) {
144 insert(__first, __last);
145 }
146
147 template <class _InputIterator>
148 requires __has_input_iterator_category<_InputIterator>::value
149 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multiset(
150 sorted_equivalent_t, _InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare())
151 : __keys_(__first, __last), __compare_(__comp) {
152 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(ranges::is_sorted(__keys_, __compare_), "Key container is not sorted");
153 }
154
155 template <_ContainerCompatibleRange<value_type> _Range>
156 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multiset(from_range_t __fr, _Range&& __rg)
157 : flat_multiset(__fr, std::forward<_Range>(__rg), key_compare()) {}
158
159 template <_ContainerCompatibleRange<value_type> _Range>
160 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
161 flat_multiset(from_range_t, _Range&& __rg, const key_compare& __comp)
162 : flat_multiset(__comp) {
163 insert_range(std::forward<_Range>(__rg));
164 }
165
166 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
167 flat_multiset(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
168 : flat_multiset(__il.begin(), __il.end(), __comp) {}
169
170 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
171 flat_multiset(sorted_equivalent_t, initializer_list<value_type> __il, const key_compare& __comp = key_compare())
172 : flat_multiset(sorted_equivalent, __il.begin(), __il.end(), __comp) {}
173
174 template <class _Allocator>
175 requires uses_allocator<container_type, _Allocator>::value
176 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit flat_multiset(const _Allocator& __alloc)
177 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_() {}
178
179 template <class _Allocator>
180 requires uses_allocator<container_type, _Allocator>::value
181 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
182 flat_multiset(const key_compare& __comp, const _Allocator& __alloc)
183 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_(__comp) {}
184
185 template <class _Allocator>
186 requires uses_allocator<container_type, _Allocator>::value
187 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
188 flat_multiset(const container_type& __keys, const _Allocator& __alloc)
189 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __keys)), __compare_() {
190 ranges::sort(__keys_, __compare_);
191 }
192
193 template <class _Allocator>
194 requires uses_allocator<container_type, _Allocator>::value
195 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
196 flat_multiset(const container_type& __keys, const key_compare& __comp, const _Allocator& __alloc)
197 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __keys)), __compare_(__comp) {
198 ranges::sort(__keys_, __compare_);
199 }
200
201 template <class _Allocator>
202 requires uses_allocator<container_type, _Allocator>::value
203 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
204 flat_multiset(sorted_equivalent_t, const container_type& __keys, const _Allocator& __alloc)
205 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __keys)), __compare_() {
206 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(ranges::is_sorted(__keys_, __compare_), "Key container is not sorted");
207 }
208
209 template <class _Allocator>
210 requires uses_allocator<container_type, _Allocator>::value
211 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
212 flat_multiset(sorted_equivalent_t, const container_type& __keys, const key_compare& __comp, const _Allocator& __alloc)
213 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __keys)), __compare_(__comp) {
214 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(ranges::is_sorted(__keys_, __compare_), "Key container is not sorted");
215 }
216
217 template <class _Allocator>
218 requires uses_allocator<container_type, _Allocator>::value
219 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
220 flat_multiset(const flat_multiset& __other, const _Allocator& __alloc)
221 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __other.__keys_)),
222 __compare_(__other.__compare_) {}
223
224 template <class _Allocator>
225 requires uses_allocator<container_type, _Allocator>::value
226 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multiset(flat_multiset&& __other, const _Allocator& __alloc)
227# if _LIBCPP_HAS_EXCEPTIONS
228 try
229# endif // _LIBCPP_HAS_EXCEPTIONS
230 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, std::move(__other.__keys_))),
231 __compare_(std::move(__other.__compare_)) {
232 __other.clear();
233# if _LIBCPP_HAS_EXCEPTIONS
234 } catch (...) {
235 __other.clear();
236 throw;
237# endif // _LIBCPP_HAS_EXCEPTIONS
238 }
239
240 template <class _InputIterator, class _Allocator>
241 requires(__has_input_iterator_category<_InputIterator>::value && uses_allocator<container_type, _Allocator>::value)
242 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
243 flat_multiset(_InputIterator __first, _InputIterator __last, const _Allocator& __alloc)
244 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_() {
245 insert(__first, __last);
246 }
247
248 template <class _InputIterator, class _Allocator>
249 requires(__has_input_iterator_category<_InputIterator>::value && uses_allocator<container_type, _Allocator>::value)
250 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
251 flat_multiset(_InputIterator __first, _InputIterator __last, const key_compare& __comp, const _Allocator& __alloc)
252 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_(__comp) {
253 insert(__first, __last);
254 }
255
256 template <class _InputIterator, class _Allocator>
257 requires(__has_input_iterator_category<_InputIterator>::value && uses_allocator<container_type, _Allocator>::value)
258 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
259 flat_multiset(sorted_equivalent_t, _InputIterator __first, _InputIterator __last, const _Allocator& __alloc)
260 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __first, __last)), __compare_() {
261 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(ranges::is_sorted(__keys_, __compare_), "Key container is not sorted");
262 }
263
264 template <class _InputIterator, class _Allocator>
265 requires(__has_input_iterator_category<_InputIterator>::value && uses_allocator<container_type, _Allocator>::value)
266 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multiset(
267 sorted_equivalent_t,
268 _InputIterator __first,
269 _InputIterator __last,
270 const key_compare& __comp,
271 const _Allocator& __alloc)
272 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __first, __last)), __compare_(__comp) {
273 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(ranges::is_sorted(__keys_, __compare_), "Key container is not sorted");
274 }
275
276 template <_ContainerCompatibleRange<value_type> _Range, class _Allocator>
277 requires uses_allocator<container_type, _Allocator>::value
278 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
279 flat_multiset(from_range_t, _Range&& __rg, const _Allocator& __alloc)
280 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_() {
281 insert_range(std::forward<_Range>(__rg));
282 }
283
284 template <_ContainerCompatibleRange<value_type> _Range, class _Allocator>
285 requires uses_allocator<container_type, _Allocator>::value
286 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
287 flat_multiset(from_range_t, _Range&& __rg, const key_compare& __comp, const _Allocator& __alloc)
288 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_(__comp) {
289 insert_range(std::forward<_Range>(__rg));
290 }
291
292 template <class _Allocator>
293 requires uses_allocator<container_type, _Allocator>::value
294 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
295 flat_multiset(initializer_list<value_type> __il, const _Allocator& __alloc)
296 : flat_multiset(__il.begin(), __il.end(), __alloc) {}
297
298 template <class _Allocator>
299 requires uses_allocator<container_type, _Allocator>::value
300 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
301 flat_multiset(initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc)
302 : flat_multiset(__il.begin(), __il.end(), __comp, __alloc) {}
303
304 template <class _Allocator>
305 requires uses_allocator<container_type, _Allocator>::value
306 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26
307 flat_multiset(sorted_equivalent_t, initializer_list<value_type> __il, const _Allocator& __alloc)
308 : flat_multiset(sorted_equivalent, __il.begin(), __il.end(), __alloc) {}
309
310 template <class _Allocator>
311 requires uses_allocator<container_type, _Allocator>::value
312 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multiset(
313 sorted_equivalent_t, initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc)
314 : flat_multiset(sorted_equivalent, __il.begin(), __il.end(), __comp, __alloc) {}
315
316 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multiset& operator=(initializer_list<value_type> __il) {
317 clear();
318 insert(__il);
319 return *this;
320 }
321
322 // copy/move assignment are not specified in the spec (defaulted)
323 // but move assignment can potentially leave moved from object in an inconsistent
324 // state if an exception is thrown
325 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multiset& operator=(const flat_multiset&) = default;
326
327 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multiset& operator=(flat_multiset&& __other) noexcept(
328 is_nothrow_move_assignable_v<_KeyContainer> && is_nothrow_move_assignable_v<_Compare>) {
329 auto __clear_other_guard = std::__make_scope_guard([&]() noexcept { __other.clear() /* noexcept */; });
330 auto __clear_self_guard = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
331 __keys_ = std::move(__other.__keys_);
332 __compare_ = std::move(__other.__compare_);
333 __clear_self_guard.__complete();
334 return *this;
335 }
336
337 // iterators
338 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator begin() noexcept {
339 return iterator(std::as_const(__keys_).begin());
340 }
341 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator begin() const noexcept {
342 return const_iterator(__keys_.begin());
343 }
344 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator end() noexcept {
345 return iterator(std::as_const(__keys_).end());
346 }
347 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator end() const noexcept {
348 return const_iterator(__keys_.end());
349 }
350
351 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 reverse_iterator rbegin() noexcept {
352 return reverse_iterator(end());
353 }
354 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator rbegin() const noexcept {
355 return const_reverse_iterator(end());
356 }
357 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 reverse_iterator rend() noexcept {
358 return reverse_iterator(begin());
359 }
360 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator rend() const noexcept {
361 return const_reverse_iterator(begin());
362 }
363
364 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator cbegin() const noexcept {
365 return begin();
366 }
367 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator cend() const noexcept {
368 return end();
369 }
370 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator crbegin() const noexcept {
371 return const_reverse_iterator(end());
372 }
373 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator crend() const noexcept {
374 return const_reverse_iterator(begin());
375 }
376
377 // capacity
378 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool empty() const noexcept {
379 return __keys_.empty();
380 }
381 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type size() const noexcept {
382 return __keys_.size();
383 }
384 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type max_size() const noexcept {
385 return __keys_.max_size();
386 }
387
388 // [flat.multiset.modifiers], modifiers
389 template <class... _Args>
390 requires is_constructible_v<value_type, _Args...>
391 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator emplace(_Args&&... __args) {
392 if constexpr (sizeof...(__args) == 1 && (is_same_v<remove_cvref_t<_Args>, _Key> && ...)) {
393 return __emplace(std::forward<_Args>(__args)...);
394 } else {
395 return __emplace(_Key(std::forward<_Args>(__args)...));
396 }
397 }
398
399 template <class... _Args>
400 requires is_constructible_v<value_type, _Args...>
401 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator emplace_hint(const_iterator __hint, _Args&&... __args) {
402 if constexpr (sizeof...(__args) == 1 && (is_same_v<remove_cvref_t<_Args>, _Key> && ...)) {
403 return __emplace_hint(std::move(__hint), std::forward<_Args>(__args)...);
404 } else {
405 return __emplace_hint(std::move(__hint), _Key(std::forward<_Args>(__args)...));
406 }
407 }
408
409 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const value_type& __x) { return emplace(__x); }
410
411 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(value_type&& __x) {
412 return emplace(std::move(__x));
413 }
414
415 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __hint, const value_type& __x) {
416 return emplace_hint(__hint, __x);
417 }
418
419 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __hint, value_type&& __x) {
420 return emplace_hint(__hint, std::move(__x));
421 }
422
423 template <class _InputIterator>
424 requires __has_input_iterator_category<_InputIterator>::value
425 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(_InputIterator __first, _InputIterator __last) {
426 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) {
427 __reserve(__last - __first);
428 }
429 __append_sort_merge</*WasSorted = */ false>(std::move(__first), std::move(__last));
430 }
431
432 template <class _InputIterator>
433 requires __has_input_iterator_category<_InputIterator>::value
434 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
435 insert(sorted_equivalent_t, _InputIterator __first, _InputIterator __last) {
436 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) {
437 __reserve(__last - __first);
438 }
439
440 __append_sort_merge</*WasSorted = */ true>(std::move(__first), std::move(__last));
441 }
442
443 template <_ContainerCompatibleRange<value_type> _Range>
444 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert_range(_Range&& __range) {
445 if constexpr (ranges::sized_range<_Range>) {
446 __reserve(ranges::size(__range));
447 }
448
449 __append_sort_merge</*WasSorted = */ false>(std::forward<_Range>(__range));
450 }
451
452 template <_ContainerCompatibleRange<value_type> _Range>
453 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert_range(sorted_equivalent_t, _Range&& __range) {
454 if constexpr (ranges::sized_range<_Range>) {
455 __reserve(ranges::size(__range));
456 }
457
458 __append_sort_merge</*WasSorted = */ true>(std::forward<_Range>(__range));
459 }
460
461 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(initializer_list<value_type> __il) {
462 insert(__il.begin(), __il.end());
463 }
464
465 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
466 insert(sorted_equivalent_t, initializer_list<value_type> __il) {
467 insert(sorted_equivalent, __il.begin(), __il.end());
468 }
469
470 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 container_type extract() && {
471 auto __guard = std::__make_scope_guard([&]() noexcept { clear() /* noexcept */; });
472 auto __ret = std::move(__keys_);
473 return __ret;
474 }
475
476 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void replace(container_type&& __keys) {
477 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(ranges::is_sorted(__keys, __compare_), "Key container is not sorted");
478 auto __guard = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
479 __keys_ = std::move(__keys);
480 __guard.__complete();
481 }
482
483 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator erase(iterator __position) {
484 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
485 auto __key_iter = __keys_.erase(__position.__base());
486 __on_failure.__complete();
487 return iterator(__key_iter);
488 }
489
490 // The following overload is the same as the iterator overload
491 // iterator erase(const_iterator __position);
492
493 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type erase(const key_type& __x) {
494 auto [__first, __last] = equal_range(__x);
495 auto __res = __last - __first;
496 erase(__first, __last);
497 return __res;
498 }
499
500 template <class _Kp>
501 requires(__is_transparent_v<_Compare> && !is_convertible_v<_Kp &&, iterator> &&
502 !is_convertible_v<_Kp &&, const_iterator>)
503 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type erase(_Kp&& __x) {
504 auto [__first, __last] = equal_range(__x);
505 auto __res = __last - __first;
506 erase(__first, __last);
507 return __res;
508 }
509
510 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator erase(const_iterator __first, const_iterator __last) {
511 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
512 auto __key_it = __keys_.erase(__first.__base(), __last.__base());
513 __on_failure.__complete();
514 return iterator(std::move(__key_it));
515 }
516
517 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
518 swap(flat_multiset& __y) noexcept(is_nothrow_swappable_v<container_type> && is_nothrow_swappable_v<key_compare>) {
519 auto __on_failure = std::__make_exception_guard([&]() noexcept {
520 clear() /* noexcept */;
521 __y.clear() /* noexcept */;
522 });
523 ranges::swap(__compare_, __y.__compare_);
524 ranges::swap(__keys_, __y.__keys_);
525 __on_failure.__complete();
526 }
527
528 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void clear() noexcept { __keys_.clear(); }
529
530 // observers
531 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 key_compare key_comp() const { return __compare_; }
532 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 value_compare value_comp() const {
533 return __compare_;
534 }
535
536 // map operations
537 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator find(const key_type& __x) {
538 return __find_impl(*this, __x);
539 }
540
541 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator find(const key_type& __x) const {
542 return __find_impl(*this, __x);
543 }
544
545 template <class _Kp>
546 requires __is_transparent_v<_Compare>
547 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator find(const _Kp& __x) {
548 return __find_impl(*this, __x);
549 }
550
551 template <class _Kp>
552 requires __is_transparent_v<_Compare>
553 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator find(const _Kp& __x) const {
554 return __find_impl(*this, __x);
555 }
556
557 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type count(const key_type& __x) const {
558 auto [__first, __last] = equal_range(__x);
559 return __last - __first;
560 }
561
562 template <class _Kp>
563 requires __is_transparent_v<_Compare>
564 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type count(const _Kp& __x) const {
565 auto [__first, __last] = equal_range(__x);
566 return __last - __first;
567 }
568
569 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool contains(const key_type& __x) const {
570 return find(__x) != end();
571 }
572
573 template <class _Kp>
574 requires __is_transparent_v<_Compare>
575 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool contains(const _Kp& __x) const {
576 return find(__x) != end();
577 }
578
579 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator lower_bound(const key_type& __x) {
580 const auto& __keys = __keys_;
581 return iterator(std::lower_bound(__keys.begin(), __keys.end(), __x, __compare_));
582 }
583
584 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator
585 lower_bound(const key_type& __x) const {
586 return const_iterator(std::lower_bound(__keys_.begin(), __keys_.end(), __x, __compare_));
587 }
588
589 template <class _Kp>
590 requires __is_transparent_v<_Compare>
591 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator lower_bound(const _Kp& __x) {
592 const auto& __keys = __keys_;
593 return iterator(std::lower_bound(__keys.begin(), __keys.end(), __x, __compare_));
594 }
595
596 template <class _Kp>
597 requires __is_transparent_v<_Compare>
598 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator lower_bound(const _Kp& __x) const {
599 return const_iterator(std::lower_bound(__keys_.begin(), __keys_.end(), __x, __compare_));
600 }
601
602 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator upper_bound(const key_type& __x) {
603 const auto& __keys = __keys_;
604 return iterator(std::upper_bound(__keys.begin(), __keys.end(), __x, __compare_));
605 }
606
607 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator
608 upper_bound(const key_type& __x) const {
609 return const_iterator(std::upper_bound(__keys_.begin(), __keys_.end(), __x, __compare_));
610 }
611
612 template <class _Kp>
613 requires __is_transparent_v<_Compare>
614 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator upper_bound(const _Kp& __x) {
615 const auto& __keys = __keys_;
616 return iterator(std::upper_bound(__keys.begin(), __keys.end(), __x, __compare_));
617 }
618
619 template <class _Kp>
620 requires __is_transparent_v<_Compare>
621 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator upper_bound(const _Kp& __x) const {
622 return const_iterator(std::upper_bound(__keys_.begin(), __keys_.end(), __x, __compare_));
623 }
624
625 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, iterator>
626 equal_range(const key_type& __x) {
627 return __equal_range_impl(*this, __x);
628 }
629
630 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<const_iterator, const_iterator>
631 equal_range(const key_type& __x) const {
632 return __equal_range_impl(*this, __x);
633 }
634
635 template <class _Kp>
636 requires __is_transparent_v<_Compare>
637 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, iterator>
638 equal_range(const _Kp& __x) {
639 return __equal_range_impl(*this, __x);
640 }
641 template <class _Kp>
642 requires __is_transparent_v<_Compare>
643 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<const_iterator, const_iterator>
644 equal_range(const _Kp& __x) const {
645 return __equal_range_impl(*this, __x);
646 }
647
648 friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
649 operator==(const flat_multiset& __x, const flat_multiset& __y) {
650 return ranges::equal(__x, __y);
651 }
652
653 friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 auto
654 operator<=>(const flat_multiset& __x, const flat_multiset& __y) {
655 return std::lexicographical_compare_three_way(
656 __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
657 }
658
659 friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
660 swap(flat_multiset& __x, flat_multiset& __y) noexcept(noexcept(__x.swap(__y))) {
661 __x.swap(__y);
662 }
663
664private:
665 template <bool _WasSorted, class... _Args>
666 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __append_sort_merge(_Args&&... __args) {
667 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });
668 size_type __old_size = size();
669 __flat_set_utils::__append(*this, std::forward<_Args>(__args)...);
670 if constexpr (!_WasSorted) {
671 ranges::sort(__keys_.begin() + __old_size, __keys_.end(), __compare_);
672 } else {
673 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
674 ranges::is_sorted(__keys_ | ranges::views::drop(__old_size), __compare_), "Key container is not sorted");
675 }
676 ranges::inplace_merge(__keys_.begin(), __keys_.begin() + __old_size, __keys_.end(), __compare_);
677 __on_failure.__complete();
678 }
679
680 template <class _Kp>
681 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator __emplace(_Kp&& __key) {
682 auto __it = upper_bound(__key);
683 return __flat_set_utils::__emplace_exact_pos(*this, __it, std::forward<_Kp>(__key));
684 }
685
686 template <class _Kp>
687 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator __emplace_hint(const_iterator __hint, _Kp&& __key) {
688 auto __prev_larger = __hint != cbegin() && __compare_(__key, *std::prev(__hint));
689 auto __next_smaller = __hint != cend() && __compare_(*__hint, __key);
690
691 if (!__prev_larger && !__next_smaller) [[likely]] {
692 // hint correct, just use exact hint iterator
693 } else if (__prev_larger && !__next_smaller) {
694 // the hint position is more to the right than the key should have been.
695 // we want to emplace the element to a position as right as possible
696 // e.g. Insert new element "2" in the following range
697 // 1, 1, 2, 2, 2, 3, 4, 6
698 // ^
699 // |
700 // hint
701 // We want to insert "2" after the last existing "2"
702 __hint = std::upper_bound(begin(), __hint, __key, __compare_);
703 } else {
704 _LIBCPP_ASSERT_INTERNAL(!__prev_larger && __next_smaller, "this means that the multiset is not sorted");
705
706 // the hint position is more to the left than the key should have been.
707 // we want to emplace the element to a position as left as possible
708 // 1, 1, 2, 2, 2, 3, 4, 6
709 // ^
710 // |
711 // hint
712 // We want to insert "2" before the first existing "2"
713 __hint = std::lower_bound(__hint, end(), __key, __compare_);
714 }
715 return __flat_set_utils::__emplace_exact_pos(*this, __hint, std::forward<_Kp>(__key));
716 }
717
718 template <class _Self, class _Kp>
719 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto __find_impl(_Self&& __self, const _Kp& __key) {
720 auto __it = __self.lower_bound(__key);
721 auto __last = __self.end();
722 if (__it == __last || __self.__compare_(__key, *__it)) {
723 return __last;
724 }
725 return __it;
726 }
727
728 template <class _Self, class _Kp>
729 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto __equal_range_impl(_Self&& __self, const _Kp& __key) {
730 using __iter = _If<is_const_v<__libcpp_remove_reference_t<_Self>>, const_iterator, iterator>;
731 auto [__key_first, __key_last] =
732 std::equal_range(__self.__keys_.begin(), __self.__keys_.end(), __key, __self.__compare_);
733 return std::make_pair(__iter(__key_first), __iter(__key_last));
734 }
735
736 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __reserve(size_t __size) {
737 if constexpr (__container_traits<_KeyContainer>::__reservable) {
738 __keys_.reserve(__size);
739 }
740 }
741
742 template <class _Key2, class _Compare2, class _KeyContainer2, class _Predicate>
743 friend typename flat_multiset<_Key2, _Compare2, _KeyContainer2>::size_type _LIBCPP_CONSTEXPR_SINCE_CXX26
744 erase_if(flat_multiset<_Key2, _Compare2, _KeyContainer2>&, _Predicate);
745
746 _KeyContainer __keys_;
747 _LIBCPP_NO_UNIQUE_ADDRESS key_compare __compare_;
748
749 struct __key_equiv {
750 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_equiv(key_compare __c) : __comp_(__c) {}
751 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
752 operator()(const_reference __x, const_reference __y) const {
753 return !__comp_(std::get<0>(__x), std::get<0>(__y)) && !__comp_(std::get<0>(__y), std::get<0>(__x));
754 }
755 key_compare __comp_;
756 };
757};
758
759template <class _KeyContainer, class _Compare = less<typename _KeyContainer::value_type>>
760 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> &&
761 is_invocable_v<const _Compare&,
762 const typename _KeyContainer::value_type&,
763 const typename _KeyContainer::value_type&>)
764flat_multiset(_KeyContainer, _Compare = _Compare())
765 -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
766
767template <class _KeyContainer, class _Allocator>
768 requires(uses_allocator_v<_KeyContainer, _Allocator> && !__is_allocator_v<_KeyContainer>)
769flat_multiset(_KeyContainer, _Allocator)
770 -> flat_multiset<typename _KeyContainer::value_type, less<typename _KeyContainer::value_type>, _KeyContainer>;
771
772template <class _KeyContainer, class _Compare, class _Allocator>
773 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> &&
774 uses_allocator_v<_KeyContainer, _Allocator> &&
775 is_invocable_v<const _Compare&,
776 const typename _KeyContainer::value_type&,
777 const typename _KeyContainer::value_type&>)
778flat_multiset(_KeyContainer, _Compare, _Allocator)
779 -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
780
781template <class _KeyContainer, class _Compare = less<typename _KeyContainer::value_type>>
782 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> &&
783 is_invocable_v<const _Compare&,
784 const typename _KeyContainer::value_type&,
785 const typename _KeyContainer::value_type&>)
786flat_multiset(sorted_equivalent_t, _KeyContainer, _Compare = _Compare())
787 -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
788
789template <class _KeyContainer, class _Allocator>
790 requires(uses_allocator_v<_KeyContainer, _Allocator> && !__is_allocator_v<_KeyContainer>)
791flat_multiset(sorted_equivalent_t, _KeyContainer, _Allocator)
792 -> flat_multiset<typename _KeyContainer::value_type, less<typename _KeyContainer::value_type>, _KeyContainer>;
793
794template <class _KeyContainer, class _Compare, class _Allocator>
795 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> &&
796 uses_allocator_v<_KeyContainer, _Allocator> &&
797 is_invocable_v<const _Compare&,
798 const typename _KeyContainer::value_type&,
799 const typename _KeyContainer::value_type&>)
800flat_multiset(sorted_equivalent_t, _KeyContainer, _Compare, _Allocator)
801 -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
802
803template <class _InputIterator, class _Compare = less<__iterator_value_type<_InputIterator>>>
804 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator_v<_Compare>)
805flat_multiset(_InputIterator, _InputIterator, _Compare = _Compare())
806 -> flat_multiset<__iterator_value_type<_InputIterator>, _Compare>;
807
808template <class _InputIterator, class _Compare = less<__iterator_value_type<_InputIterator>>>
809 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator_v<_Compare>)
810flat_multiset(sorted_equivalent_t, _InputIterator, _InputIterator, _Compare = _Compare())
811 -> flat_multiset<__iterator_value_type<_InputIterator>, _Compare>;
812
813template <ranges::input_range _Range,
814 class _Compare = less<ranges::range_value_t<_Range>>,
815 class _Allocator = allocator<ranges::range_value_t<_Range>>,
816 class = __enable_if_t<!__is_allocator_v<_Compare> && __is_allocator_v<_Allocator>>>
817flat_multiset(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator()) -> flat_multiset<
818 ranges::range_value_t<_Range>,
819 _Compare,
820 vector<ranges::range_value_t<_Range>, __allocator_traits_rebind_t<_Allocator, ranges::range_value_t<_Range>>>>;
821
822template <ranges::input_range _Range, class _Allocator, class = __enable_if_t<__is_allocator_v<_Allocator>>>
823flat_multiset(from_range_t, _Range&&, _Allocator) -> flat_multiset<
824 ranges::range_value_t<_Range>,
825 less<ranges::range_value_t<_Range>>,
826 vector<ranges::range_value_t<_Range>, __allocator_traits_rebind_t<_Allocator, ranges::range_value_t<_Range>>>>;
827
828template <class _Key, class _Compare = less<_Key>>
829 requires(!__is_allocator_v<_Compare>)
830flat_multiset(initializer_list<_Key>, _Compare = _Compare()) -> flat_multiset<_Key, _Compare>;
831
832template <class _Key, class _Compare = less<_Key>>
833 requires(!__is_allocator_v<_Compare>)
834flat_multiset(sorted_equivalent_t, initializer_list<_Key>, _Compare = _Compare()) -> flat_multiset<_Key, _Compare>;
835
836template <class _Key, class _Compare, class _KeyContainer, class _Allocator>
837struct uses_allocator<flat_multiset<_Key, _Compare, _KeyContainer>, _Allocator>
838 : bool_constant<uses_allocator_v<_KeyContainer, _Allocator> > {};
839
840template <class _Key, class _Compare, class _KeyContainer, class _Predicate>
841_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 typename flat_multiset<_Key, _Compare, _KeyContainer>::size_type
842erase_if(flat_multiset<_Key, _Compare, _KeyContainer>& __flat_multiset, _Predicate __pred) {
843 auto __guard = std::__make_exception_guard([&] { __flat_multiset.clear(); });
844 auto __it =
845 std::remove_if(__flat_multiset.__keys_.begin(), __flat_multiset.__keys_.end(), [&](const auto& __e) -> bool {
846 return static_cast<bool>(__pred(__e));
847 });
848 auto __res = __flat_multiset.__keys_.end() - __it;
849 __flat_multiset.__keys_.erase(__it, __flat_multiset.__keys_.end());
850 __guard.__complete();
851 return __res;
852}
853
854_LIBCPP_END_NAMESPACE_STD
855
856#endif // _LIBCPP_STD_VER >= 23
857
858_LIBCPP_POP_MACROS
859
860#endif // _LIBCPP___FLAT_MAP_FLAT_MULTISET_H