1277 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_MAP_H11#define _LIBCPP___FLAT_MAP_FLAT_MAP_H12 13#include <__algorithm/lexicographical_compare_three_way.h>14#include <__algorithm/lower_bound.h>15#include <__algorithm/min.h>16#include <__algorithm/ranges_adjacent_find.h>17#include <__algorithm/ranges_equal.h>18#include <__algorithm/ranges_inplace_merge.h>19#include <__algorithm/ranges_sort.h>20#include <__algorithm/ranges_unique.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_unique.h>31#include <__flat_map/utils.h>32#include <__functional/is_transparent.h>33#include <__functional/operations.h>34#include <__fwd/memory.h>35#include <__fwd/vector.h>36#include <__iterator/concepts.h>37#include <__iterator/distance.h>38#include <__iterator/iterator_traits.h>39#include <__iterator/next.h>40#include <__iterator/ranges_iterator_traits.h>41#include <__iterator/reverse_iterator.h>42#include <__memory/allocator_traits.h>43#include <__memory/uses_allocator.h>44#include <__memory/uses_allocator_construction.h>45#include <__ranges/access.h>46#include <__ranges/concepts.h>47#include <__ranges/container_compatible_range.h>48#include <__ranges/drop_view.h>49#include <__ranges/from_range.h>50#include <__ranges/range_adaptor.h>51#include <__ranges/size.h>52#include <__ranges/subrange.h>53#include <__ranges/zip_view.h>54#include <__type_traits/conjunction.h>55#include <__type_traits/container_traits.h>56#include <__type_traits/invoke.h>57#include <__type_traits/is_allocator.h>58#include <__type_traits/is_nothrow_constructible.h>59#include <__type_traits/is_same.h>60#include <__utility/exception_guard.h>61#include <__utility/move.h>62#include <__utility/pair.h>63#include <__utility/scope_guard.h>64#include <__vector/vector.h>65#include <initializer_list>66#include <stdexcept>67 68#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)69# pragma GCC system_header70#endif71 72_LIBCPP_PUSH_MACROS73#include <__undef_macros>74 75#if _LIBCPP_STD_VER >= 2376 77_LIBCPP_BEGIN_NAMESPACE_STD78 79template <class _Key,80 class _Tp,81 class _Compare = less<_Key>,82 class _KeyContainer = vector<_Key>,83 class _MappedContainer = vector<_Tp>>84class flat_map {85 template <class, class, class, class, class>86 friend class flat_map;87 88 static_assert(is_same_v<_Key, typename _KeyContainer::value_type>);89 static_assert(is_same_v<_Tp, typename _MappedContainer::value_type>);90 static_assert(!is_same_v<_KeyContainer, std::vector<bool>>, "vector<bool> is not a sequence container");91 static_assert(!is_same_v<_MappedContainer, std::vector<bool>>, "vector<bool> is not a sequence container");92 93 template <bool _Const>94 using __iterator _LIBCPP_NODEBUG = __key_value_iterator<flat_map, _KeyContainer, _MappedContainer, _Const>;95 96public:97 // types98 using key_type = _Key;99 using mapped_type = _Tp;100 using value_type = pair<key_type, mapped_type>;101 using key_compare = __type_identity_t<_Compare>;102 using reference = pair<const key_type&, mapped_type&>;103 using const_reference = pair<const key_type&, const mapped_type&>;104 using size_type = size_t;105 using difference_type = ptrdiff_t;106 using iterator = __iterator<false>; // see [container.requirements]107 using const_iterator = __iterator<true>; // see [container.requirements]108 using reverse_iterator = std::reverse_iterator<iterator>;109 using const_reverse_iterator = std::reverse_iterator<const_iterator>;110 using key_container_type = _KeyContainer;111 using mapped_container_type = _MappedContainer;112 113 class value_compare {114 private:115 _LIBCPP_NO_UNIQUE_ADDRESS key_compare __comp_;116 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 value_compare(key_compare __c) : __comp_(__c) {}117 friend flat_map;118 119 public:120 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool121 operator()(const_reference __x, const_reference __y) const {122 return __comp_(__x.first, __y.first);123 }124 };125 126 struct containers {127 key_container_type keys;128 mapped_container_type values;129 };130 131private:132 template <class _Allocator>133 _LIBCPP_HIDE_FROM_ABI static constexpr bool __allocator_ctor_constraint =134 _And<uses_allocator<key_container_type, _Allocator>, uses_allocator<mapped_container_type, _Allocator>>::value;135 136 _LIBCPP_HIDE_FROM_ABI static constexpr bool __is_compare_transparent = __is_transparent_v<_Compare>;137 138public:139 // [flat.map.cons], construct/copy/destroy140 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map() noexcept(141 is_nothrow_default_constructible_v<_KeyContainer> && is_nothrow_default_constructible_v<_MappedContainer> &&142 is_nothrow_default_constructible_v<_Compare>)143 : __containers_(), __compare_() {}144 145 _LIBCPP_HIDE_FROM_ABI flat_map(const flat_map&) = default;146 147 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(flat_map&& __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_CXX26 flat_map(const flat_map& __other, const _Allocator& __alloc)169 : flat_map(__ctor_uses_allocator_tag{},170 __alloc,171 __other.__containers_.keys,172 __other.__containers_.values,173 __other.__compare_) {}174 175 template <class _Allocator>176 requires __allocator_ctor_constraint<_Allocator>177 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(flat_map&& __other, const _Allocator& __alloc)178# if _LIBCPP_HAS_EXCEPTIONS179 try180# endif // _LIBCPP_HAS_EXCEPTIONS181 : flat_map(__ctor_uses_allocator_tag{},182 __alloc,183 std::move(__other.__containers_.keys),184 std::move(__other.__containers_.values),185 std::move(__other.__compare_)) {186 __other.clear();187# if _LIBCPP_HAS_EXCEPTIONS188 } catch (...) {189 __other.clear();190 throw;191# endif // _LIBCPP_HAS_EXCEPTIONS192 }193 194 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(195 key_container_type __key_cont, mapped_container_type __mapped_cont, const key_compare& __comp = key_compare())196 : __containers_{.keys = std::move(__key_cont), .values = std::move(__mapped_cont)}, __compare_(__comp) {197 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),198 "flat_map keys and mapped containers have different size");199 __sort_and_unique();200 }201 202 template <class _Allocator>203 requires __allocator_ctor_constraint<_Allocator>204 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26205 flat_map(const key_container_type& __key_cont, const mapped_container_type& __mapped_cont, const _Allocator& __alloc)206 : flat_map(__ctor_uses_allocator_tag{}, __alloc, __key_cont, __mapped_cont) {207 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),208 "flat_map keys and mapped containers have different size");209 __sort_and_unique();210 }211 212 template <class _Allocator>213 requires __allocator_ctor_constraint<_Allocator>214 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26215 flat_map(const key_container_type& __key_cont,216 const mapped_container_type& __mapped_cont,217 const key_compare& __comp,218 const _Allocator& __alloc)219 : flat_map(__ctor_uses_allocator_tag{}, __alloc, __key_cont, __mapped_cont, __comp) {220 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),221 "flat_map keys and mapped containers have different size");222 __sort_and_unique();223 }224 225 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26226 flat_map(sorted_unique_t,227 key_container_type __key_cont,228 mapped_container_type __mapped_cont,229 const key_compare& __comp = key_compare())230 : __containers_{.keys = std::move(__key_cont), .values = std::move(__mapped_cont)}, __compare_(__comp) {231 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),232 "flat_map keys and mapped containers have different size");233 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(234 __is_sorted_and_unique(__containers_.keys), "Either the key container is not sorted or it contains duplicates");235 }236 237 template <class _Allocator>238 requires __allocator_ctor_constraint<_Allocator>239 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26240 flat_map(sorted_unique_t,241 const key_container_type& __key_cont,242 const mapped_container_type& __mapped_cont,243 const _Allocator& __alloc)244 : flat_map(__ctor_uses_allocator_tag{}, __alloc, __key_cont, __mapped_cont) {245 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),246 "flat_map keys and mapped containers have different size");247 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(248 __is_sorted_and_unique(__containers_.keys), "Either the key container is not sorted or it contains duplicates");249 }250 251 template <class _Allocator>252 requires __allocator_ctor_constraint<_Allocator>253 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(254 sorted_unique_t,255 const key_container_type& __key_cont,256 const mapped_container_type& __mapped_cont,257 const key_compare& __comp,258 const _Allocator& __alloc)259 : flat_map(__ctor_uses_allocator_tag{}, __alloc, __key_cont, __mapped_cont, __comp) {260 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),261 "flat_map keys and mapped containers have different size");262 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(263 __is_sorted_and_unique(__containers_.keys), "Either the key container is not sorted or it contains duplicates");264 }265 266 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit flat_map(const key_compare& __comp)267 : __containers_(), __compare_(__comp) {}268 269 template <class _Allocator>270 requires __allocator_ctor_constraint<_Allocator>271 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(const key_compare& __comp, const _Allocator& __alloc)272 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) {}273 274 template <class _Allocator>275 requires __allocator_ctor_constraint<_Allocator>276 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit flat_map(const _Allocator& __alloc)277 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc) {}278 279 template <class _InputIterator>280 requires __has_input_iterator_category<_InputIterator>::value281 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26282 flat_map(_InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare())283 : __containers_(), __compare_(__comp) {284 insert(__first, __last);285 }286 287 template <class _InputIterator, class _Allocator>288 requires(__has_input_iterator_category<_InputIterator>::value && __allocator_ctor_constraint<_Allocator>)289 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26290 flat_map(_InputIterator __first, _InputIterator __last, const key_compare& __comp, const _Allocator& __alloc)291 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) {292 insert(__first, __last);293 }294 295 template <class _InputIterator, class _Allocator>296 requires(__has_input_iterator_category<_InputIterator>::value && __allocator_ctor_constraint<_Allocator>)297 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26298 flat_map(_InputIterator __first, _InputIterator __last, const _Allocator& __alloc)299 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc) {300 insert(__first, __last);301 }302 303 template <_ContainerCompatibleRange<value_type> _Range>304 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(from_range_t __fr, _Range&& __rg)305 : flat_map(__fr, std::forward<_Range>(__rg), key_compare()) {}306 307 template <_ContainerCompatibleRange<value_type> _Range, class _Allocator>308 requires __allocator_ctor_constraint<_Allocator>309 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(from_range_t, _Range&& __rg, const _Allocator& __alloc)310 : flat_map(__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_CXX26 flat_map(from_range_t, _Range&& __rg, const key_compare& __comp)316 : flat_map(__comp) {317 insert_range(std::forward<_Range>(__rg));318 }319 320 template <_ContainerCompatibleRange<value_type> _Range, class _Allocator>321 requires __allocator_ctor_constraint<_Allocator>322 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26323 flat_map(from_range_t, _Range&& __rg, const key_compare& __comp, const _Allocator& __alloc)324 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) {325 insert_range(std::forward<_Range>(__rg));326 }327 328 template <class _InputIterator>329 requires __has_input_iterator_category<_InputIterator>::value330 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26331 flat_map(sorted_unique_t, _InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare())332 : __containers_(), __compare_(__comp) {333 insert(sorted_unique, __first, __last);334 }335 template <class _InputIterator, class _Allocator>336 requires(__has_input_iterator_category<_InputIterator>::value && __allocator_ctor_constraint<_Allocator>)337 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(338 sorted_unique_t,339 _InputIterator __first,340 _InputIterator __last,341 const key_compare& __comp,342 const _Allocator& __alloc)343 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) {344 insert(sorted_unique, __first, __last);345 }346 347 template <class _InputIterator, class _Allocator>348 requires(__has_input_iterator_category<_InputIterator>::value && __allocator_ctor_constraint<_Allocator>)349 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26350 flat_map(sorted_unique_t, _InputIterator __first, _InputIterator __last, const _Allocator& __alloc)351 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc) {352 insert(sorted_unique, __first, __last);353 }354 355 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26356 flat_map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())357 : flat_map(__il.begin(), __il.end(), __comp) {}358 359 template <class _Allocator>360 requires __allocator_ctor_constraint<_Allocator>361 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26362 flat_map(initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc)363 : flat_map(__il.begin(), __il.end(), __comp, __alloc) {}364 365 template <class _Allocator>366 requires __allocator_ctor_constraint<_Allocator>367 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26368 flat_map(initializer_list<value_type> __il, const _Allocator& __alloc)369 : flat_map(__il.begin(), __il.end(), __alloc) {}370 371 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26372 flat_map(sorted_unique_t, initializer_list<value_type> __il, const key_compare& __comp = key_compare())373 : flat_map(sorted_unique, __il.begin(), __il.end(), __comp) {}374 375 template <class _Allocator>376 requires __allocator_ctor_constraint<_Allocator>377 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26378 flat_map(sorted_unique_t, initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc)379 : flat_map(sorted_unique, __il.begin(), __il.end(), __comp, __alloc) {}380 381 template <class _Allocator>382 requires __allocator_ctor_constraint<_Allocator>383 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26384 flat_map(sorted_unique_t, initializer_list<value_type> __il, const _Allocator& __alloc)385 : flat_map(sorted_unique, __il.begin(), __il.end(), __alloc) {}386 387 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map& operator=(initializer_list<value_type> __il) {388 clear();389 insert(__il);390 return *this;391 }392 393 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map& operator=(const flat_map&) = default;394 395 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map& operator=(flat_map&& __other) noexcept(396 is_nothrow_move_assignable_v<_KeyContainer> && is_nothrow_move_assignable_v<_MappedContainer> &&397 is_nothrow_move_assignable_v<_Compare>) {398 // No matter what happens, we always want to clear the other container before returning399 // since we moved from it400 auto __clear_other_guard = std::__make_scope_guard([&]() noexcept { __other.clear() /* noexcept */; });401 {402 // If an exception is thrown, we have no choice but to clear *this to preserve invariants403 auto __on_exception = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });404 __containers_ = std::move(__other.__containers_);405 __compare_ = std::move(__other.__compare_);406 __on_exception.__complete();407 }408 return *this;409 }410 411 // iterators412 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator begin() noexcept {413 return iterator(__containers_.keys.begin(), __containers_.values.begin());414 }415 416 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator begin() const noexcept {417 return const_iterator(__containers_.keys.begin(), __containers_.values.begin());418 }419 420 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator end() noexcept {421 return iterator(__containers_.keys.end(), __containers_.values.end());422 }423 424 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator end() const noexcept {425 return const_iterator(__containers_.keys.end(), __containers_.values.end());426 }427 428 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 reverse_iterator rbegin() noexcept {429 return reverse_iterator(end());430 }431 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator rbegin() const noexcept {432 return const_reverse_iterator(end());433 }434 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 reverse_iterator rend() noexcept {435 return reverse_iterator(begin());436 }437 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator rend() const noexcept {438 return const_reverse_iterator(begin());439 }440 441 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator cbegin() const noexcept {442 return begin();443 }444 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator cend() const noexcept {445 return end();446 }447 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator crbegin() const noexcept {448 return const_reverse_iterator(end());449 }450 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator crend() const noexcept {451 return const_reverse_iterator(begin());452 }453 454 // [flat.map.capacity], capacity455 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool empty() const noexcept {456 return __containers_.keys.empty();457 }458 459 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type size() const noexcept {460 return __containers_.keys.size();461 }462 463 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type max_size() const noexcept {464 return std::min<size_type>(__containers_.keys.max_size(), __containers_.values.max_size());465 }466 467 // [flat.map.access], element access468 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 mapped_type& operator[](const key_type& __x)469 requires is_constructible_v<mapped_type>470 {471 return try_emplace(__x).first->second;472 }473 474 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 mapped_type& operator[](key_type&& __x)475 requires is_constructible_v<mapped_type>476 {477 return try_emplace(std::move(__x)).first->second;478 }479 480 template <class _Kp>481 requires(__is_compare_transparent && is_constructible_v<key_type, _Kp> && is_constructible_v<mapped_type> &&482 !is_convertible_v<_Kp &&, const_iterator> && !is_convertible_v<_Kp &&, iterator>)483 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 mapped_type& operator[](_Kp&& __x) {484 return try_emplace(std::forward<_Kp>(__x)).first->second;485 }486 487 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 mapped_type& at(const key_type& __x) {488 auto __it = find(__x);489 if (__it == end()) {490 std::__throw_out_of_range("flat_map::at(const key_type&): Key does not exist");491 }492 return __it->second;493 }494 495 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const mapped_type& at(const key_type& __x) const {496 auto __it = find(__x);497 if (__it == end()) {498 std::__throw_out_of_range("flat_map::at(const key_type&) const: Key does not exist");499 }500 return __it->second;501 }502 503 template <class _Kp>504 requires __is_compare_transparent505 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 mapped_type& at(const _Kp& __x) {506 auto __it = find(__x);507 if (__it == end()) {508 std::__throw_out_of_range("flat_map::at(const K&): Key does not exist");509 }510 return __it->second;511 }512 513 template <class _Kp>514 requires __is_compare_transparent515 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const mapped_type& at(const _Kp& __x) const {516 auto __it = find(__x);517 if (__it == end()) {518 std::__throw_out_of_range("flat_map::at(const K&) const: Key does not exist");519 }520 return __it->second;521 }522 523 // [flat.map.modifiers], modifiers524 template <class... _Args>525 requires is_constructible_v<pair<key_type, mapped_type>, _Args...>526 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> emplace(_Args&&... __args) {527 std::pair<key_type, mapped_type> __pair(std::forward<_Args>(__args)...);528 return __try_emplace(std::move(__pair.first), std::move(__pair.second));529 }530 531 template <class... _Args>532 requires is_constructible_v<pair<key_type, mapped_type>, _Args...>533 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator emplace_hint(const_iterator __hint, _Args&&... __args) {534 std::pair<key_type, mapped_type> __pair(std::forward<_Args>(__args)...);535 return __try_emplace_hint(__hint, std::move(__pair.first), std::move(__pair.second)).first;536 }537 538 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> insert(const value_type& __x) {539 return emplace(__x);540 }541 542 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> insert(value_type&& __x) {543 return emplace(std::move(__x));544 }545 546 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __hint, const value_type& __x) {547 return emplace_hint(__hint, __x);548 }549 550 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __hint, value_type&& __x) {551 return emplace_hint(__hint, std::move(__x));552 }553 554 template <class _PairLike>555 requires is_constructible_v<pair<key_type, mapped_type>, _PairLike>556 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> insert(_PairLike&& __x) {557 return emplace(std::forward<_PairLike>(__x));558 }559 560 template <class _PairLike>561 requires is_constructible_v<pair<key_type, mapped_type>, _PairLike>562 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __hint, _PairLike&& __x) {563 return emplace_hint(__hint, std::forward<_PairLike>(__x));564 }565 566 template <class _InputIterator>567 requires __has_input_iterator_category<_InputIterator>::value568 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(_InputIterator __first, _InputIterator __last) {569 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) {570 __reserve(__last - __first);571 }572 __append_sort_merge_unique</*WasSorted = */ false>(std::move(__first), std::move(__last));573 }574 575 template <class _InputIterator>576 requires __has_input_iterator_category<_InputIterator>::value577 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void578 insert(sorted_unique_t, _InputIterator __first, _InputIterator __last) {579 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) {580 __reserve(__last - __first);581 }582 583 __append_sort_merge_unique</*WasSorted = */ true>(std::move(__first), std::move(__last));584 }585 586 template <_ContainerCompatibleRange<value_type> _Range>587 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert_range(_Range&& __range) {588 if constexpr (ranges::sized_range<_Range>) {589 __reserve(ranges::size(__range));590 }591 592 __append_sort_merge_unique</*WasSorted = */ false>(ranges::begin(__range), ranges::end(__range));593 }594 595 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(initializer_list<value_type> __il) {596 insert(__il.begin(), __il.end());597 }598 599 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(sorted_unique_t, initializer_list<value_type> __il) {600 insert(sorted_unique, __il.begin(), __il.end());601 }602 603 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 containers extract() && {604 auto __guard = std::__make_scope_guard([&]() noexcept { clear() /* noexcept */; });605 auto __ret = std::move(__containers_);606 return __ret;607 }608 609 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void610 replace(key_container_type&& __key_cont, mapped_container_type&& __mapped_cont) {611 _LIBCPP_ASSERT_VALID_INPUT_RANGE(612 __key_cont.size() == __mapped_cont.size(), "flat_map keys and mapped containers have different size");613 614 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(615 __is_sorted_and_unique(__key_cont), "Either the key container is not sorted or it contains duplicates");616 auto __guard = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });617 __containers_.keys = std::move(__key_cont);618 __containers_.values = std::move(__mapped_cont);619 __guard.__complete();620 }621 622 template <class... _Args>623 requires is_constructible_v<mapped_type, _Args...>624 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool>625 try_emplace(const key_type& __key, _Args&&... __args) {626 return __try_emplace(__key, std::forward<_Args>(__args)...);627 }628 629 template <class... _Args>630 requires is_constructible_v<mapped_type, _Args...>631 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool>632 try_emplace(key_type&& __key, _Args&&... __args) {633 return __try_emplace(std::move(__key), std::forward<_Args>(__args)...);634 }635 636 template <class _Kp, class... _Args>637 requires(__is_compare_transparent && is_constructible_v<key_type, _Kp> &&638 is_constructible_v<mapped_type, _Args...> && !is_convertible_v<_Kp &&, const_iterator> &&639 !is_convertible_v<_Kp &&, iterator>)640 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> try_emplace(_Kp&& __key, _Args&&... __args) {641 return __try_emplace(std::forward<_Kp>(__key), std::forward<_Args>(__args)...);642 }643 644 template <class... _Args>645 requires is_constructible_v<mapped_type, _Args...>646 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator647 try_emplace(const_iterator __hint, const key_type& __key, _Args&&... __args) {648 return __try_emplace_hint(__hint, __key, std::forward<_Args>(__args)...).first;649 }650 651 template <class... _Args>652 requires is_constructible_v<mapped_type, _Args...>653 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator654 try_emplace(const_iterator __hint, key_type&& __key, _Args&&... __args) {655 return __try_emplace_hint(__hint, std::move(__key), std::forward<_Args>(__args)...).first;656 }657 658 template <class _Kp, class... _Args>659 requires __is_compare_transparent && is_constructible_v<key_type, _Kp> && is_constructible_v<mapped_type, _Args...>660 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator661 try_emplace(const_iterator __hint, _Kp&& __key, _Args&&... __args) {662 return __try_emplace_hint(__hint, std::forward<_Kp>(__key), std::forward<_Args>(__args)...).first;663 }664 665 template <class _Mapped>666 requires is_assignable_v<mapped_type&, _Mapped> && is_constructible_v<mapped_type, _Mapped>667 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool>668 insert_or_assign(const key_type& __key, _Mapped&& __obj) {669 return __insert_or_assign(__key, std::forward<_Mapped>(__obj));670 }671 672 template <class _Mapped>673 requires is_assignable_v<mapped_type&, _Mapped> && is_constructible_v<mapped_type, _Mapped>674 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool>675 insert_or_assign(key_type&& __key, _Mapped&& __obj) {676 return __insert_or_assign(std::move(__key), std::forward<_Mapped>(__obj));677 }678 679 template <class _Kp, class _Mapped>680 requires __is_compare_transparent && is_constructible_v<key_type, _Kp> && is_assignable_v<mapped_type&, _Mapped> &&681 is_constructible_v<mapped_type, _Mapped>682 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool>683 insert_or_assign(_Kp&& __key, _Mapped&& __obj) {684 return __insert_or_assign(std::forward<_Kp>(__key), std::forward<_Mapped>(__obj));685 }686 687 template <class _Mapped>688 requires is_assignable_v<mapped_type&, _Mapped> && is_constructible_v<mapped_type, _Mapped>689 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator690 insert_or_assign(const_iterator __hint, const key_type& __key, _Mapped&& __obj) {691 return __insert_or_assign(__hint, __key, std::forward<_Mapped>(__obj));692 }693 694 template <class _Mapped>695 requires is_assignable_v<mapped_type&, _Mapped> && is_constructible_v<mapped_type, _Mapped>696 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator697 insert_or_assign(const_iterator __hint, key_type&& __key, _Mapped&& __obj) {698 return __insert_or_assign(__hint, std::move(__key), std::forward<_Mapped>(__obj));699 }700 701 template <class _Kp, class _Mapped>702 requires __is_compare_transparent && is_constructible_v<key_type, _Kp> && is_assignable_v<mapped_type&, _Mapped> &&703 is_constructible_v<mapped_type, _Mapped>704 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator705 insert_or_assign(const_iterator __hint, _Kp&& __key, _Mapped&& __obj) {706 return __insert_or_assign(__hint, std::forward<_Kp>(__key), std::forward<_Mapped>(__obj));707 }708 709 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator erase(iterator __position) {710 return __erase(__position.__key_iter_, __position.__mapped_iter_);711 }712 713 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator erase(const_iterator __position) {714 return __erase(__position.__key_iter_, __position.__mapped_iter_);715 }716 717 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type erase(const key_type& __x) {718 auto __iter = find(__x);719 if (__iter != end()) {720 erase(__iter);721 return 1;722 }723 return 0;724 }725 726 template <class _Kp>727 requires(__is_compare_transparent && !is_convertible_v<_Kp &&, iterator> &&728 !is_convertible_v<_Kp &&, const_iterator>)729 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type erase(_Kp&& __x) {730 auto [__first, __last] = equal_range(__x);731 auto __res = __last - __first;732 erase(__first, __last);733 return __res;734 }735 736 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator erase(const_iterator __first, const_iterator __last) {737 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });738 auto __key_it = __containers_.keys.erase(__first.__key_iter_, __last.__key_iter_);739 auto __mapped_it = __containers_.values.erase(__first.__mapped_iter_, __last.__mapped_iter_);740 __on_failure.__complete();741 return iterator(std::move(__key_it), std::move(__mapped_it));742 }743 744 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void swap(flat_map& __y) noexcept {745 // warning: The spec has unconditional noexcept, which means that746 // if any of the following functions throw an exception,747 // std::terminate will be called.748 // This is discussed in P2767, which hasn't been voted on yet.749 ranges::swap(__compare_, __y.__compare_);750 ranges::swap(__containers_.keys, __y.__containers_.keys);751 ranges::swap(__containers_.values, __y.__containers_.values);752 }753 754 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void clear() noexcept {755 __containers_.keys.clear();756 __containers_.values.clear();757 }758 759 // observers760 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 key_compare key_comp() const { return __compare_; }761 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 value_compare value_comp() const {762 return value_compare(__compare_);763 }764 765 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const key_container_type& keys() const noexcept {766 return __containers_.keys;767 }768 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const mapped_container_type&769 values() const noexcept {770 return __containers_.values;771 }772 773 // map operations774 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator find(const key_type& __x) {775 return __find_impl(*this, __x);776 }777 778 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator find(const key_type& __x) const {779 return __find_impl(*this, __x);780 }781 782 template <class _Kp>783 requires __is_compare_transparent784 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator find(const _Kp& __x) {785 return __find_impl(*this, __x);786 }787 788 template <class _Kp>789 requires __is_compare_transparent790 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator find(const _Kp& __x) const {791 return __find_impl(*this, __x);792 }793 794 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type count(const key_type& __x) const {795 return contains(__x) ? 1 : 0;796 }797 798 template <class _Kp>799 requires __is_compare_transparent800 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type count(const _Kp& __x) const {801 return contains(__x) ? 1 : 0;802 }803 804 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool contains(const key_type& __x) const {805 return find(__x) != end();806 }807 808 template <class _Kp>809 requires __is_compare_transparent810 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool contains(const _Kp& __x) const {811 return find(__x) != end();812 }813 814 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator lower_bound(const key_type& __x) {815 return __lower_bound<iterator>(*this, __x);816 }817 818 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator819 lower_bound(const key_type& __x) const {820 return __lower_bound<const_iterator>(*this, __x);821 }822 823 template <class _Kp>824 requires __is_compare_transparent825 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator lower_bound(const _Kp& __x) {826 return __lower_bound<iterator>(*this, __x);827 }828 829 template <class _Kp>830 requires __is_compare_transparent831 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator lower_bound(const _Kp& __x) const {832 return __lower_bound<const_iterator>(*this, __x);833 }834 835 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator upper_bound(const key_type& __x) {836 return __upper_bound<iterator>(*this, __x);837 }838 839 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator840 upper_bound(const key_type& __x) const {841 return __upper_bound<const_iterator>(*this, __x);842 }843 844 template <class _Kp>845 requires __is_compare_transparent846 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator upper_bound(const _Kp& __x) {847 return __upper_bound<iterator>(*this, __x);848 }849 850 template <class _Kp>851 requires __is_compare_transparent852 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator upper_bound(const _Kp& __x) const {853 return __upper_bound<const_iterator>(*this, __x);854 }855 856 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, iterator>857 equal_range(const key_type& __x) {858 return __equal_range_impl(*this, __x);859 }860 861 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<const_iterator, const_iterator>862 equal_range(const key_type& __x) const {863 return __equal_range_impl(*this, __x);864 }865 866 template <class _Kp>867 requires __is_compare_transparent868 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, iterator>869 equal_range(const _Kp& __x) {870 return __equal_range_impl(*this, __x);871 }872 template <class _Kp>873 requires __is_compare_transparent874 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<const_iterator, const_iterator>875 equal_range(const _Kp& __x) const {876 return __equal_range_impl(*this, __x);877 }878 879 friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool operator==(const flat_map& __x, const flat_map& __y) {880 return ranges::equal(__x, __y);881 }882 883 friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 auto884 operator<=>(const flat_map& __x, const flat_map& __y) {885 return std::lexicographical_compare_three_way(886 __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);887 }888 889 friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void swap(flat_map& __x, flat_map& __y) noexcept {890 __x.swap(__y);891 }892 893private:894 struct __ctor_uses_allocator_tag {895 explicit _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __ctor_uses_allocator_tag() = default;896 };897 struct __ctor_uses_allocator_empty_tag {898 explicit _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __ctor_uses_allocator_empty_tag() = default;899 };900 901 template <class _Allocator, class _KeyCont, class _MappedCont, class... _CompArg>902 requires __allocator_ctor_constraint<_Allocator>903 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_map(904 __ctor_uses_allocator_tag,905 const _Allocator& __alloc,906 _KeyCont&& __key_cont,907 _MappedCont&& __mapped_cont,908 _CompArg&&... __comp)909 : __containers_{.keys = std::make_obj_using_allocator<key_container_type>(910 __alloc, std::forward<_KeyCont>(__key_cont)),911 .values = std::make_obj_using_allocator<mapped_container_type>(912 __alloc, std::forward<_MappedCont>(__mapped_cont))},913 __compare_(std::forward<_CompArg>(__comp)...) {}914 915 template <class _Allocator, class... _CompArg>916 requires __allocator_ctor_constraint<_Allocator>917 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26918 flat_map(__ctor_uses_allocator_empty_tag, const _Allocator& __alloc, _CompArg&&... __comp)919 : __containers_{.keys = std::make_obj_using_allocator<key_container_type>(__alloc),920 .values = std::make_obj_using_allocator<mapped_container_type>(__alloc)},921 __compare_(std::forward<_CompArg>(__comp)...) {}922 923 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool __is_sorted_and_unique(auto&& __key_container) const {924 auto __greater_or_equal_to = [this](const auto& __x, const auto& __y) { return !__compare_(__x, __y); };925 return ranges::adjacent_find(__key_container, __greater_or_equal_to) == ranges::end(__key_container);926 }927 928 // This function is only used in constructors. So there is not exception handling in this function.929 // If the function exits via an exception, there will be no flat_map object constructed, thus, there930 // is no invariant state to preserve931 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __sort_and_unique() {932 auto __zv = ranges::views::zip(__containers_.keys, __containers_.values);933 ranges::sort(__zv, __compare_, [](const auto& __p) -> decltype(auto) { return std::get<0>(__p); });934 auto __dup_start = ranges::unique(__zv, __key_equiv(__compare_)).begin();935 auto __dist = ranges::distance(__zv.begin(), __dup_start);936 __containers_.keys.erase(__containers_.keys.begin() + __dist, __containers_.keys.end());937 __containers_.values.erase(__containers_.values.begin() + __dist, __containers_.values.end());938 }939 940 template <class _Self, class _KeyIter>941 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto942 __corresponding_mapped_it(_Self&& __self, _KeyIter&& __key_iter) {943 return __self.__containers_.values.begin() +944 static_cast<ranges::range_difference_t<mapped_container_type>>(945 ranges::distance(__self.__containers_.keys.begin(), __key_iter));946 }947 948 template <bool _WasSorted, class _InputIterator, class _Sentinel>949 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void950 __append_sort_merge_unique(_InputIterator __first, _Sentinel __last) {951 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });952 size_t __num_of_appended = __flat_map_utils::__append(*this, std::move(__first), std::move(__last));953 if (__num_of_appended != 0) {954 auto __zv = ranges::views::zip(__containers_.keys, __containers_.values);955 auto __append_start_offset = __containers_.keys.size() - __num_of_appended;956 auto __end = __zv.end();957 auto __compare_key = [this](const auto& __p1, const auto& __p2) {958 return __compare_(std::get<0>(__p1), std::get<0>(__p2));959 };960 if constexpr (!_WasSorted) {961 ranges::sort(__zv.begin() + __append_start_offset, __end, __compare_key);962 } else {963 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(964 __is_sorted_and_unique(__containers_.keys | ranges::views::drop(__append_start_offset)),965 "Either the key container is not sorted or it contains duplicates");966 }967 ranges::inplace_merge(__zv.begin(), __zv.begin() + __append_start_offset, __end, __compare_key);968 969 auto __dup_start = ranges::unique(__zv, __key_equiv(__compare_)).begin();970 auto __dist = ranges::distance(__zv.begin(), __dup_start);971 __containers_.keys.erase(__containers_.keys.begin() + __dist, __containers_.keys.end());972 __containers_.values.erase(__containers_.values.begin() + __dist, __containers_.values.end());973 }974 __on_failure.__complete();975 }976 977 template <class _Self, class _Kp>978 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto __find_impl(_Self&& __self, const _Kp& __key) {979 auto __it = __self.lower_bound(__key);980 auto __last = __self.end();981 if (__it == __last || __self.__compare_(__key, __it->first)) {982 return __last;983 }984 return __it;985 }986 987 template <class _Self, class _Kp>988 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto __key_equal_range(_Self&& __self, const _Kp& __key) {989 auto __it =990 std::lower_bound(__self.__containers_.keys.begin(), __self.__containers_.keys.end(), __key, __self.__compare_);991 auto __last = __self.__containers_.keys.end();992 if (__it == __last || __self.__compare_(__key, *__it)) {993 return std::make_pair(__it, __it);994 }995 return std::make_pair(__it, std::next(__it));996 }997 998 template <class _Self, class _Kp>999 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto __equal_range_impl(_Self&& __self, const _Kp& __key) {1000 auto [__key_first, __key_last] = __key_equal_range(__self, __key);1001 using __iterator_type = ranges::iterator_t<decltype(__self)>;1002 return std::make_pair(__iterator_type(__key_first, __corresponding_mapped_it(__self, __key_first)),1003 __iterator_type(__key_last, __corresponding_mapped_it(__self, __key_last)));1004 }1005 1006 template <class _Res, class _Self, class _Kp>1007 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static _Res __lower_bound(_Self&& __self, _Kp& __x) {1008 auto __key_iter =1009 std::lower_bound(__self.__containers_.keys.begin(), __self.__containers_.keys.end(), __x, __self.__compare_);1010 auto __mapped_iter = __corresponding_mapped_it(__self, __key_iter);1011 return _Res(std::move(__key_iter), std::move(__mapped_iter));1012 }1013 1014 template <class _Res, class _Self, class _Kp>1015 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static _Res __upper_bound(_Self&& __self, _Kp& __x) {1016 auto __key_iter =1017 std::upper_bound(__self.__containers_.keys.begin(), __self.__containers_.keys.end(), __x, __self.__compare_);1018 auto __mapped_iter = __corresponding_mapped_it(__self, __key_iter);1019 return _Res(std::move(__key_iter), std::move(__mapped_iter));1020 }1021 1022 template <class _KeyArg, class... _MArgs>1023 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool>1024 __try_emplace(_KeyArg&& __key, _MArgs&&... __mapped_args) {1025 auto __key_it = std::lower_bound(__containers_.keys.begin(), __containers_.keys.end(), __key, __compare_);1026 auto __mapped_it = __containers_.values.begin() + ranges::distance(__containers_.keys.begin(), __key_it);1027 1028 if (__key_it == __containers_.keys.end() || __compare_(__key, *__key_it)) {1029 return pair<iterator, bool>(1030 __flat_map_utils::__emplace_exact_pos(1031 *this,1032 std::move(__key_it),1033 std::move(__mapped_it),1034 std::forward<_KeyArg>(__key),1035 std::forward<_MArgs>(__mapped_args)...),1036 true);1037 } else {1038 return pair<iterator, bool>(iterator(std::move(__key_it), std::move(__mapped_it)), false);1039 }1040 }1041 1042 template <class _Kp>1043 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool __is_hint_correct(const_iterator __hint, _Kp&& __key) {1044 if (__hint != cbegin() && !__compare_((__hint - 1)->first, __key)) {1045 return false;1046 }1047 if (__hint != cend() && __compare_(__hint->first, __key)) {1048 return false;1049 }1050 return true;1051 }1052 1053 template <class _Kp, class... _Args>1054 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool>1055 __try_emplace_hint(const_iterator __hint, _Kp&& __key, _Args&&... __args) {1056 if (__is_hint_correct(__hint, __key)) {1057 if (__hint == cend() || __compare_(__key, __hint->first)) {1058 return {__flat_map_utils::__emplace_exact_pos(1059 *this,1060 __hint.__key_iter_,1061 __hint.__mapped_iter_,1062 std::forward<_Kp>(__key),1063 std::forward<_Args>(__args)...),1064 true};1065 } else {1066 // key equals1067 auto __dist = __hint - cbegin();1068 return {iterator(__containers_.keys.begin() + __dist, __containers_.values.begin() + __dist), false};1069 }1070 } else {1071 return __try_emplace(std::forward<_Kp>(__key), std::forward<_Args>(__args)...);1072 }1073 }1074 1075 template <class _Kp, class _Mapped>1076 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool>1077 __insert_or_assign(_Kp&& __key, _Mapped&& __mapped) {1078 auto __r = try_emplace(std::forward<_Kp>(__key), std::forward<_Mapped>(__mapped));1079 if (!__r.second) {1080 __r.first->second = std::forward<_Mapped>(__mapped);1081 }1082 return __r;1083 }1084 1085 template <class _Kp, class _Mapped>1086 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator1087 __insert_or_assign(const_iterator __hint, _Kp&& __key, _Mapped&& __mapped) {1088 auto __r = __try_emplace_hint(__hint, std::forward<_Kp>(__key), std::forward<_Mapped>(__mapped));1089 if (!__r.second) {1090 __r.first->second = std::forward<_Mapped>(__mapped);1091 }1092 return __r.first;1093 }1094 1095 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __reserve(size_t __size) {1096 if constexpr (__container_traits<_KeyContainer>::__reservable) {1097 __containers_.keys.reserve(__size);1098 }1099 1100 if constexpr (__container_traits<_MappedContainer>::__reservable) {1101 __containers_.values.reserve(__size);1102 }1103 }1104 1105 template <class _KIter, class _MIter>1106 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator1107 __erase(_KIter __key_iter_to_remove, _MIter __mapped_iter_to_remove) {1108 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });1109 auto __key_iter = __containers_.keys.erase(__key_iter_to_remove);1110 auto __mapped_iter = __containers_.values.erase(__mapped_iter_to_remove);1111 __on_failure.__complete();1112 return iterator(std::move(__key_iter), std::move(__mapped_iter));1113 }1114 1115 template <class _Key2, class _Tp2, class _Compare2, class _KeyContainer2, class _MappedContainer2, class _Predicate>1116 friend typename flat_map<_Key2, _Tp2, _Compare2, _KeyContainer2, _MappedContainer2>::size_type1117 _LIBCPP_CONSTEXPR_SINCE_CXX261118 erase_if(flat_map<_Key2, _Tp2, _Compare2, _KeyContainer2, _MappedContainer2>&, _Predicate);1119 1120 friend __flat_map_utils;1121 1122 containers __containers_;1123 _LIBCPP_NO_UNIQUE_ADDRESS key_compare __compare_;1124 1125 struct __key_equiv {1126 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_equiv(key_compare __c) : __comp_(__c) {}1127 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool1128 operator()(const_reference __x, const_reference __y) const {1129 return !__comp_(std::get<0>(__x), std::get<0>(__y)) && !__comp_(std::get<0>(__y), std::get<0>(__x));1130 }1131 key_compare __comp_;1132 };1133};1134 1135template <class _KeyContainer, class _MappedContainer, class _Compare = less<typename _KeyContainer::value_type>>1136 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> && !__is_allocator_v<_MappedContainer> &&1137 is_invocable_v<const _Compare&,1138 const typename _KeyContainer::value_type&,1139 const typename _KeyContainer::value_type&>)1140flat_map(_KeyContainer, _MappedContainer, _Compare = _Compare())1141 -> flat_map<typename _KeyContainer::value_type,1142 typename _MappedContainer::value_type,1143 _Compare,1144 _KeyContainer,1145 _MappedContainer>;1146 1147template <class _KeyContainer, class _MappedContainer, class _Allocator>1148 requires(uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator> &&1149 !__is_allocator_v<_KeyContainer> && !__is_allocator_v<_MappedContainer>)1150flat_map(_KeyContainer, _MappedContainer, _Allocator)1151 -> flat_map<typename _KeyContainer::value_type,1152 typename _MappedContainer::value_type,1153 less<typename _KeyContainer::value_type>,1154 _KeyContainer,1155 _MappedContainer>;1156 1157template <class _KeyContainer, class _MappedContainer, class _Compare, class _Allocator>1158 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> && !__is_allocator_v<_MappedContainer> &&1159 uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator> &&1160 is_invocable_v<const _Compare&,1161 const typename _KeyContainer::value_type&,1162 const typename _KeyContainer::value_type&>)1163flat_map(_KeyContainer, _MappedContainer, _Compare, _Allocator)1164 -> flat_map<typename _KeyContainer::value_type,1165 typename _MappedContainer::value_type,1166 _Compare,1167 _KeyContainer,1168 _MappedContainer>;1169 1170template <class _KeyContainer, class _MappedContainer, class _Compare = less<typename _KeyContainer::value_type>>1171 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> && !__is_allocator_v<_MappedContainer> &&1172 is_invocable_v<const _Compare&,1173 const typename _KeyContainer::value_type&,1174 const typename _KeyContainer::value_type&>)1175flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Compare = _Compare())1176 -> flat_map<typename _KeyContainer::value_type,1177 typename _MappedContainer::value_type,1178 _Compare,1179 _KeyContainer,1180 _MappedContainer>;1181 1182template <class _KeyContainer, class _MappedContainer, class _Allocator>1183 requires(uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator> &&1184 !__is_allocator_v<_KeyContainer> && !__is_allocator_v<_MappedContainer>)1185flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Allocator)1186 -> flat_map<typename _KeyContainer::value_type,1187 typename _MappedContainer::value_type,1188 less<typename _KeyContainer::value_type>,1189 _KeyContainer,1190 _MappedContainer>;1191 1192template <class _KeyContainer, class _MappedContainer, class _Compare, class _Allocator>1193 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> && !__is_allocator_v<_MappedContainer> &&1194 uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator> &&1195 is_invocable_v<const _Compare&,1196 const typename _KeyContainer::value_type&,1197 const typename _KeyContainer::value_type&>)1198flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Compare, _Allocator)1199 -> flat_map<typename _KeyContainer::value_type,1200 typename _MappedContainer::value_type,1201 _Compare,1202 _KeyContainer,1203 _MappedContainer>;1204 1205template <class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>>1206 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator_v<_Compare>)1207flat_map(_InputIterator, _InputIterator, _Compare = _Compare())1208 -> flat_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare>;1209 1210template <class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>>1211 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator_v<_Compare>)1212flat_map(sorted_unique_t, _InputIterator, _InputIterator, _Compare = _Compare())1213 -> flat_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare>;1214 1215template <ranges::input_range _Range,1216 class _Compare = less<__range_key_type<_Range>>,1217 class _Allocator = allocator<byte>,1218 class = __enable_if_t<!__is_allocator_v<_Compare> && __is_allocator_v<_Allocator>>>1219flat_map(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator()) -> flat_map<1220 __range_key_type<_Range>,1221 __range_mapped_type<_Range>,1222 _Compare,1223 vector<__range_key_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_key_type<_Range>>>,1224 vector<__range_mapped_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_mapped_type<_Range>>>>;1225 1226template <ranges::input_range _Range, class _Allocator, class = __enable_if_t<__is_allocator_v<_Allocator>>>1227flat_map(from_range_t, _Range&&, _Allocator) -> flat_map<1228 __range_key_type<_Range>,1229 __range_mapped_type<_Range>,1230 less<__range_key_type<_Range>>,1231 vector<__range_key_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_key_type<_Range>>>,1232 vector<__range_mapped_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_mapped_type<_Range>>>>;1233 1234template <class _Key, class _Tp, class _Compare = less<_Key>>1235 requires(!__is_allocator_v<_Compare>)1236flat_map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare()) -> flat_map<_Key, _Tp, _Compare>;1237 1238template <class _Key, class _Tp, class _Compare = less<_Key>>1239 requires(!__is_allocator_v<_Compare>)1240flat_map(sorted_unique_t, initializer_list<pair<_Key, _Tp>>, _Compare = _Compare()) -> flat_map<_Key, _Tp, _Compare>;1241 1242template <class _Key, class _Tp, class _Compare, class _KeyContainer, class _MappedContainer, class _Allocator>1243struct uses_allocator<flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>, _Allocator>1244 : bool_constant<uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator>> {};1245 1246template <class _Key, class _Tp, class _Compare, class _KeyContainer, class _MappedContainer, class _Predicate>1247_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX261248 typename flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>::size_type1249 erase_if(flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>& __flat_map, _Predicate __pred) {1250 auto __zv = ranges::views::zip(__flat_map.__containers_.keys, __flat_map.__containers_.values);1251 auto __first = __zv.begin();1252 auto __last = __zv.end();1253 auto __guard = std::__make_exception_guard([&] { __flat_map.clear(); });1254 auto __it = std::remove_if(__first, __last, [&](auto&& __zipped) -> bool {1255 using _Ref = typename flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>::const_reference;1256 return __pred(_Ref(std::get<0>(__zipped), std::get<1>(__zipped)));1257 });1258 auto __res = __last - __it;1259 auto __offset = __it - __first;1260 1261 const auto __erase_container = [&](auto& __cont) { __cont.erase(__cont.begin() + __offset, __cont.end()); };1262 1263 __erase_container(__flat_map.__containers_.keys);1264 __erase_container(__flat_map.__containers_.values);1265 1266 __guard.__complete();1267 return __res;1268}1269 1270_LIBCPP_END_NAMESPACE_STD1271 1272#endif // _LIBCPP_STD_VER >= 231273 1274_LIBCPP_POP_MACROS1275 1276#endif // _LIBCPP___FLAT_MAP_FLAT_MAP_H1277