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