File indexing completed on 2026-05-03 08:13:48
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010 #ifndef _LIBCPP___FLAT_MAP_FLAT_MAP_H
0011 #define _LIBCPP___FLAT_MAP_FLAT_MAP_H
0012
0013 #include <__algorithm/lexicographical_compare_three_way.h>
0014 #include <__algorithm/min.h>
0015 #include <__algorithm/ranges_adjacent_find.h>
0016 #include <__algorithm/ranges_equal.h>
0017 #include <__algorithm/ranges_inplace_merge.h>
0018 #include <__algorithm/ranges_lower_bound.h>
0019 #include <__algorithm/ranges_partition_point.h>
0020 #include <__algorithm/ranges_sort.h>
0021 #include <__algorithm/ranges_unique.h>
0022 #include <__algorithm/ranges_upper_bound.h>
0023 #include <__algorithm/remove_if.h>
0024 #include <__assert>
0025 #include <__compare/synth_three_way.h>
0026 #include <__concepts/swappable.h>
0027 #include <__config>
0028 #include <__cstddef/byte.h>
0029 #include <__cstddef/ptrdiff_t.h>
0030 #include <__flat_map/key_value_iterator.h>
0031 #include <__flat_map/sorted_unique.h>
0032 #include <__flat_map/utils.h>
0033 #include <__functional/invoke.h>
0034 #include <__functional/is_transparent.h>
0035 #include <__functional/operations.h>
0036 #include <__fwd/vector.h>
0037 #include <__iterator/concepts.h>
0038 #include <__iterator/distance.h>
0039 #include <__iterator/iterator_traits.h>
0040 #include <__iterator/next.h>
0041 #include <__iterator/ranges_iterator_traits.h>
0042 #include <__iterator/reverse_iterator.h>
0043 #include <__memory/allocator_traits.h>
0044 #include <__memory/uses_allocator.h>
0045 #include <__memory/uses_allocator_construction.h>
0046 #include <__ranges/access.h>
0047 #include <__ranges/concepts.h>
0048 #include <__ranges/container_compatible_range.h>
0049 #include <__ranges/drop_view.h>
0050 #include <__ranges/from_range.h>
0051 #include <__ranges/ref_view.h>
0052 #include <__ranges/size.h>
0053 #include <__ranges/subrange.h>
0054 #include <__ranges/zip_view.h>
0055 #include <__type_traits/conjunction.h>
0056 #include <__type_traits/container_traits.h>
0057 #include <__type_traits/invoke.h>
0058 #include <__type_traits/is_allocator.h>
0059 #include <__type_traits/is_nothrow_constructible.h>
0060 #include <__type_traits/is_same.h>
0061 #include <__utility/exception_guard.h>
0062 #include <__utility/move.h>
0063 #include <__utility/pair.h>
0064 #include <__utility/scope_guard.h>
0065 #include <__vector/vector.h>
0066 #include <initializer_list>
0067 #include <stdexcept>
0068
0069 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0070 # pragma GCC system_header
0071 #endif
0072
0073 _LIBCPP_PUSH_MACROS
0074 #include <__undef_macros>
0075
0076 #if _LIBCPP_STD_VER >= 23
0077
0078 _LIBCPP_BEGIN_NAMESPACE_STD
0079
0080 template <class _Key,
0081 class _Tp,
0082 class _Compare = less<_Key>,
0083 class _KeyContainer = vector<_Key>,
0084 class _MappedContainer = vector<_Tp>>
0085 class flat_map {
0086 template <class, class, class, class, class>
0087 friend class flat_map;
0088
0089 static_assert(is_same_v<_Key, typename _KeyContainer::value_type>);
0090 static_assert(is_same_v<_Tp, typename _MappedContainer::value_type>);
0091 static_assert(!is_same_v<_KeyContainer, std::vector<bool>>, "vector<bool> is not a sequence container");
0092 static_assert(!is_same_v<_MappedContainer, std::vector<bool>>, "vector<bool> is not a sequence container");
0093
0094 template <bool _Const>
0095 using __iterator _LIBCPP_NODEBUG = __key_value_iterator<flat_map, _KeyContainer, _MappedContainer, _Const>;
0096
0097 public:
0098
0099 using key_type = _Key;
0100 using mapped_type = _Tp;
0101 using value_type = pair<key_type, mapped_type>;
0102 using key_compare = __type_identity_t<_Compare>;
0103 using reference = pair<const key_type&, mapped_type&>;
0104 using const_reference = pair<const key_type&, const mapped_type&>;
0105 using size_type = size_t;
0106 using difference_type = ptrdiff_t;
0107 using iterator = __iterator<false>;
0108 using const_iterator = __iterator<true>;
0109 using reverse_iterator = std::reverse_iterator<iterator>;
0110 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
0111 using key_container_type = _KeyContainer;
0112 using mapped_container_type = _MappedContainer;
0113
0114 class value_compare {
0115 private:
0116 _LIBCPP_NO_UNIQUE_ADDRESS key_compare __comp_;
0117 _LIBCPP_HIDE_FROM_ABI value_compare(key_compare __c) : __comp_(__c) {}
0118 friend flat_map;
0119
0120 public:
0121 _LIBCPP_HIDE_FROM_ABI bool operator()(const_reference __x, const_reference __y) const {
0122 return __comp_(__x.first, __y.first);
0123 }
0124 };
0125
0126 struct containers {
0127 key_container_type keys;
0128 mapped_container_type values;
0129 };
0130
0131 private:
0132 template <class _Allocator>
0133 _LIBCPP_HIDE_FROM_ABI static constexpr bool __allocator_ctor_constraint =
0134 _And<uses_allocator<key_container_type, _Allocator>, uses_allocator<mapped_container_type, _Allocator>>::value;
0135
0136 _LIBCPP_HIDE_FROM_ABI static constexpr bool __is_compare_transparent = __is_transparent_v<_Compare>;
0137
0138 public:
0139
0140 _LIBCPP_HIDE_FROM_ABI flat_map() noexcept(
0141 is_nothrow_default_constructible_v<_KeyContainer> && is_nothrow_default_constructible_v<_MappedContainer> &&
0142 is_nothrow_default_constructible_v<_Compare>)
0143 : __containers_(), __compare_() {}
0144
0145 _LIBCPP_HIDE_FROM_ABI flat_map(const flat_map&) = default;
0146
0147 _LIBCPP_HIDE_FROM_ABI flat_map(flat_map&& __other) noexcept(
0148 is_nothrow_move_constructible_v<_KeyContainer> && is_nothrow_move_constructible_v<_MappedContainer> &&
0149 is_nothrow_move_constructible_v<_Compare>)
0150 # if _LIBCPP_HAS_EXCEPTIONS
0151 try
0152 # endif
0153 : __containers_(std::move(__other.__containers_)), __compare_(std::move(__other.__compare_)) {
0154 __other.clear();
0155 # if _LIBCPP_HAS_EXCEPTIONS
0156 } catch (...) {
0157 __other.clear();
0158
0159 if constexpr (!(is_nothrow_move_constructible_v<_KeyContainer> &&
0160 is_nothrow_move_constructible_v<_MappedContainer> && is_nothrow_move_constructible_v<_Compare>)) {
0161 throw;
0162 }
0163 # endif
0164 }
0165
0166 template <class _Allocator>
0167 requires __allocator_ctor_constraint<_Allocator>
0168 _LIBCPP_HIDE_FROM_ABI flat_map(const flat_map& __other, const _Allocator& __alloc)
0169 : flat_map(__ctor_uses_allocator_tag{},
0170 __alloc,
0171 __other.__containers_.keys,
0172 __other.__containers_.values,
0173 __other.__compare_) {}
0174
0175 template <class _Allocator>
0176 requires __allocator_ctor_constraint<_Allocator>
0177 _LIBCPP_HIDE_FROM_ABI flat_map(flat_map&& __other, const _Allocator& __alloc)
0178 # if _LIBCPP_HAS_EXCEPTIONS
0179 try
0180 # endif
0181 : flat_map(__ctor_uses_allocator_tag{},
0182 __alloc,
0183 std::move(__other.__containers_.keys),
0184 std::move(__other.__containers_.values),
0185 std::move(__other.__compare_)) {
0186 __other.clear();
0187 # if _LIBCPP_HAS_EXCEPTIONS
0188 } catch (...) {
0189 __other.clear();
0190 throw;
0191 # endif
0192 }
0193
0194 _LIBCPP_HIDE_FROM_ABI flat_map(
0195 key_container_type __key_cont, mapped_container_type __mapped_cont, const key_compare& __comp = key_compare())
0196 : __containers_{.keys = std::move(__key_cont), .values = std::move(__mapped_cont)}, __compare_(__comp) {
0197 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
0198 "flat_map keys and mapped containers have different size");
0199 __sort_and_unique();
0200 }
0201
0202 template <class _Allocator>
0203 requires __allocator_ctor_constraint<_Allocator>
0204 _LIBCPP_HIDE_FROM_ABI
0205 flat_map(const key_container_type& __key_cont, const mapped_container_type& __mapped_cont, const _Allocator& __alloc)
0206 : flat_map(__ctor_uses_allocator_tag{}, __alloc, __key_cont, __mapped_cont) {
0207 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
0208 "flat_map keys and mapped containers have different size");
0209 __sort_and_unique();
0210 }
0211
0212 template <class _Allocator>
0213 requires __allocator_ctor_constraint<_Allocator>
0214 _LIBCPP_HIDE_FROM_ABI
0215 flat_map(const key_container_type& __key_cont,
0216 const mapped_container_type& __mapped_cont,
0217 const key_compare& __comp,
0218 const _Allocator& __alloc)
0219 : flat_map(__ctor_uses_allocator_tag{}, __alloc, __key_cont, __mapped_cont, __comp) {
0220 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
0221 "flat_map keys and mapped containers have different size");
0222 __sort_and_unique();
0223 }
0224
0225 _LIBCPP_HIDE_FROM_ABI
0226 flat_map(sorted_unique_t,
0227 key_container_type __key_cont,
0228 mapped_container_type __mapped_cont,
0229 const key_compare& __comp = key_compare())
0230 : __containers_{.keys = std::move(__key_cont), .values = std::move(__mapped_cont)}, __compare_(__comp) {
0231 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
0232 "flat_map keys and mapped containers have different size");
0233 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
0234 __is_sorted_and_unique(__containers_.keys), "Either the key container is not sorted or it contains duplicates");
0235 }
0236
0237 template <class _Allocator>
0238 requires __allocator_ctor_constraint<_Allocator>
0239 _LIBCPP_HIDE_FROM_ABI
0240 flat_map(sorted_unique_t,
0241 const key_container_type& __key_cont,
0242 const mapped_container_type& __mapped_cont,
0243 const _Allocator& __alloc)
0244 : flat_map(__ctor_uses_allocator_tag{}, __alloc, __key_cont, __mapped_cont) {
0245 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
0246 "flat_map keys and mapped containers have different size");
0247 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
0248 __is_sorted_and_unique(__containers_.keys), "Either the key container is not sorted or it contains duplicates");
0249 }
0250
0251 template <class _Allocator>
0252 requires __allocator_ctor_constraint<_Allocator>
0253 _LIBCPP_HIDE_FROM_ABI
0254 flat_map(sorted_unique_t,
0255 const key_container_type& __key_cont,
0256 const mapped_container_type& __mapped_cont,
0257 const key_compare& __comp,
0258 const _Allocator& __alloc)
0259 : flat_map(__ctor_uses_allocator_tag{}, __alloc, __key_cont, __mapped_cont, __comp) {
0260 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__containers_.keys.size() == __containers_.values.size(),
0261 "flat_map keys and mapped containers have different size");
0262 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
0263 __is_sorted_and_unique(__containers_.keys), "Either the key container is not sorted or it contains duplicates");
0264 }
0265
0266 _LIBCPP_HIDE_FROM_ABI explicit flat_map(const key_compare& __comp) : __containers_(), __compare_(__comp) {}
0267
0268 template <class _Allocator>
0269 requires __allocator_ctor_constraint<_Allocator>
0270 _LIBCPP_HIDE_FROM_ABI flat_map(const key_compare& __comp, const _Allocator& __alloc)
0271 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) {}
0272
0273 template <class _Allocator>
0274 requires __allocator_ctor_constraint<_Allocator>
0275 _LIBCPP_HIDE_FROM_ABI explicit flat_map(const _Allocator& __alloc)
0276 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc) {}
0277
0278 template <class _InputIterator>
0279 requires __has_input_iterator_category<_InputIterator>::value
0280 _LIBCPP_HIDE_FROM_ABI
0281 flat_map(_InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare())
0282 : __containers_(), __compare_(__comp) {
0283 insert(__first, __last);
0284 }
0285
0286 template <class _InputIterator, class _Allocator>
0287 requires(__has_input_iterator_category<_InputIterator>::value && __allocator_ctor_constraint<_Allocator>)
0288 _LIBCPP_HIDE_FROM_ABI
0289 flat_map(_InputIterator __first, _InputIterator __last, const key_compare& __comp, const _Allocator& __alloc)
0290 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) {
0291 insert(__first, __last);
0292 }
0293
0294 template <class _InputIterator, class _Allocator>
0295 requires(__has_input_iterator_category<_InputIterator>::value && __allocator_ctor_constraint<_Allocator>)
0296 _LIBCPP_HIDE_FROM_ABI flat_map(_InputIterator __first, _InputIterator __last, const _Allocator& __alloc)
0297 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc) {
0298 insert(__first, __last);
0299 }
0300
0301 template <_ContainerCompatibleRange<value_type> _Range>
0302 _LIBCPP_HIDE_FROM_ABI flat_map(from_range_t __fr, _Range&& __rg)
0303 : flat_map(__fr, std::forward<_Range>(__rg), key_compare()) {}
0304
0305 template <_ContainerCompatibleRange<value_type> _Range, class _Allocator>
0306 requires __allocator_ctor_constraint<_Allocator>
0307 _LIBCPP_HIDE_FROM_ABI flat_map(from_range_t, _Range&& __rg, const _Allocator& __alloc)
0308 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc) {
0309 insert_range(std::forward<_Range>(__rg));
0310 }
0311
0312 template <_ContainerCompatibleRange<value_type> _Range>
0313 _LIBCPP_HIDE_FROM_ABI flat_map(from_range_t, _Range&& __rg, const key_compare& __comp) : flat_map(__comp) {
0314 insert_range(std::forward<_Range>(__rg));
0315 }
0316
0317 template <_ContainerCompatibleRange<value_type> _Range, class _Allocator>
0318 requires __allocator_ctor_constraint<_Allocator>
0319 _LIBCPP_HIDE_FROM_ABI flat_map(from_range_t, _Range&& __rg, const key_compare& __comp, const _Allocator& __alloc)
0320 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) {
0321 insert_range(std::forward<_Range>(__rg));
0322 }
0323
0324 template <class _InputIterator>
0325 requires __has_input_iterator_category<_InputIterator>::value
0326 _LIBCPP_HIDE_FROM_ABI
0327 flat_map(sorted_unique_t, _InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare())
0328 : __containers_(), __compare_(__comp) {
0329 insert(sorted_unique, __first, __last);
0330 }
0331 template <class _InputIterator, class _Allocator>
0332 requires(__has_input_iterator_category<_InputIterator>::value && __allocator_ctor_constraint<_Allocator>)
0333 _LIBCPP_HIDE_FROM_ABI
0334 flat_map(sorted_unique_t,
0335 _InputIterator __first,
0336 _InputIterator __last,
0337 const key_compare& __comp,
0338 const _Allocator& __alloc)
0339 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) {
0340 insert(sorted_unique, __first, __last);
0341 }
0342
0343 template <class _InputIterator, class _Allocator>
0344 requires(__has_input_iterator_category<_InputIterator>::value && __allocator_ctor_constraint<_Allocator>)
0345 _LIBCPP_HIDE_FROM_ABI
0346 flat_map(sorted_unique_t, _InputIterator __first, _InputIterator __last, const _Allocator& __alloc)
0347 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc) {
0348 insert(sorted_unique, __first, __last);
0349 }
0350
0351 _LIBCPP_HIDE_FROM_ABI flat_map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
0352 : flat_map(__il.begin(), __il.end(), __comp) {}
0353
0354 template <class _Allocator>
0355 requires __allocator_ctor_constraint<_Allocator>
0356 _LIBCPP_HIDE_FROM_ABI
0357 flat_map(initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc)
0358 : flat_map(__il.begin(), __il.end(), __comp, __alloc) {}
0359
0360 template <class _Allocator>
0361 requires __allocator_ctor_constraint<_Allocator>
0362 _LIBCPP_HIDE_FROM_ABI flat_map(initializer_list<value_type> __il, const _Allocator& __alloc)
0363 : flat_map(__il.begin(), __il.end(), __alloc) {}
0364
0365 _LIBCPP_HIDE_FROM_ABI
0366 flat_map(sorted_unique_t, initializer_list<value_type> __il, const key_compare& __comp = key_compare())
0367 : flat_map(sorted_unique, __il.begin(), __il.end(), __comp) {}
0368
0369 template <class _Allocator>
0370 requires __allocator_ctor_constraint<_Allocator>
0371 _LIBCPP_HIDE_FROM_ABI
0372 flat_map(sorted_unique_t, initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc)
0373 : flat_map(sorted_unique, __il.begin(), __il.end(), __comp, __alloc) {}
0374
0375 template <class _Allocator>
0376 requires __allocator_ctor_constraint<_Allocator>
0377 _LIBCPP_HIDE_FROM_ABI flat_map(sorted_unique_t, initializer_list<value_type> __il, const _Allocator& __alloc)
0378 : flat_map(sorted_unique, __il.begin(), __il.end(), __alloc) {}
0379
0380 _LIBCPP_HIDE_FROM_ABI flat_map& operator=(initializer_list<value_type> __il) {
0381 clear();
0382 insert(__il);
0383 return *this;
0384 }
0385
0386 _LIBCPP_HIDE_FROM_ABI flat_map& operator=(const flat_map&) = default;
0387
0388 _LIBCPP_HIDE_FROM_ABI flat_map& operator=(flat_map&& __other) noexcept(
0389 is_nothrow_move_assignable_v<_KeyContainer> && is_nothrow_move_assignable_v<_MappedContainer> &&
0390 is_nothrow_move_assignable_v<_Compare>) {
0391
0392
0393 auto __clear_other_guard = std::__make_scope_guard([&]() noexcept { __other.clear() ; });
0394 {
0395
0396 auto __on_exception = std::__make_exception_guard([&]() noexcept { clear() ; });
0397 __containers_ = std::move(__other.__containers_);
0398 __compare_ = std::move(__other.__compare_);
0399 __on_exception.__complete();
0400 }
0401 return *this;
0402 }
0403
0404
0405 _LIBCPP_HIDE_FROM_ABI iterator begin() noexcept {
0406 return iterator(__containers_.keys.begin(), __containers_.values.begin());
0407 }
0408
0409 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const noexcept {
0410 return const_iterator(__containers_.keys.begin(), __containers_.values.begin());
0411 }
0412
0413 _LIBCPP_HIDE_FROM_ABI iterator end() noexcept {
0414 return iterator(__containers_.keys.end(), __containers_.values.end());
0415 }
0416
0417 _LIBCPP_HIDE_FROM_ABI const_iterator end() const noexcept {
0418 return const_iterator(__containers_.keys.end(), __containers_.values.end());
0419 }
0420
0421 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
0422 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }
0423 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
0424 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }
0425
0426 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const noexcept { return begin(); }
0427 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const noexcept { return end(); }
0428 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(end()); }
0429 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const noexcept { return const_reverse_iterator(begin()); }
0430
0431
0432 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI bool empty() const noexcept { return __containers_.keys.empty(); }
0433
0434 _LIBCPP_HIDE_FROM_ABI size_type size() const noexcept { return __containers_.keys.size(); }
0435
0436 _LIBCPP_HIDE_FROM_ABI size_type max_size() const noexcept {
0437 return std::min<size_type>(__containers_.keys.max_size(), __containers_.values.max_size());
0438 }
0439
0440
0441 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __x)
0442 requires is_constructible_v<mapped_type>
0443 {
0444 return try_emplace(__x).first->second;
0445 }
0446
0447 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](key_type&& __x)
0448 requires is_constructible_v<mapped_type>
0449 {
0450 return try_emplace(std::move(__x)).first->second;
0451 }
0452
0453 template <class _Kp>
0454 requires(__is_compare_transparent && is_constructible_v<key_type, _Kp> && is_constructible_v<mapped_type> &&
0455 !is_convertible_v<_Kp &&, const_iterator> && !is_convertible_v<_Kp &&, iterator>)
0456 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](_Kp&& __x) {
0457 return try_emplace(std::forward<_Kp>(__x)).first->second;
0458 }
0459
0460 _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __x) {
0461 auto __it = find(__x);
0462 if (__it == end()) {
0463 std::__throw_out_of_range("flat_map::at(const key_type&): Key does not exist");
0464 }
0465 return __it->second;
0466 }
0467
0468 _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __x) const {
0469 auto __it = find(__x);
0470 if (__it == end()) {
0471 std::__throw_out_of_range("flat_map::at(const key_type&) const: Key does not exist");
0472 }
0473 return __it->second;
0474 }
0475
0476 template <class _Kp>
0477 requires __is_compare_transparent
0478 _LIBCPP_HIDE_FROM_ABI mapped_type& at(const _Kp& __x) {
0479 auto __it = find(__x);
0480 if (__it == end()) {
0481 std::__throw_out_of_range("flat_map::at(const K&): Key does not exist");
0482 }
0483 return __it->second;
0484 }
0485
0486 template <class _Kp>
0487 requires __is_compare_transparent
0488 _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const _Kp& __x) const {
0489 auto __it = find(__x);
0490 if (__it == end()) {
0491 std::__throw_out_of_range("flat_map::at(const K&) const: Key does not exist");
0492 }
0493 return __it->second;
0494 }
0495
0496
0497 template <class... _Args>
0498 requires is_constructible_v<pair<key_type, mapped_type>, _Args...>
0499 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {
0500 std::pair<key_type, mapped_type> __pair(std::forward<_Args>(__args)...);
0501 return __try_emplace(std::move(__pair.first), std::move(__pair.second));
0502 }
0503
0504 template <class... _Args>
0505 requires is_constructible_v<pair<key_type, mapped_type>, _Args...>
0506 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __hint, _Args&&... __args) {
0507 std::pair<key_type, mapped_type> __pair(std::forward<_Args>(__args)...);
0508 return __try_emplace_hint(__hint, std::move(__pair.first), std::move(__pair.second)).first;
0509 }
0510
0511 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return emplace(__x); }
0512
0513 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __x) { return emplace(std::move(__x)); }
0514
0515 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, const value_type& __x) {
0516 return emplace_hint(__hint, __x);
0517 }
0518
0519 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, value_type&& __x) {
0520 return emplace_hint(__hint, std::move(__x));
0521 }
0522
0523 template <class _PairLike>
0524 requires is_constructible_v<pair<key_type, mapped_type>, _PairLike>
0525 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(_PairLike&& __x) {
0526 return emplace(std::forward<_PairLike>(__x));
0527 }
0528
0529 template <class _PairLike>
0530 requires is_constructible_v<pair<key_type, mapped_type>, _PairLike>
0531 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, _PairLike&& __x) {
0532 return emplace_hint(__hint, std::forward<_PairLike>(__x));
0533 }
0534
0535 template <class _InputIterator>
0536 requires __has_input_iterator_category<_InputIterator>::value
0537 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last) {
0538 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) {
0539 __reserve(__last - __first);
0540 }
0541 __append_sort_merge_unique< false>(std::move(__first), std::move(__last));
0542 }
0543
0544 template <class _InputIterator>
0545 requires __has_input_iterator_category<_InputIterator>::value
0546 _LIBCPP_HIDE_FROM_ABI void insert(sorted_unique_t, _InputIterator __first, _InputIterator __last) {
0547 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) {
0548 __reserve(__last - __first);
0549 }
0550
0551 __append_sort_merge_unique< true>(std::move(__first), std::move(__last));
0552 }
0553
0554 template <_ContainerCompatibleRange<value_type> _Range>
0555 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
0556 if constexpr (ranges::sized_range<_Range>) {
0557 __reserve(ranges::size(__range));
0558 }
0559
0560 __append_sort_merge_unique< false>(ranges::begin(__range), ranges::end(__range));
0561 }
0562
0563 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
0564
0565 _LIBCPP_HIDE_FROM_ABI void insert(sorted_unique_t, initializer_list<value_type> __il) {
0566 insert(sorted_unique, __il.begin(), __il.end());
0567 }
0568
0569 _LIBCPP_HIDE_FROM_ABI containers extract() && {
0570 auto __guard = std::__make_scope_guard([&]() noexcept { clear() ; });
0571 auto __ret = std::move(__containers_);
0572 return __ret;
0573 }
0574
0575 _LIBCPP_HIDE_FROM_ABI void replace(key_container_type&& __key_cont, mapped_container_type&& __mapped_cont) {
0576 _LIBCPP_ASSERT_VALID_INPUT_RANGE(
0577 __key_cont.size() == __mapped_cont.size(), "flat_map keys and mapped containers have different size");
0578
0579 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
0580 __is_sorted_and_unique(__key_cont), "Either the key container is not sorted or it contains duplicates");
0581 auto __guard = std::__make_exception_guard([&]() noexcept { clear() ; });
0582 __containers_.keys = std::move(__key_cont);
0583 __containers_.values = std::move(__mapped_cont);
0584 __guard.__complete();
0585 }
0586
0587 template <class... _Args>
0588 requires is_constructible_v<mapped_type, _Args...>
0589 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(const key_type& __key, _Args&&... __args) {
0590 return __try_emplace(__key, std::forward<_Args>(__args)...);
0591 }
0592
0593 template <class... _Args>
0594 requires is_constructible_v<mapped_type, _Args...>
0595 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(key_type&& __key, _Args&&... __args) {
0596 return __try_emplace(std::move(__key), std::forward<_Args>(__args)...);
0597 }
0598
0599 template <class _Kp, class... _Args>
0600 requires(__is_compare_transparent && is_constructible_v<key_type, _Kp> &&
0601 is_constructible_v<mapped_type, _Args...> && !is_convertible_v<_Kp &&, const_iterator> &&
0602 !is_convertible_v<_Kp &&, iterator>)
0603 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(_Kp&& __key, _Args&&... __args) {
0604 return __try_emplace(std::forward<_Kp>(__key), std::forward<_Args>(__args)...);
0605 }
0606
0607 template <class... _Args>
0608 requires is_constructible_v<mapped_type, _Args...>
0609 _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __hint, const key_type& __key, _Args&&... __args) {
0610 return __try_emplace_hint(__hint, __key, std::forward<_Args>(__args)...).first;
0611 }
0612
0613 template <class... _Args>
0614 requires is_constructible_v<mapped_type, _Args...>
0615 _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __hint, key_type&& __key, _Args&&... __args) {
0616 return __try_emplace_hint(__hint, std::move(__key), std::forward<_Args>(__args)...).first;
0617 }
0618
0619 template <class _Kp, class... _Args>
0620 requires __is_compare_transparent && is_constructible_v<key_type, _Kp> && is_constructible_v<mapped_type, _Args...>
0621 _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __hint, _Kp&& __key, _Args&&... __args) {
0622 return __try_emplace_hint(__hint, std::forward<_Kp>(__key), std::forward<_Args>(__args)...).first;
0623 }
0624
0625 template <class _Mapped>
0626 requires is_assignable_v<mapped_type&, _Mapped> && is_constructible_v<mapped_type, _Mapped>
0627 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(const key_type& __key, _Mapped&& __obj) {
0628 return __insert_or_assign(__key, std::forward<_Mapped>(__obj));
0629 }
0630
0631 template <class _Mapped>
0632 requires is_assignable_v<mapped_type&, _Mapped> && is_constructible_v<mapped_type, _Mapped>
0633 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(key_type&& __key, _Mapped&& __obj) {
0634 return __insert_or_assign(std::move(__key), std::forward<_Mapped>(__obj));
0635 }
0636
0637 template <class _Kp, class _Mapped>
0638 requires __is_compare_transparent && is_constructible_v<key_type, _Kp> && is_assignable_v<mapped_type&, _Mapped> &&
0639 is_constructible_v<mapped_type, _Mapped>
0640 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(_Kp&& __key, _Mapped&& __obj) {
0641 return __insert_or_assign(std::forward<_Kp>(__key), std::forward<_Mapped>(__obj));
0642 }
0643
0644 template <class _Mapped>
0645 requires is_assignable_v<mapped_type&, _Mapped> && is_constructible_v<mapped_type, _Mapped>
0646 _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __hint, const key_type& __key, _Mapped&& __obj) {
0647 return __insert_or_assign(__hint, __key, std::forward<_Mapped>(__obj));
0648 }
0649
0650 template <class _Mapped>
0651 requires is_assignable_v<mapped_type&, _Mapped> && is_constructible_v<mapped_type, _Mapped>
0652 _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __hint, key_type&& __key, _Mapped&& __obj) {
0653 return __insert_or_assign(__hint, std::move(__key), std::forward<_Mapped>(__obj));
0654 }
0655
0656 template <class _Kp, class _Mapped>
0657 requires __is_compare_transparent && is_constructible_v<key_type, _Kp> && is_assignable_v<mapped_type&, _Mapped> &&
0658 is_constructible_v<mapped_type, _Mapped>
0659 _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __hint, _Kp&& __key, _Mapped&& __obj) {
0660 return __insert_or_assign(__hint, std::forward<_Kp>(__key), std::forward<_Mapped>(__obj));
0661 }
0662
0663 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __position) {
0664 return __erase(__position.__key_iter_, __position.__mapped_iter_);
0665 }
0666
0667 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __position) {
0668 return __erase(__position.__key_iter_, __position.__mapped_iter_);
0669 }
0670
0671 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __x) {
0672 auto __iter = find(__x);
0673 if (__iter != end()) {
0674 erase(__iter);
0675 return 1;
0676 }
0677 return 0;
0678 }
0679
0680 template <class _Kp>
0681 requires(__is_compare_transparent && !is_convertible_v<_Kp &&, iterator> &&
0682 !is_convertible_v<_Kp &&, const_iterator>)
0683 _LIBCPP_HIDE_FROM_ABI size_type erase(_Kp&& __x) {
0684 auto [__first, __last] = equal_range(__x);
0685 auto __res = __last - __first;
0686 erase(__first, __last);
0687 return __res;
0688 }
0689
0690 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
0691 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() ; });
0692 auto __key_it = __containers_.keys.erase(__first.__key_iter_, __last.__key_iter_);
0693 auto __mapped_it = __containers_.values.erase(__first.__mapped_iter_, __last.__mapped_iter_);
0694 __on_failure.__complete();
0695 return iterator(std::move(__key_it), std::move(__mapped_it));
0696 }
0697
0698 _LIBCPP_HIDE_FROM_ABI void swap(flat_map& __y) noexcept {
0699
0700
0701
0702
0703 ranges::swap(__compare_, __y.__compare_);
0704 ranges::swap(__containers_.keys, __y.__containers_.keys);
0705 ranges::swap(__containers_.values, __y.__containers_.values);
0706 }
0707
0708 _LIBCPP_HIDE_FROM_ABI void clear() noexcept {
0709 __containers_.keys.clear();
0710 __containers_.values.clear();
0711 }
0712
0713
0714 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __compare_; }
0715 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return value_compare(__compare_); }
0716
0717 _LIBCPP_HIDE_FROM_ABI const key_container_type& keys() const noexcept { return __containers_.keys; }
0718 _LIBCPP_HIDE_FROM_ABI const mapped_container_type& values() const noexcept { return __containers_.values; }
0719
0720
0721 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __x) { return __find_impl(*this, __x); }
0722
0723 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __x) const { return __find_impl(*this, __x); }
0724
0725 template <class _Kp>
0726 requires __is_compare_transparent
0727 _LIBCPP_HIDE_FROM_ABI iterator find(const _Kp& __x) {
0728 return __find_impl(*this, __x);
0729 }
0730
0731 template <class _Kp>
0732 requires __is_compare_transparent
0733 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _Kp& __x) const {
0734 return __find_impl(*this, __x);
0735 }
0736
0737 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __x) const { return contains(__x) ? 1 : 0; }
0738
0739 template <class _Kp>
0740 requires __is_compare_transparent
0741 _LIBCPP_HIDE_FROM_ABI size_type count(const _Kp& __x) const {
0742 return contains(__x) ? 1 : 0;
0743 }
0744
0745 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __x) const { return find(__x) != end(); }
0746
0747 template <class _Kp>
0748 requires __is_compare_transparent
0749 _LIBCPP_HIDE_FROM_ABI bool contains(const _Kp& __x) const {
0750 return find(__x) != end();
0751 }
0752
0753 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __x) { return __lower_bound<iterator>(*this, __x); }
0754
0755 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __x) const {
0756 return __lower_bound<const_iterator>(*this, __x);
0757 }
0758
0759 template <class _Kp>
0760 requires __is_compare_transparent
0761 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _Kp& __x) {
0762 return __lower_bound<iterator>(*this, __x);
0763 }
0764
0765 template <class _Kp>
0766 requires __is_compare_transparent
0767 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _Kp& __x) const {
0768 return __lower_bound<const_iterator>(*this, __x);
0769 }
0770
0771 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __x) { return __upper_bound<iterator>(*this, __x); }
0772
0773 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __x) const {
0774 return __upper_bound<const_iterator>(*this, __x);
0775 }
0776
0777 template <class _Kp>
0778 requires __is_compare_transparent
0779 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _Kp& __x) {
0780 return __upper_bound<iterator>(*this, __x);
0781 }
0782
0783 template <class _Kp>
0784 requires __is_compare_transparent
0785 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _Kp& __x) const {
0786 return __upper_bound<const_iterator>(*this, __x);
0787 }
0788
0789 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __x) {
0790 return __equal_range_impl(*this, __x);
0791 }
0792
0793 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __x) const {
0794 return __equal_range_impl(*this, __x);
0795 }
0796
0797 template <class _Kp>
0798 requires __is_compare_transparent
0799 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _Kp& __x) {
0800 return __equal_range_impl(*this, __x);
0801 }
0802 template <class _Kp>
0803 requires __is_compare_transparent
0804 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _Kp& __x) const {
0805 return __equal_range_impl(*this, __x);
0806 }
0807
0808 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const flat_map& __x, const flat_map& __y) {
0809 return ranges::equal(__x, __y);
0810 }
0811
0812 friend _LIBCPP_HIDE_FROM_ABI auto operator<=>(const flat_map& __x, const flat_map& __y) {
0813 return std::lexicographical_compare_three_way(
0814 __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
0815 }
0816
0817 friend _LIBCPP_HIDE_FROM_ABI void swap(flat_map& __x, flat_map& __y) noexcept { __x.swap(__y); }
0818
0819 private:
0820 struct __ctor_uses_allocator_tag {
0821 explicit _LIBCPP_HIDE_FROM_ABI __ctor_uses_allocator_tag() = default;
0822 };
0823 struct __ctor_uses_allocator_empty_tag {
0824 explicit _LIBCPP_HIDE_FROM_ABI __ctor_uses_allocator_empty_tag() = default;
0825 };
0826
0827 template <class _Allocator, class _KeyCont, class _MappedCont, class... _CompArg>
0828 requires __allocator_ctor_constraint<_Allocator>
0829 _LIBCPP_HIDE_FROM_ABI
0830 flat_map(__ctor_uses_allocator_tag,
0831 const _Allocator& __alloc,
0832 _KeyCont&& __key_cont,
0833 _MappedCont&& __mapped_cont,
0834 _CompArg&&... __comp)
0835 : __containers_{.keys = std::make_obj_using_allocator<key_container_type>(
0836 __alloc, std::forward<_KeyCont>(__key_cont)),
0837 .values = std::make_obj_using_allocator<mapped_container_type>(
0838 __alloc, std::forward<_MappedCont>(__mapped_cont))},
0839 __compare_(std::forward<_CompArg>(__comp)...) {}
0840
0841 template <class _Allocator, class... _CompArg>
0842 requires __allocator_ctor_constraint<_Allocator>
0843 _LIBCPP_HIDE_FROM_ABI flat_map(__ctor_uses_allocator_empty_tag, const _Allocator& __alloc, _CompArg&&... __comp)
0844 : __containers_{.keys = std::make_obj_using_allocator<key_container_type>(__alloc),
0845 .values = std::make_obj_using_allocator<mapped_container_type>(__alloc)},
0846 __compare_(std::forward<_CompArg>(__comp)...) {}
0847
0848 _LIBCPP_HIDE_FROM_ABI bool __is_sorted_and_unique(auto&& __key_container) const {
0849 auto __greater_or_equal_to = [this](const auto& __x, const auto& __y) { return !__compare_(__x, __y); };
0850 return ranges::adjacent_find(__key_container, __greater_or_equal_to) == ranges::end(__key_container);
0851 }
0852
0853
0854
0855
0856 _LIBCPP_HIDE_FROM_ABI void __sort_and_unique() {
0857 auto __zv = ranges::views::zip(__containers_.keys, __containers_.values);
0858 ranges::sort(__zv, __compare_, [](const auto& __p) -> decltype(auto) { return std::get<0>(__p); });
0859 auto __dup_start = ranges::unique(__zv, __key_equiv(__compare_)).begin();
0860 auto __dist = ranges::distance(__zv.begin(), __dup_start);
0861 __containers_.keys.erase(__containers_.keys.begin() + __dist, __containers_.keys.end());
0862 __containers_.values.erase(__containers_.values.begin() + __dist, __containers_.values.end());
0863 }
0864
0865 template <bool _WasSorted, class _InputIterator, class _Sentinel>
0866 _LIBCPP_HIDE_FROM_ABI void __append_sort_merge_unique(_InputIterator __first, _Sentinel __last) {
0867 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() ; });
0868 size_t __num_of_appended = __flat_map_utils::__append(*this, std::move(__first), std::move(__last));
0869 if (__num_of_appended != 0) {
0870 auto __zv = ranges::views::zip(__containers_.keys, __containers_.values);
0871 auto __append_start_offset = __containers_.keys.size() - __num_of_appended;
0872 auto __end = __zv.end();
0873 auto __compare_key = [this](const auto& __p1, const auto& __p2) {
0874 return __compare_(std::get<0>(__p1), std::get<0>(__p2));
0875 };
0876 if constexpr (!_WasSorted) {
0877 ranges::sort(__zv.begin() + __append_start_offset, __end, __compare_key);
0878 } else {
0879 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
0880 __is_sorted_and_unique(__containers_.keys | ranges::views::drop(__append_start_offset)),
0881 "Either the key container is not sorted or it contains duplicates");
0882 }
0883 ranges::inplace_merge(__zv.begin(), __zv.begin() + __append_start_offset, __end, __compare_key);
0884
0885 auto __dup_start = ranges::unique(__zv, __key_equiv(__compare_)).begin();
0886 auto __dist = ranges::distance(__zv.begin(), __dup_start);
0887 __containers_.keys.erase(__containers_.keys.begin() + __dist, __containers_.keys.end());
0888 __containers_.values.erase(__containers_.values.begin() + __dist, __containers_.values.end());
0889 }
0890 __on_failure.__complete();
0891 }
0892
0893 template <class _Self, class _Kp>
0894 _LIBCPP_HIDE_FROM_ABI static auto __find_impl(_Self&& __self, const _Kp& __key) {
0895 auto __it = __self.lower_bound(__key);
0896 auto __last = __self.end();
0897 if (__it == __last || __self.__compare_(__key, __it->first)) {
0898 return __last;
0899 }
0900 return __it;
0901 }
0902
0903 template <class _Self, class _Kp>
0904 _LIBCPP_HIDE_FROM_ABI static auto __key_equal_range(_Self&& __self, const _Kp& __key) {
0905 auto __it = ranges::lower_bound(__self.__containers_.keys, __key, __self.__compare_);
0906 auto __last = __self.__containers_.keys.end();
0907 if (__it == __last || __self.__compare_(__key, *__it)) {
0908 return std::make_pair(__it, __it);
0909 }
0910 return std::make_pair(__it, std::next(__it));
0911 }
0912
0913 template <class _Self, class _Kp>
0914 _LIBCPP_HIDE_FROM_ABI static auto __equal_range_impl(_Self&& __self, const _Kp& __key) {
0915 auto [__key_first, __key_last] = __key_equal_range(__self, __key);
0916
0917 const auto __make_mapped_iter = [&](const auto& __key_iter) {
0918 return __self.__containers_.values.begin() +
0919 static_cast<ranges::range_difference_t<mapped_container_type>>(
0920 ranges::distance(__self.__containers_.keys.begin(), __key_iter));
0921 };
0922
0923 using __iterator_type = ranges::iterator_t<decltype(__self)>;
0924 return std::make_pair(__iterator_type(__key_first, __make_mapped_iter(__key_first)),
0925 __iterator_type(__key_last, __make_mapped_iter(__key_last)));
0926 }
0927
0928 template <class _Res, class _Self, class _Kp>
0929 _LIBCPP_HIDE_FROM_ABI static _Res __lower_bound(_Self&& __self, _Kp& __x) {
0930 return __binary_search<_Res>(__self, ranges::lower_bound, __x);
0931 }
0932
0933 template <class _Res, class _Self, class _Kp>
0934 _LIBCPP_HIDE_FROM_ABI static _Res __upper_bound(_Self&& __self, _Kp& __x) {
0935 return __binary_search<_Res>(__self, ranges::upper_bound, __x);
0936 }
0937
0938 template <class _Res, class _Self, class _Fn, class _Kp>
0939 _LIBCPP_HIDE_FROM_ABI static _Res __binary_search(_Self&& __self, _Fn __search_fn, _Kp& __x) {
0940 auto __key_iter = __search_fn(__self.__containers_.keys, __x, __self.__compare_);
0941 auto __mapped_iter =
0942 __self.__containers_.values.begin() +
0943 static_cast<ranges::range_difference_t<mapped_container_type>>(
0944 ranges::distance(__self.__containers_.keys.begin(), __key_iter));
0945
0946 return _Res(std::move(__key_iter), std::move(__mapped_iter));
0947 }
0948
0949 template <class _KeyArg, class... _MArgs>
0950 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __try_emplace(_KeyArg&& __key, _MArgs&&... __mapped_args) {
0951 auto __key_it = ranges::lower_bound(__containers_.keys, __key, __compare_);
0952 auto __mapped_it = __containers_.values.begin() + ranges::distance(__containers_.keys.begin(), __key_it);
0953
0954 if (__key_it == __containers_.keys.end() || __compare_(__key, *__key_it)) {
0955 return pair<iterator, bool>(
0956 __flat_map_utils::__emplace_exact_pos(
0957 *this,
0958 std::move(__key_it),
0959 std::move(__mapped_it),
0960 std::forward<_KeyArg>(__key),
0961 std::forward<_MArgs>(__mapped_args)...),
0962 true);
0963 } else {
0964 return pair<iterator, bool>(iterator(std::move(__key_it), std::move(__mapped_it)), false);
0965 }
0966 }
0967
0968 template <class _Kp>
0969 _LIBCPP_HIDE_FROM_ABI bool __is_hint_correct(const_iterator __hint, _Kp&& __key) {
0970 if (__hint != cbegin() && !__compare_((__hint - 1)->first, __key)) {
0971 return false;
0972 }
0973 if (__hint != cend() && __compare_(__hint->first, __key)) {
0974 return false;
0975 }
0976 return true;
0977 }
0978
0979 template <class _Kp, class... _Args>
0980 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __try_emplace_hint(const_iterator __hint, _Kp&& __key, _Args&&... __args) {
0981 if (__is_hint_correct(__hint, __key)) {
0982 if (__hint == cend() || __compare_(__key, __hint->first)) {
0983 return {__flat_map_utils::__emplace_exact_pos(
0984 *this,
0985 __hint.__key_iter_,
0986 __hint.__mapped_iter_,
0987 std::forward<_Kp>(__key),
0988 std::forward<_Args>(__args)...),
0989 true};
0990 } else {
0991
0992 auto __dist = __hint - cbegin();
0993 return {iterator(__containers_.keys.begin() + __dist, __containers_.values.begin() + __dist), false};
0994 }
0995 } else {
0996 return __try_emplace(std::forward<_Kp>(__key), std::forward<_Args>(__args)...);
0997 }
0998 }
0999
1000 template <class _Kp, class _Mapped>
1001 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_or_assign(_Kp&& __key, _Mapped&& __mapped) {
1002 auto __r = try_emplace(std::forward<_Kp>(__key), std::forward<_Mapped>(__mapped));
1003 if (!__r.second) {
1004 __r.first->second = std::forward<_Mapped>(__mapped);
1005 }
1006 return __r;
1007 }
1008
1009 template <class _Kp, class _Mapped>
1010 _LIBCPP_HIDE_FROM_ABI iterator __insert_or_assign(const_iterator __hint, _Kp&& __key, _Mapped&& __mapped) {
1011 auto __r = __try_emplace_hint(__hint, std::forward<_Kp>(__key), std::forward<_Mapped>(__mapped));
1012 if (!__r.second) {
1013 __r.first->second = std::forward<_Mapped>(__mapped);
1014 }
1015 return __r.first;
1016 }
1017
1018 _LIBCPP_HIDE_FROM_ABI void __reserve(size_t __size) {
1019 if constexpr (requires { __containers_.keys.reserve(__size); }) {
1020 __containers_.keys.reserve(__size);
1021 }
1022
1023 if constexpr (requires { __containers_.values.reserve(__size); }) {
1024 __containers_.values.reserve(__size);
1025 }
1026 }
1027
1028 template <class _KIter, class _MIter>
1029 _LIBCPP_HIDE_FROM_ABI iterator __erase(_KIter __key_iter_to_remove, _MIter __mapped_iter_to_remove) {
1030 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() ; });
1031 auto __key_iter = __containers_.keys.erase(__key_iter_to_remove);
1032 auto __mapped_iter = __containers_.values.erase(__mapped_iter_to_remove);
1033 __on_failure.__complete();
1034 return iterator(std::move(__key_iter), std::move(__mapped_iter));
1035 }
1036
1037 template <class _Key2, class _Tp2, class _Compare2, class _KeyContainer2, class _MappedContainer2, class _Predicate>
1038 friend typename flat_map<_Key2, _Tp2, _Compare2, _KeyContainer2, _MappedContainer2>::size_type
1039 erase_if(flat_map<_Key2, _Tp2, _Compare2, _KeyContainer2, _MappedContainer2>&, _Predicate);
1040
1041 friend __flat_map_utils;
1042
1043 containers __containers_;
1044 _LIBCPP_NO_UNIQUE_ADDRESS key_compare __compare_;
1045
1046 struct __key_equiv {
1047 _LIBCPP_HIDE_FROM_ABI __key_equiv(key_compare __c) : __comp_(__c) {}
1048 _LIBCPP_HIDE_FROM_ABI bool operator()(const_reference __x, const_reference __y) const {
1049 return !__comp_(std::get<0>(__x), std::get<0>(__y)) && !__comp_(std::get<0>(__y), std::get<0>(__x));
1050 }
1051 key_compare __comp_;
1052 };
1053 };
1054
1055 template <class _KeyContainer, class _MappedContainer, class _Compare = less<typename _KeyContainer::value_type>>
1056 requires(!__is_allocator<_Compare>::value && !__is_allocator<_KeyContainer>::value &&
1057 !__is_allocator<_MappedContainer>::value &&
1058 is_invocable_v<const _Compare&,
1059 const typename _KeyContainer::value_type&,
1060 const typename _KeyContainer::value_type&>)
1061 flat_map(_KeyContainer, _MappedContainer, _Compare = _Compare())
1062 -> flat_map<typename _KeyContainer::value_type,
1063 typename _MappedContainer::value_type,
1064 _Compare,
1065 _KeyContainer,
1066 _MappedContainer>;
1067
1068 template <class _KeyContainer, class _MappedContainer, class _Allocator>
1069 requires(uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator> &&
1070 !__is_allocator<_KeyContainer>::value && !__is_allocator<_MappedContainer>::value)
1071 flat_map(_KeyContainer, _MappedContainer, _Allocator)
1072 -> flat_map<typename _KeyContainer::value_type,
1073 typename _MappedContainer::value_type,
1074 less<typename _KeyContainer::value_type>,
1075 _KeyContainer,
1076 _MappedContainer>;
1077
1078 template <class _KeyContainer, class _MappedContainer, class _Compare, class _Allocator>
1079 requires(!__is_allocator<_Compare>::value && !__is_allocator<_KeyContainer>::value &&
1080 !__is_allocator<_MappedContainer>::value && uses_allocator_v<_KeyContainer, _Allocator> &&
1081 uses_allocator_v<_MappedContainer, _Allocator> &&
1082 is_invocable_v<const _Compare&,
1083 const typename _KeyContainer::value_type&,
1084 const typename _KeyContainer::value_type&>)
1085 flat_map(_KeyContainer, _MappedContainer, _Compare, _Allocator)
1086 -> flat_map<typename _KeyContainer::value_type,
1087 typename _MappedContainer::value_type,
1088 _Compare,
1089 _KeyContainer,
1090 _MappedContainer>;
1091
1092 template <class _KeyContainer, class _MappedContainer, class _Compare = less<typename _KeyContainer::value_type>>
1093 requires(!__is_allocator<_Compare>::value && !__is_allocator<_KeyContainer>::value &&
1094 !__is_allocator<_MappedContainer>::value &&
1095 is_invocable_v<const _Compare&,
1096 const typename _KeyContainer::value_type&,
1097 const typename _KeyContainer::value_type&>)
1098 flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Compare = _Compare())
1099 -> flat_map<typename _KeyContainer::value_type,
1100 typename _MappedContainer::value_type,
1101 _Compare,
1102 _KeyContainer,
1103 _MappedContainer>;
1104
1105 template <class _KeyContainer, class _MappedContainer, class _Allocator>
1106 requires(uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator> &&
1107 !__is_allocator<_KeyContainer>::value && !__is_allocator<_MappedContainer>::value)
1108 flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Allocator)
1109 -> flat_map<typename _KeyContainer::value_type,
1110 typename _MappedContainer::value_type,
1111 less<typename _KeyContainer::value_type>,
1112 _KeyContainer,
1113 _MappedContainer>;
1114
1115 template <class _KeyContainer, class _MappedContainer, class _Compare, class _Allocator>
1116 requires(!__is_allocator<_Compare>::value && !__is_allocator<_KeyContainer>::value &&
1117 !__is_allocator<_MappedContainer>::value && uses_allocator_v<_KeyContainer, _Allocator> &&
1118 uses_allocator_v<_MappedContainer, _Allocator> &&
1119 is_invocable_v<const _Compare&,
1120 const typename _KeyContainer::value_type&,
1121 const typename _KeyContainer::value_type&>)
1122 flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Compare, _Allocator)
1123 -> flat_map<typename _KeyContainer::value_type,
1124 typename _MappedContainer::value_type,
1125 _Compare,
1126 _KeyContainer,
1127 _MappedContainer>;
1128
1129 template <class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>>
1130 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator<_Compare>::value)
1131 flat_map(_InputIterator, _InputIterator, _Compare = _Compare())
1132 -> flat_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare>;
1133
1134 template <class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>>
1135 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator<_Compare>::value)
1136 flat_map(sorted_unique_t, _InputIterator, _InputIterator, _Compare = _Compare())
1137 -> flat_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare>;
1138
1139 template <ranges::input_range _Range,
1140 class _Compare = less<__range_key_type<_Range>>,
1141 class _Allocator = allocator<byte>,
1142 class = __enable_if_t<!__is_allocator<_Compare>::value && __is_allocator<_Allocator>::value>>
1143 flat_map(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator()) -> flat_map<
1144 __range_key_type<_Range>,
1145 __range_mapped_type<_Range>,
1146 _Compare,
1147 vector<__range_key_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_key_type<_Range>>>,
1148 vector<__range_mapped_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_mapped_type<_Range>>>>;
1149
1150 template <ranges::input_range _Range, class _Allocator, class = __enable_if_t<__is_allocator<_Allocator>::value>>
1151 flat_map(from_range_t, _Range&&, _Allocator) -> flat_map<
1152 __range_key_type<_Range>,
1153 __range_mapped_type<_Range>,
1154 less<__range_key_type<_Range>>,
1155 vector<__range_key_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_key_type<_Range>>>,
1156 vector<__range_mapped_type<_Range>, __allocator_traits_rebind_t<_Allocator, __range_mapped_type<_Range>>>>;
1157
1158 template <class _Key, class _Tp, class _Compare = less<_Key>>
1159 requires(!__is_allocator<_Compare>::value)
1160 flat_map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare()) -> flat_map<_Key, _Tp, _Compare>;
1161
1162 template <class _Key, class _Tp, class _Compare = less<_Key>>
1163 requires(!__is_allocator<_Compare>::value)
1164 flat_map(sorted_unique_t, initializer_list<pair<_Key, _Tp>>, _Compare = _Compare()) -> flat_map<_Key, _Tp, _Compare>;
1165
1166 template <class _Key, class _Tp, class _Compare, class _KeyContainer, class _MappedContainer, class _Allocator>
1167 struct uses_allocator<flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>, _Allocator>
1168 : bool_constant<uses_allocator_v<_KeyContainer, _Allocator> && uses_allocator_v<_MappedContainer, _Allocator>> {};
1169
1170 template <class _Key, class _Tp, class _Compare, class _KeyContainer, class _MappedContainer, class _Predicate>
1171 _LIBCPP_HIDE_FROM_ABI typename flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>::size_type
1172 erase_if(flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>& __flat_map, _Predicate __pred) {
1173 auto __zv = ranges::views::zip(__flat_map.__containers_.keys, __flat_map.__containers_.values);
1174 auto __first = __zv.begin();
1175 auto __last = __zv.end();
1176 auto __guard = std::__make_exception_guard([&] { __flat_map.clear(); });
1177 auto __it = std::remove_if(__first, __last, [&](auto&& __zipped) -> bool {
1178 using _Ref = typename flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>::const_reference;
1179 return __pred(_Ref(std::get<0>(__zipped), std::get<1>(__zipped)));
1180 });
1181 auto __res = __last - __it;
1182 auto __offset = __it - __first;
1183
1184 const auto __erase_container = [&](auto& __cont) { __cont.erase(__cont.begin() + __offset, __cont.end()); };
1185
1186 __erase_container(__flat_map.__containers_.keys);
1187 __erase_container(__flat_map.__containers_.values);
1188
1189 __guard.__complete();
1190 return __res;
1191 }
1192
1193 _LIBCPP_END_NAMESPACE_STD
1194
1195 #endif
1196
1197 _LIBCPP_POP_MACROS
1198
1199 #endif
