1123 lines · c
1//===----------------------------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___VECTOR_VECTOR_BOOL_H10#define _LIBCPP___VECTOR_VECTOR_BOOL_H11 12#include <__algorithm/copy.h>13#include <__algorithm/copy_backward.h>14#include <__algorithm/copy_n.h>15#include <__algorithm/fill_n.h>16#include <__algorithm/iterator_operations.h>17#include <__algorithm/max.h>18#include <__algorithm/rotate.h>19#include <__assert>20#include <__bit_reference>21#include <__config>22#include <__functional/unary_function.h>23#include <__fwd/bit_reference.h> // TODO: This is a workaround for https://llvm.org/PR13181424#include <__fwd/functional.h>25#include <__fwd/vector.h>26#include <__iterator/distance.h>27#include <__iterator/iterator_traits.h>28#include <__iterator/reverse_iterator.h>29#include <__memory/addressof.h>30#include <__memory/allocate_at_least.h>31#include <__memory/allocator.h>32#include <__memory/allocator_traits.h>33#include <__memory/compressed_pair.h>34#include <__memory/construct_at.h>35#include <__memory/noexcept_move_assign_container.h>36#include <__memory/pointer_traits.h>37#include <__memory/swap_allocator.h>38#include <__ranges/access.h>39#include <__ranges/concepts.h>40#include <__ranges/container_compatible_range.h>41#include <__ranges/from_range.h>42#include <__type_traits/enable_if.h>43#include <__type_traits/is_constant_evaluated.h>44#include <__type_traits/is_nothrow_assignable.h>45#include <__type_traits/is_nothrow_constructible.h>46#include <__type_traits/type_identity.h>47#include <__utility/exception_guard.h>48#include <__utility/forward.h>49#include <__utility/move.h>50#include <__utility/swap.h>51#include <climits>52#include <initializer_list>53#include <limits>54#include <stdexcept>55 56// These headers define parts of vectors definition, since they define ADL functions or class specializations.57#include <__vector/comparison.h>58#include <__vector/container_traits.h>59#include <__vector/swap.h>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_LIBCPP_BEGIN_NAMESPACE_STD69 70template <class _Allocator>71struct hash<vector<bool, _Allocator> >;72 73template <class _Allocator>74struct __has_storage_type<vector<bool, _Allocator> > {75 static const bool value = true;76};77 78template <class _Allocator>79class vector<bool, _Allocator> {80public:81 using __self _LIBCPP_NODEBUG = vector;82 using value_type = bool;83 using allocator_type = _Allocator;84 using __alloc_traits _LIBCPP_NODEBUG = allocator_traits<allocator_type>;85 using size_type = typename __alloc_traits::size_type;86 using difference_type = typename __alloc_traits::difference_type;87 using __storage_type _LIBCPP_NODEBUG = size_type;88 using pointer = __bit_iterator<vector, false>;89 using const_pointer = __bit_iterator<vector, true>;90 using iterator = pointer;91 using const_iterator = const_pointer;92 using reverse_iterator = std::reverse_iterator<iterator>;93 using const_reverse_iterator = std::reverse_iterator<const_iterator>;94 95private:96 using __storage_allocator _LIBCPP_NODEBUG = __rebind_alloc<__alloc_traits, __storage_type>;97 using __storage_traits _LIBCPP_NODEBUG = allocator_traits<__storage_allocator>;98 using __storage_pointer _LIBCPP_NODEBUG = typename __storage_traits::pointer;99 using __const_storage_pointer _LIBCPP_NODEBUG = typename __storage_traits::const_pointer;100 101 __storage_pointer __begin_;102 size_type __size_;103 _LIBCPP_COMPRESSED_PAIR(size_type, __cap_, __storage_allocator, __alloc_);104 105public:106 using reference = __bit_reference<vector>;107#ifdef _LIBCPP_ABI_BITSET_VECTOR_BOOL_CONST_SUBSCRIPT_RETURN_BOOL108 using const_reference = bool;109#else110 using const_reference = __bit_const_reference<vector>;111#endif112 113private:114 static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);115 116 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static size_type117 __internal_cap_to_external(size_type __n) _NOEXCEPT {118 return __n * __bits_per_word;119 }120 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static size_type121 __external_cap_to_internal(size_type __n) _NOEXCEPT {122 return __n > 0 ? (__n - 1) / __bits_per_word + 1 : size_type(0);123 }124 125public:126 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector()127 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);128 129 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit vector(const allocator_type& __a)130#if _LIBCPP_STD_VER <= 14131 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value);132#else133 _NOEXCEPT;134#endif135 136private:137 class __destroy_vector {138 public:139 _LIBCPP_CONSTEXPR _LIBCPP_HIDE_FROM_ABI __destroy_vector(vector& __vec) : __vec_(__vec) {}140 141 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void operator()() {142 if (__vec_.__begin_ != nullptr)143 __storage_traits::deallocate(__vec_.__alloc_, __vec_.__begin_, __vec_.__cap_);144 }145 146 private:147 vector& __vec_;148 };149 150public:151 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 ~vector() { __destroy_vector (*this)(); }152 153 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit vector(size_type __n);154#if _LIBCPP_STD_VER >= 14155 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit vector(size_type __n, const allocator_type& __a);156#endif157 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(size_type __n, const value_type& __v);158 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20159 vector(size_type __n, const value_type& __v, const allocator_type& __a);160 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>161 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(_InputIterator __first, _InputIterator __last);162 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>163 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20164 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a);165 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>166 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(_ForwardIterator __first, _ForwardIterator __last);167 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>168 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20169 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a);170 171#if _LIBCPP_STD_VER >= 23172 template <_ContainerCompatibleRange<bool> _Range>173 _LIBCPP_HIDE_FROM_ABI constexpr vector(from_range_t, _Range&& __range, const allocator_type& __a = allocator_type())174 : __begin_(nullptr), __size_(0), __cap_(0), __alloc_(static_cast<__storage_allocator>(__a)) {175 if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {176 auto __n = static_cast<size_type>(ranges::distance(__range));177 __init_with_size(ranges::begin(__range), ranges::end(__range), __n);178 179 } else {180 __init_with_sentinel(ranges::begin(__range), ranges::end(__range));181 }182 }183#endif184 185 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(const vector& __v);186 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(const vector& __v, const allocator_type& __a);187 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector& operator=(const vector& __v);188 189#ifndef _LIBCPP_CXX03_LANG190 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(initializer_list<value_type> __il);191 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20192 vector(initializer_list<value_type> __il, const allocator_type& __a);193 194 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector& operator=(initializer_list<value_type> __il) {195 assign(__il.begin(), __il.end());196 return *this;197 }198 199#endif // !_LIBCPP_CXX03_LANG200 201 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(vector&& __v)202#if _LIBCPP_STD_VER >= 17203 noexcept;204#else205 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);206#endif207 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20208 vector(vector&& __v, const __type_identity_t<allocator_type>& __a);209 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector& operator=(vector&& __v)210 _NOEXCEPT_(__noexcept_move_assign_container<_Allocator, __alloc_traits>::value);211 212 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>213 void _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 assign(_InputIterator __first, _InputIterator __last);214 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>215 void _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 assign(_ForwardIterator __first, _ForwardIterator __last);216 217#if _LIBCPP_STD_VER >= 23218 template <_ContainerCompatibleRange<bool> _Range>219 _LIBCPP_HIDE_FROM_ABI constexpr void assign_range(_Range&& __range) {220 if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {221 auto __n = static_cast<size_type>(ranges::distance(__range));222 __assign_with_size(ranges::begin(__range), ranges::end(__range), __n);223 224 } else {225 __assign_with_sentinel(ranges::begin(__range), ranges::end(__range));226 }227 }228#endif229 230 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void assign(size_type __n, const value_type& __x);231 232#ifndef _LIBCPP_CXX03_LANG233 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void assign(initializer_list<value_type> __il) {234 assign(__il.begin(), __il.end());235 }236#endif237 238 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 allocator_type get_allocator() const _NOEXCEPT {239 return allocator_type(this->__alloc_);240 }241 242 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type max_size() const _NOEXCEPT;243 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type capacity() const _NOEXCEPT {244 return __internal_cap_to_external(__cap_);245 }246 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type size() const _NOEXCEPT {247 return __size_;248 }249 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool empty() const _NOEXCEPT {250 return __size_ == 0;251 }252 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void reserve(size_type __n);253 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void shrink_to_fit() _NOEXCEPT;254 255 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator begin() _NOEXCEPT {256 return __make_iter(0);257 }258 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator begin() const _NOEXCEPT {259 return __make_iter(0);260 }261 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator end() _NOEXCEPT {262 return __make_iter(__size_);263 }264 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator end() const _NOEXCEPT {265 return __make_iter(__size_);266 }267 268 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reverse_iterator rbegin() _NOEXCEPT {269 return reverse_iterator(end());270 }271 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reverse_iterator272 rbegin() const _NOEXCEPT {273 return const_reverse_iterator(end());274 }275 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reverse_iterator rend() _NOEXCEPT {276 return reverse_iterator(begin());277 }278 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reverse_iterator rend() const _NOEXCEPT {279 return const_reverse_iterator(begin());280 }281 282 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator cbegin() const _NOEXCEPT {283 return __make_iter(0);284 }285 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator cend() const _NOEXCEPT {286 return __make_iter(__size_);287 }288 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reverse_iterator289 crbegin() const _NOEXCEPT {290 return rbegin();291 }292 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reverse_iterator crend() const _NOEXCEPT {293 return rend();294 }295 296 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference operator[](size_type __n) {297 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__n < size(), "vector<bool>::operator[] index out of bounds");298 return __make_ref(__n);299 }300 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference301 operator[](size_type __n) const {302 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__n < size(), "vector<bool>::operator[] index out of bounds");303 return __make_ref(__n);304 }305 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference at(size_type __n);306 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference at(size_type __n) const;307 308 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference front() {309 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "vector<bool>::front() called on an empty vector");310 return __make_ref(0);311 }312 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference front() const {313 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "vector<bool>::front() called on an empty vector");314 return __make_ref(0);315 }316 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference back() {317 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "vector<bool>::back() called on an empty vector");318 return __make_ref(__size_ - 1);319 }320 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference back() const {321 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "vector<bool>::back() called on an empty vector");322 return __make_ref(__size_ - 1);323 }324 325 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void push_back(const value_type& __x);326#if _LIBCPP_STD_VER >= 14327 template <class... _Args>328# if _LIBCPP_STD_VER >= 17329 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference emplace_back(_Args&&... __args)330# else331 _LIBCPP_HIDE_FROM_ABI void emplace_back(_Args&&... __args)332# endif333 {334 push_back(value_type(std::forward<_Args>(__args)...));335# if _LIBCPP_STD_VER >= 17336 return this->back();337# endif338 }339#endif340 341#if _LIBCPP_STD_VER >= 23342 template <_ContainerCompatibleRange<bool> _Range>343 _LIBCPP_HIDE_FROM_ABI constexpr void append_range(_Range&& __range) {344 insert_range(end(), std::forward<_Range>(__range));345 }346#endif347 348 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void pop_back() {349 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "vector<bool>::pop_back called on an empty vector");350 --__size_;351 }352 353#if _LIBCPP_STD_VER >= 14354 template <class... _Args>355 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator emplace(const_iterator __position, _Args&&... __args) {356 return insert(__position, value_type(std::forward<_Args>(__args)...));357 }358#endif359 360 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator insert(const_iterator __position, const value_type& __x);361 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator362 insert(const_iterator __position, size_type __n, const value_type& __x);363 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>364 iterator _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20365 insert(const_iterator __position, _InputIterator __first, _InputIterator __last);366 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>367 iterator _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20368 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);369 370#if _LIBCPP_STD_VER >= 23371 template <_ContainerCompatibleRange<bool> _Range>372 _LIBCPP_HIDE_FROM_ABI constexpr iterator insert_range(const_iterator __position, _Range&& __range) {373 if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {374 auto __n = static_cast<size_type>(ranges::distance(__range));375 return __insert_with_size(__position, ranges::begin(__range), ranges::end(__range), __n);376 377 } else {378 return __insert_with_sentinel(__position, ranges::begin(__range), ranges::end(__range));379 }380 }381#endif382 383#ifndef _LIBCPP_CXX03_LANG384 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator385 insert(const_iterator __position, initializer_list<value_type> __il) {386 return insert(__position, __il.begin(), __il.end());387 }388#endif389 390 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator erase(const_iterator __position);391 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator erase(const_iterator __first, const_iterator __last);392 393 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void clear() _NOEXCEPT { __size_ = 0; }394 395 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void swap(vector&)396#if _LIBCPP_STD_VER >= 14397 _NOEXCEPT;398#else399 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>);400#endif401 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static void swap(reference __x, reference __y) _NOEXCEPT {402 std::swap(__x, __y);403 }404 405 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void resize(size_type __sz, value_type __x = false);406 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void flip() _NOEXCEPT;407 408 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __invariants() const;409 410private:411 [[__noreturn__]] _LIBCPP_HIDE_FROM_ABI static void __throw_length_error() { std::__throw_length_error("vector"); }412 413 [[__noreturn__]] _LIBCPP_HIDE_FROM_ABI static void __throw_out_of_range() { std::__throw_out_of_range("vector"); }414 415 template <class _InputIterator, class _Sentinel>416 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void417 __init_with_size(_InputIterator __first, _Sentinel __last, size_type __n) {418 auto __guard = std::__make_exception_guard(__destroy_vector(*this));419 420 if (__n > 0) {421 __vallocate(__n);422 __construct_at_end(std::move(__first), std::move(__last), __n);423 }424 425 __guard.__complete();426 }427 428 template <class _InputIterator, class _Sentinel>429 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void430 __init_with_sentinel(_InputIterator __first, _Sentinel __last) {431 auto __guard = std::__make_exception_guard(__destroy_vector(*this));432 433 for (; __first != __last; ++__first)434 push_back(*__first);435 436 __guard.__complete();437 }438 439 template <class _Iterator, class _Sentinel>440 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __assign_with_sentinel(_Iterator __first, _Sentinel __last);441 442 // The `_Iterator` in `*_with_size` functions can be input-only only if called from `*_range` (since C++23).443 // Otherwise, `_Iterator` is a forward iterator.444 445 template <class _Iterator, class _Sentinel>446 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void447 __assign_with_size(_Iterator __first, _Sentinel __last, difference_type __ns);448 449 template <class _InputIterator, class _Sentinel>450 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator451 __insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last);452 453 template <class _Iterator, class _Sentinel>454 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator455 __insert_with_size(const_iterator __position, _Iterator __first, _Sentinel __last, difference_type __n);456 457 // Allocate space for __n objects458 // throws length_error if __n > max_size()459 // throws (probably bad_alloc) if memory run out460 // Precondition: __begin_ == __end_ == __cap_ == nullptr461 // Precondition: __n > 0462 // Postcondition: capacity() >= __n463 // Postcondition: size() == 0464 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __vallocate(size_type __n) {465 if (__n > max_size())466 this->__throw_length_error();467 auto __allocation = std::__allocate_at_least(__alloc_, __external_cap_to_internal(__n));468 __begin_ = __allocation.ptr;469 __size_ = 0;470 __cap_ = __allocation.count;471 if (__libcpp_is_constant_evaluated()) {472 for (size_type __i = 0; __i != __cap_; ++__i)473 std::__construct_at(std::__to_address(__begin_) + __i);474 }475 }476 477 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __vdeallocate() _NOEXCEPT;478 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static size_type __align_it(size_type __new_size) _NOEXCEPT {479 return (__new_size + (__bits_per_word - 1)) & ~((size_type)__bits_per_word - 1);480 }481 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type __recommend(size_type __new_size) const;482 template <class _InputIterator, class _Sentinel>483 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void484 __construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n);485 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference __make_ref(size_type __pos) _NOEXCEPT {486 return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);487 }488 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference __make_ref(size_type __pos) const _NOEXCEPT {489 return __bit_const_reference<vector>(490 __begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);491 }492 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator __make_iter(size_type __pos) _NOEXCEPT {493 return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));494 }495 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator __make_iter(size_type __pos) const _NOEXCEPT {496 return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));497 }498 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT {499 return begin() + (__p - cbegin());500 }501 502 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __copy_assign_alloc(const vector& __v) {503 __copy_assign_alloc(504 __v, integral_constant<bool, __storage_traits::propagate_on_container_copy_assignment::value>());505 }506 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __copy_assign_alloc(const vector& __c, true_type) {507 if (__alloc_ != __c.__alloc_)508 __vdeallocate();509 __alloc_ = __c.__alloc_;510 }511 512 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __copy_assign_alloc(const vector&, false_type) {}513 514 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign(vector& __c, false_type);515 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign(vector& __c, true_type)516 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);517 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign_alloc(vector& __c)518 _NOEXCEPT_(!__storage_traits::propagate_on_container_move_assignment::value ||519 is_nothrow_move_assignable<allocator_type>::value) {520 __move_assign_alloc(521 __c, integral_constant<bool, __storage_traits::propagate_on_container_move_assignment::value>());522 }523 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign_alloc(vector& __c, true_type)524 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {525 __alloc_ = std::move(__c.__alloc_);526 }527 528 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign_alloc(vector&, false_type) _NOEXCEPT {}529 530 _LIBCPP_HIDE_FROM_ABI size_t __hash_code() const _NOEXCEPT;531 532 friend class __bit_reference<vector>;533 friend class __bit_const_reference<vector>;534 friend class __bit_iterator<vector, false>;535 friend class __bit_iterator<vector, true>;536 friend struct __bit_array<vector>;537 friend struct hash<vector>;538};539 540template <class _Allocator>541_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::__vdeallocate() _NOEXCEPT {542 if (this->__begin_ != nullptr) {543 __storage_traits::deallocate(this->__alloc_, this->__begin_, __cap_);544 this->__begin_ = nullptr;545 this->__size_ = this->__cap_ = 0;546 }547}548 549template <class _Allocator>550_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::size_type551vector<bool, _Allocator>::max_size() const _NOEXCEPT {552 size_type __amax = __storage_traits::max_size(__alloc_);553 size_type __nmax = numeric_limits<difference_type>::max();554 return __nmax / __bits_per_word <= __amax ? __nmax : __internal_cap_to_external(__amax);555}556 557// Precondition: __new_size > capacity()558template <class _Allocator>559inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::size_type560vector<bool, _Allocator>::__recommend(size_type __new_size) const {561 const size_type __ms = max_size();562 if (__new_size > __ms)563 this->__throw_length_error();564 const size_type __cap = capacity();565 if (__cap >= __ms / 2)566 return __ms;567 return std::max<size_type>(2 * __cap, __align_it(__new_size));568}569 570template <class _Allocator>571template <class _InputIterator, class _Sentinel>572_LIBCPP_CONSTEXPR_SINCE_CXX20 void573vector<bool, _Allocator>::__construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n) {574 _LIBCPP_ASSERT_INTERNAL(575 capacity() >= size() + __n, "vector<bool>::__construct_at_end called with insufficient capacity");576 std::__copy(std::move(__first), std::move(__last), end());577 this->__size_ += __n;578 if (end().__ctz_ != 0) // Ensure uninitialized leading bits in the last word are set to zero579 std::fill_n(end(), __bits_per_word - end().__ctz_, 0);580}581 582template <class _Allocator>583inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector()584 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)585 : __begin_(nullptr), __size_(0), __cap_(0) {}586 587template <class _Allocator>588inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(const allocator_type& __a)589#if _LIBCPP_STD_VER <= 14590 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)591#else592 _NOEXCEPT593#endif594 : __begin_(nullptr), __size_(0), __cap_(0), __alloc_(static_cast<__storage_allocator>(__a)) {595}596 597template <class _Allocator>598_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(size_type __n)599 : __begin_(nullptr), __size_(0), __cap_(0) {600 if (__n > 0) {601 __vallocate(__n);602 std::fill_n(__begin_, __external_cap_to_internal(__n), __storage_type(0));603 __size_ = __n;604 }605}606 607#if _LIBCPP_STD_VER >= 14608template <class _Allocator>609_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(size_type __n, const allocator_type& __a)610 : __begin_(nullptr), __size_(0), __cap_(0), __alloc_(static_cast<__storage_allocator>(__a)) {611 if (__n > 0) {612 __vallocate(__n);613 std::fill_n(__begin_, __external_cap_to_internal(__n), __storage_type(0));614 __size_ = __n;615 }616}617#endif618 619template <class _Allocator>620_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(size_type __n, const value_type& __x)621 : __begin_(nullptr), __size_(0), __cap_(0) {622 if (__n > 0) {623 __vallocate(__n);624 std::fill_n(__begin_, __external_cap_to_internal(__n), __storage_type(0) - __x);625 __size_ = __n;626 }627}628 629template <class _Allocator>630_LIBCPP_CONSTEXPR_SINCE_CXX20631vector<bool, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a)632 : __begin_(nullptr), __size_(0), __cap_(0), __alloc_(static_cast<__storage_allocator>(__a)) {633 if (__n > 0) {634 __vallocate(__n);635 std::fill_n(__begin_, __external_cap_to_internal(__n), __storage_type(0) - __x);636 __size_ = __n;637 }638}639 640template <class _Allocator>641template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> >642_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last)643 : __begin_(nullptr), __size_(0), __cap_(0) {644 __init_with_sentinel(__first, __last);645}646 647template <class _Allocator>648template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> >649_LIBCPP_CONSTEXPR_SINCE_CXX20650vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a)651 : __begin_(nullptr), __size_(0), __cap_(0), __alloc_(static_cast<__storage_allocator>(__a)) {652 __init_with_sentinel(__first, __last);653}654 655template <class _Allocator>656template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >657_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last)658 : __begin_(nullptr), __size_(0), __cap_(0) {659 auto __n = static_cast<size_type>(std::distance(__first, __last));660 __init_with_size(__first, __last, __n);661}662 663template <class _Allocator>664template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >665_LIBCPP_CONSTEXPR_SINCE_CXX20666vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a)667 : __begin_(nullptr), __size_(0), __cap_(0), __alloc_(static_cast<__storage_allocator>(__a)) {668 auto __n = static_cast<size_type>(std::distance(__first, __last));669 __init_with_size(__first, __last, __n);670}671 672#ifndef _LIBCPP_CXX03_LANG673 674template <class _Allocator>675_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(initializer_list<value_type> __il)676 : __begin_(nullptr), __size_(0), __cap_(0) {677 size_type __n = static_cast<size_type>(__il.size());678 if (__n > 0) {679 __vallocate(__n);680 __construct_at_end(__il.begin(), __il.end(), __n);681 }682}683 684template <class _Allocator>685_LIBCPP_CONSTEXPR_SINCE_CXX20686vector<bool, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)687 : __begin_(nullptr), __size_(0), __cap_(0), __alloc_(static_cast<__storage_allocator>(__a)) {688 size_type __n = static_cast<size_type>(__il.size());689 if (__n > 0) {690 __vallocate(__n);691 __construct_at_end(__il.begin(), __il.end(), __n);692 }693}694 695#endif // _LIBCPP_CXX03_LANG696 697template <class _Allocator>698_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(const vector& __v)699 : __begin_(nullptr),700 __size_(0),701 __cap_(0),702 __alloc_(__storage_traits::select_on_container_copy_construction(__v.__alloc_)) {703 if (__v.size() > 0) {704 __vallocate(__v.size());705 std::copy_n(__v.__begin_, __external_cap_to_internal(__v.size()), __begin_);706 __size_ = __v.size();707 }708}709 710template <class _Allocator>711_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a)712 : __begin_(nullptr), __size_(0), __cap_(0), __alloc_(__a) {713 if (__v.size() > 0) {714 __vallocate(__v.size());715 std::copy_n(__v.__begin_, __external_cap_to_internal(__v.size()), __begin_);716 __size_ = __v.size();717 }718}719 720template <class _Allocator>721_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>& vector<bool, _Allocator>::operator=(const vector& __v) {722 if (this != std::addressof(__v)) {723 __copy_assign_alloc(__v);724 if (__v.__size_) {725 if (__v.__size_ > capacity()) {726 __vdeallocate();727 __vallocate(__v.__size_);728 }729 std::copy_n(__v.__begin_, __external_cap_to_internal(__v.size()), __begin_);730 }731 __size_ = __v.__size_;732 }733 return *this;734}735 736template <class _Allocator>737inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(vector&& __v)738#if _LIBCPP_STD_VER >= 17739 _NOEXCEPT740#else741 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)742#endif743 : __begin_(__v.__begin_),744 __size_(__v.__size_),745 __cap_(__v.__cap_),746 __alloc_(std::move(__v.__alloc_)) {747 __v.__begin_ = nullptr;748 __v.__size_ = 0;749 __v.__cap_ = 0;750}751 752template <class _Allocator>753_LIBCPP_CONSTEXPR_SINCE_CXX20754vector<bool, _Allocator>::vector(vector&& __v, const __type_identity_t<allocator_type>& __a)755 : __begin_(nullptr), __size_(0), __cap_(0), __alloc_(__a) {756 if (__a == allocator_type(__v.__alloc_)) {757 this->__begin_ = __v.__begin_;758 this->__size_ = __v.__size_;759 this->__cap_ = __v.__cap_;760 __v.__begin_ = nullptr;761 __v.__cap_ = __v.__size_ = 0;762 } else if (__v.size() > 0) {763 __vallocate(__v.size());764 __construct_at_end(__v.begin(), __v.end(), __v.size());765 }766}767 768template <class _Allocator>769inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>&770vector<bool, _Allocator>::operator=(vector&& __v)771 _NOEXCEPT_(__noexcept_move_assign_container<_Allocator, __alloc_traits>::value) {772 __move_assign(__v, integral_constant<bool, __storage_traits::propagate_on_container_move_assignment::value>());773 return *this;774}775 776template <class _Allocator>777_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::__move_assign(vector& __c, false_type) {778 if (__alloc_ != __c.__alloc_)779 assign(__c.begin(), __c.end());780 else781 __move_assign(__c, true_type());782}783 784template <class _Allocator>785_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::__move_assign(vector& __c, true_type)786 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {787 __vdeallocate();788 __move_assign_alloc(__c);789 this->__begin_ = __c.__begin_;790 this->__size_ = __c.__size_;791 this->__cap_ = __c.__cap_;792 __c.__begin_ = nullptr;793 __c.__cap_ = __c.__size_ = 0;794}795 796template <class _Allocator>797_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::assign(size_type __n, const value_type& __x) {798 __size_ = 0;799 if (__n > 0) {800 size_type __c = capacity();801 if (__n <= __c)802 __size_ = __n;803 else {804 vector __v(get_allocator());805 __v.reserve(__recommend(__n));806 __v.__size_ = __n;807 swap(__v);808 }809 std::fill_n(begin(), __n, __x);810 }811}812 813template <class _Allocator>814template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> >815_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last) {816 __assign_with_sentinel(__first, __last);817}818 819template <class _Allocator>820template <class _Iterator, class _Sentinel>821_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void822vector<bool, _Allocator>::__assign_with_sentinel(_Iterator __first, _Sentinel __last) {823 clear();824 for (; __first != __last; ++__first)825 push_back(*__first);826}827 828template <class _Allocator>829template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >830_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) {831 __assign_with_size(__first, __last, std::distance(__first, __last));832}833 834template <class _Allocator>835template <class _Iterator, class _Sentinel>836_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void837vector<bool, _Allocator>::__assign_with_size(_Iterator __first, _Sentinel __last, difference_type __ns) {838 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__ns >= 0, "invalid range specified");839 840 clear();841 842 const size_t __n = static_cast<size_type>(__ns);843 if (__n) {844 if (__n > capacity()) {845 __vdeallocate();846 __vallocate(__n);847 }848 __construct_at_end(std::move(__first), std::move(__last), __n);849 }850}851 852template <class _Allocator>853_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::reserve(size_type __n) {854 if (__n > capacity()) {855 if (__n > max_size())856 this->__throw_length_error();857 vector __v(this->get_allocator());858 __v.__vallocate(__n);859 __v.__construct_at_end(this->begin(), this->end(), this->size());860 swap(__v);861 }862}863 864template <class _Allocator>865_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT {866 if (__external_cap_to_internal(size()) < __cap_) {867#if _LIBCPP_HAS_EXCEPTIONS868 try {869#endif // _LIBCPP_HAS_EXCEPTIONS870 vector __v(*this, allocator_type(__alloc_));871 if (__v.__cap_ < __cap_)872 __v.swap(*this);873#if _LIBCPP_HAS_EXCEPTIONS874 } catch (...) {875 }876#endif // _LIBCPP_HAS_EXCEPTIONS877 }878}879 880template <class _Allocator>881_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::reference vector<bool, _Allocator>::at(size_type __n) {882 if (__n >= size())883 this->__throw_out_of_range();884 return (*this)[__n];885}886 887template <class _Allocator>888_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::const_reference889vector<bool, _Allocator>::at(size_type __n) const {890 if (__n >= size())891 this->__throw_out_of_range();892 return (*this)[__n];893}894 895template <class _Allocator>896_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::push_back(const value_type& __x) {897 if (this->__size_ == this->capacity())898 reserve(__recommend(this->__size_ + 1));899 ++this->__size_;900 back() = __x;901}902 903template <class _Allocator>904_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator905vector<bool, _Allocator>::insert(const_iterator __position, const value_type& __x) {906 iterator __r;907 if (size() < capacity()) {908 const_iterator __old_end = end();909 ++__size_;910 std::copy_backward(__position, __old_end, end());911 __r = __const_iterator_cast(__position);912 } else {913 vector __v(get_allocator());914 __v.reserve(__recommend(__size_ + 1));915 __v.__size_ = __size_ + 1;916 __r = std::copy(cbegin(), __position, __v.begin());917 std::copy_backward(__position, cend(), __v.end());918 swap(__v);919 }920 *__r = __x;921 return __r;922}923 924template <class _Allocator>925_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator926vector<bool, _Allocator>::insert(const_iterator __position, size_type __n, const value_type& __x) {927 iterator __r;928 size_type __c = capacity();929 if (__n <= __c && size() <= __c - __n) {930 const_iterator __old_end = end();931 __size_ += __n;932 std::copy_backward(__position, __old_end, end());933 __r = __const_iterator_cast(__position);934 } else {935 vector __v(get_allocator());936 __v.reserve(__recommend(__size_ + __n));937 __v.__size_ = __size_ + __n;938 __r = std::copy(cbegin(), __position, __v.begin());939 std::copy_backward(__position, cend(), __v.end());940 swap(__v);941 }942 std::fill_n(__r, __n, __x);943 return __r;944}945 946template <class _Allocator>947template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> >948_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator949vector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) {950 return __insert_with_sentinel(__position, __first, __last);951}952 953template <class _Allocator>954template <class _InputIterator, class _Sentinel>955_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI typename vector<bool, _Allocator>::iterator956vector<bool, _Allocator>::__insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last) {957 difference_type __off = __position - begin();958 iterator __p = __const_iterator_cast(__position);959 iterator __old_end = end();960 for (; size() != capacity() && __first != __last; ++__first) {961 ++this->__size_;962 back() = *__first;963 }964 vector __v(get_allocator());965 if (__first != __last) {966 auto __guard = std::__make_exception_guard([&] { erase(__old_end, end()); });967 __v.__assign_with_sentinel(std::move(__first), std::move(__last));968 difference_type __old_size = static_cast<difference_type>(__old_end - begin());969 difference_type __old_p = __p - begin();970 reserve(__recommend(size() + __v.size()));971 __p = begin() + __old_p;972 __old_end = begin() + __old_size;973 __guard.__complete();974 }975 __p = std::rotate(__p, __old_end, end());976 insert(__p, __v.begin(), __v.end());977 return begin() + __off;978}979 980template <class _Allocator>981template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >982_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator983vector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) {984 return __insert_with_size(__position, __first, __last, std::distance(__first, __last));985}986 987template <class _Allocator>988template <class _Iterator, class _Sentinel>989_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI typename vector<bool, _Allocator>::iterator990vector<bool, _Allocator>::__insert_with_size(991 const_iterator __position, _Iterator __first, _Sentinel __last, difference_type __n_signed) {992 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__n_signed >= 0, "invalid range specified");993 const size_type __n = static_cast<size_type>(__n_signed);994 iterator __r;995 size_type __c = capacity();996 if (__n <= __c && size() <= __c - __n) {997 const_iterator __old_end = end();998 __size_ += __n;999 std::copy_backward(__position, __old_end, end());1000 __r = __const_iterator_cast(__position);1001 } else {1002 vector __v(get_allocator());1003 __v.reserve(__recommend(__size_ + __n));1004 __v.__size_ = __size_ + __n;1005 __r = std::copy(cbegin(), __position, __v.begin());1006 std::copy_backward(__position, cend(), __v.end());1007 swap(__v);1008 }1009 std::__copy(std::move(__first), std::move(__last), __r);1010 return __r;1011}1012 1013template <class _Allocator>1014inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator1015vector<bool, _Allocator>::erase(const_iterator __position) {1016 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(1017 __position != end(), "vector<bool>::erase(iterator) called with a non-dereferenceable iterator");1018 iterator __r = __const_iterator_cast(__position);1019 std::copy(__position + 1, this->cend(), __r);1020 --__size_;1021 return __r;1022}1023 1024template <class _Allocator>1025_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator1026vector<bool, _Allocator>::erase(const_iterator __first, const_iterator __last) {1027 _LIBCPP_ASSERT_VALID_INPUT_RANGE(1028 __first <= __last, "vector<bool>::erase(iterator, iterator) called with an invalid range");1029 iterator __r = __const_iterator_cast(__first);1030 difference_type __d = __last - __first;1031 std::copy(__last, this->cend(), __r);1032 __size_ -= __d;1033 return __r;1034}1035 1036template <class _Allocator>1037_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::swap(vector& __x)1038#if _LIBCPP_STD_VER >= 141039 _NOEXCEPT1040#else1041 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>)1042#endif1043{1044 std::swap(this->__begin_, __x.__begin_);1045 std::swap(this->__size_, __x.__size_);1046 std::swap(this->__cap_, __x.__cap_);1047 std::__swap_allocator(this->__alloc_, __x.__alloc_);1048}1049 1050template <class _Allocator>1051_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::resize(size_type __sz, value_type __x) {1052 size_type __cs = size();1053 if (__cs < __sz) {1054 iterator __r;1055 size_type __c = capacity();1056 size_type __n = __sz - __cs;1057 if (__n <= __c && __cs <= __c - __n) {1058 __r = end();1059 __size_ += __n;1060 } else {1061 vector __v(get_allocator());1062 __v.reserve(__recommend(__size_ + __n));1063 __v.__size_ = __size_ + __n;1064 __r = std::copy(cbegin(), cend(), __v.begin());1065 swap(__v);1066 }1067 std::fill_n(__r, __n, __x);1068 } else1069 __size_ = __sz;1070}1071 1072template <class _Allocator>1073_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::flip() _NOEXCEPT {1074 // Flip each storage word entirely, including the last potentially partial word.1075 // The unused bits in the last word are safe to flip as they won't be accessed.1076 __storage_pointer __p = __begin_;1077 for (size_type __n = __external_cap_to_internal(size()); __n != 0; ++__p, --__n)1078 *__p = ~*__p;1079}1080 1081template <class _Allocator>1082_LIBCPP_CONSTEXPR_SINCE_CXX20 bool vector<bool, _Allocator>::__invariants() const {1083 if (this->__begin_ == nullptr) {1084 if (this->__size_ != 0 || this->__cap_ != 0)1085 return false;1086 } else {1087 if (this->__cap_ == 0)1088 return false;1089 if (this->__size_ > this->capacity())1090 return false;1091 }1092 return true;1093}1094 1095template <class _Allocator>1096size_t vector<bool, _Allocator>::__hash_code() const _NOEXCEPT {1097 size_t __h = 0;1098 // do middle whole words1099 size_type __n = __size_;1100 __storage_pointer __p = __begin_;1101 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)1102 __h ^= *__p;1103 // do last partial word1104 if (__n > 0) {1105 const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);1106 __h ^= *__p & __m;1107 }1108 return __h;1109}1110 1111template <class _Allocator>1112struct hash<vector<bool, _Allocator> > : public __unary_function<vector<bool, _Allocator>, size_t> {1113 _LIBCPP_HIDE_FROM_ABI size_t operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT {1114 return __vec.__hash_code();1115 }1116};1117 1118_LIBCPP_END_NAMESPACE_STD1119 1120_LIBCPP_POP_MACROS1121 1122#endif // _LIBCPP___VECTOR_VECTOR_BOOL_H1123