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_SET_FLAT_SET_H 11 #define _LIBCPP___FLAT_SET_FLAT_SET_H 12 13 #include <__algorithm/lexicographical_compare_three_way.h> 14 #include <__algorithm/lower_bound.h> 15 #include <__algorithm/min.h> 16 #include <__algorithm/ranges_adjacent_find.h> 17 #include <__algorithm/ranges_equal.h> 18 #include <__algorithm/ranges_inplace_merge.h> 19 #include <__algorithm/ranges_sort.h> 20 #include <__algorithm/ranges_unique.h> 21 #include <__algorithm/remove_if.h> 22 #include <__algorithm/upper_bound.h> 23 #include <__assert> 24 #include <__compare/synth_three_way.h> 25 #include <__concepts/swappable.h> 26 #include <__config> 27 #include <__cstddef/ptrdiff_t.h> 28 #include <__flat_map/sorted_unique.h> 29 #include <__flat_set/ra_iterator.h> 30 #include <__flat_set/utils.h> 31 #include <__functional/invoke.h> 32 #include <__functional/is_transparent.h> 33 #include <__functional/operations.h> 34 #include <__fwd/vector.h> 35 #include <__iterator/concepts.h> 36 #include <__iterator/distance.h> 37 #include <__iterator/iterator_traits.h> 38 #include <__iterator/next.h> 39 #include <__iterator/prev.h> 40 #include <__iterator/ranges_iterator_traits.h> 41 #include <__iterator/reverse_iterator.h> 42 #include <__memory/allocator_traits.h> 43 #include <__memory/uses_allocator.h> 44 #include <__memory/uses_allocator_construction.h> 45 #include <__ranges/access.h> 46 #include <__ranges/concepts.h> 47 #include <__ranges/container_compatible_range.h> 48 #include <__ranges/drop_view.h> 49 #include <__ranges/from_range.h> 50 #include <__ranges/ref_view.h> 51 #include <__ranges/size.h> 52 #include <__ranges/subrange.h> 53 #include <__type_traits/conjunction.h> 54 #include <__type_traits/container_traits.h> 55 #include <__type_traits/invoke.h> 56 #include <__type_traits/is_allocator.h> 57 #include <__type_traits/is_const.h> 58 #include <__type_traits/is_nothrow_constructible.h> 59 #include <__type_traits/is_same.h> 60 #include <__type_traits/remove_reference.h> 61 #include <__utility/as_const.h> 62 #include <__utility/exception_guard.h> 63 #include <__utility/move.h> 64 #include <__utility/pair.h> 65 #include <__utility/scope_guard.h> 66 #include <__vector/vector.h> 67 #include <initializer_list> 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, class _Compare = less<_Key>, class _KeyContainer = vector<_Key>> 81 class flat_set { 82 template <class, class, class> 83 friend class flat_set; 84 85 friend __flat_set_utils; 86 87 static_assert(is_same_v<_Key, typename _KeyContainer::value_type>); 88 static_assert(!is_same_v<_KeyContainer, std::vector<bool>>, "vector<bool> is not a sequence container"); 89 90 using __key_iterator _LIBCPP_NODEBUG = typename _KeyContainer::const_iterator; 91 92 public: 93 // types 94 using key_type = _Key; 95 using value_type = _Key; 96 using key_compare = __type_identity_t<_Compare>; 97 using value_compare = _Compare; 98 using reference = value_type&; 99 using const_reference = const value_type&; 100 using size_type = typename _KeyContainer::size_type; 101 using difference_type = typename _KeyContainer::difference_type; 102 using iterator = __ra_iterator<flat_set, typename _KeyContainer::const_iterator>; 103 using const_iterator = iterator; 104 using reverse_iterator = std::reverse_iterator<iterator>; 105 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 106 using container_type = _KeyContainer; 107 108 public: 109 // [flat.set.cons], construct/copy/destroy 110 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set()111 flat_set() noexcept(is_nothrow_default_constructible_v<_KeyContainer> && is_nothrow_default_constructible_v<_Compare>) 112 : __keys_(), __compare_() {} 113 114 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(const flat_set&) = default; 115 flat_set(flat_set && __other)116 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(flat_set&& __other) noexcept( 117 is_nothrow_move_constructible_v<_KeyContainer> && is_nothrow_move_constructible_v<_Compare>) 118 # if _LIBCPP_HAS_EXCEPTIONS 119 try 120 # endif // _LIBCPP_HAS_EXCEPTIONS 121 : __keys_(std::move(__other.__keys_)), __compare_(std::move(__other.__compare_)) { 122 __other.clear(); 123 # if _LIBCPP_HAS_EXCEPTIONS 124 } catch (...) { 125 __other.clear(); 126 // gcc does not like the `throw` keyword in a conditionally noexcept function 127 if constexpr (!(is_nothrow_move_constructible_v<_KeyContainer> && is_nothrow_move_constructible_v<_Compare>)) { 128 throw; 129 } 130 # endif // _LIBCPP_HAS_EXCEPTIONS 131 } 132 flat_set(const key_compare & __comp)133 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit flat_set(const key_compare& __comp) 134 : __keys_(), __compare_(__comp) {} 135 136 _LIBCPP_HIDE_FROM_ABI 137 _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit flat_set(container_type __keys, const key_compare& __comp = key_compare()) __keys_(std::move (__keys))138 : __keys_(std::move(__keys)), __compare_(__comp) { 139 __sort_and_unique(); 140 } 141 142 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 143 flat_set(sorted_unique_t, container_type __keys, const key_compare& __comp = key_compare()) __keys_(std::move (__keys))144 : __keys_(std::move(__keys)), __compare_(__comp) { 145 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT( 146 __is_sorted_and_unique(__keys_), "Either the key container is not sorted or it contains duplicates"); 147 } 148 149 template <class _InputIterator> 150 requires __has_input_iterator_category<_InputIterator>::value 151 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 152 flat_set(_InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare()) __keys_()153 : __keys_(), __compare_(__comp) { 154 insert(__first, __last); 155 } 156 157 template <class _InputIterator> 158 requires __has_input_iterator_category<_InputIterator>::value 159 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 160 flat_set(sorted_unique_t, _InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare()) __keys_(__first,__last)161 : __keys_(__first, __last), __compare_(__comp) { 162 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT( 163 __is_sorted_and_unique(__keys_), "Either the key container is not sorted or it contains duplicates"); 164 } 165 166 template <_ContainerCompatibleRange<value_type> _Range> flat_set(from_range_t,_Range && __rg)167 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(from_range_t, _Range&& __rg) 168 : flat_set(from_range, std::forward<_Range>(__rg), key_compare()) {} 169 170 template <_ContainerCompatibleRange<value_type> _Range> flat_set(from_range_t,_Range && __rg,const key_compare & __comp)171 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(from_range_t, _Range&& __rg, const key_compare& __comp) 172 : flat_set(__comp) { 173 insert_range(std::forward<_Range>(__rg)); 174 } 175 176 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 177 flat_set(initializer_list<value_type> __il, const key_compare& __comp = key_compare()) 178 : flat_set(__il.begin(), __il.end(), __comp) {} 179 180 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 181 flat_set(sorted_unique_t, initializer_list<value_type> __il, const key_compare& __comp = key_compare()) 182 : flat_set(sorted_unique, __il.begin(), __il.end(), __comp) {} 183 184 template <class _Allocator> 185 requires uses_allocator<container_type, _Allocator>::value flat_set(const _Allocator & __alloc)186 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit flat_set(const _Allocator& __alloc) 187 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_() {} 188 189 template <class _Allocator> 190 requires uses_allocator<container_type, _Allocator>::value flat_set(const key_compare & __comp,const _Allocator & __alloc)191 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(const key_compare& __comp, const _Allocator& __alloc) 192 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_(__comp) {} 193 194 template <class _Allocator> 195 requires uses_allocator<container_type, _Allocator>::value flat_set(const container_type & __keys,const _Allocator & __alloc)196 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(const container_type& __keys, const _Allocator& __alloc) 197 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __keys)), __compare_() { 198 __sort_and_unique(); 199 } 200 201 template <class _Allocator> 202 requires uses_allocator<container_type, _Allocator>::value 203 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(const container_type & __keys,const key_compare & __comp,const _Allocator & __alloc)204 flat_set(const container_type& __keys, const key_compare& __comp, const _Allocator& __alloc) 205 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __keys)), __compare_(__comp) { 206 __sort_and_unique(); 207 } 208 209 template <class _Allocator> 210 requires uses_allocator<container_type, _Allocator>::value 211 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(sorted_unique_t,const container_type & __keys,const _Allocator & __alloc)212 flat_set(sorted_unique_t, const container_type& __keys, const _Allocator& __alloc) 213 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __keys)), __compare_() { 214 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT( 215 __is_sorted_and_unique(__keys_), "Either the key container is not sorted or it contains duplicates"); 216 } 217 218 template <class _Allocator> 219 requires uses_allocator<container_type, _Allocator>::value 220 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(sorted_unique_t,const container_type & __keys,const key_compare & __comp,const _Allocator & __alloc)221 flat_set(sorted_unique_t, const container_type& __keys, const key_compare& __comp, const _Allocator& __alloc) 222 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __keys)), __compare_(__comp) { 223 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT( 224 __is_sorted_and_unique(__keys_), "Either the key container is not sorted or it contains duplicates"); 225 } 226 227 template <class _Allocator> 228 requires uses_allocator<container_type, _Allocator>::value flat_set(const flat_set & __other,const _Allocator & __alloc)229 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(const flat_set& __other, const _Allocator& __alloc) 230 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __other.__keys_)), 231 __compare_(__other.__compare_) {} 232 233 template <class _Allocator> 234 requires uses_allocator<container_type, _Allocator>::value flat_set(flat_set && __other,const _Allocator & __alloc)235 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(flat_set&& __other, const _Allocator& __alloc) 236 # if _LIBCPP_HAS_EXCEPTIONS 237 try 238 # endif // _LIBCPP_HAS_EXCEPTIONS 239 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, std::move(__other.__keys_))), 240 __compare_(std::move(__other.__compare_)) { 241 __other.clear(); 242 # if _LIBCPP_HAS_EXCEPTIONS 243 } catch (...) { 244 __other.clear(); 245 throw; 246 # endif // _LIBCPP_HAS_EXCEPTIONS 247 } 248 249 template <class _InputIterator, class _Allocator> requires(__has_input_iterator_category<_InputIterator>::value && uses_allocator<container_type,_Allocator>::value)250 requires(__has_input_iterator_category<_InputIterator>::value && uses_allocator<container_type, _Allocator>::value) 251 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 252 flat_set(_InputIterator __first, _InputIterator __last, const _Allocator& __alloc) 253 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_() { 254 insert(__first, __last); 255 } 256 257 template <class _InputIterator, class _Allocator> requires(__has_input_iterator_category<_InputIterator>::value && uses_allocator<container_type,_Allocator>::value)258 requires(__has_input_iterator_category<_InputIterator>::value && uses_allocator<container_type, _Allocator>::value) 259 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 260 flat_set(_InputIterator __first, _InputIterator __last, const key_compare& __comp, const _Allocator& __alloc) 261 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_(__comp) { 262 insert(__first, __last); 263 } 264 265 template <class _InputIterator, class _Allocator> requires(__has_input_iterator_category<_InputIterator>::value && uses_allocator<container_type,_Allocator>::value)266 requires(__has_input_iterator_category<_InputIterator>::value && uses_allocator<container_type, _Allocator>::value) 267 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 268 flat_set(sorted_unique_t, _InputIterator __first, _InputIterator __last, const _Allocator& __alloc) 269 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __first, __last)), __compare_() { 270 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT( 271 __is_sorted_and_unique(__keys_), "Either the key container is not sorted or it contains duplicates"); 272 } 273 274 template <class _InputIterator, class _Allocator> requires(__has_input_iterator_category<_InputIterator>::value && uses_allocator<container_type,_Allocator>::value)275 requires(__has_input_iterator_category<_InputIterator>::value && uses_allocator<container_type, _Allocator>::value) 276 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set( 277 sorted_unique_t, 278 _InputIterator __first, 279 _InputIterator __last, 280 const key_compare& __comp, 281 const _Allocator& __alloc) 282 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __first, __last)), __compare_(__comp) { 283 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT( 284 __is_sorted_and_unique(__keys_), "Either the key container is not sorted or it contains duplicates"); 285 } 286 287 template <_ContainerCompatibleRange<value_type> _Range, class _Allocator> 288 requires uses_allocator<container_type, _Allocator>::value flat_set(from_range_t,_Range && __rg,const _Allocator & __alloc)289 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(from_range_t, _Range&& __rg, const _Allocator& __alloc) 290 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_() { 291 insert_range(std::forward<_Range>(__rg)); 292 } 293 294 template <_ContainerCompatibleRange<value_type> _Range, class _Allocator> 295 requires uses_allocator<container_type, _Allocator>::value 296 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(from_range_t,_Range && __rg,const key_compare & __comp,const _Allocator & __alloc)297 flat_set(from_range_t, _Range&& __rg, const key_compare& __comp, const _Allocator& __alloc) 298 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_(__comp) { 299 insert_range(std::forward<_Range>(__rg)); 300 } 301 302 template <class _Allocator> 303 requires uses_allocator<container_type, _Allocator>::value 304 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(initializer_list<value_type> __il,const _Allocator & __alloc)305 flat_set(initializer_list<value_type> __il, const _Allocator& __alloc) 306 : flat_set(__il.begin(), __il.end(), __alloc) {} 307 308 template <class _Allocator> 309 requires uses_allocator<container_type, _Allocator>::value 310 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(initializer_list<value_type> __il,const key_compare & __comp,const _Allocator & __alloc)311 flat_set(initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc) 312 : flat_set(__il.begin(), __il.end(), __comp, __alloc) {} 313 314 template <class _Allocator> 315 requires uses_allocator<container_type, _Allocator>::value 316 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(sorted_unique_t,initializer_list<value_type> __il,const _Allocator & __alloc)317 flat_set(sorted_unique_t, initializer_list<value_type> __il, const _Allocator& __alloc) 318 : flat_set(sorted_unique, __il.begin(), __il.end(), __alloc) {} 319 320 template <class _Allocator> 321 requires uses_allocator<container_type, _Allocator>::value 322 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(sorted_unique_t,initializer_list<value_type> __il,const key_compare & __comp,const _Allocator & __alloc)323 flat_set(sorted_unique_t, initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc) 324 : flat_set(sorted_unique, __il.begin(), __il.end(), __comp, __alloc) {} 325 326 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set& operator=(initializer_list<value_type> __il) { 327 clear(); 328 insert(__il); 329 return *this; 330 } 331 332 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set& operator=(const flat_set&) = default; 333 noexcept(is_nothrow_move_assignable_v<_KeyContainer> && is_nothrow_move_assignable_v<_Compare>)334 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set& operator=(flat_set&& __other) noexcept( 335 is_nothrow_move_assignable_v<_KeyContainer> && is_nothrow_move_assignable_v<_Compare>) { 336 // No matter what happens, we always want to clear the other container before returning 337 // since we moved from it 338 auto __clear_other_guard = std::__make_scope_guard([&]() noexcept { __other.clear() /* noexcept */; }); 339 { 340 // If an exception is thrown, we have no choice but to clear *this to preserve invariants 341 auto __on_exception = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; }); 342 __keys_ = std::move(__other.__keys_); 343 __compare_ = std::move(__other.__compare_); 344 __on_exception.__complete(); 345 } 346 return *this; 347 } 348 349 // iterators begin()350 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator begin() noexcept { 351 return iterator(std::as_const(__keys_).begin()); 352 } begin()353 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator begin() const noexcept { 354 return const_iterator(__keys_.begin()); 355 } end()356 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator end() noexcept { 357 return iterator(std::as_const(__keys_).end()); 358 } end()359 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator end() const noexcept { 360 return const_iterator(__keys_.end()); 361 } 362 rbegin()363 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 reverse_iterator rbegin() noexcept { 364 return reverse_iterator(end()); 365 } rbegin()366 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator rbegin() const noexcept { 367 return const_reverse_iterator(end()); 368 } rend()369 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 reverse_iterator rend() noexcept { 370 return reverse_iterator(begin()); 371 } rend()372 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator rend() const noexcept { 373 return const_reverse_iterator(begin()); 374 } 375 cbegin()376 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator cbegin() const noexcept { return begin(); } cend()377 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator cend() const noexcept { return end(); } crbegin()378 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator crbegin() const noexcept { 379 return const_reverse_iterator(end()); 380 } crend()381 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator crend() const noexcept { 382 return const_reverse_iterator(begin()); 383 } 384 385 // [flat.set.capacity], capacity empty()386 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool empty() const noexcept { 387 return __keys_.empty(); 388 } 389 size()390 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type size() const noexcept { return __keys_.size(); } 391 max_size()392 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type max_size() const noexcept { return __keys_.max_size(); } 393 394 // [flat.set.modifiers], modifiers 395 template <class... _Args> emplace(_Args &&...__args)396 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> emplace(_Args&&... __args) { 397 if constexpr (sizeof...(__args) == 1 && (is_same_v<remove_cvref_t<_Args>, _Key> && ...)) { 398 return __emplace(std::forward<_Args>(__args)...); 399 } else { 400 return __emplace(_Key(std::forward<_Args>(__args)...)); 401 } 402 } 403 404 template <class... _Args> emplace_hint(const_iterator __hint,_Args &&...__args)405 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator emplace_hint(const_iterator __hint, _Args&&... __args) { 406 if constexpr (sizeof...(__args) == 1 && (is_same_v<remove_cvref_t<_Args>, _Key> && ...)) { 407 return __emplace_hint(std::move(__hint), std::forward<_Args>(__args)...); 408 } else { 409 return __emplace_hint(std::move(__hint), _Key(std::forward<_Args>(__args)...)); 410 } 411 } 412 insert(const value_type & __x)413 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> insert(const value_type& __x) { 414 return emplace(__x); 415 } 416 insert(value_type && __x)417 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> insert(value_type&& __x) { 418 return emplace(std::move(__x)); 419 } 420 421 template <class _Kp> requires(__is_transparent_v<_Compare> && is_constructible_v<value_type,_Kp>)422 requires(__is_transparent_v<_Compare> && is_constructible_v<value_type, _Kp>) 423 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> insert(_Kp&& __x) { 424 return __emplace(std::forward<_Kp>(__x)); 425 } insert(const_iterator __hint,const value_type & __x)426 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __hint, const value_type& __x) { 427 return emplace_hint(__hint, __x); 428 } 429 insert(const_iterator __hint,value_type && __x)430 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __hint, value_type&& __x) { 431 return emplace_hint(__hint, std::move(__x)); 432 } 433 434 template <class _Kp> requires(__is_transparent_v<_Compare> && is_constructible_v<value_type,_Kp>)435 requires(__is_transparent_v<_Compare> && is_constructible_v<value_type, _Kp>) 436 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator insert(const_iterator __hint, _Kp&& __x) { 437 return __emplace_hint(__hint, std::forward<_Kp>(__x)); 438 } 439 440 template <class _InputIterator> 441 requires __has_input_iterator_category<_InputIterator>::value insert(_InputIterator __first,_InputIterator __last)442 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(_InputIterator __first, _InputIterator __last) { 443 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) { 444 __reserve(__last - __first); 445 } 446 __append_sort_merge_unique</*WasSorted = */ false>(std::move(__first), std::move(__last)); 447 } 448 449 template <class _InputIterator> 450 requires __has_input_iterator_category<_InputIterator>::value 451 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(sorted_unique_t,_InputIterator __first,_InputIterator __last)452 insert(sorted_unique_t, _InputIterator __first, _InputIterator __last) { 453 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>) { 454 __reserve(__last - __first); 455 } 456 457 __append_sort_merge_unique</*WasSorted = */ true>(std::move(__first), std::move(__last)); 458 } 459 460 template <_ContainerCompatibleRange<value_type> _Range> insert_range(_Range && __range)461 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert_range(_Range&& __range) { 462 if constexpr (ranges::sized_range<_Range>) { 463 __reserve(ranges::size(__range)); 464 } 465 466 __append_sort_merge_unique</*WasSorted = */ false>(std::forward<_Range>(__range)); 467 } 468 insert(initializer_list<value_type> __il)469 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(initializer_list<value_type> __il) { 470 insert(__il.begin(), __il.end()); 471 } 472 insert(sorted_unique_t,initializer_list<value_type> __il)473 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(sorted_unique_t, initializer_list<value_type> __il) { 474 insert(sorted_unique, __il.begin(), __il.end()); 475 } 476 extract()477 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 container_type extract() && { 478 auto __guard = std::__make_scope_guard([&]() noexcept { clear() /* noexcept */; }); 479 auto __ret = std::move(__keys_); 480 return __ret; 481 } 482 replace(container_type && __keys)483 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void replace(container_type&& __keys) { 484 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT( 485 __is_sorted_and_unique(__keys), "Either the key container is not sorted or it contains duplicates"); 486 auto __guard = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; }); 487 __keys_ = std::move(__keys); 488 __guard.__complete(); 489 } 490 erase(iterator __position)491 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator erase(iterator __position) { 492 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; }); 493 auto __key_iter = __keys_.erase(__position.__base()); 494 __on_failure.__complete(); 495 return iterator(__key_iter); 496 } 497 498 // The following overload is the same as the iterator overload 499 // iterator erase(const_iterator __position); 500 erase(const key_type & __x)501 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type erase(const key_type& __x) { 502 auto __iter = find(__x); 503 if (__iter != end()) { 504 erase(__iter); 505 return 1; 506 } 507 return 0; 508 } 509 510 template <class _Kp> 511 requires(__is_transparent_v<_Compare> && !is_convertible_v<_Kp &&, iterator> && 512 !is_convertible_v<_Kp &&, const_iterator>) erase(_Kp && __x)513 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type erase(_Kp&& __x) { 514 auto [__first, __last] = equal_range(__x); 515 auto __res = __last - __first; 516 erase(__first, __last); 517 return __res; 518 } 519 erase(const_iterator __first,const_iterator __last)520 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator erase(const_iterator __first, const_iterator __last) { 521 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; }); 522 auto __key_it = __keys_.erase(__first.__base(), __last.__base()); 523 __on_failure.__complete(); 524 return iterator(std::move(__key_it)); 525 } 526 swap(flat_set & __y)527 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void swap(flat_set& __y) noexcept { 528 // warning: The spec has unconditional noexcept, which means that 529 // if any of the following functions throw an exception, 530 // std::terminate will be called. 531 // This is discussed in P2767, which hasn't been voted on yet. 532 ranges::swap(__compare_, __y.__compare_); 533 ranges::swap(__keys_, __y.__keys_); 534 } 535 clear()536 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void clear() noexcept { __keys_.clear(); } 537 538 // observers key_comp()539 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 key_compare key_comp() const { return __compare_; } value_comp()540 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 value_compare value_comp() const { return __compare_; } 541 542 // set operations find(const key_type & __x)543 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator find(const key_type& __x) { 544 return __find_impl(*this, __x); 545 } 546 find(const key_type & __x)547 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator find(const key_type& __x) const { 548 return __find_impl(*this, __x); 549 } 550 551 template <class _Kp> 552 requires __is_transparent_v<_Compare> find(const _Kp & __x)553 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator find(const _Kp& __x) { 554 return __find_impl(*this, __x); 555 } 556 557 template <class _Kp> 558 requires __is_transparent_v<_Compare> find(const _Kp & __x)559 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator find(const _Kp& __x) const { 560 return __find_impl(*this, __x); 561 } 562 count(const key_type & __x)563 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type count(const key_type& __x) const { 564 return contains(__x) ? 1 : 0; 565 } 566 567 template <class _Kp> 568 requires __is_transparent_v<_Compare> count(const _Kp & __x)569 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type count(const _Kp& __x) const { 570 return contains(__x) ? 1 : 0; 571 } 572 contains(const key_type & __x)573 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool contains(const key_type& __x) const { 574 return find(__x) != end(); 575 } 576 577 template <class _Kp> 578 requires __is_transparent_v<_Compare> contains(const _Kp & __x)579 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool contains(const _Kp& __x) const { 580 return find(__x) != end(); 581 } 582 lower_bound(const key_type & __x)583 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator lower_bound(const key_type& __x) { 584 const auto& __keys = __keys_; 585 return iterator(std::lower_bound(__keys.begin(), __keys.end(), __x, __compare_)); 586 } 587 lower_bound(const key_type & __x)588 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator lower_bound(const key_type& __x) const { 589 return const_iterator(std::lower_bound(__keys_.begin(), __keys_.end(), __x, __compare_)); 590 } 591 592 template <class _Kp> 593 requires __is_transparent_v<_Compare> lower_bound(const _Kp & __x)594 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator lower_bound(const _Kp& __x) { 595 const auto& __keys = __keys_; 596 return iterator(std::lower_bound(__keys.begin(), __keys.end(), __x, __compare_)); 597 } 598 599 template <class _Kp> 600 requires __is_transparent_v<_Compare> lower_bound(const _Kp & __x)601 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator lower_bound(const _Kp& __x) const { 602 return const_iterator(std::lower_bound(__keys_.begin(), __keys_.end(), __x, __compare_)); 603 } 604 upper_bound(const key_type & __x)605 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator upper_bound(const key_type& __x) { 606 const auto& __keys = __keys_; 607 return iterator(std::upper_bound(__keys.begin(), __keys.end(), __x, __compare_)); 608 } 609 upper_bound(const key_type & __x)610 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator upper_bound(const key_type& __x) const { 611 return const_iterator(std::upper_bound(__keys_.begin(), __keys_.end(), __x, __compare_)); 612 } 613 614 template <class _Kp> 615 requires __is_transparent_v<_Compare> upper_bound(const _Kp & __x)616 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator upper_bound(const _Kp& __x) { 617 const auto& __keys = __keys_; 618 return iterator(std::upper_bound(__keys.begin(), __keys.end(), __x, __compare_)); 619 } 620 621 template <class _Kp> 622 requires __is_transparent_v<_Compare> upper_bound(const _Kp & __x)623 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator upper_bound(const _Kp& __x) const { 624 return const_iterator(std::upper_bound(__keys_.begin(), __keys_.end(), __x, __compare_)); 625 } 626 equal_range(const key_type & __x)627 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, iterator> equal_range(const key_type& __x) { 628 return __equal_range_impl(*this, __x); 629 } 630 631 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<const_iterator, const_iterator> equal_range(const key_type & __x)632 equal_range(const key_type& __x) const { 633 return __equal_range_impl(*this, __x); 634 } 635 636 template <class _Kp> 637 requires __is_transparent_v<_Compare> equal_range(const _Kp & __x)638 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, iterator> equal_range(const _Kp& __x) { 639 return __equal_range_impl(*this, __x); 640 } 641 template <class _Kp> 642 requires __is_transparent_v<_Compare> 643 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<const_iterator, const_iterator> equal_range(const _Kp & __x)644 equal_range(const _Kp& __x) const { 645 return __equal_range_impl(*this, __x); 646 } 647 648 friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool operator==(const flat_set& __x, const flat_set& __y) { 649 return ranges::equal(__x, __y); 650 } 651 652 friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 auto 653 operator<=>(const flat_set& __x, const flat_set& __y) { 654 return std::lexicographical_compare_three_way( 655 __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way); 656 } 657 swap(flat_set & __x,flat_set & __y)658 friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void swap(flat_set& __x, flat_set& __y) noexcept { 659 __x.swap(__y); 660 } 661 662 private: __is_sorted_and_unique(auto && __key_container)663 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool __is_sorted_and_unique(auto&& __key_container) const { 664 auto __greater_or_equal_to = [this](const auto& __x, const auto& __y) { return !__compare_(__x, __y); }; 665 return ranges::adjacent_find(__key_container, __greater_or_equal_to) == ranges::end(__key_container); 666 } 667 668 // This function is only used in constructors. So there is not exception handling in this function. 669 // If the function exits via an exception, there will be no flat_set object constructed, thus, there 670 // is no invariant state to preserve __sort_and_unique()671 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __sort_and_unique() { 672 ranges::sort(__keys_, __compare_); 673 auto __dup_start = ranges::unique(__keys_, __key_equiv(__compare_)).begin(); 674 __keys_.erase(__dup_start, __keys_.end()); 675 } 676 677 template <bool _WasSorted, class... _Args> __append_sort_merge_unique(_Args &&...__args)678 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __append_sort_merge_unique(_Args&&... __args) { 679 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; }); 680 size_type __old_size = size(); 681 __flat_set_utils::__append(*this, std::forward<_Args>(__args)...); 682 if (size() != __old_size) { 683 if constexpr (!_WasSorted) { 684 ranges::sort(__keys_.begin() + __old_size, __keys_.end(), __compare_); 685 } else { 686 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(__is_sorted_and_unique(__keys_ | ranges::views::drop(__old_size)), 687 "Either the key container is not sorted or it contains duplicates"); 688 } 689 ranges::inplace_merge(__keys_.begin(), __keys_.begin() + __old_size, __keys_.end(), __compare_); 690 691 auto __dup_start = ranges::unique(__keys_, __key_equiv(__compare_)).begin(); 692 __keys_.erase(__dup_start, __keys_.end()); 693 } 694 __on_failure.__complete(); 695 } 696 697 template <class _Self, class _Kp> __find_impl(_Self && __self,const _Kp & __key)698 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto __find_impl(_Self&& __self, const _Kp& __key) { 699 auto __it = __self.lower_bound(__key); 700 auto __last = __self.end(); 701 if (__it == __last || __self.__compare_(__key, *__it)) { 702 return __last; 703 } 704 return __it; 705 } 706 707 template <class _Self, class _Kp> __equal_range_impl(_Self && __self,const _Kp & __key)708 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto __equal_range_impl(_Self&& __self, const _Kp& __key) { 709 using __iter = _If<is_const_v<__libcpp_remove_reference_t<_Self>>, const_iterator, iterator>; 710 auto __it = std::lower_bound(__self.__keys_.begin(), __self.__keys_.end(), __key, __self.__compare_); 711 auto __last = __self.__keys_.end(); 712 if (__it == __last || __self.__compare_(__key, *__it)) { 713 return std::make_pair(__iter(__it), __iter(__it)); 714 } 715 return std::make_pair(__iter(__it), __iter(std::next(__it))); 716 } 717 718 template <class _Kp> __emplace(_Kp && __key)719 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> __emplace(_Kp&& __key) { 720 auto __it = lower_bound(__key); 721 if (__it == end() || __compare_(__key, *__it)) { 722 return pair<iterator, bool>(__flat_set_utils::__emplace_exact_pos(*this, __it, std::forward<_Kp>(__key)), true); 723 } else { 724 return pair<iterator, bool>(std::move(__it), false); 725 } 726 } 727 728 template <class _Kp> __is_hint_correct(const_iterator __hint,_Kp && __key)729 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool __is_hint_correct(const_iterator __hint, _Kp&& __key) { 730 if (__hint != cbegin() && !__compare_(*std::prev(__hint), __key)) { 731 return false; 732 } 733 if (__hint != cend() && __compare_(*__hint, __key)) { 734 return false; 735 } 736 return true; 737 } 738 739 template <class _Kp> __emplace_hint(const_iterator __hint,_Kp && __key)740 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator __emplace_hint(const_iterator __hint, _Kp&& __key) { 741 if (__is_hint_correct(__hint, __key)) { 742 if (__hint == cend() || __compare_(__key, *__hint)) { 743 return __flat_set_utils::__emplace_exact_pos(*this, __hint, std::forward<_Kp>(__key)); 744 } else { 745 // we already have an equal key 746 return __hint; 747 } 748 } else { 749 return __emplace(std::forward<_Kp>(__key)).first; 750 } 751 } 752 __reserve(size_t __size)753 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __reserve(size_t __size) { 754 if constexpr (__container_traits<_KeyContainer>::__reservable) { 755 __keys_.reserve(__size); 756 } 757 } 758 759 template <class _Key2, class _Compare2, class _KeyContainer2, class _Predicate> 760 friend typename flat_set<_Key2, _Compare2, _KeyContainer2>::size_type _LIBCPP_CONSTEXPR_SINCE_CXX26 761 erase_if(flat_set<_Key2, _Compare2, _KeyContainer2>&, _Predicate); 762 763 _KeyContainer __keys_; 764 _LIBCPP_NO_UNIQUE_ADDRESS key_compare __compare_; 765 766 struct __key_equiv { __key_equiv__key_equiv767 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_equiv(key_compare __c) : __comp_(__c) {} 768 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool operator__key_equiv769 operator()(const_reference __x, const_reference __y) const { 770 return !__comp_(__x, __y) && !__comp_(__y, __x); 771 } 772 key_compare __comp_; 773 }; 774 }; 775 776 template <class _KeyContainer, class _Compare = less<typename _KeyContainer::value_type>> 777 requires(!__is_allocator<_Compare>::value && !__is_allocator<_KeyContainer>::value && 778 is_invocable_v<const _Compare&, 779 const typename _KeyContainer::value_type&, 780 const typename _KeyContainer::value_type&>) 781 flat_set(_KeyContainer, _Compare = _Compare()) -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>; 782 783 template <class _KeyContainer, class _Allocator> 784 requires(uses_allocator_v<_KeyContainer, _Allocator> && !__is_allocator<_KeyContainer>::value) 785 flat_set(_KeyContainer, _Allocator) 786 -> flat_set<typename _KeyContainer::value_type, less<typename _KeyContainer::value_type>, _KeyContainer>; 787 788 template <class _KeyContainer, class _Compare, class _Allocator> 789 requires(!__is_allocator<_Compare>::value && !__is_allocator<_KeyContainer>::value && 790 uses_allocator_v<_KeyContainer, _Allocator> && 791 is_invocable_v<const _Compare&, 792 const typename _KeyContainer::value_type&, 793 const typename _KeyContainer::value_type&>) 794 flat_set(_KeyContainer, _Compare, _Allocator) -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>; 795 796 template <class _KeyContainer, class _Compare = less<typename _KeyContainer::value_type>> 797 requires(!__is_allocator<_Compare>::value && !__is_allocator<_KeyContainer>::value && 798 is_invocable_v<const _Compare&, 799 const typename _KeyContainer::value_type&, 800 const typename _KeyContainer::value_type&>) 801 flat_set(sorted_unique_t, _KeyContainer, _Compare = _Compare()) 802 -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>; 803 804 template <class _KeyContainer, class _Allocator> 805 requires(uses_allocator_v<_KeyContainer, _Allocator> && !__is_allocator<_KeyContainer>::value) 806 flat_set(sorted_unique_t, _KeyContainer, _Allocator) 807 -> flat_set<typename _KeyContainer::value_type, less<typename _KeyContainer::value_type>, _KeyContainer>; 808 809 template <class _KeyContainer, class _Compare, class _Allocator> 810 requires(!__is_allocator<_Compare>::value && !__is_allocator<_KeyContainer>::value && 811 uses_allocator_v<_KeyContainer, _Allocator> && 812 is_invocable_v<const _Compare&, 813 const typename _KeyContainer::value_type&, 814 const typename _KeyContainer::value_type&>) 815 flat_set(sorted_unique_t, _KeyContainer, _Compare, _Allocator) 816 -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>; 817 818 template <class _InputIterator, class _Compare = less<__iter_value_type<_InputIterator>>> 819 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator<_Compare>::value) 820 flat_set(_InputIterator, _InputIterator, _Compare = _Compare()) 821 -> flat_set<__iter_value_type<_InputIterator>, _Compare>; 822 823 template <class _InputIterator, class _Compare = less<__iter_value_type<_InputIterator>>> 824 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator<_Compare>::value) 825 flat_set(sorted_unique_t, _InputIterator, _InputIterator, _Compare = _Compare()) 826 -> flat_set<__iter_value_type<_InputIterator>, _Compare>; 827 828 template <ranges::input_range _Range, 829 class _Compare = less<ranges::range_value_t<_Range>>, 830 class _Allocator = allocator<ranges::range_value_t<_Range>>, 831 class = __enable_if_t<!__is_allocator<_Compare>::value && __is_allocator<_Allocator>::value>> 832 flat_set(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator()) -> flat_set< 833 ranges::range_value_t<_Range>, 834 _Compare, 835 vector<ranges::range_value_t<_Range>, __allocator_traits_rebind_t<_Allocator, ranges::range_value_t<_Range>>>>; 836 837 template <ranges::input_range _Range, class _Allocator, class = __enable_if_t<__is_allocator<_Allocator>::value>> 838 flat_set(from_range_t, _Range&&, _Allocator) -> flat_set< 839 ranges::range_value_t<_Range>, 840 less<ranges::range_value_t<_Range>>, 841 vector<ranges::range_value_t<_Range>, __allocator_traits_rebind_t<_Allocator, ranges::range_value_t<_Range>>>>; 842 843 template <class _Key, class _Compare = less<_Key>> 844 requires(!__is_allocator<_Compare>::value) 845 flat_set(initializer_list<_Key>, _Compare = _Compare()) -> flat_set<_Key, _Compare>; 846 847 template <class _Key, class _Compare = less<_Key>> 848 requires(!__is_allocator<_Compare>::value) 849 flat_set(sorted_unique_t, initializer_list<_Key>, _Compare = _Compare()) -> flat_set<_Key, _Compare>; 850 851 template <class _Key, class _Compare, class _KeyContainer, class _Allocator> 852 struct uses_allocator<flat_set<_Key, _Compare, _KeyContainer>, _Allocator> 853 : bool_constant<uses_allocator_v<_KeyContainer, _Allocator>> {}; 854 855 template <class _Key, class _Compare, class _KeyContainer, class _Predicate> 856 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 typename flat_set<_Key, _Compare, _KeyContainer>::size_type 857 erase_if(flat_set<_Key, _Compare, _KeyContainer>& __flat_set, _Predicate __pred) { 858 auto __guard = std::__make_exception_guard([&] { __flat_set.clear(); }); 859 auto __it = std::remove_if(__flat_set.__keys_.begin(), __flat_set.__keys_.end(), [&](const auto& __e) -> bool { 860 return static_cast<bool>(__pred(__e)); 861 }); 862 auto __res = __flat_set.__keys_.end() - __it; 863 __flat_set.__keys_.erase(__it, __flat_set.__keys_.end()); 864 __guard.__complete(); 865 return __res; 866 } 867 868 _LIBCPP_END_NAMESPACE_STD 869 870 #endif // _LIBCPP_STD_VER >= 23 871 872 _LIBCPP_POP_MACROS 873 874 #endif // _LIBCPP___FLAT_SET_FLAT_SET_H 875