xref: /freebsd/contrib/llvm-project/libcxx/include/__vector/vector_bool.h (revision 700637cbb5e582861067a11aaca4d053546871d2) 
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 
69 template <class _Allocator>
70 struct hash<vector<bool, _Allocator> >;
71 
72 template <class _Allocator>
73 struct __has_storage_type<vector<bool, _Allocator> > {
74   static const bool value = true;
75 };
76 
77 template <class _Allocator>
78 class vector<bool, _Allocator> {
79 public:
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 
94 private:
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 
104 public:
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 
112 private:
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 
124 public:
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 
135 private:
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 
149 public:
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 
394 private:
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 
525 template <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 
534 template <class _Allocator>
535 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::size_type
536 vector<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()
543 template <class _Allocator>
544 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::size_type
545 vector<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
558 template <class _Allocator>
559 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
560 vector<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 
569 template <class _Allocator>
570 template <class _InputIterator, class _Sentinel>
571 _LIBCPP_CONSTEXPR_SINCE_CXX20 void
572 vector<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 
581 template <class _Allocator>
582 inline _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 
586 template <class _Allocator>
587 inline _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 
596 template <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
606 template <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 
616 template <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 
625 template <class _Allocator>
626 _LIBCPP_CONSTEXPR_SINCE_CXX20
627 vector<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 
635 template <class _Allocator>
636 template <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 
642 template <class _Allocator>
643 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> >
644 _LIBCPP_CONSTEXPR_SINCE_CXX20
645 vector<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 
650 template <class _Allocator>
651 template <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 
658 template <class _Allocator>
659 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >
660 _LIBCPP_CONSTEXPR_SINCE_CXX20
661 vector<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 
669 template <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 
679 template <class _Allocator>
680 _LIBCPP_CONSTEXPR_SINCE_CXX20
681 vector<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 
692 template <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 
704 template <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 
713 template <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 
729 template <class _Allocator>
730 inline _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 
745 template <class _Allocator>
746 _LIBCPP_CONSTEXPR_SINCE_CXX20
747 vector<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 
761 template <class _Allocator>
762 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>&
763 vector<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 
769 template <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 
777 template <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 
789 template <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 
806 template <class _Allocator>
807 template <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 
812 template <class _Allocator>
813 template <class _Iterator, class _Sentinel>
814 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
815 vector<bool, _Allocator>::__assign_with_sentinel(_Iterator __first, _Sentinel __last) {
816   clear();
817   for (; __first != __last; ++__first)
818     push_back(*__first);
819 }
820 
821 template <class _Allocator>
822 template <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 
827 template <class _Allocator>
828 template <class _Iterator, class _Sentinel>
829 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
830 vector<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 
845 template <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 
857 template <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 
873 template <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 
880 template <class _Allocator>
881 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::const_reference
882 vector<bool, _Allocator>::at(size_type __n) const {
883   if (__n >= size())
884     this->__throw_out_of_range();
885   return (*this)[__n];
886 }
887 
888 template <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 
896 template <class _Allocator>
897 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator
898 vector<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 
917 template <class _Allocator>
918 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator
919 vector<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 
939 template <class _Allocator>
940 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> >
941 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator
942 vector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) {
943   return __insert_with_sentinel(__position, __first, __last);
944 }
945 
946 template <class _Allocator>
947 template <class _InputIterator, class _Sentinel>
948 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI typename vector<bool, _Allocator>::iterator
949 vector<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 
980 template <class _Allocator>
981 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >
982 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator
983 vector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) {
984   return __insert_with_size(__position, __first, __last, std::distance(__first, __last));
985 }
986 
987 template <class _Allocator>
988 template <class _Iterator, class _Sentinel>
989 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI typename vector<bool, _Allocator>::iterator
990 vector<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 
1013 template <class _Allocator>
1014 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator
1015 vector<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 
1024 template <class _Allocator>
1025 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator
1026 vector<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 
1036 template <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 
1050 template <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 
1072 template <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 
1081 template <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 
1095 template <class _Allocator>
1096 size_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 
1111 template <class _Allocator>
1112 struct 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
1123