836 lines · c
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___FLAT_MAP_FLAT_MULTISET_H11#define _LIBCPP___FLAT_MAP_FLAT_MULTISET_H12 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_header61#endif62 63_LIBCPP_PUSH_MACROS64#include <__undef_macros>65 66#if _LIBCPP_STD_VER >= 2367 68_LIBCPP_BEGIN_NAMESPACE_STD69 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 // types82 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], constructors98 _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 inconsistent106 // 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_EXCEPTIONS110 try111# endif // _LIBCPP_HAS_EXCEPTIONS112 : __keys_(std::move(__other.__keys_)), __compare_(std::move(__other.__compare_)) {113 __other.clear();114# if _LIBCPP_HAS_EXCEPTIONS115 } catch (...) {116 __other.clear();117 // gcc does not like the `throw` keyword in a conditionally noexcept function118 if constexpr (!(is_nothrow_move_constructible_v<_KeyContainer> && is_nothrow_move_constructible_v<_Compare>)) {119 throw;120 }121# endif // _LIBCPP_HAS_EXCEPTIONS122 }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_ABI128 _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_CXX26134 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>::value141 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26142 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>::value149 _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_CXX26161 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_CXX26167 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_CXX26171 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>::value176 _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>::value181 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26182 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>::value187 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26188 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>::value195 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26196 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>::value203 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26204 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>::value211 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26212 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>::value219 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26220 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>::value226 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_multiset(flat_multiset&& __other, const _Allocator& __alloc)227# if _LIBCPP_HAS_EXCEPTIONS228 try229# endif // _LIBCPP_HAS_EXCEPTIONS230 : __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_EXCEPTIONS234 } catch (...) {235 __other.clear();236 throw;237# endif // _LIBCPP_HAS_EXCEPTIONS238 }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_CXX26243 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_CXX26251 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_CXX26259 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>::value278 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26279 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>::value286 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26287 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>::value294 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26295 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>::value300 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26301 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>::value306 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26307 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>::value312 _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 inconsistent324 // state if an exception is thrown325 _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 // iterators338 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator begin() noexcept {339 return iterator(std::as_const(__keys_).begin());340 }341 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator begin() const noexcept {342 return const_iterator(__keys_.begin());343 }344 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator end() noexcept {345 return iterator(std::as_const(__keys_).end());346 }347 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator end() const noexcept {348 return const_iterator(__keys_.end());349 }350 351 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 reverse_iterator rbegin() noexcept {352 return reverse_iterator(end());353 }354 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator rbegin() const noexcept {355 return const_reverse_iterator(end());356 }357 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 reverse_iterator rend() noexcept {358 return reverse_iterator(begin());359 }360 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator rend() const noexcept {361 return const_reverse_iterator(begin());362 }363 364 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator cbegin() const noexcept { return begin(); }365 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator cend() const noexcept { return end(); }366 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator crbegin() const noexcept {367 return const_reverse_iterator(end());368 }369 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator crend() const noexcept {370 return const_reverse_iterator(begin());371 }372 373 // capacity374 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool empty() const noexcept {375 return __keys_.empty();376 }377 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type size() const noexcept { return __keys_.size(); }378 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type max_size() const noexcept { return __keys_.max_size(); }379 380 // [flat.multiset.modifiers], modifiers381 template <class... _Args>382 requires is_constructible_v<value_type, _Args...>383 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator emplace(_Args&&... __args) {384 if constexpr (sizeof...(__args) == 1 && (is_same_v<remove_cvref_t<_Args>, _Key> && ...)) {385 return __emplace(std::forward<_Args>(__args)...);386 } else {387 return __emplace(_Key(std::forward<_Args>(__args)...));388 }389 }390 391 template <class... _Args>392 requires is_constructible_v<value_type, _Args...>393 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator emplace_hint(const_iterator __hint, _Args&&... __args) {394 if constexpr (sizeof...(__args) == 1 && (is_same_v<remove_cvref_t<_Args>, _Key> && ...)) {395 return __emplace_hint(std::move(__hint), std::forward<_Args>(__args)...);396 } else {397 return __emplace_hint(std::move(__hint), _Key(std::forward<_Args>(__args)...));398 }399 }400 401 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const value_type& __x) { return emplace(__x); }402 403 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(value_type&& __x) {404 return emplace(std::move(__x));405 }406 407 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __hint, const value_type& __x) {408 return emplace_hint(__hint, __x);409 }410 411 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __hint, value_type&& __x) {412 return emplace_hint(__hint, std::move(__x));413 }414 415 template <class _InputIterator>416 requires __has_input_iterator_category<_InputIterator>::value417 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(_InputIterator __first, _InputIterator __last) {418 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) {419 __reserve(__last - __first);420 }421 __append_sort_merge</*WasSorted = */ false>(std::move(__first), std::move(__last));422 }423 424 template <class _InputIterator>425 requires __has_input_iterator_category<_InputIterator>::value426 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void427 insert(sorted_equivalent_t, _InputIterator __first, _InputIterator __last) {428 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) {429 __reserve(__last - __first);430 }431 432 __append_sort_merge</*WasSorted = */ true>(std::move(__first), std::move(__last));433 }434 435 template <_ContainerCompatibleRange<value_type> _Range>436 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert_range(_Range&& __range) {437 if constexpr (ranges::sized_range<_Range>) {438 __reserve(ranges::size(__range));439 }440 441 __append_sort_merge</*WasSorted = */ false>(std::forward<_Range>(__range));442 }443 444 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(initializer_list<value_type> __il) {445 insert(__il.begin(), __il.end());446 }447 448 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void449 insert(sorted_equivalent_t, initializer_list<value_type> __il) {450 insert(sorted_equivalent, __il.begin(), __il.end());451 }452 453 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 container_type extract() && {454 auto __guard = std::__make_scope_guard([&]() noexcept { clear() /* noexcept */; });455 auto __ret = std::move(__keys_);456 return __ret;457 }458 459 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void replace(container_type&& __keys) {460 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(ranges::is_sorted(__keys, __compare_), "Key container is not sorted");461 auto __guard = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });462 __keys_ = std::move(__keys);463 __guard.__complete();464 }465 466 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator erase(iterator __position) {467 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });468 auto __key_iter = __keys_.erase(__position.__base());469 __on_failure.__complete();470 return iterator(__key_iter);471 }472 473 // The following overload is the same as the iterator overload474 // iterator erase(const_iterator __position);475 476 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type erase(const key_type& __x) {477 auto [__first, __last] = equal_range(__x);478 auto __res = __last - __first;479 erase(__first, __last);480 return __res;481 }482 483 template <class _Kp>484 requires(__is_transparent_v<_Compare> && !is_convertible_v<_Kp &&, iterator> &&485 !is_convertible_v<_Kp &&, const_iterator>)486 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type erase(_Kp&& __x) {487 auto [__first, __last] = equal_range(__x);488 auto __res = __last - __first;489 erase(__first, __last);490 return __res;491 }492 493 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator erase(const_iterator __first, const_iterator __last) {494 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });495 auto __key_it = __keys_.erase(__first.__base(), __last.__base());496 __on_failure.__complete();497 return iterator(std::move(__key_it));498 }499 500 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void swap(flat_multiset& __y) noexcept {501 // warning: The spec has unconditional noexcept, which means that502 // if any of the following functions throw an exception,503 // std::terminate will be called504 // This is discussed in P3567, which hasn't been voted on yet.505 ranges::swap(__compare_, __y.__compare_);506 ranges::swap(__keys_, __y.__keys_);507 }508 509 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void clear() noexcept { __keys_.clear(); }510 511 // observers512 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 key_compare key_comp() const { return __compare_; }513 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 value_compare value_comp() const { return __compare_; }514 515 // map operations516 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator find(const key_type& __x) {517 return __find_impl(*this, __x);518 }519 520 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator find(const key_type& __x) const {521 return __find_impl(*this, __x);522 }523 524 template <class _Kp>525 requires __is_transparent_v<_Compare>526 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator find(const _Kp& __x) {527 return __find_impl(*this, __x);528 }529 530 template <class _Kp>531 requires __is_transparent_v<_Compare>532 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator find(const _Kp& __x) const {533 return __find_impl(*this, __x);534 }535 536 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type count(const key_type& __x) const {537 auto [__first, __last] = equal_range(__x);538 return __last - __first;539 }540 541 template <class _Kp>542 requires __is_transparent_v<_Compare>543 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type count(const _Kp& __x) const {544 auto [__first, __last] = equal_range(__x);545 return __last - __first;546 }547 548 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool contains(const key_type& __x) const {549 return find(__x) != end();550 }551 552 template <class _Kp>553 requires __is_transparent_v<_Compare>554 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool contains(const _Kp& __x) const {555 return find(__x) != end();556 }557 558 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator lower_bound(const key_type& __x) {559 const auto& __keys = __keys_;560 return iterator(std::lower_bound(__keys.begin(), __keys.end(), __x, __compare_));561 }562 563 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator lower_bound(const key_type& __x) const {564 return const_iterator(std::lower_bound(__keys_.begin(), __keys_.end(), __x, __compare_));565 }566 567 template <class _Kp>568 requires __is_transparent_v<_Compare>569 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator lower_bound(const _Kp& __x) {570 const auto& __keys = __keys_;571 return iterator(std::lower_bound(__keys.begin(), __keys.end(), __x, __compare_));572 }573 574 template <class _Kp>575 requires __is_transparent_v<_Compare>576 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator lower_bound(const _Kp& __x) const {577 return const_iterator(std::lower_bound(__keys_.begin(), __keys_.end(), __x, __compare_));578 }579 580 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator upper_bound(const key_type& __x) {581 const auto& __keys = __keys_;582 return iterator(std::upper_bound(__keys.begin(), __keys.end(), __x, __compare_));583 }584 585 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator upper_bound(const key_type& __x) const {586 return const_iterator(std::upper_bound(__keys_.begin(), __keys_.end(), __x, __compare_));587 }588 589 template <class _Kp>590 requires __is_transparent_v<_Compare>591 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator upper_bound(const _Kp& __x) {592 const auto& __keys = __keys_;593 return iterator(std::upper_bound(__keys.begin(), __keys.end(), __x, __compare_));594 }595 596 template <class _Kp>597 requires __is_transparent_v<_Compare>598 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator upper_bound(const _Kp& __x) const {599 return const_iterator(std::upper_bound(__keys_.begin(), __keys_.end(), __x, __compare_));600 }601 602 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, iterator> equal_range(const key_type& __x) {603 return __equal_range_impl(*this, __x);604 }605 606 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<const_iterator, const_iterator>607 equal_range(const key_type& __x) const {608 return __equal_range_impl(*this, __x);609 }610 611 template <class _Kp>612 requires __is_transparent_v<_Compare>613 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, iterator> equal_range(const _Kp& __x) {614 return __equal_range_impl(*this, __x);615 }616 template <class _Kp>617 requires __is_transparent_v<_Compare>618 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<const_iterator, const_iterator>619 equal_range(const _Kp& __x) const {620 return __equal_range_impl(*this, __x);621 }622 623 friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool624 operator==(const flat_multiset& __x, const flat_multiset& __y) {625 return ranges::equal(__x, __y);626 }627 628 friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 auto629 operator<=>(const flat_multiset& __x, const flat_multiset& __y) {630 return std::lexicographical_compare_three_way(631 __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);632 }633 634 friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void635 swap(flat_multiset& __x, flat_multiset& __y) noexcept {636 __x.swap(__y);637 }638 639private:640 template <bool _WasSorted, class... _Args>641 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __append_sort_merge(_Args&&... __args) {642 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });643 size_type __old_size = size();644 __flat_set_utils::__append(*this, std::forward<_Args>(__args)...);645 if constexpr (!_WasSorted) {646 ranges::sort(__keys_.begin() + __old_size, __keys_.end(), __compare_);647 } else {648 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(649 ranges::is_sorted(__keys_ | ranges::views::drop(__old_size)), "Key container is not sorted");650 }651 ranges::inplace_merge(__keys_.begin(), __keys_.begin() + __old_size, __keys_.end(), __compare_);652 __on_failure.__complete();653 }654 655 template <class _Kp>656 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator __emplace(_Kp&& __key) {657 auto __it = upper_bound(__key);658 return __flat_set_utils::__emplace_exact_pos(*this, __it, std::forward<_Kp>(__key));659 }660 661 template <class _Kp>662 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator __emplace_hint(const_iterator __hint, _Kp&& __key) {663 auto __prev_larger = __hint != cbegin() && __compare_(__key, *std::prev(__hint));664 auto __next_smaller = __hint != cend() && __compare_(*__hint, __key);665 666 if (!__prev_larger && !__next_smaller) [[likely]] {667 // hint correct, just use exact hint iterator668 } else if (__prev_larger && !__next_smaller) {669 // the hint position is more to the right than the key should have been.670 // we want to emplace the element to a position as right as possible671 // e.g. Insert new element "2" in the following range672 // 1, 1, 2, 2, 2, 3, 4, 6673 // ^674 // |675 // hint676 // We want to insert "2" after the last existing "2"677 __hint = std::upper_bound(begin(), __hint, __key, __compare_);678 } else {679 _LIBCPP_ASSERT_INTERNAL(!__prev_larger && __next_smaller, "this means that the multiset is not sorted");680 681 // the hint position is more to the left than the key should have been.682 // we want to emplace the element to a position as left as possible683 // 1, 1, 2, 2, 2, 3, 4, 6684 // ^685 // |686 // hint687 // We want to insert "2" before the first existing "2"688 __hint = std::lower_bound(__hint, end(), __key, __compare_);689 }690 return __flat_set_utils::__emplace_exact_pos(*this, __hint, std::forward<_Kp>(__key));691 }692 693 template <class _Self, class _Kp>694 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto __find_impl(_Self&& __self, const _Kp& __key) {695 auto __it = __self.lower_bound(__key);696 auto __last = __self.end();697 if (__it == __last || __self.__compare_(__key, *__it)) {698 return __last;699 }700 return __it;701 }702 703 template <class _Self, class _Kp>704 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto __equal_range_impl(_Self&& __self, const _Kp& __key) {705 using __iter = _If<is_const_v<__libcpp_remove_reference_t<_Self>>, const_iterator, iterator>;706 auto [__key_first, __key_last] =707 std::equal_range(__self.__keys_.begin(), __self.__keys_.end(), __key, __self.__compare_);708 return std::make_pair(__iter(__key_first), __iter(__key_last));709 }710 711 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __reserve(size_t __size) {712 if constexpr (__container_traits<_KeyContainer>::__reservable) {713 __keys_.reserve(__size);714 }715 }716 717 template <class _Key2, class _Compare2, class _KeyContainer2, class _Predicate>718 friend typename flat_multiset<_Key2, _Compare2, _KeyContainer2>::size_type _LIBCPP_CONSTEXPR_SINCE_CXX26719 erase_if(flat_multiset<_Key2, _Compare2, _KeyContainer2>&, _Predicate);720 721 _KeyContainer __keys_;722 _LIBCPP_NO_UNIQUE_ADDRESS key_compare __compare_;723 724 struct __key_equiv {725 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_equiv(key_compare __c) : __comp_(__c) {}726 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool727 operator()(const_reference __x, const_reference __y) const {728 return !__comp_(std::get<0>(__x), std::get<0>(__y)) && !__comp_(std::get<0>(__y), std::get<0>(__x));729 }730 key_compare __comp_;731 };732};733 734template <class _KeyContainer, class _Compare = less<typename _KeyContainer::value_type>>735 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> &&736 is_invocable_v<const _Compare&,737 const typename _KeyContainer::value_type&,738 const typename _KeyContainer::value_type&>)739flat_multiset(_KeyContainer, _Compare = _Compare())740 -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>;741 742template <class _KeyContainer, class _Allocator>743 requires(uses_allocator_v<_KeyContainer, _Allocator> && !__is_allocator_v<_KeyContainer>)744flat_multiset(_KeyContainer, _Allocator)745 -> flat_multiset<typename _KeyContainer::value_type, less<typename _KeyContainer::value_type>, _KeyContainer>;746 747template <class _KeyContainer, class _Compare, class _Allocator>748 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> &&749 uses_allocator_v<_KeyContainer, _Allocator> &&750 is_invocable_v<const _Compare&,751 const typename _KeyContainer::value_type&,752 const typename _KeyContainer::value_type&>)753flat_multiset(_KeyContainer, _Compare, _Allocator)754 -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>;755 756template <class _KeyContainer, class _Compare = less<typename _KeyContainer::value_type>>757 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> &&758 is_invocable_v<const _Compare&,759 const typename _KeyContainer::value_type&,760 const typename _KeyContainer::value_type&>)761flat_multiset(sorted_equivalent_t, _KeyContainer, _Compare = _Compare())762 -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>;763 764template <class _KeyContainer, class _Allocator>765 requires(uses_allocator_v<_KeyContainer, _Allocator> && !__is_allocator_v<_KeyContainer>)766flat_multiset(sorted_equivalent_t, _KeyContainer, _Allocator)767 -> flat_multiset<typename _KeyContainer::value_type, less<typename _KeyContainer::value_type>, _KeyContainer>;768 769template <class _KeyContainer, class _Compare, class _Allocator>770 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> &&771 uses_allocator_v<_KeyContainer, _Allocator> &&772 is_invocable_v<const _Compare&,773 const typename _KeyContainer::value_type&,774 const typename _KeyContainer::value_type&>)775flat_multiset(sorted_equivalent_t, _KeyContainer, _Compare, _Allocator)776 -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>;777 778template <class _InputIterator, class _Compare = less<__iterator_value_type<_InputIterator>>>779 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator_v<_Compare>)780flat_multiset(_InputIterator, _InputIterator, _Compare = _Compare())781 -> flat_multiset<__iterator_value_type<_InputIterator>, _Compare>;782 783template <class _InputIterator, class _Compare = less<__iterator_value_type<_InputIterator>>>784 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator_v<_Compare>)785flat_multiset(sorted_equivalent_t, _InputIterator, _InputIterator, _Compare = _Compare())786 -> flat_multiset<__iterator_value_type<_InputIterator>, _Compare>;787 788template <ranges::input_range _Range,789 class _Compare = less<ranges::range_value_t<_Range>>,790 class _Allocator = allocator<ranges::range_value_t<_Range>>,791 class = __enable_if_t<!__is_allocator_v<_Compare> && __is_allocator_v<_Allocator>>>792flat_multiset(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator()) -> flat_multiset<793 ranges::range_value_t<_Range>,794 _Compare,795 vector<ranges::range_value_t<_Range>, __allocator_traits_rebind_t<_Allocator, ranges::range_value_t<_Range>>>>;796 797template <ranges::input_range _Range, class _Allocator, class = __enable_if_t<__is_allocator_v<_Allocator>>>798flat_multiset(from_range_t, _Range&&, _Allocator) -> flat_multiset<799 ranges::range_value_t<_Range>,800 less<ranges::range_value_t<_Range>>,801 vector<ranges::range_value_t<_Range>, __allocator_traits_rebind_t<_Allocator, ranges::range_value_t<_Range>>>>;802 803template <class _Key, class _Compare = less<_Key>>804 requires(!__is_allocator_v<_Compare>)805flat_multiset(initializer_list<_Key>, _Compare = _Compare()) -> flat_multiset<_Key, _Compare>;806 807template <class _Key, class _Compare = less<_Key>>808 requires(!__is_allocator_v<_Compare>)809flat_multiset(sorted_equivalent_t, initializer_list<_Key>, _Compare = _Compare()) -> flat_multiset<_Key, _Compare>;810 811template <class _Key, class _Compare, class _KeyContainer, class _Allocator>812struct uses_allocator<flat_multiset<_Key, _Compare, _KeyContainer>, _Allocator>813 : bool_constant<uses_allocator_v<_KeyContainer, _Allocator> > {};814 815template <class _Key, class _Compare, class _KeyContainer, class _Predicate>816_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 typename flat_multiset<_Key, _Compare, _KeyContainer>::size_type817erase_if(flat_multiset<_Key, _Compare, _KeyContainer>& __flat_multiset, _Predicate __pred) {818 auto __guard = std::__make_exception_guard([&] { __flat_multiset.clear(); });819 auto __it =820 std::remove_if(__flat_multiset.__keys_.begin(), __flat_multiset.__keys_.end(), [&](const auto& __e) -> bool {821 return static_cast<bool>(__pred(__e));822 });823 auto __res = __flat_multiset.__keys_.end() - __it;824 __flat_multiset.__keys_.erase(__it, __flat_multiset.__keys_.end());825 __guard.__complete();826 return __res;827}828 829_LIBCPP_END_NAMESPACE_STD830 831#endif // _LIBCPP_STD_VER >= 23832 833_LIBCPP_POP_MACROS834 835#endif // _LIBCPP___FLAT_MAP_FLAT_MULTISET_H836