libcxx/include/__vector/vector_bool.h

   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 <__assert>
  18 #include <__bit_reference>
  19 #include <__config>
  20 #include <__functional/unary_function.h>
  21 #include <__fwd/functional.h>
  22 #include <__fwd/vector.h>
  23 #include <__iterator/distance.h>
  24 #include <__iterator/iterator_traits.h>
  25 #include <__iterator/reverse_iterator.h>
  26 #include <__memory/addressof.h>
  27 #include <__memory/allocate_at_least.h>
  28 #include <__memory/allocator.h>
  29 #include <__memory/allocator_traits.h>
  30 #include <__memory/compressed_pair.h>
  31 #include <__memory/construct_at.h>
  32 #include <__memory/noexcept_move_assign_container.h>
  33 #include <__memory/pointer_traits.h>
  34 #include <__memory/swap_allocator.h>
  35 #include <__ranges/access.h>
  36 #include <__ranges/concepts.h>
  37 #include <__ranges/container_compatible_range.h>
  38 #include <__ranges/from_range.h>
  39 #include <__type_traits/enable_if.h>
  40 #include <__type_traits/is_constant_evaluated.h>
  41 #include <__type_traits/is_nothrow_assignable.h>
  42 #include <__type_traits/is_nothrow_constructible.h>
  43 #include <__type_traits/type_identity.h>
  44 #include <__utility/exception_guard.h>
  45 #include <__utility/forward.h>
  46 #include <__utility/move.h>
  47 #include <__utility/swap.h>
  48 #include <climits>
  49 #include <initializer_list>
  50 #include <limits>
  51 #include <stdexcept>
  52
  53 // These headers define parts of vectors definition, since they define ADL functions or class specializations.
  54 #include <__vector/comparison.h>
  55 #include <__vector/container_traits.h>
  56 #include <__vector/swap.h>
  57
  58 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  59 #  pragma GCC system_header
  60 #endif
  61
  62 _LIBCPP_PUSH_MACROS
  63 #include <__undef_macros>
  64
  65 _LIBCPP_BEGIN_NAMESPACE_STD
  66
  67 template <class _Allocator>
  68 struct hash<vector<bool, _Allocator> >;
  69
  70 template <class _Allocator>
  71 struct __has_storage_type<vector<bool, _Allocator> > {
  72   static const bool value = true;
  73 };
  74
  75 template <class _Allocator>
  76 class _LIBCPP_TEMPLATE_VIS vector<bool, _Allocator> {
  77 public:
  78   typedef vector __self;
  79   typedef bool value_type;
  80   typedef _Allocator allocator_type;
  81   typedef allocator_traits<allocator_type> __alloc_traits;
  82   typedef typename __alloc_traits::size_type size_type;
  83   typedef typename __alloc_traits::difference_type difference_type;
  84   typedef size_type __storage_type;
  85   typedef __bit_iterator<vector, false> pointer;
  86   typedef __bit_iterator<vector, true> const_pointer;
  87   typedef pointer iterator;
  88   typedef const_pointer const_iterator;
  89   typedef std::reverse_iterator<iterator> reverse_iterator;
  90   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  91
  92 private:
  93   typedef __rebind_alloc<__alloc_traits, __storage_type> __storage_allocator;
  94   typedef allocator_traits<__storage_allocator> __storage_traits;
  95   typedef typename __storage_traits::pointer __storage_pointer;
  96   typedef typename __storage_traits::const_pointer __const_storage_pointer;
  97
  98   __storage_pointer __begin_;
  99   size_type __size_;
 100   _LIBCPP_COMPRESSED_PAIR(size_type, __cap_, __storage_allocator, __alloc_);
 101
 102 public:
 103   typedef __bit_reference<vector> reference;
 104 #ifdef _LIBCPP_ABI_BITSET_VECTOR_BOOL_CONST_SUBSCRIPT_RETURN_BOOL
 105   using const_reference = bool;
 106 #else
 107   typedef __bit_const_reference<vector> const_reference;
 108 #endif
 109
 110 private:
 111   static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
 112
 113   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static size_type
 114   __internal_cap_to_external(size_type __n) _NOEXCEPT {
 115     return __n * __bits_per_word;
 116   }
 117   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static size_type
 118   __external_cap_to_internal(size_type __n) _NOEXCEPT {
 119     return __n > 0 ? (__n - 1) / __bits_per_word + 1 : size_type(0);
 120   }
 121
 122 public:
 123   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector()
 124       _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
 125
 126   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit vector(const allocator_type& __a)
 127 #if _LIBCPP_STD_VER <= 14
 128       _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value);
 129 #else
 130       _NOEXCEPT;
 131 #endif
 132
 133 private:
 134   class __destroy_vector {
 135   public:
 136     _LIBCPP_CONSTEXPR _LIBCPP_HIDE_FROM_ABI __destroy_vector(vector& __vec) : __vec_(__vec) {}
 137
 138     _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void operator()() {
 139       if (__vec_.__begin_ != nullptr)
 140         __storage_traits::deallocate(__vec_.__alloc_, __vec_.__begin_, __vec_.__cap_);
 141     }
 142
 143   private:
 144     vector& __vec_;
 145   };
 146
 147 public:
 148   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 ~vector() { __destroy_vector (*this)(); }
 149
 150   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit vector(size_type __n);
 151 #if _LIBCPP_STD_VER >= 14
 152   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit vector(size_type __n, const allocator_type& __a);
 153 #endif
 154   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(size_type __n, const value_type& __v);
 155   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 156   vector(size_type __n, const value_type& __v, const allocator_type& __a);
 157   template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>
 158   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(_InputIterator __first, _InputIterator __last);
 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
 161   vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a);
 162   template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
 163   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(_ForwardIterator __first, _ForwardIterator __last);
 164   template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
 165   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 166   vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a);
 167
 168 #if _LIBCPP_STD_VER >= 23
 169   template <_ContainerCompatibleRange<bool> _Range>
 170   _LIBCPP_HIDE_FROM_ABI constexpr vector(from_range_t, _Range&& __range, const allocator_type& __a = allocator_type())
 171       : __begin_(nullptr), __size_(0), __cap_(0), __alloc_(static_cast<__storage_allocator>(__a)) {
 172     if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
 173       auto __n = static_cast<size_type>(ranges::distance(__range));
 174       __init_with_size(ranges::begin(__range), ranges::end(__range), __n);
 175
 176     } else {
 177       __init_with_sentinel(ranges::begin(__range), ranges::end(__range));
 178     }
 179   }
 180 #endif
 181
 182   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(const vector& __v);
 183   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(const vector& __v, const allocator_type& __a);
 184   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector& operator=(const vector& __v);
 185
 186 #ifndef _LIBCPP_CXX03_LANG
 187   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(initializer_list<value_type> __il);
 188   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 189   vector(initializer_list<value_type> __il, const allocator_type& __a);
 190
 191   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector& operator=(initializer_list<value_type> __il) {
 192     assign(__il.begin(), __il.end());
 193     return *this;
 194   }
 195
 196 #endif // !_LIBCPP_CXX03_LANG
 197
 198   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(vector&& __v)
 199 #if _LIBCPP_STD_VER >= 17
 200       noexcept;
 201 #else
 202       _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
 203 #endif
 204   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 205   vector(vector&& __v, const __type_identity_t<allocator_type>& __a);
 206   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector& operator=(vector&& __v)
 207       _NOEXCEPT_(__noexcept_move_assign_container<_Allocator, __alloc_traits>::value);
 208
 209   template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>
 210   void _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 assign(_InputIterator __first, _InputIterator __last);
 211   template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
 212   void _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 assign(_ForwardIterator __first, _ForwardIterator __last);
 213
 214 #if _LIBCPP_STD_VER >= 23
 215   template <_ContainerCompatibleRange<bool> _Range>
 216   _LIBCPP_HIDE_FROM_ABI constexpr void assign_range(_Range&& __range) {
 217     if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
 218       auto __n = static_cast<size_type>(ranges::distance(__range));
 219       __assign_with_size(ranges::begin(__range), ranges::end(__range), __n);
 220
 221     } else {
 222       __assign_with_sentinel(ranges::begin(__range), ranges::end(__range));
 223     }
 224   }
 225 #endif
 226
 227   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void assign(size_type __n, const value_type& __x);
 228
 229 #ifndef _LIBCPP_CXX03_LANG
 230   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void assign(initializer_list<value_type> __il) {
 231     assign(__il.begin(), __il.end());
 232   }
 233 #endif
 234
 235   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 allocator_type get_allocator() const _NOEXCEPT {
 236     return allocator_type(this->__alloc_);
 237   }
 238
 239   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type max_size() const _NOEXCEPT;
 240   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type capacity() const _NOEXCEPT {
 241     return __internal_cap_to_external(__cap_);
 242   }
 243   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type size() const _NOEXCEPT { return __size_; }
 244   [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool empty() const _NOEXCEPT {
 245     return __size_ == 0;
 246   }
 247   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void reserve(size_type __n);
 248   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void shrink_to_fit() _NOEXCEPT;
 249
 250   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator begin() _NOEXCEPT { return __make_iter(0); }
 251   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator begin() const _NOEXCEPT { return __make_iter(0); }
 252   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator end() _NOEXCEPT { return __make_iter(__size_); }
 253   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator end() const _NOEXCEPT {
 254     return __make_iter(__size_);
 255   }
 256
 257   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reverse_iterator rbegin() _NOEXCEPT {
 258     return reverse_iterator(end());
 259   }
 260   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reverse_iterator rbegin() const _NOEXCEPT {
 261     return const_reverse_iterator(end());
 262   }
 263   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reverse_iterator rend() _NOEXCEPT {
 264     return reverse_iterator(begin());
 265   }
 266   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reverse_iterator rend() const _NOEXCEPT {
 267     return const_reverse_iterator(begin());
 268   }
 269
 270   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator cbegin() const _NOEXCEPT { return __make_iter(0); }
 271   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator cend() const _NOEXCEPT {
 272     return __make_iter(__size_);
 273   }
 274   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reverse_iterator crbegin() const _NOEXCEPT {
 275     return rbegin();
 276   }
 277   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
 278
 279   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference operator[](size_type __n) {
 280     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__n < size(), "vector<bool>::operator[] index out of bounds");
 281     return __make_ref(__n);
 282   }
 283   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference operator[](size_type __n) const {
 284     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__n < size(), "vector<bool>::operator[] index out of bounds");
 285     return __make_ref(__n);
 286   }
 287   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference at(size_type __n);
 288   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference at(size_type __n) const;
 289
 290   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference front() {
 291     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "vector<bool>::front() called on an empty vector");
 292     return __make_ref(0);
 293   }
 294   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference front() const {
 295     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "vector<bool>::front() called on an empty vector");
 296     return __make_ref(0);
 297   }
 298   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference back() {
 299     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "vector<bool>::back() called on an empty vector");
 300     return __make_ref(__size_ - 1);
 301   }
 302   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference back() const {
 303     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "vector<bool>::back() called on an empty vector");
 304     return __make_ref(__size_ - 1);
 305   }
 306
 307   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void push_back(const value_type& __x);
 308 #if _LIBCPP_STD_VER >= 14
 309   template <class... _Args>
 310 #  if _LIBCPP_STD_VER >= 17
 311   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference emplace_back(_Args&&... __args)
 312 #  else
 313   _LIBCPP_HIDE_FROM_ABI void emplace_back(_Args&&... __args)
 314 #  endif
 315   {
 316     push_back(value_type(std::forward<_Args>(__args)...));
 317 #  if _LIBCPP_STD_VER >= 17
 318     return this->back();
 319 #  endif
 320   }
 321 #endif
 322
 323 #if _LIBCPP_STD_VER >= 23
 324   template <_ContainerCompatibleRange<bool> _Range>
 325   _LIBCPP_HIDE_FROM_ABI constexpr void append_range(_Range&& __range) {
 326     insert_range(end(), std::forward<_Range>(__range));
 327   }
 328 #endif
 329
 330   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void pop_back() {
 331     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "vector<bool>::pop_back called on an empty vector");
 332     --__size_;
 333   }
 334
 335 #if _LIBCPP_STD_VER >= 14
 336   template <class... _Args>
 337   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator emplace(const_iterator __position, _Args&&... __args) {
 338     return insert(__position, value_type(std::forward<_Args>(__args)...));
 339   }
 340 #endif
 341
 342   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator insert(const_iterator __position, const value_type& __x);
 343   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator
 344   insert(const_iterator __position, size_type __n, const value_type& __x);
 345   template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>
 346   iterator _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 347   insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
 348   template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
 349   iterator _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 350   insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
 351
 352 #if _LIBCPP_STD_VER >= 23
 353   template <_ContainerCompatibleRange<bool> _Range>
 354   _LIBCPP_HIDE_FROM_ABI constexpr iterator insert_range(const_iterator __position, _Range&& __range) {
 355     if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
 356       auto __n = static_cast<size_type>(ranges::distance(__range));
 357       return __insert_with_size(__position, ranges::begin(__range), ranges::end(__range), __n);
 358
 359     } else {
 360       return __insert_with_sentinel(__position, ranges::begin(__range), ranges::end(__range));
 361     }
 362   }
 363 #endif
 364
 365 #ifndef _LIBCPP_CXX03_LANG
 366   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator
 367   insert(const_iterator __position, initializer_list<value_type> __il) {
 368     return insert(__position, __il.begin(), __il.end());
 369   }
 370 #endif
 371
 372   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator erase(const_iterator __position);
 373   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator erase(const_iterator __first, const_iterator __last);
 374
 375   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void clear() _NOEXCEPT { __size_ = 0; }
 376
 377   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void swap(vector&)
 378 #if _LIBCPP_STD_VER >= 14
 379       _NOEXCEPT;
 380 #else
 381       _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>);
 382 #endif
 383   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static void swap(reference __x, reference __y) _NOEXCEPT {
 384     std::swap(__x, __y);
 385   }
 386
 387   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void resize(size_type __sz, value_type __x = false);
 388   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void flip() _NOEXCEPT;
 389
 390   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __invariants() const;
 391
 392 private:
 393   [[__noreturn__]] _LIBCPP_HIDE_FROM_ABI static void __throw_length_error() { std::__throw_length_error("vector"); }
 394
 395   [[__noreturn__]] _LIBCPP_HIDE_FROM_ABI static void __throw_out_of_range() { std::__throw_out_of_range("vector"); }
 396
 397   template <class _InputIterator, class _Sentinel>
 398   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
 399   __init_with_size(_InputIterator __first, _Sentinel __last, size_type __n) {
 400     auto __guard = std::__make_exception_guard(__destroy_vector(*this));
 401
 402     if (__n > 0) {
 403       __vallocate(__n);
 404       __construct_at_end(std::move(__first), std::move(__last), __n);
 405     }
 406
 407     __guard.__complete();
 408   }
 409
 410   template <class _InputIterator, class _Sentinel>
 411   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
 412   __init_with_sentinel(_InputIterator __first, _Sentinel __last) {
 413     auto __guard = std::__make_exception_guard(__destroy_vector(*this));
 414
 415     for (; __first != __last; ++__first)
 416       push_back(*__first);
 417
 418     __guard.__complete();
 419   }
 420
 421   template <class _Iterator, class _Sentinel>
 422   _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __assign_with_sentinel(_Iterator __first, _Sentinel __last);
 423
 424   // The `_Iterator` in `*_with_size` functions can be input-only only if called from `*_range` (since C++23).
 425   // Otherwise, `_Iterator` is a forward iterator.
 426
 427   template <class _Iterator, class _Sentinel>
 428   _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
 429   __assign_with_size(_Iterator __first, _Sentinel __last, difference_type __ns);
 430
 431   template <class _InputIterator, class _Sentinel>
 432   _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
 433   __insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last);
 434
 435   template <class _Iterator, class _Sentinel>
 436   _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
 437   __insert_with_size(const_iterator __position, _Iterator __first, _Sentinel __last, difference_type __n);
 438
 439   //  Allocate space for __n objects
 440   //  throws length_error if __n > max_size()
 441   //  throws (probably bad_alloc) if memory run out
 442   //  Precondition:  __begin_ == __end_ == __cap_ == nullptr
 443   //  Precondition:  __n > 0
 444   //  Postcondition:  capacity() >= __n
 445   //  Postcondition:  size() == 0
 446   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __vallocate(size_type __n) {
 447     if (__n > max_size())
 448       __throw_length_error();
 449     auto __allocation = std::__allocate_at_least(__alloc_, __external_cap_to_internal(__n));
 450     __begin_          = __allocation.ptr;
 451     __size_           = 0;
 452     __cap_            = __allocation.count;
 453     if (__libcpp_is_constant_evaluated()) {
 454       for (size_type __i = 0; __i != __cap_; ++__i)
 455         std::__construct_at(std::__to_address(__begin_) + __i);
 456     }
 457   }
 458
 459   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __vdeallocate() _NOEXCEPT;
 460   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static size_type __align_it(size_type __new_size) _NOEXCEPT {
 461     return (__new_size + (__bits_per_word - 1)) & ~((size_type)__bits_per_word - 1);
 462   }
 463   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type __recommend(size_type __new_size) const;
 464   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __construct_at_end(size_type __n, bool __x);
 465   template <class _InputIterator, class _Sentinel>
 466   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
 467   __construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n);
 468   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference __make_ref(size_type __pos) _NOEXCEPT {
 469     return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);
 470   }
 471   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference __make_ref(size_type __pos) const _NOEXCEPT {
 472     return __bit_const_reference<vector>(
 473         __begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);
 474   }
 475   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator __make_iter(size_type __pos) _NOEXCEPT {
 476     return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));
 477   }
 478   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator __make_iter(size_type __pos) const _NOEXCEPT {
 479     return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));
 480   }
 481   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT {
 482     return begin() + (__p - cbegin());
 483   }
 484
 485   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __copy_assign_alloc(const vector& __v) {
 486     __copy_assign_alloc(
 487         __v, integral_constant<bool, __storage_traits::propagate_on_container_copy_assignment::value>());
 488   }
 489   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __copy_assign_alloc(const vector& __c, true_type) {
 490     if (__alloc_ != __c.__alloc_)
 491       __vdeallocate();
 492     __alloc_ = __c.__alloc_;
 493   }
 494
 495   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __copy_assign_alloc(const vector&, false_type) {}
 496
 497   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign(vector& __c, false_type);
 498   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign(vector& __c, true_type)
 499       _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
 500   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign_alloc(vector& __c)
 501       _NOEXCEPT_(!__storage_traits::propagate_on_container_move_assignment::value ||
 502                  is_nothrow_move_assignable<allocator_type>::value) {
 503     __move_assign_alloc(
 504         __c, integral_constant<bool, __storage_traits::propagate_on_container_move_assignment::value>());
 505   }
 506   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign_alloc(vector& __c, true_type)
 507       _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {
 508     __alloc_ = std::move(__c.__alloc_);
 509   }
 510
 511   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign_alloc(vector&, false_type) _NOEXCEPT {}
 512
 513   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_t __hash_code() const _NOEXCEPT;
 514
 515   friend class __bit_reference<vector>;
 516   friend class __bit_const_reference<vector>;
 517   friend class __bit_iterator<vector, false>;
 518   friend class __bit_iterator<vector, true>;
 519   friend struct __bit_array<vector>;
 520   friend struct _LIBCPP_TEMPLATE_VIS hash<vector>;
 521 };
 522
 523 template <class _Allocator>
 524 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::__vdeallocate() _NOEXCEPT {
 525   if (this->__begin_ != nullptr) {
 526     __storage_traits::deallocate(this->__alloc_, this->__begin_, __cap_);
 527     this->__begin_ = nullptr;
 528     this->__size_ = this->__cap_ = 0;
 529   }
 530 }
 531
 532 template <class _Allocator>
 533 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::size_type
 534 vector<bool, _Allocator>::max_size() const _NOEXCEPT {
 535   size_type __amax = __storage_traits::max_size(__alloc_);
 536   size_type __nmax = numeric_limits<size_type>::max() / 2; // end() >= begin(), always
 537   if (__nmax / __bits_per_word <= __amax)
 538     return __nmax;
 539   return __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(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 _LIBCPP_CONSTEXPR_SINCE_CXX20 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 _LIBCPP_TEMPLATE_VIS hash<vector<bool, _Allocator> >
1113     : public __unary_function<vector<bool, _Allocator>, size_t> {
1114   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_t
1115   operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT {
1116     return __vec.__hash_code();
1117   }
1118 };
1119
1120 _LIBCPP_END_NAMESPACE_STD
1121
1122 _LIBCPP_POP_MACROS
1123
1124 #endif // _LIBCPP___VECTOR_VECTOR_BOOL_H