881 lines · c
1// -*- C++ -*-2//===----------------------------------------------------------------------===//3//4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5// See https://llvm.org/LICENSE.txt for license information.6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___FLAT_SET_FLAT_SET_H11#define _LIBCPP___FLAT_SET_FLAT_SET_H12 13#include <__algorithm/lexicographical_compare_three_way.h>14#include <__algorithm/lower_bound.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_sort.h>19#include <__algorithm/ranges_unique.h>20#include <__algorithm/remove_if.h>21#include <__algorithm/upper_bound.h>22#include <__assert>23#include <__compare/synth_three_way.h>24#include <__concepts/swappable.h>25#include <__config>26#include <__flat_map/sorted_unique.h>27#include <__flat_set/ra_iterator.h>28#include <__flat_set/utils.h>29#include <__functional/is_transparent.h>30#include <__functional/operations.h>31#include <__fwd/vector.h>32#include <__iterator/concepts.h>33#include <__iterator/iterator_traits.h>34#include <__iterator/next.h>35#include <__iterator/prev.h>36#include <__iterator/reverse_iterator.h>37#include <__memory/allocator_traits.h>38#include <__memory/uses_allocator.h>39#include <__memory/uses_allocator_construction.h>40#include <__ranges/access.h>41#include <__ranges/concepts.h>42#include <__ranges/container_compatible_range.h>43#include <__ranges/drop_view.h>44#include <__ranges/from_range.h>45#include <__ranges/size.h>46#include <__type_traits/container_traits.h>47#include <__type_traits/invoke.h>48#include <__type_traits/is_allocator.h>49#include <__type_traits/is_const.h>50#include <__type_traits/is_nothrow_constructible.h>51#include <__type_traits/is_same.h>52#include <__type_traits/remove_reference.h>53#include <__utility/as_const.h>54#include <__utility/exception_guard.h>55#include <__utility/move.h>56#include <__utility/pair.h>57#include <__utility/scope_guard.h>58#include <__vector/vector.h>59#include <initializer_list>60 61#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)62# pragma GCC system_header63#endif64 65_LIBCPP_PUSH_MACROS66#include <__undef_macros>67 68#if _LIBCPP_STD_VER >= 2369 70_LIBCPP_BEGIN_NAMESPACE_STD71 72template <class _Key, class _Compare = less<_Key>, class _KeyContainer = vector<_Key>>73class flat_set {74 template <class, class, class>75 friend class flat_set;76 77 friend __flat_set_utils;78 79 static_assert(is_same_v<_Key, typename _KeyContainer::value_type>);80 static_assert(!is_same_v<_KeyContainer, std::vector<bool>>, "vector<bool> is not a sequence container");81 82 using __key_iterator _LIBCPP_NODEBUG = typename _KeyContainer::const_iterator;83 84public:85 // types86 using key_type = _Key;87 using value_type = _Key;88 using key_compare = __type_identity_t<_Compare>;89 using value_compare = _Compare;90 using reference = value_type&;91 using const_reference = const value_type&;92 using size_type = typename _KeyContainer::size_type;93 using difference_type = typename _KeyContainer::difference_type;94 using iterator = __ra_iterator<flat_set, typename _KeyContainer::const_iterator>;95 using const_iterator = iterator;96 using reverse_iterator = std::reverse_iterator<iterator>;97 using const_reverse_iterator = std::reverse_iterator<const_iterator>;98 using container_type = _KeyContainer;99 100public:101 // [flat.set.cons], construct/copy/destroy102 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26103 flat_set() noexcept(is_nothrow_default_constructible_v<_KeyContainer> && is_nothrow_default_constructible_v<_Compare>)104 : __keys_(), __compare_() {}105 106 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(const flat_set&) = default;107 108 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(flat_set&& __other) noexcept(109 is_nothrow_move_constructible_v<_KeyContainer> && is_nothrow_move_constructible_v<_Compare>)110# if _LIBCPP_HAS_EXCEPTIONS111 try112# endif // _LIBCPP_HAS_EXCEPTIONS113 : __keys_(std::move(__other.__keys_)), __compare_(std::move(__other.__compare_)) {114 __other.clear();115# if _LIBCPP_HAS_EXCEPTIONS116 } catch (...) {117 __other.clear();118 // gcc does not like the `throw` keyword in a conditionally noexcept function119 if constexpr (!(is_nothrow_move_constructible_v<_KeyContainer> && is_nothrow_move_constructible_v<_Compare>)) {120 throw;121 }122# endif // _LIBCPP_HAS_EXCEPTIONS123 }124 125 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit flat_set(const key_compare& __comp)126 : __keys_(), __compare_(__comp) {}127 128 _LIBCPP_HIDE_FROM_ABI129 _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit flat_set(container_type __keys, const key_compare& __comp = key_compare())130 : __keys_(std::move(__keys)), __compare_(__comp) {131 __sort_and_unique();132 }133 134 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26135 flat_set(sorted_unique_t, container_type __keys, const key_compare& __comp = key_compare())136 : __keys_(std::move(__keys)), __compare_(__comp) {137 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(138 __is_sorted_and_unique(__keys_), "Either the key container is not sorted or it contains duplicates");139 }140 141 template <class _InputIterator>142 requires __has_input_iterator_category<_InputIterator>::value143 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26144 flat_set(_InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare())145 : __keys_(), __compare_(__comp) {146 insert(__first, __last);147 }148 149 template <class _InputIterator>150 requires __has_input_iterator_category<_InputIterator>::value151 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26152 flat_set(sorted_unique_t, _InputIterator __first, _InputIterator __last, const key_compare& __comp = key_compare())153 : __keys_(__first, __last), __compare_(__comp) {154 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(155 __is_sorted_and_unique(__keys_), "Either the key container is not sorted or it contains duplicates");156 }157 158 template <_ContainerCompatibleRange<value_type> _Range>159 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(from_range_t, _Range&& __rg)160 : flat_set(from_range, std::forward<_Range>(__rg), key_compare()) {}161 162 template <_ContainerCompatibleRange<value_type> _Range>163 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(from_range_t, _Range&& __rg, const key_compare& __comp)164 : flat_set(__comp) {165 insert_range(std::forward<_Range>(__rg));166 }167 168 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26169 flat_set(initializer_list<value_type> __il, const key_compare& __comp = key_compare())170 : flat_set(__il.begin(), __il.end(), __comp) {}171 172 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26173 flat_set(sorted_unique_t, initializer_list<value_type> __il, const key_compare& __comp = key_compare())174 : flat_set(sorted_unique, __il.begin(), __il.end(), __comp) {}175 176 template <class _Allocator>177 requires uses_allocator<container_type, _Allocator>::value178 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit flat_set(const _Allocator& __alloc)179 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_() {}180 181 template <class _Allocator>182 requires uses_allocator<container_type, _Allocator>::value183 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(const key_compare& __comp, const _Allocator& __alloc)184 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_(__comp) {}185 186 template <class _Allocator>187 requires uses_allocator<container_type, _Allocator>::value188 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(const container_type& __keys, const _Allocator& __alloc)189 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __keys)), __compare_() {190 __sort_and_unique();191 }192 193 template <class _Allocator>194 requires uses_allocator<container_type, _Allocator>::value195 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26196 flat_set(const container_type& __keys, const key_compare& __comp, const _Allocator& __alloc)197 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __keys)), __compare_(__comp) {198 __sort_and_unique();199 }200 201 template <class _Allocator>202 requires uses_allocator<container_type, _Allocator>::value203 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26204 flat_set(sorted_unique_t, const container_type& __keys, const _Allocator& __alloc)205 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __keys)), __compare_() {206 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(207 __is_sorted_and_unique(__keys_), "Either the key container is not sorted or it contains duplicates");208 }209 210 template <class _Allocator>211 requires uses_allocator<container_type, _Allocator>::value212 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26213 flat_set(sorted_unique_t, const container_type& __keys, const key_compare& __comp, const _Allocator& __alloc)214 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __keys)), __compare_(__comp) {215 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(216 __is_sorted_and_unique(__keys_), "Either the key container is not sorted or it contains duplicates");217 }218 219 template <class _Allocator>220 requires uses_allocator<container_type, _Allocator>::value221 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(const flat_set& __other, const _Allocator& __alloc)222 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __other.__keys_)),223 __compare_(__other.__compare_) {}224 225 template <class _Allocator>226 requires uses_allocator<container_type, _Allocator>::value227 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(flat_set&& __other, const _Allocator& __alloc)228# if _LIBCPP_HAS_EXCEPTIONS229 try230# endif // _LIBCPP_HAS_EXCEPTIONS231 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, std::move(__other.__keys_))),232 __compare_(std::move(__other.__compare_)) {233 __other.clear();234# if _LIBCPP_HAS_EXCEPTIONS235 } catch (...) {236 __other.clear();237 throw;238# endif // _LIBCPP_HAS_EXCEPTIONS239 }240 241 template <class _InputIterator, class _Allocator>242 requires(__has_input_iterator_category<_InputIterator>::value && uses_allocator<container_type, _Allocator>::value)243 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26244 flat_set(_InputIterator __first, _InputIterator __last, const _Allocator& __alloc)245 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_() {246 insert(__first, __last);247 }248 249 template <class _InputIterator, class _Allocator>250 requires(__has_input_iterator_category<_InputIterator>::value && uses_allocator<container_type, _Allocator>::value)251 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26252 flat_set(_InputIterator __first, _InputIterator __last, const key_compare& __comp, const _Allocator& __alloc)253 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_(__comp) {254 insert(__first, __last);255 }256 257 template <class _InputIterator, class _Allocator>258 requires(__has_input_iterator_category<_InputIterator>::value && uses_allocator<container_type, _Allocator>::value)259 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26260 flat_set(sorted_unique_t, _InputIterator __first, _InputIterator __last, const _Allocator& __alloc)261 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __first, __last)), __compare_() {262 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(263 __is_sorted_and_unique(__keys_), "Either the key container is not sorted or it contains duplicates");264 }265 266 template <class _InputIterator, class _Allocator>267 requires(__has_input_iterator_category<_InputIterator>::value && uses_allocator<container_type, _Allocator>::value)268 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(269 sorted_unique_t,270 _InputIterator __first,271 _InputIterator __last,272 const key_compare& __comp,273 const _Allocator& __alloc)274 : __keys_(std::make_obj_using_allocator<container_type>(__alloc, __first, __last)), __compare_(__comp) {275 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(276 __is_sorted_and_unique(__keys_), "Either the key container is not sorted or it contains duplicates");277 }278 279 template <_ContainerCompatibleRange<value_type> _Range, class _Allocator>280 requires uses_allocator<container_type, _Allocator>::value281 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set(from_range_t, _Range&& __rg, const _Allocator& __alloc)282 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_() {283 insert_range(std::forward<_Range>(__rg));284 }285 286 template <_ContainerCompatibleRange<value_type> _Range, class _Allocator>287 requires uses_allocator<container_type, _Allocator>::value288 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26289 flat_set(from_range_t, _Range&& __rg, const key_compare& __comp, const _Allocator& __alloc)290 : __keys_(std::make_obj_using_allocator<container_type>(__alloc)), __compare_(__comp) {291 insert_range(std::forward<_Range>(__rg));292 }293 294 template <class _Allocator>295 requires uses_allocator<container_type, _Allocator>::value296 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26297 flat_set(initializer_list<value_type> __il, const _Allocator& __alloc)298 : flat_set(__il.begin(), __il.end(), __alloc) {}299 300 template <class _Allocator>301 requires uses_allocator<container_type, _Allocator>::value302 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26303 flat_set(initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc)304 : flat_set(__il.begin(), __il.end(), __comp, __alloc) {}305 306 template <class _Allocator>307 requires uses_allocator<container_type, _Allocator>::value308 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26309 flat_set(sorted_unique_t, initializer_list<value_type> __il, const _Allocator& __alloc)310 : flat_set(sorted_unique, __il.begin(), __il.end(), __alloc) {}311 312 template <class _Allocator>313 requires uses_allocator<container_type, _Allocator>::value314 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26315 flat_set(sorted_unique_t, initializer_list<value_type> __il, const key_compare& __comp, const _Allocator& __alloc)316 : flat_set(sorted_unique, __il.begin(), __il.end(), __comp, __alloc) {}317 318 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set& operator=(initializer_list<value_type> __il) {319 clear();320 insert(__il);321 return *this;322 }323 324 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set& operator=(const flat_set&) = default;325 326 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 flat_set& operator=(flat_set&& __other) noexcept(327 is_nothrow_move_assignable_v<_KeyContainer> && is_nothrow_move_assignable_v<_Compare>) {328 // No matter what happens, we always want to clear the other container before returning329 // since we moved from it330 auto __clear_other_guard = std::__make_scope_guard([&]() noexcept { __other.clear() /* noexcept */; });331 {332 // If an exception is thrown, we have no choice but to clear *this to preserve invariants333 auto __on_exception = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });334 __keys_ = std::move(__other.__keys_);335 __compare_ = std::move(__other.__compare_);336 __on_exception.__complete();337 }338 return *this;339 }340 341 // iterators342 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator begin() noexcept {343 return iterator(std::as_const(__keys_).begin());344 }345 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator begin() const noexcept {346 return const_iterator(__keys_.begin());347 }348 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator end() noexcept {349 return iterator(std::as_const(__keys_).end());350 }351 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator end() const noexcept {352 return const_iterator(__keys_.end());353 }354 355 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 reverse_iterator rbegin() noexcept {356 return reverse_iterator(end());357 }358 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator rbegin() const noexcept {359 return const_reverse_iterator(end());360 }361 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 reverse_iterator rend() noexcept {362 return reverse_iterator(begin());363 }364 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator rend() const noexcept {365 return const_reverse_iterator(begin());366 }367 368 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator cbegin() const noexcept {369 return begin();370 }371 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator cend() const noexcept {372 return end();373 }374 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator crbegin() const noexcept {375 return const_reverse_iterator(end());376 }377 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_reverse_iterator crend() const noexcept {378 return const_reverse_iterator(begin());379 }380 381 // [flat.set.capacity], capacity382 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool empty() const noexcept {383 return __keys_.empty();384 }385 386 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type size() const noexcept {387 return __keys_.size();388 }389 390 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type max_size() const noexcept {391 return __keys_.max_size();392 }393 394 // [flat.set.modifiers], modifiers395 template <class... _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>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 413 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> insert(const value_type& __x) {414 return emplace(__x);415 }416 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>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 }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 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>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>::value442 _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>::value451 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void452 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>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 469 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void insert(initializer_list<value_type> __il) {470 insert(__il.begin(), __il.end());471 }472 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 477 [[nodiscard]] _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 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 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 overload499 // iterator erase(const_iterator __position);500 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>)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 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 527 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void swap(flat_set& __y) noexcept {528 // warning: The spec has unconditional noexcept, which means that529 // 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 536 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void clear() noexcept { __keys_.clear(); }537 538 // observers539 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 key_compare key_comp() const { return __compare_; }540 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 value_compare value_comp() const {541 return __compare_;542 }543 544 // set operations545 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator find(const key_type& __x) {546 return __find_impl(*this, __x);547 }548 549 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator find(const key_type& __x) const {550 return __find_impl(*this, __x);551 }552 553 template <class _Kp>554 requires __is_transparent_v<_Compare>555 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator find(const _Kp& __x) {556 return __find_impl(*this, __x);557 }558 559 template <class _Kp>560 requires __is_transparent_v<_Compare>561 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator find(const _Kp& __x) const {562 return __find_impl(*this, __x);563 }564 565 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type count(const key_type& __x) const {566 return contains(__x) ? 1 : 0;567 }568 569 template <class _Kp>570 requires __is_transparent_v<_Compare>571 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 size_type count(const _Kp& __x) const {572 return contains(__x) ? 1 : 0;573 }574 575 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool contains(const key_type& __x) const {576 return find(__x) != end();577 }578 579 template <class _Kp>580 requires __is_transparent_v<_Compare>581 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool contains(const _Kp& __x) const {582 return find(__x) != end();583 }584 585 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator lower_bound(const key_type& __x) {586 const auto& __keys = __keys_;587 return iterator(std::lower_bound(__keys.begin(), __keys.end(), __x, __compare_));588 }589 590 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator591 lower_bound(const key_type& __x) const {592 return const_iterator(std::lower_bound(__keys_.begin(), __keys_.end(), __x, __compare_));593 }594 595 template <class _Kp>596 requires __is_transparent_v<_Compare>597 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator lower_bound(const _Kp& __x) {598 const auto& __keys = __keys_;599 return iterator(std::lower_bound(__keys.begin(), __keys.end(), __x, __compare_));600 }601 602 template <class _Kp>603 requires __is_transparent_v<_Compare>604 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator lower_bound(const _Kp& __x) const {605 return const_iterator(std::lower_bound(__keys_.begin(), __keys_.end(), __x, __compare_));606 }607 608 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator upper_bound(const key_type& __x) {609 const auto& __keys = __keys_;610 return iterator(std::upper_bound(__keys.begin(), __keys.end(), __x, __compare_));611 }612 613 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator614 upper_bound(const key_type& __x) const {615 return const_iterator(std::upper_bound(__keys_.begin(), __keys_.end(), __x, __compare_));616 }617 618 template <class _Kp>619 requires __is_transparent_v<_Compare>620 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator upper_bound(const _Kp& __x) {621 const auto& __keys = __keys_;622 return iterator(std::upper_bound(__keys.begin(), __keys.end(), __x, __compare_));623 }624 625 template <class _Kp>626 requires __is_transparent_v<_Compare>627 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 const_iterator upper_bound(const _Kp& __x) const {628 return const_iterator(std::upper_bound(__keys_.begin(), __keys_.end(), __x, __compare_));629 }630 631 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, iterator>632 equal_range(const key_type& __x) {633 return __equal_range_impl(*this, __x);634 }635 636 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<const_iterator, const_iterator>637 equal_range(const key_type& __x) const {638 return __equal_range_impl(*this, __x);639 }640 641 template <class _Kp>642 requires __is_transparent_v<_Compare>643 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, iterator>644 equal_range(const _Kp& __x) {645 return __equal_range_impl(*this, __x);646 }647 template <class _Kp>648 requires __is_transparent_v<_Compare>649 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<const_iterator, const_iterator>650 equal_range(const _Kp& __x) const {651 return __equal_range_impl(*this, __x);652 }653 654 friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool operator==(const flat_set& __x, const flat_set& __y) {655 return ranges::equal(__x, __y);656 }657 658 friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 auto659 operator<=>(const flat_set& __x, const flat_set& __y) {660 return std::lexicographical_compare_three_way(661 __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);662 }663 664 friend _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void swap(flat_set& __x, flat_set& __y) noexcept {665 __x.swap(__y);666 }667 668private:669 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool __is_sorted_and_unique(auto&& __key_container) const {670 auto __greater_or_equal_to = [this](const auto& __x, const auto& __y) { return !__compare_(__x, __y); };671 return ranges::adjacent_find(__key_container, __greater_or_equal_to) == ranges::end(__key_container);672 }673 674 // This function is only used in constructors. So there is not exception handling in this function.675 // If the function exits via an exception, there will be no flat_set object constructed, thus, there676 // is no invariant state to preserve677 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __sort_and_unique() {678 ranges::sort(__keys_, __compare_);679 auto __dup_start = ranges::unique(__keys_, __key_equiv(__compare_)).begin();680 __keys_.erase(__dup_start, __keys_.end());681 }682 683 template <bool _WasSorted, class... _Args>684 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __append_sort_merge_unique(_Args&&... __args) {685 auto __on_failure = std::__make_exception_guard([&]() noexcept { clear() /* noexcept */; });686 size_type __old_size = size();687 __flat_set_utils::__append(*this, std::forward<_Args>(__args)...);688 if (size() != __old_size) {689 if constexpr (!_WasSorted) {690 ranges::sort(__keys_.begin() + __old_size, __keys_.end(), __compare_);691 } else {692 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(__is_sorted_and_unique(__keys_ | ranges::views::drop(__old_size)),693 "Either the key container is not sorted or it contains duplicates");694 }695 ranges::inplace_merge(__keys_.begin(), __keys_.begin() + __old_size, __keys_.end(), __compare_);696 697 auto __dup_start = ranges::unique(__keys_, __key_equiv(__compare_)).begin();698 __keys_.erase(__dup_start, __keys_.end());699 }700 __on_failure.__complete();701 }702 703 template <class _Self, class _Kp>704 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto __find_impl(_Self&& __self, const _Kp& __key) {705 auto __it = __self.lower_bound(__key);706 auto __last = __self.end();707 if (__it == __last || __self.__compare_(__key, *__it)) {708 return __last;709 }710 return __it;711 }712 713 template <class _Self, class _Kp>714 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto __equal_range_impl(_Self&& __self, const _Kp& __key) {715 using __iter = _If<is_const_v<__libcpp_remove_reference_t<_Self>>, const_iterator, iterator>;716 auto __it = std::lower_bound(__self.__keys_.begin(), __self.__keys_.end(), __key, __self.__compare_);717 auto __last = __self.__keys_.end();718 if (__it == __last || __self.__compare_(__key, *__it)) {719 return std::make_pair(__iter(__it), __iter(__it));720 }721 return std::make_pair(__iter(__it), __iter(std::next(__it)));722 }723 724 template <class _Kp>725 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<iterator, bool> __emplace(_Kp&& __key) {726 auto __it = lower_bound(__key);727 if (__it == end() || __compare_(__key, *__it)) {728 return pair<iterator, bool>(__flat_set_utils::__emplace_exact_pos(*this, __it, std::forward<_Kp>(__key)), true);729 } else {730 return pair<iterator, bool>(std::move(__it), false);731 }732 }733 734 template <class _Kp>735 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool __is_hint_correct(const_iterator __hint, _Kp&& __key) {736 if (__hint != cbegin() && !__compare_(*std::prev(__hint), __key)) {737 return false;738 }739 if (__hint != cend() && __compare_(*__hint, __key)) {740 return false;741 }742 return true;743 }744 745 template <class _Kp>746 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 iterator __emplace_hint(const_iterator __hint, _Kp&& __key) {747 if (__is_hint_correct(__hint, __key)) {748 if (__hint == cend() || __compare_(__key, *__hint)) {749 return __flat_set_utils::__emplace_exact_pos(*this, __hint, std::forward<_Kp>(__key));750 } else {751 // we already have an equal key752 return __hint;753 }754 } else {755 return __emplace(std::forward<_Kp>(__key)).first;756 }757 }758 759 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __reserve(size_t __size) {760 if constexpr (__container_traits<_KeyContainer>::__reservable) {761 __keys_.reserve(__size);762 }763 }764 765 template <class _Key2, class _Compare2, class _KeyContainer2, class _Predicate>766 friend typename flat_set<_Key2, _Compare2, _KeyContainer2>::size_type _LIBCPP_CONSTEXPR_SINCE_CXX26767 erase_if(flat_set<_Key2, _Compare2, _KeyContainer2>&, _Predicate);768 769 _KeyContainer __keys_;770 _LIBCPP_NO_UNIQUE_ADDRESS key_compare __compare_;771 772 struct __key_equiv {773 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_equiv(key_compare __c) : __comp_(__c) {}774 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool775 operator()(const_reference __x, const_reference __y) const {776 return !__comp_(__x, __y) && !__comp_(__y, __x);777 }778 key_compare __comp_;779 };780};781 782template <class _KeyContainer, class _Compare = less<typename _KeyContainer::value_type>>783 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> &&784 is_invocable_v<const _Compare&,785 const typename _KeyContainer::value_type&,786 const typename _KeyContainer::value_type&>)787flat_set(_KeyContainer, _Compare = _Compare()) -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;788 789template <class _KeyContainer, class _Allocator>790 requires(uses_allocator_v<_KeyContainer, _Allocator> && !__is_allocator_v<_KeyContainer>)791flat_set(_KeyContainer, _Allocator)792 -> flat_set<typename _KeyContainer::value_type, less<typename _KeyContainer::value_type>, _KeyContainer>;793 794template <class _KeyContainer, class _Compare, class _Allocator>795 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> &&796 uses_allocator_v<_KeyContainer, _Allocator> &&797 is_invocable_v<const _Compare&,798 const typename _KeyContainer::value_type&,799 const typename _KeyContainer::value_type&>)800flat_set(_KeyContainer, _Compare, _Allocator) -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;801 802template <class _KeyContainer, class _Compare = less<typename _KeyContainer::value_type>>803 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> &&804 is_invocable_v<const _Compare&,805 const typename _KeyContainer::value_type&,806 const typename _KeyContainer::value_type&>)807flat_set(sorted_unique_t, _KeyContainer, _Compare = _Compare())808 -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;809 810template <class _KeyContainer, class _Allocator>811 requires(uses_allocator_v<_KeyContainer, _Allocator> && !__is_allocator_v<_KeyContainer>)812flat_set(sorted_unique_t, _KeyContainer, _Allocator)813 -> flat_set<typename _KeyContainer::value_type, less<typename _KeyContainer::value_type>, _KeyContainer>;814 815template <class _KeyContainer, class _Compare, class _Allocator>816 requires(!__is_allocator_v<_Compare> && !__is_allocator_v<_KeyContainer> &&817 uses_allocator_v<_KeyContainer, _Allocator> &&818 is_invocable_v<const _Compare&,819 const typename _KeyContainer::value_type&,820 const typename _KeyContainer::value_type&>)821flat_set(sorted_unique_t, _KeyContainer, _Compare, _Allocator)822 -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;823 824template <class _InputIterator, class _Compare = less<__iterator_value_type<_InputIterator>>>825 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator_v<_Compare>)826flat_set(_InputIterator, _InputIterator, _Compare = _Compare())827 -> flat_set<__iterator_value_type<_InputIterator>, _Compare>;828 829template <class _InputIterator, class _Compare = less<__iterator_value_type<_InputIterator>>>830 requires(__has_input_iterator_category<_InputIterator>::value && !__is_allocator_v<_Compare>)831flat_set(sorted_unique_t, _InputIterator, _InputIterator, _Compare = _Compare())832 -> flat_set<__iterator_value_type<_InputIterator>, _Compare>;833 834template <ranges::input_range _Range,835 class _Compare = less<ranges::range_value_t<_Range>>,836 class _Allocator = allocator<ranges::range_value_t<_Range>>,837 class = __enable_if_t<!__is_allocator_v<_Compare> && __is_allocator_v<_Allocator>>>838flat_set(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator()) -> flat_set<839 ranges::range_value_t<_Range>,840 _Compare,841 vector<ranges::range_value_t<_Range>, __allocator_traits_rebind_t<_Allocator, ranges::range_value_t<_Range>>>>;842 843template <ranges::input_range _Range, class _Allocator, class = __enable_if_t<__is_allocator_v<_Allocator>>>844flat_set(from_range_t, _Range&&, _Allocator) -> flat_set<845 ranges::range_value_t<_Range>,846 less<ranges::range_value_t<_Range>>,847 vector<ranges::range_value_t<_Range>, __allocator_traits_rebind_t<_Allocator, ranges::range_value_t<_Range>>>>;848 849template <class _Key, class _Compare = less<_Key>>850 requires(!__is_allocator_v<_Compare>)851flat_set(initializer_list<_Key>, _Compare = _Compare()) -> flat_set<_Key, _Compare>;852 853template <class _Key, class _Compare = less<_Key>>854 requires(!__is_allocator_v<_Compare>)855flat_set(sorted_unique_t, initializer_list<_Key>, _Compare = _Compare()) -> flat_set<_Key, _Compare>;856 857template <class _Key, class _Compare, class _KeyContainer, class _Allocator>858struct uses_allocator<flat_set<_Key, _Compare, _KeyContainer>, _Allocator>859 : bool_constant<uses_allocator_v<_KeyContainer, _Allocator>> {};860 861template <class _Key, class _Compare, class _KeyContainer, class _Predicate>862_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 typename flat_set<_Key, _Compare, _KeyContainer>::size_type863erase_if(flat_set<_Key, _Compare, _KeyContainer>& __flat_set, _Predicate __pred) {864 auto __guard = std::__make_exception_guard([&] { __flat_set.clear(); });865 auto __it = std::remove_if(__flat_set.__keys_.begin(), __flat_set.__keys_.end(), [&](const auto& __e) -> bool {866 return static_cast<bool>(__pred(__e));867 });868 auto __res = __flat_set.__keys_.end() - __it;869 __flat_set.__keys_.erase(__it, __flat_set.__keys_.end());870 __guard.__complete();871 return __res;872}873 874_LIBCPP_END_NAMESPACE_STD875 876#endif // _LIBCPP_STD_VER >= 23877 878_LIBCPP_POP_MACROS879 880#endif // _LIBCPP___FLAT_SET_FLAT_SET_H881