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