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