1 // -*- C++ -*- 2 //===----------------------------------------------------------------------===// 3 // 4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5 // See https://llvm.org/LICENSE.txt for license information. 6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7 // 8 //===----------------------------------------------------------------------===// 9 10 #ifndef _LIBCPP___FLAT_MAP_FLAT_MAP_H 11 #define _LIBCPP___FLAT_MAP_FLAT_MAP_H 12 13 #include <__algorithm/lexicographical_compare_three_way.h> 14 #include <__algorithm/min.h> 15 #include <__algorithm/ranges_adjacent_find.h> 16 #include <__algorithm/ranges_equal.h> 17 #include <__algorithm/ranges_inplace_merge.h> 18 #include <__algorithm/ranges_lower_bound.h> 19 #include <__algorithm/ranges_partition_point.h> 20 #include <__algorithm/ranges_sort.h> 21 #include <__algorithm/ranges_unique.h> 22 #include <__algorithm/ranges_upper_bound.h> 23 #include <__algorithm/remove_if.h> 24 #include <__assert> 25 #include <__compare/synth_three_way.h> 26 #include <__concepts/swappable.h> 27 #include <__config> 28 #include <__cstddef/byte.h> 29 #include <__cstddef/ptrdiff_t.h> 30 #include <__flat_map/key_value_iterator.h> 31 #include <__flat_map/sorted_unique.h> 32 #include <__flat_map/utils.h> 33 #include <__functional/invoke.h> 34 #include <__functional/is_transparent.h> 35 #include <__functional/operations.h> 36 #include <__fwd/vector.h> 37 #include <__iterator/concepts.h> 38 #include <__iterator/distance.h> 39 #include <__iterator/iterator_traits.h> 40 #include <__iterator/next.h> 41 #include <__iterator/ranges_iterator_traits.h> 42 #include <__iterator/reverse_iterator.h> 43 #include <__memory/allocator_traits.h> 44 #include <__memory/uses_allocator.h> 45 #include <__memory/uses_allocator_construction.h> 46 #include <__ranges/access.h> 47 #include <__ranges/concepts.h> 48 #include <__ranges/container_compatible_range.h> 49 #include <__ranges/drop_view.h> 50 #include <__ranges/from_range.h> 51 #include <__ranges/ref_view.h> 52 #include <__ranges/size.h> 53 #include <__ranges/subrange.h> 54 #include <__ranges/zip_view.h> 55 #include <__type_traits/conjunction.h> 56 #include <__type_traits/container_traits.h> 57 #include <__type_traits/invoke.h> 58 #include <__type_traits/is_allocator.h> 59 #include <__type_traits/is_nothrow_constructible.h> 60 #include <__type_traits/is_same.h> 61 #include <__utility/exception_guard.h> 62 #include <__utility/move.h> 63 #include <__utility/pair.h> 64 #include <__utility/scope_guard.h> 65 #include <__vector/vector.h> 66 #include <initializer_list> 67 #include <stdexcept> 68 69 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 70 # pragma GCC system_header 71 #endif 72 73 _LIBCPP_PUSH_MACROS 74 #include <__undef_macros> 75 76 #if _LIBCPP_STD_VER >= 23 77 78 _LIBCPP_BEGIN_NAMESPACE_STD 79 80 template <class _Key, 81 class _Tp, 82 class _Compare = less<_Key>, 83 class _KeyContainer = vector<_Key>, 84 class _MappedContainer = vector<_Tp>> 85 class flat_map { 86 template <class, class, class, class, class> 87 friend class flat_map; 88 89 static_assert(is_same_v<_Key, typename _KeyContainer::value_type>); 90 static_assert(is_same_v<_Tp, typename _MappedContainer::value_type>); 91 static_assert(!is_same_v<_KeyContainer, std::vector<bool>>, "vector<bool> is not a sequence container"); 92 static_assert(!is_same_v<_MappedContainer, std::vector<bool>>, "vector<bool> is not a sequence container"); 93 94 template <bool _Const> 95 using __iterator _LIBCPP_NODEBUG = __key_value_iterator<flat_map, _KeyContainer, _MappedContainer, _Const>; 96 97 public: 98 // types 99 using key_type = _Key; 100 using mapped_type = _Tp; 101 using value_type = pair<key_type, mapped_type>; 102 using key_compare = __type_identity_t<_Compare>; 103 using reference = pair<const key_type&, mapped_type&>; 104 using const_reference = pair<const key_type&, const mapped_type&>; 105 using size_type = size_t; 106 using difference_type = ptrdiff_t; 107 using iterator = __iterator<false>; // see [container.requirements] 108 using const_iterator = __iterator<true>; // see [container.requirements] 109 using reverse_iterator = std::reverse_iterator<iterator>; 110 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 111 using key_container_type = _KeyContainer; 112 using mapped_container_type = _MappedContainer; 113 114 class value_compare { 115 private: 116 key_compare __comp_; 117 _LIBCPP_HIDE_FROM_ABI value_compare(key_compare __c) : __comp_(__c) {} 118 friend flat_map; 119 120 public: 121 _LIBCPP_HIDE_FROM_ABI bool 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 131 private: 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 138 public: 139 // [flat.map.cons], construct/copy/destroy 140 _LIBCPP_HIDE_FROM_ABI 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 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_EXCEPTIONS 151 try 152 # endif // _LIBCPP_HAS_EXCEPTIONS 153 : __containers_(std::move(__other.__containers_)), __compare_(std::move(__other.__compare_)) { 154 __other.clear(); 155 # if _LIBCPP_HAS_EXCEPTIONS 156 } catch (...) { 157 __other.clear(); 158 // gcc does not like the `throw` keyword in a conditionally noexcept function 159 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_EXCEPTIONS 164 } 165 166 template <class _Allocator> 167 requires __allocator_ctor_constraint<_Allocator> 168 _LIBCPP_HIDE_FROM_ABI 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 flat_map(flat_map&& __other, const _Allocator& __alloc) 178 # if _LIBCPP_HAS_EXCEPTIONS 179 try 180 # endif // _LIBCPP_HAS_EXCEPTIONS 181 : 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_EXCEPTIONS 188 } catch (...) { 189 __other.clear(); 190 throw; 191 # endif // _LIBCPP_HAS_EXCEPTIONS 192 } 193 194 _LIBCPP_HIDE_FROM_ABI 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 205 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 215 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 226 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 240 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 254 flat_map(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 explicit flat_map(const key_compare& __comp) : __containers_(), __compare_(__comp) {} 267 268 template <class _Allocator> 269 requires __allocator_ctor_constraint<_Allocator> 270 _LIBCPP_HIDE_FROM_ABI flat_map(const key_compare& __comp, const _Allocator& __alloc) 271 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) {} 272 273 template <class _Allocator> 274 requires __allocator_ctor_constraint<_Allocator> 275 _LIBCPP_HIDE_FROM_ABI explicit flat_map(const _Allocator& __alloc) 276 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc) {} 277 278 template <class _InputIterator> 279 requires __has_input_iterator_category<_InputIterator>::value 280 _LIBCPP_HIDE_FROM_ABI 281 flat_map(_InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare()) 282 : __containers_(), __compare_(__comp) { 283 insert(__first, __last); 284 } 285 286 template <class _InputIterator, class _Allocator> 287 requires(__has_input_iterator_category<_InputIterator>::value && __allocator_ctor_constraint<_Allocator>) 288 _LIBCPP_HIDE_FROM_ABI 289 flat_map(_InputIterator __first, _InputIterator __last, const key_compare& __comp, const _Allocator& __alloc) 290 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) { 291 insert(__first, __last); 292 } 293 294 template <class _InputIterator, class _Allocator> 295 requires(__has_input_iterator_category<_InputIterator>::value && __allocator_ctor_constraint<_Allocator>) 296 _LIBCPP_HIDE_FROM_ABI flat_map(_InputIterator __first, _InputIterator __last, const _Allocator& __alloc) 297 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc) { 298 insert(__first, __last); 299 } 300 301 template <_ContainerCompatibleRange<value_type> _Range> 302 _LIBCPP_HIDE_FROM_ABI flat_map(from_range_t __fr, _Range&& __rg) 303 : flat_map(__fr, std::forward<_Range>(__rg), key_compare()) {} 304 305 template <_ContainerCompatibleRange<value_type> _Range, class _Allocator> 306 requires __allocator_ctor_constraint<_Allocator> 307 _LIBCPP_HIDE_FROM_ABI flat_map(from_range_t, _Range&& __rg, const _Allocator& __alloc) 308 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc) { 309 insert_range(std::forward<_Range>(__rg)); 310 } 311 312 template <_ContainerCompatibleRange<value_type> _Range> 313 _LIBCPP_HIDE_FROM_ABI flat_map(from_range_t, _Range&& __rg, const key_compare& __comp) : flat_map(__comp) { 314 insert_range(std::forward<_Range>(__rg)); 315 } 316 317 template <_ContainerCompatibleRange<value_type> _Range, class _Allocator> 318 requires __allocator_ctor_constraint<_Allocator> 319 _LIBCPP_HIDE_FROM_ABI flat_map(from_range_t, _Range&& __rg, const key_compare& __comp, const _Allocator& __alloc) 320 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) { 321 insert_range(std::forward<_Range>(__rg)); 322 } 323 324 template <class _InputIterator> 325 requires __has_input_iterator_category<_InputIterator>::value 326 _LIBCPP_HIDE_FROM_ABI 327 flat_map(sorted_unique_t, _InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare()) 328 : __containers_(), __compare_(__comp) { 329 insert(sorted_unique, __first, __last); 330 } 331 template <class _InputIterator, class _Allocator> 332 requires(__has_input_iterator_category<_InputIterator>::value && __allocator_ctor_constraint<_Allocator>) 333 _LIBCPP_HIDE_FROM_ABI 334 flat_map(sorted_unique_t, 335 _InputIterator __first, 336 _InputIterator __last, 337 const key_compare& __comp, 338 const _Allocator& __alloc) 339 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc, __comp) { 340 insert(sorted_unique, __first, __last); 341 } 342 343 template <class _InputIterator, class _Allocator> 344 requires(__has_input_iterator_category<_InputIterator>::value && __allocator_ctor_constraint<_Allocator>) 345 _LIBCPP_HIDE_FROM_ABI 346 flat_map(sorted_unique_t, _InputIterator __first, _InputIterator __last, const _Allocator& __alloc) 347 : flat_map(__ctor_uses_allocator_empty_tag{}, __alloc) { 348 insert(sorted_unique, __first, __last); 349 } 350 351 _LIBCPP_HIDE_FROM_ABI flat_map(initializer_list<value_type> __il, const key_compare& __comp = key_compare()) 352 : flat_map(__il.begin(), __il.end(), __comp) {} 353 354 template <class _Allocator> 355 requires __allocator_ctor_constraint<_Allocator> 356 _LIBCPP_HIDE_FROM_ABI 357 flat_map(initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc) 358 : flat_map(__il.begin(), __il.end(), __comp, __alloc) {} 359 360 template <class _Allocator> 361 requires __allocator_ctor_constraint<_Allocator> 362 _LIBCPP_HIDE_FROM_ABI flat_map(initializer_list<value_type> __il, const _Allocator& __alloc) 363 : flat_map(__il.begin(), __il.end(), __alloc) {} 364 365 _LIBCPP_HIDE_FROM_ABI 366 flat_map(sorted_unique_t, initializer_list<value_type> __il, const key_compare& __comp = key_compare()) 367 : flat_map(sorted_unique, __il.begin(), __il.end(), __comp) {} 368 369 template <class _Allocator> 370 requires __allocator_ctor_constraint<_Allocator> 371 _LIBCPP_HIDE_FROM_ABI 372 flat_map(sorted_unique_t, initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc) 373 : flat_map(sorted_unique, __il.begin(), __il.end(), __comp, __alloc) {} 374 375 template <class _Allocator> 376 requires __allocator_ctor_constraint<_Allocator> 377 _LIBCPP_HIDE_FROM_ABI flat_map(sorted_unique_t, initializer_list<value_type> __il, const _Allocator& __alloc) 378 : flat_map(sorted_unique, __il.begin(), __il.end(), __alloc) {} 379 380 _LIBCPP_HIDE_FROM_ABI flat_map& operator=(initializer_list<value_type> __il) { 381 clear(); 382 insert(__il); 383 return *this; 384 } 385 386 _LIBCPP_HIDE_FROM_ABI flat_map& operator=(const flat_map&) = default; 387 388 _LIBCPP_HIDE_FROM_ABI flat_map& operator=(flat_map&& __other) noexcept( 389 is_nothrow_move_assignable_v<_KeyContainer> && is_nothrow_move_assignable_v<_MappedContainer> && 390 is_nothrow_move_assignable_v<_Compare>) { 391 // No matter what happens, we always want to clear the other container before returning 392 // since we moved from it 393 auto __clear_other_guard = std::__make_scope_guard([&]() noexcept { __other.clear() /* noexcept */; }); 394 { 395 // If an exception is thrown, we have no choice but to clear *this to preserve invariants 396 auto __on_exception = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; }); 397 __containers_ = std::move(__other.__containers_); 398 __compare_ = std::move(__other.__compare_); 399 __on_exception.__complete(); 400 } 401 return *this; 402 } 403 404 // iterators 405 _LIBCPP_HIDE_FROM_ABI iterator begin() noexcept { 406 return iterator(__containers_.keys.begin(), __containers_.values.begin()); 407 } 408 409 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const noexcept { 410 return const_iterator(__containers_.keys.begin(), __containers_.values.begin()); 411 } 412 413 _LIBCPP_HIDE_FROM_ABI iterator end() noexcept { 414 return iterator(__containers_.keys.end(), __containers_.values.end()); 415 } 416 417 _LIBCPP_HIDE_FROM_ABI const_iterator end() const noexcept { 418 return const_iterator(__containers_.keys.end(), __containers_.values.end()); 419 } 420 421 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() noexcept { return reverse_iterator(end()); } 422 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); } 423 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() noexcept { return reverse_iterator(begin()); } 424 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); } 425 426 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const noexcept { return begin(); } 427 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const noexcept { return end(); } 428 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(end()); } 429 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const noexcept { return const_reverse_iterator(begin()); } 430 431 // [flat.map.capacity], capacity 432 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI bool empty() const noexcept { return __containers_.keys.empty(); } 433 434 _LIBCPP_HIDE_FROM_ABI size_type size() const noexcept { return __containers_.keys.size(); } 435 436 _LIBCPP_HIDE_FROM_ABI size_type max_size() const noexcept { 437 return std::min<size_type>(__containers_.keys.max_size(), __containers_.values.max_size()); 438 } 439 440 // [flat.map.access], element access 441 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __x) 442 requires is_constructible_v<mapped_type> 443 { 444 return try_emplace(__x).first->second; 445 } 446 447 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](key_type&& __x) 448 requires is_constructible_v<mapped_type> 449 { 450 return try_emplace(std::move(__x)).first->second; 451 } 452 453 template <class _Kp> 454 requires(__is_compare_transparent && is_constructible_v<key_type, _Kp> && is_constructible_v<mapped_type> && 455 !is_convertible_v<_Kp &&, const_iterator> && !is_convertible_v<_Kp &&, iterator>) 456 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](_Kp&& __x) { 457 return try_emplace(std::forward<_Kp>(__x)).first->second; 458 } 459 460 _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __x) { 461 auto __it = find(__x); 462 if (__it == end()) { 463 std::__throw_out_of_range("flat_map::at(const key_type&): Key does not exist"); 464 } 465 return __it->second; 466 } 467 468 _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __x) const { 469 auto __it = find(__x); 470 if (__it == end()) { 471 std::__throw_out_of_range("flat_map::at(const key_type&) const: Key does not exist"); 472 } 473 return __it->second; 474 } 475 476 template <class _Kp> 477 requires __is_compare_transparent 478 _LIBCPP_HIDE_FROM_ABI mapped_type& at(const _Kp& __x) { 479 auto __it = find(__x); 480 if (__it == end()) { 481 std::__throw_out_of_range("flat_map::at(const K&): Key does not exist"); 482 } 483 return __it->second; 484 } 485 486 template <class _Kp> 487 requires __is_compare_transparent 488 _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const _Kp& __x) const { 489 auto __it = find(__x); 490 if (__it == end()) { 491 std::__throw_out_of_range("flat_map::at(const K&) const: Key does not exist"); 492 } 493 return __it->second; 494 } 495 496 // [flat.map.modifiers], modifiers 497 template <class... _Args> 498 requires is_constructible_v<pair<key_type, mapped_type>, _Args...> 499 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) { 500 std::pair<key_type, mapped_type> __pair(std::forward<_Args>(__args)...); 501 return __try_emplace(std::move(__pair.first), std::move(__pair.second)); 502 } 503 504 template <class... _Args> 505 requires is_constructible_v<pair<key_type, mapped_type>, _Args...> 506 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __hint, _Args&&... __args) { 507 std::pair<key_type, mapped_type> __pair(std::forward<_Args>(__args)...); 508 return __try_emplace_hint(__hint, std::move(__pair.first), std::move(__pair.second)).first; 509 } 510 511 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return emplace(__x); } 512 513 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __x) { return emplace(std::move(__x)); } 514 515 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, const value_type& __x) { 516 return emplace_hint(__hint, __x); 517 } 518 519 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, value_type&& __x) { 520 return emplace_hint(__hint, std::move(__x)); 521 } 522 523 template <class _PairLike> 524 requires is_constructible_v<pair<key_type, mapped_type>, _PairLike> 525 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(_PairLike&& __x) { 526 return emplace(std::forward<_PairLike>(__x)); 527 } 528 529 template <class _PairLike> 530 requires is_constructible_v<pair<key_type, mapped_type>, _PairLike> 531 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, _PairLike&& __x) { 532 return emplace_hint(__hint, std::forward<_PairLike>(__x)); 533 } 534 535 template <class _InputIterator> 536 requires __has_input_iterator_category<_InputIterator>::value 537 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last) { 538 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) { 539 __reserve(__last - __first); 540 } 541 __append_sort_merge_unique</*WasSorted = */ false>(std::move(__first), std::move(__last)); 542 } 543 544 template <class _InputIterator> 545 requires __has_input_iterator_category<_InputIterator>::value 546 _LIBCPP_HIDE_FROM_ABI void insert(sorted_unique_t, _InputIterator __first, _InputIterator __last) { 547 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) { 548 __reserve(__last - __first); 549 } 550 551 __append_sort_merge_unique</*WasSorted = */ true>(std::move(__first), std::move(__last)); 552 } 553 554 template <_ContainerCompatibleRange<value_type> _Range> 555 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) { 556 if constexpr (ranges::sized_range<_Range>) { 557 __reserve(ranges::size(__range)); 558 } 559 560 __append_sort_merge_unique</*WasSorted = */ false>(ranges::begin(__range), ranges::end(__range)); 561 } 562 563 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); } 564 565 _LIBCPP_HIDE_FROM_ABI void insert(sorted_unique_t, initializer_list<value_type> __il) { 566 insert(sorted_unique, __il.begin(), __il.end()); 567 } 568 569 _LIBCPP_HIDE_FROM_ABI containers extract() && { 570 auto __guard = std::__make_scope_guard([&]() noexcept { clear() /* noexcept */; }); 571 auto __ret = std::move(__containers_); 572 return __ret; 573 } 574 575 _LIBCPP_HIDE_FROM_ABI void replace(key_container_type&& __key_cont, mapped_container_type&& __mapped_cont) { 576 _LIBCPP_ASSERT_VALID_INPUT_RANGE( 577 __key_cont.size() == __mapped_cont.size(), "flat_map keys and mapped containers have different size"); 578 579 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT( 580 __is_sorted_and_unique(__key_cont), "Either the key container is not sorted or it contains duplicates"); 581 auto __guard = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; }); 582 __containers_.keys = std::move(__key_cont); 583 __containers_.values = std::move(__mapped_cont); 584 __guard.__complete(); 585 } 586 587 template <class... _Args> 588 requires is_constructible_v<mapped_type, _Args...> 589 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(const key_type& __key, _Args&&... __args) { 590 return __try_emplace(__key, std::forward<_Args>(__args)...); 591 } 592 593 template <class... _Args> 594 requires is_constructible_v<mapped_type, _Args...> 595 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(key_type&& __key, _Args&&... __args) { 596 return __try_emplace(std::move(__key), std::forward<_Args>(__args)...); 597 } 598 599 template <class _Kp, class... _Args> 600 requires(__is_compare_transparent && is_constructible_v<key_type, _Kp> && 601 is_constructible_v<mapped_type, _Args...> && !is_convertible_v<_Kp &&, const_iterator> && 602 !is_convertible_v<_Kp &&, iterator>) 603 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(_Kp&& __key, _Args&&... __args) { 604 return __try_emplace(std::forward<_Kp>(__key), std::forward<_Args>(__args)...); 605 } 606 607 template <class... _Args> 608 requires is_constructible_v<mapped_type, _Args...> 609 _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __hint, const key_type& __key, _Args&&... __args) { 610 return __try_emplace_hint(__hint, __key, std::forward<_Args>(__args)...).first; 611 } 612 613 template <class... _Args> 614 requires is_constructible_v<mapped_type, _Args...> 615 _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __hint, key_type&& __key, _Args&&... __args) { 616 return __try_emplace_hint(__hint, std::move(__key), std::forward<_Args>(__args)...).first; 617 } 618 619 template <class _Kp, class... _Args> 620 requires __is_compare_transparent && is_constructible_v<key_type, _Kp> && is_constructible_v<mapped_type, _Args...> 621 _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __hint, _Kp&& __key, _Args&&... __args) { 622 return __try_emplace_hint(__hint, std::forward<_Kp>(__key), std::forward<_Args>(__args)...).first; 623 } 624 625 template <class _Mapped> 626 requires is_assignable_v<mapped_type&, _Mapped> && is_constructible_v<mapped_type, _Mapped> 627 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(const key_type& __key, _Mapped&& __obj) { 628 return __insert_or_assign(__key, std::forward<_Mapped>(__obj)); 629 } 630 631 template <class _Mapped> 632 requires is_assignable_v<mapped_type&, _Mapped> && is_constructible_v<mapped_type, _Mapped> 633 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(key_type&& __key, _Mapped&& __obj) { 634 return __insert_or_assign(std::move(__key), std::forward<_Mapped>(__obj)); 635 } 636 637 template <class _Kp, class _Mapped> 638 requires __is_compare_transparent && is_constructible_v<key_type, _Kp> && is_assignable_v<mapped_type&, _Mapped> && 639 is_constructible_v<mapped_type, _Mapped> 640 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(_Kp&& __key, _Mapped&& __obj) { 641 return __insert_or_assign(std::forward<_Kp>(__key), std::forward<_Mapped>(__obj)); 642 } 643 644 template <class _Mapped> 645 requires is_assignable_v<mapped_type&, _Mapped> && is_constructible_v<mapped_type, _Mapped> 646 _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __hint, const key_type& __key, _Mapped&& __obj) { 647 return __insert_or_assign(__hint, __key, std::forward<_Mapped>(__obj)); 648 } 649 650 template <class _Mapped> 651 requires is_assignable_v<mapped_type&, _Mapped> && is_constructible_v<mapped_type, _Mapped> 652 _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __hint, key_type&& __key, _Mapped&& __obj) { 653 return __insert_or_assign(__hint, std::move(__key), std::forward<_Mapped>(__obj)); 654 } 655 656 template <class _Kp, class _Mapped> 657 requires __is_compare_transparent && is_constructible_v<key_type, _Kp> && is_assignable_v<mapped_type&, _Mapped> && 658 is_constructible_v<mapped_type, _Mapped> 659 _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __hint, _Kp&& __key, _Mapped&& __obj) { 660 return __insert_or_assign(__hint, std::forward<_Kp>(__key), std::forward<_Mapped>(__obj)); 661 } 662 663 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __position) { 664 return __erase(__position.__key_iter_, __position.__mapped_iter_); 665 } 666 667 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __position) { 668 return __erase(__position.__key_iter_, __position.__mapped_iter_); 669 } 670 671 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __x) { 672 auto __iter = find(__x); 673 if (__iter != end()) { 674 erase(__iter); 675 return 1; 676 } 677 return 0; 678 } 679 680 template <class _Kp> 681 requires(__is_compare_transparent && !is_convertible_v<_Kp &&, iterator> && 682 !is_convertible_v<_Kp &&, const_iterator>) 683 _LIBCPP_HIDE_FROM_ABI size_type erase(_Kp&& __x) { 684 auto [__first, __last] = equal_range(__x); 685 auto __res = __last - __first; 686 erase(__first, __last); 687 return __res; 688 } 689 690 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) { 691 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; }); 692 auto __key_it = __containers_.keys.erase(__first.__key_iter_, __last.__key_iter_); 693 auto __mapped_it = __containers_.values.erase(__first.__mapped_iter_, __last.__mapped_iter_); 694 __on_failure.__complete(); 695 return iterator(std::move(__key_it), std::move(__mapped_it)); 696 } 697 698 _LIBCPP_HIDE_FROM_ABI void swap(flat_map& __y) noexcept { 699 // warning: The spec has unconditional noexcept, which means that 700 // if any of the following functions throw an exception, 701 // std::terminate will be called. 702 // This is discussed in P2767, which hasn't been voted on yet. 703 ranges::swap(__compare_, __y.__compare_); 704 ranges::swap(__containers_.keys, __y.__containers_.keys); 705 ranges::swap(__containers_.values, __y.__containers_.values); 706 } 707 708 _LIBCPP_HIDE_FROM_ABI void clear() noexcept { 709 __containers_.keys.clear(); 710 __containers_.values.clear(); 711 } 712 713 // observers 714 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __compare_; } 715 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return value_compare(__compare_); } 716 717 _LIBCPP_HIDE_FROM_ABI const key_container_type& keys() const noexcept { return __containers_.keys; } 718 _LIBCPP_HIDE_FROM_ABI const mapped_container_type& values() const noexcept { return __containers_.values; } 719 720 // map operations 721 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __x) { return __find_impl(*this, __x); } 722 723 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __x) const { return __find_impl(*this, __x); } 724 725 template <class _Kp> 726 requires __is_compare_transparent 727 _LIBCPP_HIDE_FROM_ABI iterator find(const _Kp& __x) { 728 return __find_impl(*this, __x); 729 } 730 731 template <class _Kp> 732 requires __is_compare_transparent 733 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _Kp& __x) const { 734 return __find_impl(*this, __x); 735 } 736 737 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __x) const { return contains(__x) ? 1 : 0; } 738 739 template <class _Kp> 740 requires __is_compare_transparent 741 _LIBCPP_HIDE_FROM_ABI size_type count(const _Kp& __x) const { 742 return contains(__x) ? 1 : 0; 743 } 744 745 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __x) const { return find(__x) != end(); } 746 747 template <class _Kp> 748 requires __is_compare_transparent 749 _LIBCPP_HIDE_FROM_ABI bool contains(const _Kp& __x) const { 750 return find(__x) != end(); 751 } 752 753 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __x) { return __lower_bound<iterator>(*this, __x); } 754 755 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __x) const { 756 return __lower_bound<const_iterator>(*this, __x); 757 } 758 759 template <class _Kp> 760 requires __is_compare_transparent 761 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _Kp& __x) { 762 return __lower_bound<iterator>(*this, __x); 763 } 764 765 template <class _Kp> 766 requires __is_compare_transparent 767 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _Kp& __x) const { 768 return __lower_bound<const_iterator>(*this, __x); 769 } 770 771 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __x) { return __upper_bound<iterator>(*this, __x); } 772 773 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __x) const { 774 return __upper_bound<const_iterator>(*this, __x); 775 } 776 777 template <class _Kp> 778 requires __is_compare_transparent 779 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _Kp& __x) { 780 return __upper_bound<iterator>(*this, __x); 781 } 782 783 template <class _Kp> 784 requires __is_compare_transparent 785 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _Kp& __x) const { 786 return __upper_bound<const_iterator>(*this, __x); 787 } 788 789 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __x) { 790 return __equal_range_impl(*this, __x); 791 } 792 793 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __x) const { 794 return __equal_range_impl(*this, __x); 795 } 796 797 template <class _Kp> 798 requires __is_compare_transparent 799 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _Kp& __x) { 800 return __equal_range_impl(*this, __x); 801 } 802 template <class _Kp> 803 requires __is_compare_transparent 804 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _Kp& __x) const { 805 return __equal_range_impl(*this, __x); 806 } 807 808 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const flat_map& __x, const flat_map& __y) { 809 return ranges::equal(__x, __y); 810 } 811 812 friend _LIBCPP_HIDE_FROM_ABI auto operator<=>(const flat_map& __x, const flat_map& __y) { 813 return std::lexicographical_compare_three_way( 814 __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way); 815 } 816 817 friend _LIBCPP_HIDE_FROM_ABI void swap(flat_map& __x, flat_map& __y) noexcept { __x.swap(__y); } 818 819 private: 820 struct __ctor_uses_allocator_tag { 821 explicit _LIBCPP_HIDE_FROM_ABI __ctor_uses_allocator_tag() = default; 822 }; 823 struct __ctor_uses_allocator_empty_tag { 824 explicit _LIBCPP_HIDE_FROM_ABI __ctor_uses_allocator_empty_tag() = default; 825 }; 826 827 template <class _Allocator, class _KeyCont, class _MappedCont, class... _CompArg> 828 requires __allocator_ctor_constraint<_Allocator> 829 _LIBCPP_HIDE_FROM_ABI 830 flat_map(__ctor_uses_allocator_tag, 831 const _Allocator& __alloc, 832 _KeyCont&& __key_cont, 833 _MappedCont&& __mapped_cont, 834 _CompArg&&... __comp) 835 : __containers_{.keys = std::make_obj_using_allocator<key_container_type>( 836 __alloc, std::forward<_KeyCont>(__key_cont)), 837 .values = std::make_obj_using_allocator<mapped_container_type>( 838 __alloc, std::forward<_MappedCont>(__mapped_cont))}, 839 __compare_(std::forward<_CompArg>(__comp)...) {} 840 841 template <class _Allocator, class... _CompArg> 842 requires __allocator_ctor_constraint<_Allocator> 843 _LIBCPP_HIDE_FROM_ABI flat_map(__ctor_uses_allocator_empty_tag, const _Allocator& __alloc, _CompArg&&... __comp) 844 : __containers_{.keys = std::make_obj_using_allocator<key_container_type>(__alloc), 845 .values = std::make_obj_using_allocator<mapped_container_type>(__alloc)}, 846 __compare_(std::forward<_CompArg>(__comp)...) {} 847 848 _LIBCPP_HIDE_FROM_ABI bool __is_sorted_and_unique(auto&& __key_container) const { 849 auto __greater_or_equal_to = [this](const auto& __x, const auto& __y) { return !__compare_(__x, __y); }; 850 return ranges::adjacent_find(__key_container, __greater_or_equal_to) == ranges::end(__key_container); 851 } 852 853 // This function is only used in constructors. So there is not exception handling in this function. 854 // If the function exits via an exception, there will be no flat_map object constructed, thus, there 855 // is no invariant state to preserve 856 _LIBCPP_HIDE_FROM_ABI void __sort_and_unique() { 857 auto __zv = ranges::views::zip(__containers_.keys, __containers_.values); 858 ranges::sort(__zv, __compare_, [](const auto& __p) -> decltype(auto) { return std::get<0>(__p); }); 859 auto __dup_start = ranges::unique(__zv, __key_equiv(__compare_)).begin(); 860 auto __dist = ranges::distance(__zv.begin(), __dup_start); 861 __containers_.keys.erase(__containers_.keys.begin() + __dist, __containers_.keys.end()); 862 __containers_.values.erase(__containers_.values.begin() + __dist, __containers_.values.end()); 863 } 864 865 template <bool _WasSorted, class _InputIterator, class _Sentinel> 866 _LIBCPP_HIDE_FROM_ABI void __append_sort_merge_unique(_InputIterator __first, _Sentinel __last) { 867 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; }); 868 size_t __num_of_appended = __flat_map_utils::__append(*this, std::move(__first), std::move(__last)); 869 if (__num_of_appended != 0) { 870 auto __zv = ranges::views::zip(__containers_.keys, __containers_.values); 871 auto __append_start_offset = __containers_.keys.size() - __num_of_appended; 872 auto __end = __zv.end(); 873 auto __compare_key = [this](const auto& __p1, const auto& __p2) { 874 return __compare_(std::get<0>(__p1), std::get<0>(__p2)); 875 }; 876 if constexpr (!_WasSorted) { 877 ranges::sort(__zv.begin() + __append_start_offset, __end, __compare_key); 878 } else { 879 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT( 880 __is_sorted_and_unique(__containers_.keys | ranges::views::drop(__append_start_offset)), 881 "Either the key container is not sorted or it contains duplicates"); 882 } 883 ranges::inplace_merge(__zv.begin(), __zv.begin() + __append_start_offset, __end, __compare_key); 884 885 auto __dup_start = ranges::unique(__zv, __key_equiv(__compare_)).begin(); 886 auto __dist = ranges::distance(__zv.begin(), __dup_start); 887 __containers_.keys.erase(__containers_.keys.begin() + __dist, __containers_.keys.end()); 888 __containers_.values.erase(__containers_.values.begin() + __dist, __containers_.values.end()); 889 } 890 __on_failure.__complete(); 891 } 892 893 template <class _Self, class _Kp> 894 _LIBCPP_HIDE_FROM_ABI static auto __find_impl(_Self&& __self, const _Kp& __key) { 895 auto __it = __self.lower_bound(__key); 896 auto __last = __self.end(); 897 if (__it == __last || __self.__compare_(__key, __it->first)) { 898 return __last; 899 } 900 return __it; 901 } 902 903 template <class _Self, class _Kp> 904 _LIBCPP_HIDE_FROM_ABI static auto __key_equal_range(_Self&& __self, const _Kp& __key) { 905 auto __it = ranges::lower_bound(__self.__containers_.keys, __key, __self.__compare_); 906 auto __last = __self.__containers_.keys.end(); 907 if (__it == __last || __self.__compare_(__key, *__it)) { 908 return std::make_pair(__it, __it); 909 } 910 return std::make_pair(__it, std::next(__it)); 911 } 912 913 template <class _Self, class _Kp> 914 _LIBCPP_HIDE_FROM_ABI static auto __equal_range_impl(_Self&& __self, const _Kp& __key) { 915 auto [__key_first, __key_last] = __key_equal_range(__self, __key); 916 917 const auto __make_mapped_iter = [&](const auto& __key_iter) { 918 return __self.__containers_.values.begin() + 919 static_cast<ranges::range_difference_t<mapped_container_type>>( 920 ranges::distance(__self.__containers_.keys.begin(), __key_iter)); 921 }; 922 923 using __iterator_type = ranges::iterator_t<decltype(__self)>; 924 return std::make_pair(__iterator_type(__key_first, __make_mapped_iter(__key_first)), 925 __iterator_type(__key_last, __make_mapped_iter(__key_last))); 926 } 927 928 template <class _Res, class _Self, class _Kp> 929 _LIBCPP_HIDE_FROM_ABI static _Res __lower_bound(_Self&& __self, _Kp& __x) { 930 return __binary_search<_Res>(__self, ranges::lower_bound, __x); 931 } 932 933 template <class _Res, class _Self, class _Kp> 934 _LIBCPP_HIDE_FROM_ABI static _Res __upper_bound(_Self&& __self, _Kp& __x) { 935 return __binary_search<_Res>(__self, ranges::upper_bound, __x); 936 } 937 938 template <class _Res, class _Self, class _Fn, class _Kp> 939 _LIBCPP_HIDE_FROM_ABI static _Res __binary_search(_Self&& __self, _Fn __search_fn, _Kp& __x) { 940 auto __key_iter = __search_fn(__self.__containers_.keys, __x, __self.__compare_); 941 auto __mapped_iter = 942 __self.__containers_.values.begin() + 943 static_cast<ranges::range_difference_t<mapped_container_type>>( 944 ranges::distance(__self.__containers_.keys.begin(), __key_iter)); 945 946 return _Res(std::move(__key_iter), std::move(__mapped_iter)); 947 } 948 949 template <class _KeyArg, class... _MArgs> 950 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __try_emplace(_KeyArg&& __key, _MArgs&&... __mapped_args) { 951 auto __key_it = ranges::lower_bound(__containers_.keys, __key, __compare_); 952 auto __mapped_it = __containers_.values.begin() + ranges::distance(__containers_.keys.begin(), __key_it); 953 954 if (__key_it == __containers_.keys.end() || __compare_(__key, *__key_it)) { 955 return pair<iterator, bool>( 956 __flat_map_utils::__emplace_exact_pos( 957 *this, 958 std::move(__key_it), 959 std::move(__mapped_it), 960 std::forward<_KeyArg>(__key), 961 std::forward<_MArgs>(__mapped_args)...), 962 true); 963 } else { 964 return pair<iterator, bool>(iterator(std::move(__key_it), std::move(__mapped_it)), false); 965 } 966 } 967 968 template <class _Kp> 969 _LIBCPP_HIDE_FROM_ABI bool __is_hint_correct(const_iterator __hint, _Kp&& __key) { 970 if (__hint != cbegin() && !__compare_((__hint - 1)->first, __key)) { 971 return false; 972 } 973 if (__hint != cend() && __compare_(__hint->first, __key)) { 974 return false; 975 } 976 return true; 977 } 978 979 template <class _Kp, class... _Args> 980 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __try_emplace_hint(const_iterator __hint, _Kp&& __key, _Args&&... __args) { 981 if (__is_hint_correct(__hint, __key)) { 982 if (__hint == cend() || __compare_(__key, __hint->first)) { 983 return {__flat_map_utils::__emplace_exact_pos( 984 *this, 985 __hint.__key_iter_, 986 __hint.__mapped_iter_, 987 std::forward<_Kp>(__key), 988 std::forward<_Args>(__args)...), 989 true}; 990 } else { 991 // key equals 992 auto __dist = __hint - cbegin(); 993 return {iterator(__containers_.keys.begin() + __dist, __containers_.values.begin() + __dist), false}; 994 } 995 } else { 996 return __try_emplace(std::forward<_Kp>(__key), std::forward<_Args>(__args)...); 997 } 998 } 999 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() /* noexcept */; }); 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 // _LIBCPP_STD_VER >= 23 1196 1197 _LIBCPP_POP_MACROS 1198 1199 #endif // _LIBCPP___FLAT_MAP_FLAT_MAP_H 1200