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-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef _LIBCPP___VECTOR_VECTOR_BOOL_H
10#define _LIBCPP___VECTOR_VECTOR_BOOL_H
11
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/PR131814
24#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/exchange.h>
49#include <__utility/forward.h>
50#include <__utility/move.h>
51#include <__utility/swap.h>
52#include <climits>
53#include <initializer_list>
54#include <limits>
55#include <stdexcept>
56
57// These headers define parts of vectors definition, since they define ADL functions or class specializations.
58#include <__vector/comparison.h>
59#include <__vector/container_traits.h>
60#include <__vector/swap.h>
61
62#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
63# pragma GCC system_header
64#endif
65
66_LIBCPP_PUSH_MACROS
67#include <__undef_macros>
68
69_LIBCPP_BEGIN_NAMESPACE_STD
70
71template <class _Allocator>
72struct hash<vector<bool, _Allocator> >;
73
74template <class _Allocator>
75struct __has_storage_type<vector<bool, _Allocator> > {
76 static const bool value = true;
77};
78
79template <class _Allocator>
80class vector<bool, _Allocator> {
81public:
82 using __self _LIBCPP_NODEBUG = vector;
83 using value_type = bool;
84 using allocator_type = _Allocator;
85 using __alloc_traits _LIBCPP_NODEBUG = allocator_traits<allocator_type>;
86 using size_type = typename __alloc_traits::size_type;
87 using difference_type = typename __alloc_traits::difference_type;
88 using __storage_type _LIBCPP_NODEBUG = size_type;
89 using pointer = __bit_iterator<vector, false>;
90 using const_pointer = __bit_iterator<vector, true>;
91 using iterator = pointer;
92 using const_iterator = const_pointer;
93 using reverse_iterator = std::reverse_iterator<iterator>;
94 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
95
96private:
97 using __storage_allocator _LIBCPP_NODEBUG = __rebind_alloc<__alloc_traits, __storage_type>;
98 using __storage_traits _LIBCPP_NODEBUG = allocator_traits<__storage_allocator>;
99 using __storage_pointer _LIBCPP_NODEBUG = typename __storage_traits::pointer;
100 using __const_storage_pointer _LIBCPP_NODEBUG = typename __storage_traits::const_pointer;
101
102 __storage_pointer __begin_;
103 size_type __size_;
104 _LIBCPP_COMPRESSED_PAIR(size_type, __cap_, __storage_allocator, __alloc_);
105
106public:
107 using reference = __bit_reference<vector>;
108#ifdef _LIBCPP_ABI_BITSET_VECTOR_BOOL_CONST_SUBSCRIPT_RETURN_BOOL
109 using const_reference = bool;
110#else
111 using const_reference = __bit_const_reference<vector>;
112#endif
113
114private:
115 static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
116
117 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static size_type
118 __internal_cap_to_external(size_type __n) _NOEXCEPT {
119 return __n * __bits_per_word;
120 }
121 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static size_type
122 __external_cap_to_internal(size_type __n) _NOEXCEPT {
123 return __n > 0 ? (__n - 1) / __bits_per_word + 1 : size_type(0);
124 }
125
126public:
127 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector()
128 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
129
130 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit vector(const allocator_type& __a)
131#if _LIBCPP_STD_VER <= 14
132 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value);
133#else
134 _NOEXCEPT;
135#endif
136
137private:
138 class __destroy_vector {
139 public:
140 _LIBCPP_CONSTEXPR _LIBCPP_HIDE_FROM_ABI __destroy_vector(vector& __vec) : __vec_(__vec) {}
141
142 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void operator()() {
143 if (__vec_.__begin_ != nullptr)
144 __storage_traits::deallocate(__vec_.__alloc_, __vec_.__begin_, __vec_.__cap_);
145 }
146
147 private:
148 vector& __vec_;
149 };
150
151public:
152 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 ~vector() { __destroy_vector (*this)(); }
153
154 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit vector(size_type __n);
155#if _LIBCPP_STD_VER >= 14
156 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit vector(size_type __n, const allocator_type& __a);
157#endif
158 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(size_type __n, const value_type& __v);
159 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
160 vector(size_type __n, const value_type& __v, const allocator_type& __a);
161 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>
162 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(_InputIterator __first, _InputIterator __last);
163 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>
164 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
165 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a);
166 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
167 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(_ForwardIterator __first, _ForwardIterator __last);
168 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
169 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
170 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a);
171
172#if _LIBCPP_STD_VER >= 23
173 template <_ContainerCompatibleRange<bool> _Range>
174 _LIBCPP_HIDE_FROM_ABI constexpr vector(from_range_t, _Range&& __range, const allocator_type& __a = allocator_type())
175 : __begin_(nullptr), __size_(0), __cap_(0), __alloc_(static_cast<__storage_allocator>(__a)) {
176 if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
177 auto __n = static_cast<size_type>(ranges::distance(__range));
178 __init_with_size(ranges::begin(__range), ranges::end(__range), __n);
179
180 } else {
181 __init_with_sentinel(ranges::begin(__range), ranges::end(__range));
182 }
183 }
184#endif
185
186 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(const vector& __v);
187 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(const vector& __v, const allocator_type& __a);
188 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector& operator=(const vector& __v);
189
190#ifndef _LIBCPP_CXX03_LANG
191 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(initializer_list<value_type> __il);
192 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
193 vector(initializer_list<value_type> __il, const allocator_type& __a);
194
195 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector& operator=(initializer_list<value_type> __il) {
196 assign(__il.begin(), __il.end());
197 return *this;
198 }
199
200#endif // !_LIBCPP_CXX03_LANG
201
202 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(vector&& __v)
203#if _LIBCPP_STD_VER >= 17
204 noexcept;
205#else
206 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
207#endif
208 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
209 vector(vector&& __v, const __type_identity_t<allocator_type>& __a);
210 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector& operator=(vector&& __v)
211 _NOEXCEPT_(__noexcept_move_assign_container<_Allocator, __alloc_traits>::value);
212
213 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>
214 void _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 assign(_InputIterator __first, _InputIterator __last);
215 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
216 void _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 assign(_ForwardIterator __first, _ForwardIterator __last);
217
218#if _LIBCPP_STD_VER >= 23
219 template <_ContainerCompatibleRange<bool> _Range>
220 _LIBCPP_HIDE_FROM_ABI constexpr void assign_range(_Range&& __range) {
221 if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
222 auto __n = static_cast<size_type>(ranges::distance(__range));
223 __assign_with_size(ranges::begin(__range), ranges::end(__range), __n);
224
225 } else {
226 __assign_with_sentinel(ranges::begin(__range), ranges::end(__range));
227 }
228 }
229#endif
230
231 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void assign(size_type __n, const value_type& __x);
232
233#ifndef _LIBCPP_CXX03_LANG
234 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void assign(initializer_list<value_type> __il) {
235 assign(__il.begin(), __il.end());
236 }
237#endif
238
239 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 allocator_type get_allocator() const _NOEXCEPT {
240 return allocator_type(this->__alloc_);
241 }
242
243 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type max_size() const _NOEXCEPT;
244 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type capacity() const _NOEXCEPT {
245 return __internal_cap_to_external(n: __cap_);
246 }
247 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type size() const _NOEXCEPT {
248 return __size_;
249 }
250 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool empty() const _NOEXCEPT {
251 return __size_ == 0;
252 }
253 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void reserve(size_type __n);
254 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void shrink_to_fit() _NOEXCEPT;
255
256 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator begin() _NOEXCEPT {
257 return __make_iter(0);
258 }
259 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator begin() const _NOEXCEPT {
260 return __make_iter(0);
261 }
262 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator end() _NOEXCEPT {
263 return __make_iter(__size_);
264 }
265 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator end() const _NOEXCEPT {
266 return __make_iter(__size_);
267 }
268
269 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reverse_iterator rbegin() _NOEXCEPT {
270 return reverse_iterator(end());
271 }
272 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reverse_iterator
273 rbegin() const _NOEXCEPT {
274 return const_reverse_iterator(end());
275 }
276 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reverse_iterator rend() _NOEXCEPT {
277 return reverse_iterator(begin());
278 }
279 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reverse_iterator rend() const _NOEXCEPT {
280 return const_reverse_iterator(begin());
281 }
282
283 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator cbegin() const _NOEXCEPT {
284 return __make_iter(0);
285 }
286 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator cend() const _NOEXCEPT {
287 return __make_iter(__size_);
288 }
289 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reverse_iterator
290 crbegin() const _NOEXCEPT {
291 return rbegin();
292 }
293 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reverse_iterator crend() const _NOEXCEPT {
294 return rend();
295 }
296
297 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference operator[](size_type __n) {
298 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__n < size(), "vector<bool>::operator[] index out of bounds");
299 return __make_ref(__n);
300 }
301 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference
302 operator[](size_type __n) const {
303 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__n < size(), "vector<bool>::operator[] index out of bounds");
304 return __make_ref(__n);
305 }
306 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference at(size_type __n);
307 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference at(size_type __n) const;
308
309 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference front() {
310 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "vector<bool>::front() called on an empty vector");
311 return __make_ref(0);
312 }
313 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference front() const {
314 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "vector<bool>::front() called on an empty vector");
315 return __make_ref(0);
316 }
317 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference back() {
318 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "vector<bool>::back() called on an empty vector");
319 return __make_ref(__size_ - 1);
320 }
321 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference back() const {
322 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "vector<bool>::back() called on an empty vector");
323 return __make_ref(__size_ - 1);
324 }
325
326 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void push_back(const value_type& __x);
327#if _LIBCPP_STD_VER >= 14
328 template <class... _Args>
329# if _LIBCPP_STD_VER >= 17
330 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference emplace_back(_Args&&... __args)
331# else
332 _LIBCPP_HIDE_FROM_ABI void emplace_back(_Args&&... __args)
333# endif
334 {
335 push_back(x: value_type(std::forward<_Args>(__args)...));
336# if _LIBCPP_STD_VER >= 17
337 return this->back();
338# endif
339 }
340#endif
341
342#if _LIBCPP_STD_VER >= 23
343 template <_ContainerCompatibleRange<bool> _Range>
344 _LIBCPP_HIDE_FROM_ABI constexpr void append_range(_Range&& __range) {
345 insert_range(end(), std::forward<_Range>(__range));
346 }
347#endif
348
349 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void pop_back() {
350 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "vector<bool>::pop_back called on an empty vector");
351 --__size_;
352 }
353
354#if _LIBCPP_STD_VER >= 14
355 template <class... _Args>
356 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator emplace(const_iterator __position, _Args&&... __args) {
357 return insert(__position, value_type(std::forward<_Args>(__args)...));
358 }
359#endif
360
361 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator insert(const_iterator __position, const value_type& __x);
362 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator
363 insert(const_iterator __position, size_type __n, const value_type& __x);
364 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>
365 iterator _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
366 insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
367 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
368 iterator _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
369 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
370
371#if _LIBCPP_STD_VER >= 23
372 template <_ContainerCompatibleRange<bool> _Range>
373 _LIBCPP_HIDE_FROM_ABI constexpr iterator insert_range(const_iterator __position, _Range&& __range) {
374 if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
375 auto __n = static_cast<size_type>(ranges::distance(__range));
376 return __insert_with_size(__position, ranges::begin(__range), ranges::end(__range), __n);
377
378 } else {
379 return __insert_with_sentinel(__position, ranges::begin(__range), ranges::end(__range));
380 }
381 }
382#endif
383
384#ifndef _LIBCPP_CXX03_LANG
385 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator
386 insert(const_iterator __position, initializer_list<value_type> __il) {
387 return insert(__position, __il.begin(), __il.end());
388 }
389#endif
390
391 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator erase(const_iterator __position);
392 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator erase(const_iterator __first, const_iterator __last);
393
394 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void clear() _NOEXCEPT { __size_ = 0; }
395
396 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void swap(vector&)
397#if _LIBCPP_STD_VER >= 14
398 _NOEXCEPT;
399#else
400 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>);
401#endif
402 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static void swap(reference __x, reference __y) _NOEXCEPT {
403 std::swap(__x, __y);
404 }
405
406 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void resize(size_type __sz, value_type __x = false);
407 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void flip() _NOEXCEPT;
408
409 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __invariants() const;
410
411private:
412 [[__noreturn__]] _LIBCPP_HIDE_FROM_ABI static void __throw_length_error() { std::__throw_length_error(msg: "vector"); }
413
414 [[__noreturn__]] _LIBCPP_HIDE_FROM_ABI static void __throw_out_of_range() { std::__throw_out_of_range(msg: "vector"); }
415
416 template <class _InputIterator, class _Sentinel>
417 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
418 __init_with_size(_InputIterator __first, _Sentinel __last, size_type __n) {
419 auto __guard = std::__make_exception_guard(__destroy_vector(*this));
420
421 if (__n > 0) {
422 __vallocate(__n);
423 __construct_at_end(std::move(__first), std::move(__last), __n);
424 }
425
426 __guard.__complete();
427 }
428
429 template <class _InputIterator, class _Sentinel>
430 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
431 __init_with_sentinel(_InputIterator __first, _Sentinel __last) {
432 auto __guard = std::__make_exception_guard(__destroy_vector(*this));
433
434 for (; __first != __last; ++__first)
435 push_back(x: *__first);
436
437 __guard.__complete();
438 }
439
440 template <class _Iterator, class _Sentinel>
441 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __assign_with_sentinel(_Iterator __first, _Sentinel __last);
442
443 // The `_Iterator` in `*_with_size` functions can be input-only only if called from `*_range` (since C++23).
444 // Otherwise, `_Iterator` is a forward iterator.
445
446 template <class _Iterator, class _Sentinel>
447 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
448 __assign_with_size(_Iterator __first, _Sentinel __last, difference_type __ns);
449
450 template <class _InputIterator, class _Sentinel>
451 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
452 __insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last);
453
454 template <class _Iterator, class _Sentinel>
455 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
456 __insert_with_size(const_iterator __position, _Iterator __first, _Sentinel __last, difference_type __n);
457
458 // Allocate space for __n objects
459 // throws length_error if __n > max_size()
460 // throws (probably bad_alloc) if memory run out
461 // Precondition: __begin_ == __end_ == __cap_ == nullptr
462 // Precondition: __n > 0
463 // Postcondition: capacity() >= __n
464 // Postcondition: size() == 0
465 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __vallocate(size_type __n) {
466 if (__n > max_size())
467 this->__throw_length_error();
468 auto __allocation = std::__allocate_at_least(__alloc_, __external_cap_to_internal(__n));
469 __begin_ = __allocation.ptr;
470 __size_ = 0;
471 __cap_ = __allocation.count;
472 if (__libcpp_is_constant_evaluated()) {
473 for (size_type __i = 0; __i != __cap_; ++__i)
474 std::__construct_at(std::__to_address(__begin_) + __i);
475 }
476 }
477
478 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __vdeallocate() _NOEXCEPT;
479 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static size_type __align_it(size_type __new_size) _NOEXCEPT {
480 return (__new_size + (__bits_per_word - 1)) & ~((size_type)__bits_per_word - 1);
481 }
482 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type __recommend(size_type __new_size) const;
483 template <class _InputIterator, class _Sentinel>
484 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
485 __construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n);
486 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference __make_ref(size_type __pos) _NOEXCEPT {
487 return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);
488 }
489 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference __make_ref(size_type __pos) const _NOEXCEPT {
490 return __bit_const_reference<vector>(
491 __begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);
492 }
493 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator __make_iter(size_type __pos) _NOEXCEPT {
494 return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));
495 }
496 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator __make_iter(size_type __pos) const _NOEXCEPT {
497 return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));
498 }
499 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT {
500 return begin() + (__p - cbegin());
501 }
502
503 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __copy_assign_alloc(const vector& __v) {
504 __copy_assign_alloc(
505 __v, integral_constant<bool, __storage_traits::propagate_on_container_copy_assignment::value>());
506 }
507 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __copy_assign_alloc(const vector& __c, true_type) {
508 if (__alloc_ != __c.__alloc_)
509 __vdeallocate();
510 __alloc_ = __c.__alloc_;
511 }
512
513 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __copy_assign_alloc(const vector&, false_type) {}
514
515 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign(vector& __c, false_type);
516 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign(vector& __c, true_type)
517 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
518 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign_alloc(vector& __c)
519 _NOEXCEPT_(!__storage_traits::propagate_on_container_move_assignment::value ||
520 is_nothrow_move_assignable<allocator_type>::value) {
521 __move_assign_alloc(
522 __c, integral_constant<bool, __storage_traits::propagate_on_container_move_assignment::value>());
523 }
524 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign_alloc(vector& __c, true_type)
525 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {
526 __alloc_ = std::move(__c.__alloc_);
527 }
528
529 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign_alloc(vector&, false_type) _NOEXCEPT {}
530
531 _LIBCPP_HIDE_FROM_ABI size_t __hash_code() const _NOEXCEPT;
532
533 friend class __bit_reference<vector>;
534 friend class __bit_const_reference<vector>;
535 friend class __bit_iterator<vector, false>;
536 friend class __bit_iterator<vector, true>;
537 friend struct __bit_array<vector>;
538 friend struct hash<vector>;
539};
540
541template <class _Allocator>
542_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::__vdeallocate() _NOEXCEPT {
543 if (this->__begin_ != nullptr) {
544 __storage_traits::deallocate(this->__alloc_, this->__begin_, __cap_);
545 this->__begin_ = nullptr;
546 this->__size_ = this->__cap_ = 0;
547 }
548}
549
550template <class _Allocator>
551_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::size_type
552vector<bool, _Allocator>::max_size() const _NOEXCEPT {
553 size_type __amax = __storage_traits::max_size(__alloc_);
554 size_type __nmax = numeric_limits<difference_type>::max();
555 return __nmax / __bits_per_word <= __amax ? __nmax : __internal_cap_to_external(n: __amax);
556}
557
558// Precondition: __new_size > capacity()
559template <class _Allocator>
560inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::size_type
561vector<bool, _Allocator>::__recommend(size_type __new_size) const {
562 const size_type __ms = max_size();
563 if (__new_size > __ms)
564 this->__throw_length_error();
565 const size_type __cap = capacity();
566 if (__cap >= __ms / 2)
567 return __ms;
568 return std::max<size_type>(2 * __cap, __align_it(__new_size));
569}
570
571template <class _Allocator>
572template <class _InputIterator, class _Sentinel>
573_LIBCPP_CONSTEXPR_SINCE_CXX20 void
574vector<bool, _Allocator>::__construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n) {
575 _LIBCPP_ASSERT_INTERNAL(
576 capacity() >= size() + __n, "vector<bool>::__construct_at_end called with insufficient capacity");
577 std::__copy(std::move(__first), std::move(__last), end());
578 this->__size_ += __n;
579 if (end().__ctz_ != 0) // Ensure uninitialized leading bits in the last word are set to zero
580 std::fill_n(end(), __bits_per_word - end().__ctz_, 0);
581}
582
583template <class _Allocator>
584inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector()
585 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
586 : __begin_(nullptr), __size_(0), __cap_(0) {}
587
588template <class _Allocator>
589inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(const allocator_type& __a)
590#if _LIBCPP_STD_VER <= 14
591 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
592#else
593 _NOEXCEPT
594#endif
595 : __begin_(nullptr), __size_(0), __cap_(0), __alloc_(static_cast<__storage_allocator>(__a)) {
596}
597
598template <class _Allocator>
599_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(size_type __n)
600 : __begin_(nullptr), __size_(0), __cap_(0) {
601 if (__n > 0) {
602 __vallocate(__n);
603 std::fill_n(__begin_, __external_cap_to_internal(__n), __storage_type(0));
604 __size_ = __n;
605 }
606}
607
608#if _LIBCPP_STD_VER >= 14
609template <class _Allocator>
610_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(size_type __n, const allocator_type& __a)
611 : __begin_(nullptr), __size_(0), __cap_(0), __alloc_(static_cast<__storage_allocator>(__a)) {
612 if (__n > 0) {
613 __vallocate(__n);
614 std::fill_n(__begin_, __external_cap_to_internal(__n), __storage_type(0));
615 __size_ = __n;
616 }
617}
618#endif
619
620template <class _Allocator>
621_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(size_type __n, const value_type& __x)
622 : __begin_(nullptr), __size_(0), __cap_(0) {
623 if (__n > 0) {
624 __vallocate(__n);
625 std::fill_n(__begin_, __external_cap_to_internal(__n), __storage_type(0) - __x);
626 __size_ = __n;
627 }
628}
629
630template <class _Allocator>
631_LIBCPP_CONSTEXPR_SINCE_CXX20
632vector<bool, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a)
633 : __begin_(nullptr), __size_(0), __cap_(0), __alloc_(static_cast<__storage_allocator>(__a)) {
634 if (__n > 0) {
635 __vallocate(__n);
636 std::fill_n(__begin_, __external_cap_to_internal(__n), __storage_type(0) - __x);
637 __size_ = __n;
638 }
639}
640
641template <class _Allocator>
642template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> >
643_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last)
644 : __begin_(nullptr), __size_(0), __cap_(0) {
645 __init_with_sentinel(__first, __last);
646}
647
648template <class _Allocator>
649template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> >
650_LIBCPP_CONSTEXPR_SINCE_CXX20
651vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a)
652 : __begin_(nullptr), __size_(0), __cap_(0), __alloc_(static_cast<__storage_allocator>(__a)) {
653 __init_with_sentinel(__first, __last);
654}
655
656template <class _Allocator>
657template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >
658_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last)
659 : __begin_(nullptr), __size_(0), __cap_(0) {
660 auto __n = static_cast<size_type>(std::distance(__first, __last));
661 __init_with_size(__first, __last, __n);
662}
663
664template <class _Allocator>
665template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >
666_LIBCPP_CONSTEXPR_SINCE_CXX20
667vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a)
668 : __begin_(nullptr), __size_(0), __cap_(0), __alloc_(static_cast<__storage_allocator>(__a)) {
669 auto __n = static_cast<size_type>(std::distance(__first, __last));
670 __init_with_size(__first, __last, __n);
671}
672
673#ifndef _LIBCPP_CXX03_LANG
674
675template <class _Allocator>
676_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(initializer_list<value_type> __il)
677 : __begin_(nullptr), __size_(0), __cap_(0) {
678 size_type __n = static_cast<size_type>(__il.size());
679 if (__n > 0) {
680 __vallocate(__n);
681 __construct_at_end(__il.begin(), __il.end(), __n);
682 }
683}
684
685template <class _Allocator>
686_LIBCPP_CONSTEXPR_SINCE_CXX20
687vector<bool, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
688 : __begin_(nullptr), __size_(0), __cap_(0), __alloc_(static_cast<__storage_allocator>(__a)) {
689 size_type __n = static_cast<size_type>(__il.size());
690 if (__n > 0) {
691 __vallocate(__n);
692 __construct_at_end(__il.begin(), __il.end(), __n);
693 }
694}
695
696#endif // _LIBCPP_CXX03_LANG
697
698template <class _Allocator>
699_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(const vector& __v)
700 : __begin_(nullptr),
701 __size_(0),
702 __cap_(0),
703 __alloc_(__storage_traits::select_on_container_copy_construction(__v.__alloc_)) {
704 if (__v.size() > 0) {
705 __vallocate(n: __v.size());
706 std::copy_n(__v.__begin_, __external_cap_to_internal(n: __v.size()), __begin_);
707 __size_ = __v.size();
708 }
709}
710
711template <class _Allocator>
712_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a)
713 : __begin_(nullptr), __size_(0), __cap_(0), __alloc_(__a) {
714 if (__v.size() > 0) {
715 __vallocate(n: __v.size());
716 std::copy_n(__v.__begin_, __external_cap_to_internal(n: __v.size()), __begin_);
717 __size_ = __v.size();
718 }
719}
720
721template <class _Allocator>
722_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>& vector<bool, _Allocator>::operator=(const vector& __v) {
723 if (this != std::addressof(__v)) {
724 __copy_assign_alloc(__v);
725 if (__v.__size_) {
726 if (__v.__size_ > capacity()) {
727 __vdeallocate();
728 __vallocate(n: __v.__size_);
729 }
730 std::copy_n(__v.__begin_, __external_cap_to_internal(n: __v.size()), __begin_);
731 }
732 __size_ = __v.__size_;
733 }
734 return *this;
735}
736
737template <class _Allocator>
738inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(vector&& __v)
739#if _LIBCPP_STD_VER >= 17
740 _NOEXCEPT
741#else
742 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
743#endif
744 : __begin_(std::__exchange(__v.__begin_, nullptr)),
745 __size_(std::__exchange(__v.__size_, 0)),
746 __cap_(std::__exchange(__v.__cap_, 0)),
747 __alloc_(std::move(__v.__alloc_)) {
748}
749
750template <class _Allocator>
751_LIBCPP_CONSTEXPR_SINCE_CXX20
752vector<bool, _Allocator>::vector(vector&& __v, const __type_identity_t<allocator_type>& __a)
753 : __begin_(nullptr), __size_(0), __cap_(0), __alloc_(__a) {
754 if (__a == allocator_type(__v.__alloc_)) {
755 __begin_ = std::__exchange(__v.__begin_, nullptr);
756 __size_ = std::__exchange(__v.__size_, 0);
757 __cap_ = std::__exchange(__v.__cap_, 0);
758 } else if (__v.size() > 0) {
759 __vallocate(n: __v.size());
760 __size_ = __v.__size_;
761 std::copy_n(__v.__begin_, __external_cap_to_internal(n: __v.size()), __begin_);
762 }
763}
764
765template <class _Allocator>
766inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>&
767vector<bool, _Allocator>::operator=(vector&& __v)
768 _NOEXCEPT_(__noexcept_move_assign_container<_Allocator, __alloc_traits>::value) {
769 __move_assign(__v, integral_constant<bool, __storage_traits::propagate_on_container_move_assignment::value>());
770 return *this;
771}
772
773template <class _Allocator>
774_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::__move_assign(vector& __c, false_type) {
775 if (__alloc_ != __c.__alloc_)
776 assign(__c.begin(), __c.end());
777 else
778 __move_assign(__c, true_type());
779}
780
781template <class _Allocator>
782_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::__move_assign(vector& __c, true_type)
783 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {
784 __vdeallocate();
785 __move_assign_alloc(__c);
786 __begin_ = std::__exchange(__c.__begin_, nullptr);
787 __size_ = std::__exchange(__c.__size_, 0);
788 __cap_ = std::__exchange(__c.__cap_, 0);
789}
790
791template <class _Allocator>
792_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::assign(size_type __n, const value_type& __x) {
793 __size_ = 0;
794 if (__n > 0) {
795 size_type __c = capacity();
796 if (__n <= __c)
797 __size_ = __n;
798 else {
799 vector __v(get_allocator());
800 __v.reserve(n: __recommend(new_size: __n));
801 __v.__size_ = __n;
802 swap(__v);
803 }
804 std::fill_n(begin(), __n, __x);
805 }
806}
807
808template <class _Allocator>
809template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> >
810_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last) {
811 __assign_with_sentinel(__first, __last);
812}
813
814template <class _Allocator>
815template <class _Iterator, class _Sentinel>
816_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
817vector<bool, _Allocator>::__assign_with_sentinel(_Iterator __first, _Sentinel __last) {
818 clear();
819 for (; __first != __last; ++__first)
820 push_back(x: *__first);
821}
822
823template <class _Allocator>
824template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >
825_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) {
826 __assign_with_size(__first, __last, std::distance(__first, __last));
827}
828
829template <class _Allocator>
830template <class _Iterator, class _Sentinel>
831_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
832vector<bool, _Allocator>::__assign_with_size(_Iterator __first, _Sentinel __last, difference_type __ns) {
833 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__ns >= 0, "invalid range specified");
834
835 clear();
836
837 const size_t __n = static_cast<size_type>(__ns);
838 if (__n) {
839 if (__n > capacity()) {
840 __vdeallocate();
841 __vallocate(__n);
842 }
843 __construct_at_end(std::move(__first), std::move(__last), __n);
844 }
845}
846
847template <class _Allocator>
848_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::reserve(size_type __n) {
849 if (__n > capacity()) {
850 if (__n > max_size())
851 this->__throw_length_error();
852 vector __v(this->get_allocator());
853 __v.__vallocate(__n);
854 __v.__size_ = __size_;
855 std::copy_n(__begin_, __external_cap_to_internal(n: __size_), __v.__begin_);
856 swap(__v);
857 }
858}
859
860template <class _Allocator>
861_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT {
862 if (__external_cap_to_internal(n: size()) < __cap_) {
863#if _LIBCPP_HAS_EXCEPTIONS
864 try {
865#endif // _LIBCPP_HAS_EXCEPTIONS
866 vector __v(*this, allocator_type(__alloc_));
867 if (__v.__cap_ < __cap_)
868 __v.swap(*this);
869#if _LIBCPP_HAS_EXCEPTIONS
870 } catch (...) {
871 }
872#endif // _LIBCPP_HAS_EXCEPTIONS
873 }
874}
875
876template <class _Allocator>
877_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::reference vector<bool, _Allocator>::at(size_type __n) {
878 if (__n >= size())
879 this->__throw_out_of_range();
880 return (*this)[__n];
881}
882
883template <class _Allocator>
884_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::const_reference
885vector<bool, _Allocator>::at(size_type __n) const {
886 if (__n >= size())
887 this->__throw_out_of_range();
888 return (*this)[__n];
889}
890
891template <class _Allocator>
892_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::push_back(const value_type& __x) {
893 if (this->__size_ == this->capacity())
894 reserve(n: __recommend(new_size: this->__size_ + 1));
895 ++this->__size_;
896 back() = __x;
897}
898
899template <class _Allocator>
900_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator
901vector<bool, _Allocator>::insert(const_iterator __position, const value_type& __x) {
902 iterator __r;
903 if (size() < capacity()) {
904 const_iterator __old_end = end();
905 ++__size_;
906 std::copy_backward(__position, __old_end, end());
907 __r = __const_iterator_cast(p: __position);
908 } else {
909 vector __v(get_allocator());
910 __v.reserve(n: __recommend(new_size: __size_ + 1));
911 __v.__size_ = __size_ + 1;
912 __r = std::copy(cbegin(), __position, __v.begin());
913 std::copy_backward(__position, cend(), __v.end());
914 swap(__v);
915 }
916 *__r = __x;
917 return __r;
918}
919
920template <class _Allocator>
921_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator
922vector<bool, _Allocator>::insert(const_iterator __position, size_type __n, const value_type& __x) {
923 iterator __r;
924 size_type __c = capacity();
925 if (__n <= __c && size() <= __c - __n) {
926 const_iterator __old_end = end();
927 __size_ += __n;
928 std::copy_backward(__position, __old_end, end());
929 __r = __const_iterator_cast(p: __position);
930 } else {
931 vector __v(get_allocator());
932 __v.reserve(n: __recommend(new_size: __size_ + __n));
933 __v.__size_ = __size_ + __n;
934 __r = std::copy(cbegin(), __position, __v.begin());
935 std::copy_backward(__position, cend(), __v.end());
936 swap(__v);
937 }
938 std::fill_n(__r, __n, __x);
939 return __r;
940}
941
942template <class _Allocator>
943template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> >
944_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator
945vector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) {
946 return __insert_with_sentinel(__position, __first, __last);
947}
948
949template <class _Allocator>
950template <class _InputIterator, class _Sentinel>
951_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI typename vector<bool, _Allocator>::iterator
952vector<bool, _Allocator>::__insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last) {
953 difference_type __off = __position - begin();
954 iterator __p = __const_iterator_cast(p: __position);
955 iterator __old_end = end();
956 for (; size() != capacity() && __first != __last; ++__first) {
957 ++this->__size_;
958 back() = *__first;
959 }
960 vector __v(get_allocator());
961 if (__first != __last) {
962 auto __guard = std::__make_exception_guard([&] { erase(__old_end, end()); });
963 __v.__assign_with_sentinel(std::move(__first), std::move(__last));
964 difference_type __old_size = static_cast<difference_type>(__old_end - begin());
965 difference_type __old_p = __p - begin();
966 reserve(n: __recommend(new_size: size() + __v.size()));
967 __p = begin() + __old_p;
968 __old_end = begin() + __old_size;
969 __guard.__complete();
970 }
971 __p = std::rotate(__p, __old_end, end());
972 insert(__p, __v.begin(), __v.end());
973 return begin() + __off;
974}
975
976template <class _Allocator>
977template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >
978_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator
979vector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) {
980 return __insert_with_size(__position, __first, __last, std::distance(__first, __last));
981}
982
983template <class _Allocator>
984template <class _Iterator, class _Sentinel>
985_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI typename vector<bool, _Allocator>::iterator
986vector<bool, _Allocator>::__insert_with_size(
987 const_iterator __position, _Iterator __first, _Sentinel __last, difference_type __n_signed) {
988 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__n_signed >= 0, "invalid range specified");
989 const size_type __n = static_cast<size_type>(__n_signed);
990 iterator __r;
991 size_type __c = capacity();
992 if (__n <= __c && size() <= __c - __n) {
993 const_iterator __old_end = end();
994 __size_ += __n;
995 std::copy_backward(__position, __old_end, end());
996 __r = __const_iterator_cast(p: __position);
997 } else {
998 vector __v(get_allocator());
999 __v.reserve(n: __recommend(new_size: __size_ + __n));
1000 __v.__size_ = __size_ + __n;
1001 __r = std::copy(cbegin(), __position, __v.begin());
1002 std::copy_backward(__position, cend(), __v.end());
1003 swap(__v);
1004 }
1005 std::__copy(std::move(__first), std::move(__last), __r);
1006 return __r;
1007}
1008
1009template <class _Allocator>
1010inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator
1011vector<bool, _Allocator>::erase(const_iterator __position) {
1012 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
1013 __position != end(), "vector<bool>::erase(iterator) called with a non-dereferenceable iterator");
1014 iterator __r = __const_iterator_cast(p: __position);
1015 std::copy(__position + 1, this->cend(), __r);
1016 --__size_;
1017 return __r;
1018}
1019
1020template <class _Allocator>
1021_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator
1022vector<bool, _Allocator>::erase(const_iterator __first, const_iterator __last) {
1023 _LIBCPP_ASSERT_VALID_INPUT_RANGE(
1024 __first <= __last, "vector<bool>::erase(iterator, iterator) called with an invalid range");
1025 iterator __r = __const_iterator_cast(p: __first);
1026 difference_type __d = __last - __first;
1027 std::copy(__last, this->cend(), __r);
1028 __size_ -= __d;
1029 return __r;
1030}
1031
1032template <class _Allocator>
1033_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::swap(vector& __x)
1034#if _LIBCPP_STD_VER >= 14
1035 _NOEXCEPT
1036#else
1037 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>)
1038#endif
1039{
1040 std::swap(this->__begin_, __x.__begin_);
1041 std::swap(this->__size_, __x.__size_);
1042 std::swap(this->__cap_, __x.__cap_);
1043 std::__swap_allocator(this->__alloc_, __x.__alloc_);
1044}
1045
1046template <class _Allocator>
1047_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::resize(size_type __new_size, value_type __x) {
1048 size_type __current_size = size();
1049 if (__new_size < __current_size) {
1050 __size_ = __new_size;
1051 return;
1052 }
1053
1054 reserve(n: __new_size);
1055 std::fill_n(end(), __new_size - __current_size, __x);
1056 __size_ = __new_size;
1057}
1058
1059template <class _Allocator>
1060_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::flip() _NOEXCEPT {
1061 // Flip each storage word entirely, including the last potentially partial word.
1062 // The unused bits in the last word are safe to flip as they won't be accessed.
1063 __storage_pointer __p = __begin_;
1064 for (size_type __n = __external_cap_to_internal(n: size()); __n != 0; ++__p, --__n)
1065 *__p = ~*__p;
1066}
1067
1068template <class _Allocator>
1069_LIBCPP_CONSTEXPR_SINCE_CXX20 bool vector<bool, _Allocator>::__invariants() const {
1070 if (this->__begin_ == nullptr) {
1071 if (this->__size_ != 0 || this->__cap_ != 0)
1072 return false;
1073 } else {
1074 if (this->__cap_ == 0)
1075 return false;
1076 if (this->__size_ > this->capacity())
1077 return false;
1078 }
1079 return true;
1080}
1081
1082template <class _Allocator>
1083size_t vector<bool, _Allocator>::__hash_code() const _NOEXCEPT {
1084 size_t __h = 0;
1085 // do middle whole words
1086 size_type __n = __size_;
1087 __storage_pointer __p = __begin_;
1088 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
1089 __h ^= *__p;
1090 // do last partial word
1091 if (__n > 0) {
1092 const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
1093 __h ^= *__p & __m;
1094 }
1095 return __h;
1096}
1097
1098template <class _Allocator>
1099struct hash<vector<bool, _Allocator> > : public __unary_function<vector<bool, _Allocator>, size_t> {
1100 _LIBCPP_HIDE_FROM_ABI size_t operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT {
1101 return __vec.__hash_code();
1102 }
1103};
1104
1105_LIBCPP_END_NAMESPACE_STD
1106
1107_LIBCPP_POP_MACROS
1108
1109#endif // _LIBCPP___VECTOR_VECTOR_BOOL_H
1110