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