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