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