Warning, /include/c++/v1/__cxx03/vector is written in an unsupported language. File is not indexed.
0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP___CXX03_VECTOR
0011 #define _LIBCPP___CXX03_VECTOR
0012
0013 // clang-format off
0014
0015 /*
0016 vector synopsis
0017
0018 namespace std
0019 {
0020
0021 template <class T, class Allocator = allocator<T> >
0022 class vector
0023 {
0024 public:
0025 typedef T value_type;
0026 typedef Allocator allocator_type;
0027 typedef typename allocator_type::reference reference;
0028 typedef typename allocator_type::const_reference const_reference;
0029 typedef implementation-defined iterator;
0030 typedef implementation-defined const_iterator;
0031 typedef typename allocator_type::size_type size_type;
0032 typedef typename allocator_type::difference_type difference_type;
0033 typedef typename allocator_type::pointer pointer;
0034 typedef typename allocator_type::const_pointer const_pointer;
0035 typedef std::reverse_iterator<iterator> reverse_iterator;
0036 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
0037
0038 vector()
0039 noexcept(is_nothrow_default_constructible<allocator_type>::value);
0040 explicit vector(const allocator_type&);
0041 explicit vector(size_type n);
0042 explicit vector(size_type n, const allocator_type&); // C++14
0043 vector(size_type n, const value_type& value, const allocator_type& = allocator_type());
0044 template <class InputIterator>
0045 vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type());
0046 template<container-compatible-range<T> R>
0047 constexpr vector(from_range_t, R&& rg, const Allocator& = Allocator()); // C++23
0048 vector(const vector& x);
0049 vector(vector&& x)
0050 noexcept(is_nothrow_move_constructible<allocator_type>::value);
0051 vector(initializer_list<value_type> il);
0052 vector(initializer_list<value_type> il, const allocator_type& a);
0053 ~vector();
0054 vector& operator=(const vector& x);
0055 vector& operator=(vector&& x)
0056 noexcept(
0057 allocator_type::propagate_on_container_move_assignment::value ||
0058 allocator_type::is_always_equal::value); // C++17
0059 vector& operator=(initializer_list<value_type> il);
0060 template <class InputIterator>
0061 void assign(InputIterator first, InputIterator last);
0062 template<container-compatible-range<T> R>
0063 constexpr void assign_range(R&& rg); // C++23
0064 void assign(size_type n, const value_type& u);
0065 void assign(initializer_list<value_type> il);
0066
0067 allocator_type get_allocator() const noexcept;
0068
0069 iterator begin() noexcept;
0070 const_iterator begin() const noexcept;
0071 iterator end() noexcept;
0072 const_iterator end() const noexcept;
0073
0074 reverse_iterator rbegin() noexcept;
0075 const_reverse_iterator rbegin() const noexcept;
0076 reverse_iterator rend() noexcept;
0077 const_reverse_iterator rend() const noexcept;
0078
0079 const_iterator cbegin() const noexcept;
0080 const_iterator cend() const noexcept;
0081 const_reverse_iterator crbegin() const noexcept;
0082 const_reverse_iterator crend() const noexcept;
0083
0084 size_type size() const noexcept;
0085 size_type max_size() const noexcept;
0086 size_type capacity() const noexcept;
0087 bool empty() const noexcept;
0088 void reserve(size_type n);
0089 void shrink_to_fit() noexcept;
0090
0091 reference operator[](size_type n);
0092 const_reference operator[](size_type n) const;
0093 reference at(size_type n);
0094 const_reference at(size_type n) const;
0095
0096 reference front();
0097 const_reference front() const;
0098 reference back();
0099 const_reference back() const;
0100
0101 value_type* data() noexcept;
0102 const value_type* data() const noexcept;
0103
0104 void push_back(const value_type& x);
0105 void push_back(value_type&& x);
0106 template <class... Args>
0107 reference emplace_back(Args&&... args); // reference in C++17
0108 template<container-compatible-range<T> R>
0109 constexpr void append_range(R&& rg); // C++23
0110 void pop_back();
0111
0112 template <class... Args> iterator emplace(const_iterator position, Args&&... args);
0113 iterator insert(const_iterator position, const value_type& x);
0114 iterator insert(const_iterator position, value_type&& x);
0115 iterator insert(const_iterator position, size_type n, const value_type& x);
0116 template <class InputIterator>
0117 iterator insert(const_iterator position, InputIterator first, InputIterator last);
0118 template<container-compatible-range<T> R>
0119 constexpr iterator insert_range(const_iterator position, R&& rg); // C++23
0120 iterator insert(const_iterator position, initializer_list<value_type> il);
0121
0122 iterator erase(const_iterator position);
0123 iterator erase(const_iterator first, const_iterator last);
0124
0125 void clear() noexcept;
0126
0127 void resize(size_type sz);
0128 void resize(size_type sz, const value_type& c);
0129
0130 void swap(vector&)
0131 noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value ||
0132 allocator_traits<allocator_type>::is_always_equal::value); // C++17
0133
0134 bool __invariants() const;
0135 };
0136
0137 template <class Allocator = allocator<T> >
0138 class vector<bool, Allocator>
0139 {
0140 public:
0141 typedef bool value_type;
0142 typedef Allocator allocator_type;
0143 typedef implementation-defined iterator;
0144 typedef implementation-defined const_iterator;
0145 typedef typename allocator_type::size_type size_type;
0146 typedef typename allocator_type::difference_type difference_type;
0147 typedef iterator pointer;
0148 typedef const_iterator const_pointer;
0149 typedef std::reverse_iterator<iterator> reverse_iterator;
0150 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
0151
0152 class reference
0153 {
0154 public:
0155 reference(const reference&) noexcept;
0156 operator bool() const noexcept;
0157 reference& operator=(bool x) noexcept;
0158 reference& operator=(const reference& x) noexcept;
0159 iterator operator&() const noexcept;
0160 void flip() noexcept;
0161 };
0162
0163 class const_reference
0164 {
0165 public:
0166 const_reference(const reference&) noexcept;
0167 operator bool() const noexcept;
0168 const_iterator operator&() const noexcept;
0169 };
0170
0171 vector()
0172 noexcept(is_nothrow_default_constructible<allocator_type>::value);
0173 explicit vector(const allocator_type&);
0174 explicit vector(size_type n, const allocator_type& a = allocator_type()); // C++14
0175 vector(size_type n, const value_type& value, const allocator_type& = allocator_type());
0176 template <class InputIterator>
0177 vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type());
0178 template<container-compatible-range<bool> R>
0179 constexpr vector(from_range_t, R&& rg, const Allocator& = Allocator());
0180 vector(const vector& x);
0181 vector(vector&& x)
0182 noexcept(is_nothrow_move_constructible<allocator_type>::value);
0183 vector(initializer_list<value_type> il);
0184 vector(initializer_list<value_type> il, const allocator_type& a);
0185 ~vector();
0186 vector& operator=(const vector& x);
0187 vector& operator=(vector&& x)
0188 noexcept(
0189 allocator_type::propagate_on_container_move_assignment::value ||
0190 allocator_type::is_always_equal::value); // C++17
0191 vector& operator=(initializer_list<value_type> il);
0192 template <class InputIterator>
0193 void assign(InputIterator first, InputIterator last);
0194 template<container-compatible-range<T> R>
0195 constexpr void assign_range(R&& rg); // C++23
0196 void assign(size_type n, const value_type& u);
0197 void assign(initializer_list<value_type> il);
0198
0199 allocator_type get_allocator() const noexcept;
0200
0201 iterator begin() noexcept;
0202 const_iterator begin() const noexcept;
0203 iterator end() noexcept;
0204 const_iterator end() const noexcept;
0205
0206 reverse_iterator rbegin() noexcept;
0207 const_reverse_iterator rbegin() const noexcept;
0208 reverse_iterator rend() noexcept;
0209 const_reverse_iterator rend() const noexcept;
0210
0211 const_iterator cbegin() const noexcept;
0212 const_iterator cend() const noexcept;
0213 const_reverse_iterator crbegin() const noexcept;
0214 const_reverse_iterator crend() const noexcept;
0215
0216 size_type size() const noexcept;
0217 size_type max_size() const noexcept;
0218 size_type capacity() const noexcept;
0219 bool empty() const noexcept;
0220 void reserve(size_type n);
0221 void shrink_to_fit() noexcept;
0222
0223 reference operator[](size_type n);
0224 const_reference operator[](size_type n) const;
0225 reference at(size_type n);
0226 const_reference at(size_type n) const;
0227
0228 reference front();
0229 const_reference front() const;
0230 reference back();
0231 const_reference back() const;
0232
0233 void push_back(const value_type& x);
0234 template <class... Args> reference emplace_back(Args&&... args); // C++14; reference in C++17
0235 template<container-compatible-range<T> R>
0236 constexpr void append_range(R&& rg); // C++23
0237 void pop_back();
0238
0239 template <class... Args> iterator emplace(const_iterator position, Args&&... args); // C++14
0240 iterator insert(const_iterator position, const value_type& x);
0241 iterator insert(const_iterator position, size_type n, const value_type& x);
0242 template <class InputIterator>
0243 iterator insert(const_iterator position, InputIterator first, InputIterator last);
0244 template<container-compatible-range<T> R>
0245 constexpr iterator insert_range(const_iterator position, R&& rg); // C++23
0246 iterator insert(const_iterator position, initializer_list<value_type> il);
0247
0248 iterator erase(const_iterator position);
0249 iterator erase(const_iterator first, const_iterator last);
0250
0251 void clear() noexcept;
0252
0253 void resize(size_type sz);
0254 void resize(size_type sz, value_type x);
0255
0256 void swap(vector&)
0257 noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value ||
0258 allocator_traits<allocator_type>::is_always_equal::value); // C++17
0259 void flip() noexcept;
0260
0261 bool __invariants() const;
0262 };
0263
0264 template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
0265 vector(InputIterator, InputIterator, Allocator = Allocator())
0266 -> vector<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17
0267
0268 template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
0269 vector(from_range_t, R&&, Allocator = Allocator())
0270 -> vector<ranges::range_value_t<R>, Allocator>; // C++23
0271
0272 template <class Allocator> struct hash<std::vector<bool, Allocator>>;
0273
0274 template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y); // constexpr since C++20
0275 template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); // removed in C++20
0276 template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y); // removed in C++20
0277 template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y); // removed in C++20
0278 template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); // removed in C++20
0279 template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); // removed in C++20
0280 template <class T, class Allocator> constexpr
0281 constexpr synth-three-way-result<T> operator<=>(const vector<T, Allocator>& x,
0282 const vector<T, Allocator>& y); // since C++20
0283
0284 template <class T, class Allocator>
0285 void swap(vector<T,Allocator>& x, vector<T,Allocator>& y)
0286 noexcept(noexcept(x.swap(y)));
0287
0288 template <class T, class Allocator, class U>
0289 typename vector<T, Allocator>::size_type
0290 erase(vector<T, Allocator>& c, const U& value); // since C++20
0291 template <class T, class Allocator, class Predicate>
0292 typename vector<T, Allocator>::size_type
0293 erase_if(vector<T, Allocator>& c, Predicate pred); // since C++20
0294
0295
0296 template<class T>
0297 inline constexpr bool is-vector-bool-reference = see below; // exposition only, since C++23
0298
0299 template<class T, class charT> requires is-vector-bool-reference<T> // Since C++23
0300 struct formatter<T, charT>;
0301
0302 } // std
0303
0304 */
0305
0306 // clang-format on
0307
0308 #include <__cxx03/__algorithm/copy.h>
0309 #include <__cxx03/__algorithm/equal.h>
0310 #include <__cxx03/__algorithm/fill_n.h>
0311 #include <__cxx03/__algorithm/iterator_operations.h>
0312 #include <__cxx03/__algorithm/lexicographical_compare.h>
0313 #include <__cxx03/__algorithm/lexicographical_compare_three_way.h>
0314 #include <__cxx03/__algorithm/remove.h>
0315 #include <__cxx03/__algorithm/remove_if.h>
0316 #include <__cxx03/__algorithm/rotate.h>
0317 #include <__cxx03/__algorithm/unwrap_iter.h>
0318 #include <__cxx03/__assert>
0319 #include <__cxx03/__bit_reference>
0320 #include <__cxx03/__concepts/same_as.h>
0321 #include <__cxx03/__config>
0322 #include <__cxx03/__debug_utils/sanitizers.h>
0323 #include <__cxx03/__format/enable_insertable.h>
0324 #include <__cxx03/__format/formatter.h>
0325 #include <__cxx03/__format/formatter_bool.h>
0326 #include <__cxx03/__functional/hash.h>
0327 #include <__cxx03/__functional/unary_function.h>
0328 #include <__cxx03/__fwd/vector.h>
0329 #include <__cxx03/__iterator/advance.h>
0330 #include <__cxx03/__iterator/bounded_iter.h>
0331 #include <__cxx03/__iterator/distance.h>
0332 #include <__cxx03/__iterator/iterator_traits.h>
0333 #include <__cxx03/__iterator/reverse_iterator.h>
0334 #include <__cxx03/__iterator/wrap_iter.h>
0335 #include <__cxx03/__memory/addressof.h>
0336 #include <__cxx03/__memory/allocate_at_least.h>
0337 #include <__cxx03/__memory/allocator_traits.h>
0338 #include <__cxx03/__memory/pointer_traits.h>
0339 #include <__cxx03/__memory/swap_allocator.h>
0340 #include <__cxx03/__memory/temp_value.h>
0341 #include <__cxx03/__memory/uninitialized_algorithms.h>
0342 #include <__cxx03/__memory_resource/polymorphic_allocator.h>
0343 #include <__cxx03/__ranges/access.h>
0344 #include <__cxx03/__ranges/concepts.h>
0345 #include <__cxx03/__ranges/container_compatible_range.h>
0346 #include <__cxx03/__ranges/from_range.h>
0347 #include <__cxx03/__ranges/size.h>
0348 #include <__cxx03/__split_buffer>
0349 #include <__cxx03/__type_traits/is_allocator.h>
0350 #include <__cxx03/__type_traits/is_constructible.h>
0351 #include <__cxx03/__type_traits/is_nothrow_assignable.h>
0352 #include <__cxx03/__type_traits/noexcept_move_assign_container.h>
0353 #include <__cxx03/__type_traits/type_identity.h>
0354 #include <__cxx03/__utility/exception_guard.h>
0355 #include <__cxx03/__utility/forward.h>
0356 #include <__cxx03/__utility/is_pointer_in_range.h>
0357 #include <__cxx03/__utility/move.h>
0358 #include <__cxx03/__utility/pair.h>
0359 #include <__cxx03/__utility/swap.h>
0360 #include <__cxx03/climits>
0361 #include <__cxx03/cstring>
0362 #include <__cxx03/limits>
0363 #include <__cxx03/stdexcept>
0364 #include <__cxx03/version>
0365
0366 // standard-mandated includes
0367
0368 // [iterator.range]
0369 #include <__cxx03/__iterator/access.h>
0370 #include <__cxx03/__iterator/data.h>
0371 #include <__cxx03/__iterator/empty.h>
0372 #include <__cxx03/__iterator/reverse_access.h>
0373 #include <__cxx03/__iterator/size.h>
0374
0375 // [vector.syn]
0376 #include <__cxx03/compare>
0377 #include <__cxx03/initializer_list>
0378
0379 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0380 # pragma GCC system_header
0381 #endif
0382
0383 _LIBCPP_PUSH_MACROS
0384 #include <__cxx03/__undef_macros>
0385
0386 _LIBCPP_BEGIN_NAMESPACE_STD
0387
0388 template <class _Tp, class _Allocator /* = allocator<_Tp> */>
0389 class _LIBCPP_TEMPLATE_VIS vector {
0390 private:
0391 typedef allocator<_Tp> __default_allocator_type;
0392
0393 public:
0394 typedef vector __self;
0395 typedef _Tp value_type;
0396 typedef _Allocator allocator_type;
0397 typedef allocator_traits<allocator_type> __alloc_traits;
0398 typedef value_type& reference;
0399 typedef const value_type& const_reference;
0400 typedef typename __alloc_traits::size_type size_type;
0401 typedef typename __alloc_traits::difference_type difference_type;
0402 typedef typename __alloc_traits::pointer pointer;
0403 typedef typename __alloc_traits::const_pointer const_pointer;
0404 #ifdef _LIBCPP_ABI_BOUNDED_ITERATORS_IN_VECTOR
0405 // Users might provide custom allocators, and prior to C++20 we have no existing way to detect whether the allocator's
0406 // pointer type is contiguous (though it has to be by the Standard). Using the wrapper type ensures the iterator is
0407 // considered contiguous.
0408 typedef __bounded_iter<__wrap_iter<pointer>> iterator;
0409 typedef __bounded_iter<__wrap_iter<const_pointer>> const_iterator;
0410 #else
0411 typedef __wrap_iter<pointer> iterator;
0412 typedef __wrap_iter<const_pointer> const_iterator;
0413 #endif
0414 typedef std::reverse_iterator<iterator> reverse_iterator;
0415 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
0416
0417 // A vector containers the following members which may be trivially relocatable:
0418 // - pointer: may be trivially relocatable, so it's checked
0419 // - allocator_type: may be trivially relocatable, so it's checked
0420 // vector doesn't contain any self-references, so it's trivially relocatable if its members are.
0421 using __trivially_relocatable = __conditional_t<
0422 __libcpp_is_trivially_relocatable<pointer>::value && __libcpp_is_trivially_relocatable<allocator_type>::value,
0423 vector,
0424 void>;
0425
0426 static_assert(__check_valid_allocator<allocator_type>::value, "");
0427 static_assert(is_same<typename allocator_type::value_type, value_type>::value,
0428 "Allocator::value_type must be same type as value_type");
0429
0430 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector()
0431 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) {}
0432 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit vector(const allocator_type& __a)
0433 #if _LIBCPP_STD_VER <= 14
0434 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
0435 #else
0436 _NOEXCEPT
0437 #endif
0438 : __end_cap_(nullptr, __a) {
0439 }
0440
0441 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit vector(size_type __n) {
0442 auto __guard = std::__make_exception_guard(__destroy_vector(*this));
0443 if (__n > 0) {
0444 __vallocate(__n);
0445 __construct_at_end(__n);
0446 }
0447 __guard.__complete();
0448 }
0449
0450 #if _LIBCPP_STD_VER >= 14
0451 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit vector(size_type __n, const allocator_type& __a)
0452 : __end_cap_(nullptr, __a) {
0453 auto __guard = std::__make_exception_guard(__destroy_vector(*this));
0454 if (__n > 0) {
0455 __vallocate(__n);
0456 __construct_at_end(__n);
0457 }
0458 __guard.__complete();
0459 }
0460 #endif
0461
0462 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector(size_type __n, const value_type& __x) {
0463 auto __guard = std::__make_exception_guard(__destroy_vector(*this));
0464 if (__n > 0) {
0465 __vallocate(__n);
0466 __construct_at_end(__n, __x);
0467 }
0468 __guard.__complete();
0469 }
0470
0471 template <__enable_if_t<__is_allocator<_Allocator>::value, int> = 0>
0472 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
0473 vector(size_type __n, const value_type& __x, const allocator_type& __a)
0474 : __end_cap_(nullptr, __a) {
0475 if (__n > 0) {
0476 __vallocate(__n);
0477 __construct_at_end(__n, __x);
0478 }
0479 }
0480
0481 template <class _InputIterator,
0482 __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value &&
0483 is_constructible<value_type, typename iterator_traits<_InputIterator>::reference>::value,
0484 int> = 0>
0485 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector(_InputIterator __first, _InputIterator __last);
0486 template <class _InputIterator,
0487 __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value &&
0488 is_constructible<value_type, typename iterator_traits<_InputIterator>::reference>::value,
0489 int> = 0>
0490 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
0491 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a);
0492
0493 template <
0494 class _ForwardIterator,
0495 __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value &&
0496 is_constructible<value_type, typename iterator_traits<_ForwardIterator>::reference>::value,
0497 int> = 0>
0498 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector(_ForwardIterator __first, _ForwardIterator __last);
0499
0500 template <
0501 class _ForwardIterator,
0502 __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value &&
0503 is_constructible<value_type, typename iterator_traits<_ForwardIterator>::reference>::value,
0504 int> = 0>
0505 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
0506 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a);
0507
0508 #if _LIBCPP_STD_VER >= 23
0509 template <_ContainerCompatibleRange<_Tp> _Range>
0510 _LIBCPP_HIDE_FROM_ABI constexpr vector(
0511 from_range_t, _Range&& __range, const allocator_type& __alloc = allocator_type())
0512 : __end_cap_(nullptr, __alloc) {
0513 if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
0514 auto __n = static_cast<size_type>(ranges::distance(__range));
0515 __init_with_size(ranges::begin(__range), ranges::end(__range), __n);
0516
0517 } else {
0518 __init_with_sentinel(ranges::begin(__range), ranges::end(__range));
0519 }
0520 }
0521 #endif
0522
0523 private:
0524 class __destroy_vector {
0525 public:
0526 _LIBCPP_CONSTEXPR _LIBCPP_HIDE_FROM_ABI __destroy_vector(vector& __vec) : __vec_(__vec) {}
0527
0528 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void operator()() {
0529 if (__vec_.__begin_ != nullptr) {
0530 __vec_.__clear();
0531 __vec_.__annotate_delete();
0532 __alloc_traits::deallocate(__vec_.__alloc(), __vec_.__begin_, __vec_.capacity());
0533 }
0534 }
0535
0536 private:
0537 vector& __vec_;
0538 };
0539
0540 public:
0541 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI ~vector() { __destroy_vector (*this)(); }
0542
0543 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector(const vector& __x);
0544 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
0545 vector(const vector& __x, const __type_identity_t<allocator_type>& __a);
0546 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector& operator=(const vector& __x);
0547
0548 #ifndef _LIBCPP_CXX03_LANG
0549 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector(initializer_list<value_type> __il);
0550
0551 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
0552 vector(initializer_list<value_type> __il, const allocator_type& __a);
0553
0554 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector& operator=(initializer_list<value_type> __il) {
0555 assign(__il.begin(), __il.end());
0556 return *this;
0557 }
0558 #endif // !_LIBCPP_CXX03_LANG
0559
0560 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector(vector&& __x)
0561 #if _LIBCPP_STD_VER >= 17
0562 noexcept;
0563 #else
0564 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
0565 #endif
0566
0567 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
0568 vector(vector&& __x, const __type_identity_t<allocator_type>& __a);
0569 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector& operator=(vector&& __x)
0570 _NOEXCEPT_(__noexcept_move_assign_container<_Allocator, __alloc_traits>::value);
0571
0572 template <class _InputIterator,
0573 __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value &&
0574 is_constructible<value_type, typename iterator_traits<_InputIterator>::reference>::value,
0575 int> = 0>
0576 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void assign(_InputIterator __first, _InputIterator __last);
0577 template <
0578 class _ForwardIterator,
0579 __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value &&
0580 is_constructible<value_type, typename iterator_traits<_ForwardIterator>::reference>::value,
0581 int> = 0>
0582 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void assign(_ForwardIterator __first, _ForwardIterator __last);
0583
0584 #if _LIBCPP_STD_VER >= 23
0585 template <_ContainerCompatibleRange<_Tp> _Range>
0586 _LIBCPP_HIDE_FROM_ABI constexpr void assign_range(_Range&& __range) {
0587 if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
0588 auto __n = static_cast<size_type>(ranges::distance(__range));
0589 __assign_with_size(ranges::begin(__range), ranges::end(__range), __n);
0590
0591 } else {
0592 __assign_with_sentinel(ranges::begin(__range), ranges::end(__range));
0593 }
0594 }
0595 #endif
0596
0597 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const_reference __u);
0598
0599 #ifndef _LIBCPP_CXX03_LANG
0600 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void assign(initializer_list<value_type> __il) {
0601 assign(__il.begin(), __il.end());
0602 }
0603 #endif
0604
0605 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
0606 return this->__alloc();
0607 }
0608
0609 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT;
0610 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT;
0611 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT;
0612 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT;
0613
0614 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT {
0615 return reverse_iterator(end());
0616 }
0617 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT {
0618 return const_reverse_iterator(end());
0619 }
0620 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT {
0621 return reverse_iterator(begin());
0622 }
0623 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT {
0624 return const_reverse_iterator(begin());
0625 }
0626
0627 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
0628 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
0629 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT {
0630 return rbegin();
0631 }
0632 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
0633
0634 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT {
0635 return static_cast<size_type>(this->__end_ - this->__begin_);
0636 }
0637 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type capacity() const _NOEXCEPT {
0638 return static_cast<size_type>(__end_cap() - this->__begin_);
0639 }
0640 _LIBCPP_NODISCARD _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT {
0641 return this->__begin_ == this->__end_;
0642 }
0643 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT;
0644 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n);
0645 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void shrink_to_fit() _NOEXCEPT;
0646
0647 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference operator[](size_type __n) _NOEXCEPT;
0648 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference operator[](size_type __n) const _NOEXCEPT;
0649 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference at(size_type __n);
0650 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference at(size_type __n) const;
0651
0652 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference front() _NOEXCEPT {
0653 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "front() called on an empty vector");
0654 return *this->__begin_;
0655 }
0656 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference front() const _NOEXCEPT {
0657 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "front() called on an empty vector");
0658 return *this->__begin_;
0659 }
0660 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference back() _NOEXCEPT {
0661 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "back() called on an empty vector");
0662 return *(this->__end_ - 1);
0663 }
0664 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference back() const _NOEXCEPT {
0665 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "back() called on an empty vector");
0666 return *(this->__end_ - 1);
0667 }
0668
0669 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI value_type* data() _NOEXCEPT {
0670 return std::__to_address(this->__begin_);
0671 }
0672
0673 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const value_type* data() const _NOEXCEPT {
0674 return std::__to_address(this->__begin_);
0675 }
0676
0677 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void push_back(const_reference __x);
0678
0679 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void push_back(value_type&& __x);
0680
0681 template <class... _Args>
0682 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
0683 #if _LIBCPP_STD_VER >= 17
0684 reference
0685 emplace_back(_Args&&... __args);
0686 #else
0687 void
0688 emplace_back(_Args&&... __args);
0689 #endif
0690
0691 #if _LIBCPP_STD_VER >= 23
0692 template <_ContainerCompatibleRange<_Tp> _Range>
0693 _LIBCPP_HIDE_FROM_ABI constexpr void append_range(_Range&& __range) {
0694 insert_range(end(), std::forward<_Range>(__range));
0695 }
0696 #endif
0697
0698 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void pop_back();
0699
0700 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __position, const_reference __x);
0701
0702 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __position, value_type&& __x);
0703 template <class... _Args>
0704 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator emplace(const_iterator __position, _Args&&... __args);
0705
0706 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
0707 insert(const_iterator __position, size_type __n, const_reference __x);
0708
0709 template <class _InputIterator,
0710 __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value &&
0711 is_constructible< value_type, typename iterator_traits<_InputIterator>::reference>::value,
0712 int> = 0>
0713 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
0714 insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
0715
0716 #if _LIBCPP_STD_VER >= 23
0717 template <_ContainerCompatibleRange<_Tp> _Range>
0718 _LIBCPP_HIDE_FROM_ABI constexpr iterator insert_range(const_iterator __position, _Range&& __range) {
0719 if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
0720 auto __n = static_cast<size_type>(ranges::distance(__range));
0721 return __insert_with_size(__position, ranges::begin(__range), ranges::end(__range), __n);
0722
0723 } else {
0724 return __insert_with_sentinel(__position, ranges::begin(__range), ranges::end(__range));
0725 }
0726 }
0727 #endif
0728
0729 template <
0730 class _ForwardIterator,
0731 __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value &&
0732 is_constructible< value_type, typename iterator_traits<_ForwardIterator>::reference>::value,
0733 int> = 0>
0734 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
0735 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
0736
0737 #ifndef _LIBCPP_CXX03_LANG
0738 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
0739 insert(const_iterator __position, initializer_list<value_type> __il) {
0740 return insert(__position, __il.begin(), __il.end());
0741 }
0742 #endif
0743
0744 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __position);
0745 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last);
0746
0747 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT {
0748 size_type __old_size = size();
0749 __clear();
0750 __annotate_shrink(__old_size);
0751 }
0752
0753 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void resize(size_type __sz);
0754 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void resize(size_type __sz, const_reference __x);
0755
0756 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void swap(vector&)
0757 #if _LIBCPP_STD_VER >= 14
0758 _NOEXCEPT;
0759 #else
0760 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>);
0761 #endif
0762
0763 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool __invariants() const;
0764
0765 private:
0766 pointer __begin_ = nullptr;
0767 pointer __end_ = nullptr;
0768 __compressed_pair<pointer, allocator_type> __end_cap_ =
0769 __compressed_pair<pointer, allocator_type>(nullptr, __default_init_tag());
0770
0771 // Allocate space for __n objects
0772 // throws length_error if __n > max_size()
0773 // throws (probably bad_alloc) if memory run out
0774 // Precondition: __begin_ == __end_ == __end_cap() == 0
0775 // Precondition: __n > 0
0776 // Postcondition: capacity() >= __n
0777 // Postcondition: size() == 0
0778 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __vallocate(size_type __n) {
0779 if (__n > max_size())
0780 __throw_length_error();
0781 auto __allocation = std::__allocate_at_least(__alloc(), __n);
0782 __begin_ = __allocation.ptr;
0783 __end_ = __allocation.ptr;
0784 __end_cap() = __begin_ + __allocation.count;
0785 __annotate_new(0);
0786 }
0787
0788 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __vdeallocate() _NOEXCEPT;
0789 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type __recommend(size_type __new_size) const;
0790 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(size_type __n);
0791 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(size_type __n, const_reference __x);
0792
0793 template <class _InputIterator, class _Sentinel>
0794 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
0795 __init_with_size(_InputIterator __first, _Sentinel __last, size_type __n) {
0796 auto __guard = std::__make_exception_guard(__destroy_vector(*this));
0797
0798 if (__n > 0) {
0799 __vallocate(__n);
0800 __construct_at_end(__first, __last, __n);
0801 }
0802
0803 __guard.__complete();
0804 }
0805
0806 template <class _InputIterator, class _Sentinel>
0807 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
0808 __init_with_sentinel(_InputIterator __first, _Sentinel __last) {
0809 auto __guard = std::__make_exception_guard(__destroy_vector(*this));
0810
0811 for (; __first != __last; ++__first)
0812 emplace_back(*__first);
0813
0814 __guard.__complete();
0815 }
0816
0817 template <class _Iterator, class _Sentinel>
0818 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __assign_with_sentinel(_Iterator __first, _Sentinel __last);
0819
0820 template <class _ForwardIterator, class _Sentinel>
0821 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
0822 __assign_with_size(_ForwardIterator __first, _Sentinel __last, difference_type __n);
0823
0824 template <class _InputIterator, class _Sentinel>
0825 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
0826 __insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last);
0827
0828 template <class _Iterator, class _Sentinel>
0829 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
0830 __insert_with_size(const_iterator __position, _Iterator __first, _Sentinel __last, difference_type __n);
0831
0832 template <class _InputIterator, class _Sentinel>
0833 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
0834 __construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n);
0835
0836 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __append(size_type __n);
0837 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __append(size_type __n, const_reference __x);
0838
0839 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator __make_iter(pointer __p) _NOEXCEPT {
0840 #ifdef _LIBCPP_ABI_BOUNDED_ITERATORS_IN_VECTOR
0841 // Bound the iterator according to the capacity, rather than the size.
0842 //
0843 // Vector guarantees that iterators stay valid as long as no reallocation occurs even if new elements are inserted
0844 // into the container; for these cases, we need to make sure that the newly-inserted elements can be accessed
0845 // through the bounded iterator without failing checks. The downside is that the bounded iterator won't catch
0846 // access that is logically out-of-bounds, i.e., goes beyond the size, but is still within the capacity. With the
0847 // current implementation, there is no connection between a bounded iterator and its associated container, so we
0848 // don't have a way to update existing valid iterators when the container is resized and thus have to go with
0849 // a laxer approach.
0850 return std::__make_bounded_iter(
0851 std::__wrap_iter<pointer>(__p),
0852 std::__wrap_iter<pointer>(this->__begin_),
0853 std::__wrap_iter<pointer>(this->__end_cap()));
0854 #else
0855 return iterator(__p);
0856 #endif // _LIBCPP_ABI_BOUNDED_ITERATORS_IN_VECTOR
0857 }
0858
0859 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator __make_iter(const_pointer __p) const _NOEXCEPT {
0860 #ifdef _LIBCPP_ABI_BOUNDED_ITERATORS_IN_VECTOR
0861 // Bound the iterator according to the capacity, rather than the size.
0862 return std::__make_bounded_iter(
0863 std::__wrap_iter<const_pointer>(__p),
0864 std::__wrap_iter<const_pointer>(this->__begin_),
0865 std::__wrap_iter<const_pointer>(this->__end_cap()));
0866 #else
0867 return const_iterator(__p);
0868 #endif // _LIBCPP_ABI_BOUNDED_ITERATORS_IN_VECTOR
0869 }
0870
0871 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
0872 __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v);
0873 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer
0874 __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p);
0875 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
0876 __move_range(pointer __from_s, pointer __from_e, pointer __to);
0877 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign(vector& __c, true_type)
0878 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
0879 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign(vector& __c, false_type)
0880 _NOEXCEPT_(__alloc_traits::is_always_equal::value);
0881 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __destruct_at_end(pointer __new_last) _NOEXCEPT {
0882 size_type __old_size = size();
0883 __base_destruct_at_end(__new_last);
0884 __annotate_shrink(__old_size);
0885 }
0886
0887 template <class _Up>
0888 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI inline pointer __push_back_slow_path(_Up&& __x);
0889
0890 template <class... _Args>
0891 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI inline pointer __emplace_back_slow_path(_Args&&... __args);
0892
0893 // The following functions are no-ops outside of AddressSanitizer mode.
0894 // We call annotations for every allocator, unless explicitly disabled.
0895 //
0896 // To disable annotations for a particular allocator, change value of
0897 // __asan_annotate_container_with_allocator to false.
0898 // For more details, see the "Using libc++" documentation page or
0899 // the documentation for __sanitizer_annotate_contiguous_container.
0900
0901 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
0902 __annotate_contiguous_container(const void* __old_mid, const void* __new_mid) const {
0903 std::__annotate_contiguous_container<_Allocator>(data(), data() + capacity(), __old_mid, __new_mid);
0904 }
0905
0906 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __annotate_new(size_type __current_size) const _NOEXCEPT {
0907 (void)__current_size;
0908 #ifndef _LIBCPP_HAS_NO_ASAN
0909 __annotate_contiguous_container(data() + capacity(), data() + __current_size);
0910 #endif
0911 }
0912
0913 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __annotate_delete() const _NOEXCEPT {
0914 #ifndef _LIBCPP_HAS_NO_ASAN
0915 __annotate_contiguous_container(data() + size(), data() + capacity());
0916 #endif
0917 }
0918
0919 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __annotate_increase(size_type __n) const _NOEXCEPT {
0920 (void)__n;
0921 #ifndef _LIBCPP_HAS_NO_ASAN
0922 __annotate_contiguous_container(data() + size(), data() + size() + __n);
0923 #endif
0924 }
0925
0926 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __annotate_shrink(size_type __old_size) const _NOEXCEPT {
0927 (void)__old_size;
0928 #ifndef _LIBCPP_HAS_NO_ASAN
0929 __annotate_contiguous_container(data() + __old_size, data() + size());
0930 #endif
0931 }
0932
0933 struct _ConstructTransaction {
0934 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit _ConstructTransaction(vector& __v, size_type __n)
0935 : __v_(__v), __pos_(__v.__end_), __new_end_(__v.__end_ + __n) {
0936 #ifndef _LIBCPP_HAS_NO_ASAN
0937 __v_.__annotate_increase(__n);
0938 #endif
0939 }
0940
0941 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI ~_ConstructTransaction() {
0942 __v_.__end_ = __pos_;
0943 #ifndef _LIBCPP_HAS_NO_ASAN
0944 if (__pos_ != __new_end_) {
0945 __v_.__annotate_shrink(__new_end_ - __v_.__begin_);
0946 }
0947 #endif
0948 }
0949
0950 vector& __v_;
0951 pointer __pos_;
0952 const_pointer const __new_end_;
0953
0954 _ConstructTransaction(_ConstructTransaction const&) = delete;
0955 _ConstructTransaction& operator=(_ConstructTransaction const&) = delete;
0956 };
0957
0958 template <class... _Args>
0959 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __construct_one_at_end(_Args&&... __args) {
0960 _ConstructTransaction __tx(*this, 1);
0961 __alloc_traits::construct(this->__alloc(), std::__to_address(__tx.__pos_), std::forward<_Args>(__args)...);
0962 ++__tx.__pos_;
0963 }
0964
0965 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI allocator_type& __alloc() _NOEXCEPT {
0966 return this->__end_cap_.second();
0967 }
0968 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const allocator_type& __alloc() const _NOEXCEPT {
0969 return this->__end_cap_.second();
0970 }
0971 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer& __end_cap() _NOEXCEPT {
0972 return this->__end_cap_.first();
0973 }
0974 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const pointer& __end_cap() const _NOEXCEPT {
0975 return this->__end_cap_.first();
0976 }
0977
0978 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __clear() _NOEXCEPT {
0979 __base_destruct_at_end(this->__begin_);
0980 }
0981
0982 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __base_destruct_at_end(pointer __new_last) _NOEXCEPT {
0983 pointer __soon_to_be_end = this->__end_;
0984 while (__new_last != __soon_to_be_end)
0985 __alloc_traits::destroy(__alloc(), std::__to_address(--__soon_to_be_end));
0986 this->__end_ = __new_last;
0987 }
0988
0989 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const vector& __c) {
0990 __copy_assign_alloc(__c, integral_constant<bool, __alloc_traits::propagate_on_container_copy_assignment::value>());
0991 }
0992
0993 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(vector& __c)
0994 _NOEXCEPT_(!__alloc_traits::propagate_on_container_move_assignment::value ||
0995 is_nothrow_move_assignable<allocator_type>::value) {
0996 __move_assign_alloc(__c, integral_constant<bool, __alloc_traits::propagate_on_container_move_assignment::value>());
0997 }
0998
0999 _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI void __throw_length_error() const { std::__throw_length_error("vector"); }
1000
1001 _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI void __throw_out_of_range() const { std::__throw_out_of_range("vector"); }
1002
1003 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const vector& __c, true_type) {
1004 if (__alloc() != __c.__alloc()) {
1005 __clear();
1006 __annotate_delete();
1007 __alloc_traits::deallocate(__alloc(), this->__begin_, capacity());
1008 this->__begin_ = this->__end_ = __end_cap() = nullptr;
1009 }
1010 __alloc() = __c.__alloc();
1011 }
1012
1013 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const vector&, false_type) {}
1014
1015 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(vector& __c, true_type)
1016 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {
1017 __alloc() = std::move(__c.__alloc());
1018 }
1019
1020 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(vector&, false_type) _NOEXCEPT {}
1021 };
1022
1023 #if _LIBCPP_STD_VER >= 17
1024 template <class _InputIterator,
1025 class _Alloc = allocator<__iter_value_type<_InputIterator>>,
1026 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1027 class = enable_if_t<__is_allocator<_Alloc>::value> >
1028 vector(_InputIterator, _InputIterator) -> vector<__iter_value_type<_InputIterator>, _Alloc>;
1029
1030 template <class _InputIterator,
1031 class _Alloc,
1032 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1033 class = enable_if_t<__is_allocator<_Alloc>::value> >
1034 vector(_InputIterator, _InputIterator, _Alloc) -> vector<__iter_value_type<_InputIterator>, _Alloc>;
1035 #endif
1036
1037 #if _LIBCPP_STD_VER >= 23
1038 template <ranges::input_range _Range,
1039 class _Alloc = allocator<ranges::range_value_t<_Range>>,
1040 class = enable_if_t<__is_allocator<_Alloc>::value> >
1041 vector(from_range_t, _Range&&, _Alloc = _Alloc()) -> vector<ranges::range_value_t<_Range>, _Alloc>;
1042 #endif
1043
1044 // __swap_out_circular_buffer relocates the objects in [__begin_, __end_) into the front of __v and swaps the buffers of
1045 // *this and __v. It is assumed that __v provides space for exactly (__end_ - __begin_) objects in the front. This
1046 // function has a strong exception guarantee.
1047 template <class _Tp, class _Allocator>
1048 _LIBCPP_CONSTEXPR_SINCE_CXX20 void
1049 vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v) {
1050 __annotate_delete();
1051 auto __new_begin = __v.__begin_ - (__end_ - __begin_);
1052 std::__uninitialized_allocator_relocate(
1053 __alloc(), std::__to_address(__begin_), std::__to_address(__end_), std::__to_address(__new_begin));
1054 __v.__begin_ = __new_begin;
1055 __end_ = __begin_; // All the objects have been destroyed by relocating them.
1056 std::swap(this->__begin_, __v.__begin_);
1057 std::swap(this->__end_, __v.__end_);
1058 std::swap(this->__end_cap(), __v.__end_cap());
1059 __v.__first_ = __v.__begin_;
1060 __annotate_new(size());
1061 }
1062
1063 // __swap_out_circular_buffer relocates the objects in [__begin_, __p) into the front of __v, the objects in
1064 // [__p, __end_) into the back of __v and swaps the buffers of *this and __v. It is assumed that __v provides space for
1065 // exactly (__p - __begin_) objects in the front and space for at least (__end_ - __p) objects in the back. This
1066 // function has a strong exception guarantee if __begin_ == __p || __end_ == __p.
1067 template <class _Tp, class _Allocator>
1068 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::pointer
1069 vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p) {
1070 __annotate_delete();
1071 pointer __ret = __v.__begin_;
1072
1073 // Relocate [__p, __end_) first to avoid having a hole in [__begin_, __end_)
1074 // in case something in [__begin_, __p) throws.
1075 std::__uninitialized_allocator_relocate(
1076 __alloc(), std::__to_address(__p), std::__to_address(__end_), std::__to_address(__v.__end_));
1077 __v.__end_ += (__end_ - __p);
1078 __end_ = __p; // The objects in [__p, __end_) have been destroyed by relocating them.
1079 auto __new_begin = __v.__begin_ - (__p - __begin_);
1080
1081 std::__uninitialized_allocator_relocate(
1082 __alloc(), std::__to_address(__begin_), std::__to_address(__p), std::__to_address(__new_begin));
1083 __v.__begin_ = __new_begin;
1084 __end_ = __begin_; // All the objects have been destroyed by relocating them.
1085
1086 std::swap(this->__begin_, __v.__begin_);
1087 std::swap(this->__end_, __v.__end_);
1088 std::swap(this->__end_cap(), __v.__end_cap());
1089 __v.__first_ = __v.__begin_;
1090 __annotate_new(size());
1091 return __ret;
1092 }
1093
1094 template <class _Tp, class _Allocator>
1095 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::__vdeallocate() _NOEXCEPT {
1096 if (this->__begin_ != nullptr) {
1097 clear();
1098 __annotate_delete();
1099 __alloc_traits::deallocate(this->__alloc(), this->__begin_, capacity());
1100 this->__begin_ = this->__end_ = this->__end_cap() = nullptr;
1101 }
1102 }
1103
1104 template <class _Tp, class _Allocator>
1105 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::size_type
1106 vector<_Tp, _Allocator>::max_size() const _NOEXCEPT {
1107 return std::min<size_type>(__alloc_traits::max_size(this->__alloc()), numeric_limits<difference_type>::max());
1108 }
1109
1110 // Precondition: __new_size > capacity()
1111 template <class _Tp, class _Allocator>
1112 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::size_type
1113 vector<_Tp, _Allocator>::__recommend(size_type __new_size) const {
1114 const size_type __ms = max_size();
1115 if (__new_size > __ms)
1116 this->__throw_length_error();
1117 const size_type __cap = capacity();
1118 if (__cap >= __ms / 2)
1119 return __ms;
1120 return std::max<size_type>(2 * __cap, __new_size);
1121 }
1122
1123 // Default constructs __n objects starting at __end_
1124 // throws if construction throws
1125 // Precondition: __n > 0
1126 // Precondition: size() + __n <= capacity()
1127 // Postcondition: size() == size() + __n
1128 template <class _Tp, class _Allocator>
1129 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::__construct_at_end(size_type __n) {
1130 _ConstructTransaction __tx(*this, __n);
1131 const_pointer __new_end = __tx.__new_end_;
1132 for (pointer __pos = __tx.__pos_; __pos != __new_end; __tx.__pos_ = ++__pos) {
1133 __alloc_traits::construct(this->__alloc(), std::__to_address(__pos));
1134 }
1135 }
1136
1137 // Copy constructs __n objects starting at __end_ from __x
1138 // throws if construction throws
1139 // Precondition: __n > 0
1140 // Precondition: size() + __n <= capacity()
1141 // Postcondition: size() == old size() + __n
1142 // Postcondition: [i] == __x for all i in [size() - __n, __n)
1143 template <class _Tp, class _Allocator>
1144 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline void
1145 vector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x) {
1146 _ConstructTransaction __tx(*this, __n);
1147 const_pointer __new_end = __tx.__new_end_;
1148 for (pointer __pos = __tx.__pos_; __pos != __new_end; __tx.__pos_ = ++__pos) {
1149 __alloc_traits::construct(this->__alloc(), std::__to_address(__pos), __x);
1150 }
1151 }
1152
1153 template <class _Tp, class _Allocator>
1154 template <class _InputIterator, class _Sentinel>
1155 _LIBCPP_CONSTEXPR_SINCE_CXX20 void
1156 vector<_Tp, _Allocator>::__construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n) {
1157 _ConstructTransaction __tx(*this, __n);
1158 __tx.__pos_ = std::__uninitialized_allocator_copy(__alloc(), __first, __last, __tx.__pos_);
1159 }
1160
1161 // Default constructs __n objects starting at __end_
1162 // throws if construction throws
1163 // Postcondition: size() == size() + __n
1164 // Exception safety: strong.
1165 template <class _Tp, class _Allocator>
1166 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::__append(size_type __n) {
1167 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
1168 this->__construct_at_end(__n);
1169 else {
1170 allocator_type& __a = this->__alloc();
1171 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
1172 __v.__construct_at_end(__n);
1173 __swap_out_circular_buffer(__v);
1174 }
1175 }
1176
1177 // Default constructs __n objects starting at __end_
1178 // throws if construction throws
1179 // Postcondition: size() == size() + __n
1180 // Exception safety: strong.
1181 template <class _Tp, class _Allocator>
1182 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::__append(size_type __n, const_reference __x) {
1183 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
1184 this->__construct_at_end(__n, __x);
1185 else {
1186 allocator_type& __a = this->__alloc();
1187 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
1188 __v.__construct_at_end(__n, __x);
1189 __swap_out_circular_buffer(__v);
1190 }
1191 }
1192
1193 template <class _Tp, class _Allocator>
1194 template <class _InputIterator,
1195 __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value &&
1196 is_constructible<_Tp, typename iterator_traits<_InputIterator>::reference>::value,
1197 int> >
1198 _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last) {
1199 __init_with_sentinel(__first, __last);
1200 }
1201
1202 template <class _Tp, class _Allocator>
1203 template <class _InputIterator,
1204 __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value &&
1205 is_constructible<_Tp, typename iterator_traits<_InputIterator>::reference>::value,
1206 int> >
1207 _LIBCPP_CONSTEXPR_SINCE_CXX20
1208 vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a)
1209 : __end_cap_(nullptr, __a) {
1210 __init_with_sentinel(__first, __last);
1211 }
1212
1213 template <class _Tp, class _Allocator>
1214 template <class _ForwardIterator,
1215 __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value &&
1216 is_constructible<_Tp, typename iterator_traits<_ForwardIterator>::reference>::value,
1217 int> >
1218 _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last) {
1219 size_type __n = static_cast<size_type>(std::distance(__first, __last));
1220 __init_with_size(__first, __last, __n);
1221 }
1222
1223 template <class _Tp, class _Allocator>
1224 template <class _ForwardIterator,
1225 __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value &&
1226 is_constructible<_Tp, typename iterator_traits<_ForwardIterator>::reference>::value,
1227 int> >
1228 _LIBCPP_CONSTEXPR_SINCE_CXX20
1229 vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a)
1230 : __end_cap_(nullptr, __a) {
1231 size_type __n = static_cast<size_type>(std::distance(__first, __last));
1232 __init_with_size(__first, __last, __n);
1233 }
1234
1235 template <class _Tp, class _Allocator>
1236 _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<_Tp, _Allocator>::vector(const vector& __x)
1237 : __end_cap_(nullptr, __alloc_traits::select_on_container_copy_construction(__x.__alloc())) {
1238 __init_with_size(__x.__begin_, __x.__end_, __x.size());
1239 }
1240
1241 template <class _Tp, class _Allocator>
1242 _LIBCPP_CONSTEXPR_SINCE_CXX20
1243 vector<_Tp, _Allocator>::vector(const vector& __x, const __type_identity_t<allocator_type>& __a)
1244 : __end_cap_(nullptr, __a) {
1245 __init_with_size(__x.__begin_, __x.__end_, __x.size());
1246 }
1247
1248 template <class _Tp, class _Allocator>
1249 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI vector<_Tp, _Allocator>::vector(vector&& __x)
1250 #if _LIBCPP_STD_VER >= 17
1251 noexcept
1252 #else
1253 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
1254 #endif
1255 : __end_cap_(nullptr, std::move(__x.__alloc())) {
1256 this->__begin_ = __x.__begin_;
1257 this->__end_ = __x.__end_;
1258 this->__end_cap() = __x.__end_cap();
1259 __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
1260 }
1261
1262 template <class _Tp, class _Allocator>
1263 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI
1264 vector<_Tp, _Allocator>::vector(vector&& __x, const __type_identity_t<allocator_type>& __a)
1265 : __end_cap_(nullptr, __a) {
1266 if (__a == __x.__alloc()) {
1267 this->__begin_ = __x.__begin_;
1268 this->__end_ = __x.__end_;
1269 this->__end_cap() = __x.__end_cap();
1270 __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
1271 } else {
1272 typedef move_iterator<iterator> _Ip;
1273 auto __guard = std::__make_exception_guard(__destroy_vector(*this));
1274 assign(_Ip(__x.begin()), _Ip(__x.end()));
1275 __guard.__complete();
1276 }
1277 }
1278
1279 #ifndef _LIBCPP_CXX03_LANG
1280
1281 template <class _Tp, class _Allocator>
1282 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI
1283 vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il) {
1284 auto __guard = std::__make_exception_guard(__destroy_vector(*this));
1285 if (__il.size() > 0) {
1286 __vallocate(__il.size());
1287 __construct_at_end(__il.begin(), __il.end(), __il.size());
1288 }
1289 __guard.__complete();
1290 }
1291
1292 template <class _Tp, class _Allocator>
1293 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI
1294 vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
1295 : __end_cap_(nullptr, __a) {
1296 auto __guard = std::__make_exception_guard(__destroy_vector(*this));
1297 if (__il.size() > 0) {
1298 __vallocate(__il.size());
1299 __construct_at_end(__il.begin(), __il.end(), __il.size());
1300 }
1301 __guard.__complete();
1302 }
1303
1304 #endif // _LIBCPP_CXX03_LANG
1305
1306 template <class _Tp, class _Allocator>
1307 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI vector<_Tp, _Allocator>&
1308 vector<_Tp, _Allocator>::operator=(vector&& __x)
1309 _NOEXCEPT_(__noexcept_move_assign_container<_Allocator, __alloc_traits>::value) {
1310 __move_assign(__x, integral_constant<bool, __alloc_traits::propagate_on_container_move_assignment::value>());
1311 return *this;
1312 }
1313
1314 template <class _Tp, class _Allocator>
1315 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::__move_assign(vector& __c, false_type)
1316 _NOEXCEPT_(__alloc_traits::is_always_equal::value) {
1317 if (__alloc() != __c.__alloc()) {
1318 typedef move_iterator<iterator> _Ip;
1319 assign(_Ip(__c.begin()), _Ip(__c.end()));
1320 } else
1321 __move_assign(__c, true_type());
1322 }
1323
1324 template <class _Tp, class _Allocator>
1325 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::__move_assign(vector& __c, true_type)
1326 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {
1327 __vdeallocate();
1328 __move_assign_alloc(__c); // this can throw
1329 this->__begin_ = __c.__begin_;
1330 this->__end_ = __c.__end_;
1331 this->__end_cap() = __c.__end_cap();
1332 __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr;
1333 }
1334
1335 template <class _Tp, class _Allocator>
1336 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI vector<_Tp, _Allocator>&
1337 vector<_Tp, _Allocator>::operator=(const vector& __x) {
1338 if (this != std::addressof(__x)) {
1339 __copy_assign_alloc(__x);
1340 assign(__x.__begin_, __x.__end_);
1341 }
1342 return *this;
1343 }
1344
1345 template <class _Tp, class _Allocator>
1346 template <class _InputIterator,
1347 __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value &&
1348 is_constructible<_Tp, typename iterator_traits<_InputIterator>::reference>::value,
1349 int> >
1350 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last) {
1351 __assign_with_sentinel(__first, __last);
1352 }
1353
1354 template <class _Tp, class _Allocator>
1355 template <class _Iterator, class _Sentinel>
1356 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
1357 vector<_Tp, _Allocator>::__assign_with_sentinel(_Iterator __first, _Sentinel __last) {
1358 clear();
1359 for (; __first != __last; ++__first)
1360 emplace_back(*__first);
1361 }
1362
1363 template <class _Tp, class _Allocator>
1364 template <class _ForwardIterator,
1365 __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value &&
1366 is_constructible<_Tp, typename iterator_traits<_ForwardIterator>::reference>::value,
1367 int> >
1368 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) {
1369 __assign_with_size(__first, __last, std::distance(__first, __last));
1370 }
1371
1372 template <class _Tp, class _Allocator>
1373 template <class _ForwardIterator, class _Sentinel>
1374 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
1375 vector<_Tp, _Allocator>::__assign_with_size(_ForwardIterator __first, _Sentinel __last, difference_type __n) {
1376 size_type __new_size = static_cast<size_type>(__n);
1377 if (__new_size <= capacity()) {
1378 if (__new_size > size()) {
1379 _ForwardIterator __mid = std::next(__first, size());
1380 std::copy(__first, __mid, this->__begin_);
1381 __construct_at_end(__mid, __last, __new_size - size());
1382 } else {
1383 pointer __m = std::__copy<_ClassicAlgPolicy>(__first, __last, this->__begin_).second;
1384 this->__destruct_at_end(__m);
1385 }
1386 } else {
1387 __vdeallocate();
1388 __vallocate(__recommend(__new_size));
1389 __construct_at_end(__first, __last, __new_size);
1390 }
1391 }
1392
1393 template <class _Tp, class _Allocator>
1394 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::assign(size_type __n, const_reference __u) {
1395 if (__n <= capacity()) {
1396 size_type __s = size();
1397 std::fill_n(this->__begin_, std::min(__n, __s), __u);
1398 if (__n > __s)
1399 __construct_at_end(__n - __s, __u);
1400 else
1401 this->__destruct_at_end(this->__begin_ + __n);
1402 } else {
1403 __vdeallocate();
1404 __vallocate(__recommend(static_cast<size_type>(__n)));
1405 __construct_at_end(__n, __u);
1406 }
1407 }
1408
1409 template <class _Tp, class _Allocator>
1410 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::iterator
1411 vector<_Tp, _Allocator>::begin() _NOEXCEPT {
1412 return __make_iter(this->__begin_);
1413 }
1414
1415 template <class _Tp, class _Allocator>
1416 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::const_iterator
1417 vector<_Tp, _Allocator>::begin() const _NOEXCEPT {
1418 return __make_iter(this->__begin_);
1419 }
1420
1421 template <class _Tp, class _Allocator>
1422 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::iterator
1423 vector<_Tp, _Allocator>::end() _NOEXCEPT {
1424 return __make_iter(this->__end_);
1425 }
1426
1427 template <class _Tp, class _Allocator>
1428 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::const_iterator
1429 vector<_Tp, _Allocator>::end() const _NOEXCEPT {
1430 return __make_iter(this->__end_);
1431 }
1432
1433 template <class _Tp, class _Allocator>
1434 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::reference
1435 vector<_Tp, _Allocator>::operator[](size_type __n) _NOEXCEPT {
1436 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__n < size(), "vector[] index out of bounds");
1437 return this->__begin_[__n];
1438 }
1439
1440 template <class _Tp, class _Allocator>
1441 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::const_reference
1442 vector<_Tp, _Allocator>::operator[](size_type __n) const _NOEXCEPT {
1443 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__n < size(), "vector[] index out of bounds");
1444 return this->__begin_[__n];
1445 }
1446
1447 template <class _Tp, class _Allocator>
1448 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::reference vector<_Tp, _Allocator>::at(size_type __n) {
1449 if (__n >= size())
1450 this->__throw_out_of_range();
1451 return this->__begin_[__n];
1452 }
1453
1454 template <class _Tp, class _Allocator>
1455 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::const_reference
1456 vector<_Tp, _Allocator>::at(size_type __n) const {
1457 if (__n >= size())
1458 this->__throw_out_of_range();
1459 return this->__begin_[__n];
1460 }
1461
1462 template <class _Tp, class _Allocator>
1463 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::reserve(size_type __n) {
1464 if (__n > capacity()) {
1465 if (__n > max_size())
1466 this->__throw_length_error();
1467 allocator_type& __a = this->__alloc();
1468 __split_buffer<value_type, allocator_type&> __v(__n, size(), __a);
1469 __swap_out_circular_buffer(__v);
1470 }
1471 }
1472
1473 template <class _Tp, class _Allocator>
1474 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT {
1475 if (capacity() > size()) {
1476 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1477 try {
1478 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1479 allocator_type& __a = this->__alloc();
1480 __split_buffer<value_type, allocator_type&> __v(size(), size(), __a);
1481 // The Standard mandates shrink_to_fit() does not increase the capacity.
1482 // With equal capacity keep the existing buffer. This avoids extra work
1483 // due to swapping the elements.
1484 if (__v.capacity() < capacity())
1485 __swap_out_circular_buffer(__v);
1486 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1487 } catch (...) {
1488 }
1489 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1490 }
1491 }
1492
1493 template <class _Tp, class _Allocator>
1494 template <class _Up>
1495 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::pointer
1496 vector<_Tp, _Allocator>::__push_back_slow_path(_Up&& __x) {
1497 allocator_type& __a = this->__alloc();
1498 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
1499 // __v.push_back(std::forward<_Up>(__x));
1500 __alloc_traits::construct(__a, std::__to_address(__v.__end_), std::forward<_Up>(__x));
1501 __v.__end_++;
1502 __swap_out_circular_buffer(__v);
1503 return this->__end_;
1504 }
1505
1506 template <class _Tp, class _Allocator>
1507 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI void
1508 vector<_Tp, _Allocator>::push_back(const_reference __x) {
1509 pointer __end = this->__end_;
1510 if (__end < this->__end_cap()) {
1511 __construct_one_at_end(__x);
1512 ++__end;
1513 } else {
1514 __end = __push_back_slow_path(__x);
1515 }
1516 this->__end_ = __end;
1517 }
1518
1519 template <class _Tp, class _Allocator>
1520 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI void vector<_Tp, _Allocator>::push_back(value_type&& __x) {
1521 pointer __end = this->__end_;
1522 if (__end < this->__end_cap()) {
1523 __construct_one_at_end(std::move(__x));
1524 ++__end;
1525 } else {
1526 __end = __push_back_slow_path(std::move(__x));
1527 }
1528 this->__end_ = __end;
1529 }
1530
1531 template <class _Tp, class _Allocator>
1532 template <class... _Args>
1533 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::pointer
1534 vector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args) {
1535 allocator_type& __a = this->__alloc();
1536 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
1537 // __v.emplace_back(std::forward<_Args>(__args)...);
1538 __alloc_traits::construct(__a, std::__to_address(__v.__end_), std::forward<_Args>(__args)...);
1539 __v.__end_++;
1540 __swap_out_circular_buffer(__v);
1541 return this->__end_;
1542 }
1543
1544 template <class _Tp, class _Allocator>
1545 template <class... _Args>
1546 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline
1547 #if _LIBCPP_STD_VER >= 17
1548 typename vector<_Tp, _Allocator>::reference
1549 #else
1550 void
1551 #endif
1552 vector<_Tp, _Allocator>::emplace_back(_Args&&... __args) {
1553 pointer __end = this->__end_;
1554 if (__end < this->__end_cap()) {
1555 __construct_one_at_end(std::forward<_Args>(__args)...);
1556 ++__end;
1557 } else {
1558 __end = __emplace_back_slow_path(std::forward<_Args>(__args)...);
1559 }
1560 this->__end_ = __end;
1561 #if _LIBCPP_STD_VER >= 17
1562 return *(__end - 1);
1563 #endif
1564 }
1565
1566 template <class _Tp, class _Allocator>
1567 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline void vector<_Tp, _Allocator>::pop_back() {
1568 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "vector::pop_back called on an empty vector");
1569 this->__destruct_at_end(this->__end_ - 1);
1570 }
1571
1572 template <class _Tp, class _Allocator>
1573 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::iterator
1574 vector<_Tp, _Allocator>::erase(const_iterator __position) {
1575 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
1576 __position != end(), "vector::erase(iterator) called with a non-dereferenceable iterator");
1577 difference_type __ps = __position - cbegin();
1578 pointer __p = this->__begin_ + __ps;
1579 this->__destruct_at_end(std::move(__p + 1, this->__end_, __p));
1580 return __make_iter(__p);
1581 }
1582
1583 template <class _Tp, class _Allocator>
1584 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator
1585 vector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last) {
1586 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__first <= __last, "vector::erase(first, last) called with invalid range");
1587 pointer __p = this->__begin_ + (__first - begin());
1588 if (__first != __last) {
1589 this->__destruct_at_end(std::move(__p + (__last - __first), this->__end_, __p));
1590 }
1591 return __make_iter(__p);
1592 }
1593
1594 template <class _Tp, class _Allocator>
1595 _LIBCPP_CONSTEXPR_SINCE_CXX20 void
1596 vector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to) {
1597 pointer __old_last = this->__end_;
1598 difference_type __n = __old_last - __to;
1599 {
1600 pointer __i = __from_s + __n;
1601 _ConstructTransaction __tx(*this, __from_e - __i);
1602 for (pointer __pos = __tx.__pos_; __i < __from_e; ++__i, (void)++__pos, __tx.__pos_ = __pos) {
1603 __alloc_traits::construct(this->__alloc(), std::__to_address(__pos), std::move(*__i));
1604 }
1605 }
1606 std::move_backward(__from_s, __from_s + __n, __old_last);
1607 }
1608
1609 template <class _Tp, class _Allocator>
1610 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator
1611 vector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x) {
1612 pointer __p = this->__begin_ + (__position - begin());
1613 if (this->__end_ < this->__end_cap()) {
1614 if (__p == this->__end_) {
1615 __construct_one_at_end(__x);
1616 } else {
1617 __move_range(__p, this->__end_, __p + 1);
1618 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1619 if (std::__is_pointer_in_range(std::__to_address(__p), std::__to_address(__end_), std::addressof(__x)))
1620 ++__xr;
1621 *__p = *__xr;
1622 }
1623 } else {
1624 allocator_type& __a = this->__alloc();
1625 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1626 __v.push_back(__x);
1627 __p = __swap_out_circular_buffer(__v, __p);
1628 }
1629 return __make_iter(__p);
1630 }
1631
1632 template <class _Tp, class _Allocator>
1633 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator
1634 vector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x) {
1635 pointer __p = this->__begin_ + (__position - begin());
1636 if (this->__end_ < this->__end_cap()) {
1637 if (__p == this->__end_) {
1638 __construct_one_at_end(std::move(__x));
1639 } else {
1640 __move_range(__p, this->__end_, __p + 1);
1641 *__p = std::move(__x);
1642 }
1643 } else {
1644 allocator_type& __a = this->__alloc();
1645 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1646 __v.push_back(std::move(__x));
1647 __p = __swap_out_circular_buffer(__v, __p);
1648 }
1649 return __make_iter(__p);
1650 }
1651
1652 template <class _Tp, class _Allocator>
1653 template <class... _Args>
1654 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator
1655 vector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args) {
1656 pointer __p = this->__begin_ + (__position - begin());
1657 if (this->__end_ < this->__end_cap()) {
1658 if (__p == this->__end_) {
1659 __construct_one_at_end(std::forward<_Args>(__args)...);
1660 } else {
1661 __temp_value<value_type, _Allocator> __tmp(this->__alloc(), std::forward<_Args>(__args)...);
1662 __move_range(__p, this->__end_, __p + 1);
1663 *__p = std::move(__tmp.get());
1664 }
1665 } else {
1666 allocator_type& __a = this->__alloc();
1667 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1668 __v.emplace_back(std::forward<_Args>(__args)...);
1669 __p = __swap_out_circular_buffer(__v, __p);
1670 }
1671 return __make_iter(__p);
1672 }
1673
1674 template <class _Tp, class _Allocator>
1675 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator
1676 vector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x) {
1677 pointer __p = this->__begin_ + (__position - begin());
1678 if (__n > 0) {
1679 // We can't compare unrelated pointers inside constant expressions
1680 if (!__libcpp_is_constant_evaluated() && __n <= static_cast<size_type>(this->__end_cap() - this->__end_)) {
1681 size_type __old_n = __n;
1682 pointer __old_last = this->__end_;
1683 if (__n > static_cast<size_type>(this->__end_ - __p)) {
1684 size_type __cx = __n - (this->__end_ - __p);
1685 __construct_at_end(__cx, __x);
1686 __n -= __cx;
1687 }
1688 if (__n > 0) {
1689 __move_range(__p, __old_last, __p + __old_n);
1690 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1691 if (__p <= __xr && __xr < this->__end_)
1692 __xr += __old_n;
1693 std::fill_n(__p, __n, *__xr);
1694 }
1695 } else {
1696 allocator_type& __a = this->__alloc();
1697 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
1698 __v.__construct_at_end(__n, __x);
1699 __p = __swap_out_circular_buffer(__v, __p);
1700 }
1701 }
1702 return __make_iter(__p);
1703 }
1704 template <class _Tp, class _Allocator>
1705 template <class _InputIterator,
1706 __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value &&
1707 is_constructible<_Tp, typename iterator_traits<_InputIterator>::reference>::value,
1708 int> >
1709 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator
1710 vector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) {
1711 return __insert_with_sentinel(__position, __first, __last);
1712 }
1713
1714 template <class _Tp, class _Allocator>
1715 template <class _InputIterator, class _Sentinel>
1716 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::iterator
1717 vector<_Tp, _Allocator>::__insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last) {
1718 difference_type __off = __position - begin();
1719 pointer __p = this->__begin_ + __off;
1720 allocator_type& __a = this->__alloc();
1721 pointer __old_last = this->__end_;
1722 for (; this->__end_ != this->__end_cap() && __first != __last; ++__first) {
1723 __construct_one_at_end(*__first);
1724 }
1725 __split_buffer<value_type, allocator_type&> __v(__a);
1726 if (__first != __last) {
1727 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1728 try {
1729 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1730 __v.__construct_at_end_with_sentinel(std::move(__first), std::move(__last));
1731 difference_type __old_size = __old_last - this->__begin_;
1732 difference_type __old_p = __p - this->__begin_;
1733 reserve(__recommend(size() + __v.size()));
1734 __p = this->__begin_ + __old_p;
1735 __old_last = this->__begin_ + __old_size;
1736 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1737 } catch (...) {
1738 erase(__make_iter(__old_last), end());
1739 throw;
1740 }
1741 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1742 }
1743 __p = std::rotate(__p, __old_last, this->__end_);
1744 insert(__make_iter(__p), std::make_move_iterator(__v.begin()), std::make_move_iterator(__v.end()));
1745 return begin() + __off;
1746 }
1747
1748 template <class _Tp, class _Allocator>
1749 template <class _ForwardIterator,
1750 __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value &&
1751 is_constructible<_Tp, typename iterator_traits<_ForwardIterator>::reference>::value,
1752 int> >
1753 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator
1754 vector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) {
1755 return __insert_with_size(__position, __first, __last, std::distance(__first, __last));
1756 }
1757
1758 template <class _Tp, class _Allocator>
1759 template <class _Iterator, class _Sentinel>
1760 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::iterator
1761 vector<_Tp, _Allocator>::__insert_with_size(
1762 const_iterator __position, _Iterator __first, _Sentinel __last, difference_type __n) {
1763 auto __insertion_size = __n;
1764 pointer __p = this->__begin_ + (__position - begin());
1765 if (__n > 0) {
1766 if (__n <= this->__end_cap() - this->__end_) {
1767 size_type __old_n = __n;
1768 pointer __old_last = this->__end_;
1769 _Iterator __m = std::next(__first, __n);
1770 difference_type __dx = this->__end_ - __p;
1771 if (__n > __dx) {
1772 __m = __first;
1773 difference_type __diff = this->__end_ - __p;
1774 std::advance(__m, __diff);
1775 __construct_at_end(__m, __last, __n - __diff);
1776 __n = __dx;
1777 }
1778 if (__n > 0) {
1779 __move_range(__p, __old_last, __p + __old_n);
1780 std::copy(__first, __m, __p);
1781 }
1782 } else {
1783 allocator_type& __a = this->__alloc();
1784 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
1785 __v.__construct_at_end_with_size(__first, __insertion_size);
1786 __p = __swap_out_circular_buffer(__v, __p);
1787 }
1788 }
1789 return __make_iter(__p);
1790 }
1791
1792 template <class _Tp, class _Allocator>
1793 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::resize(size_type __sz) {
1794 size_type __cs = size();
1795 if (__cs < __sz)
1796 this->__append(__sz - __cs);
1797 else if (__cs > __sz)
1798 this->__destruct_at_end(this->__begin_ + __sz);
1799 }
1800
1801 template <class _Tp, class _Allocator>
1802 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::resize(size_type __sz, const_reference __x) {
1803 size_type __cs = size();
1804 if (__cs < __sz)
1805 this->__append(__sz - __cs, __x);
1806 else if (__cs > __sz)
1807 this->__destruct_at_end(this->__begin_ + __sz);
1808 }
1809
1810 template <class _Tp, class _Allocator>
1811 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::swap(vector& __x)
1812 #if _LIBCPP_STD_VER >= 14
1813 _NOEXCEPT
1814 #else
1815 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>)
1816 #endif
1817 {
1818 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1819 __alloc_traits::propagate_on_container_swap::value || this->__alloc() == __x.__alloc(),
1820 "vector::swap: Either propagate_on_container_swap must be true"
1821 " or the allocators must compare equal");
1822 std::swap(this->__begin_, __x.__begin_);
1823 std::swap(this->__end_, __x.__end_);
1824 std::swap(this->__end_cap(), __x.__end_cap());
1825 std::__swap_allocator(
1826 this->__alloc(), __x.__alloc(), integral_constant<bool, __alloc_traits::propagate_on_container_swap::value>());
1827 }
1828
1829 template <class _Tp, class _Allocator>
1830 _LIBCPP_CONSTEXPR_SINCE_CXX20 bool vector<_Tp, _Allocator>::__invariants() const {
1831 if (this->__begin_ == nullptr) {
1832 if (this->__end_ != nullptr || this->__end_cap() != nullptr)
1833 return false;
1834 } else {
1835 if (this->__begin_ > this->__end_)
1836 return false;
1837 if (this->__begin_ == this->__end_cap())
1838 return false;
1839 if (this->__end_ > this->__end_cap())
1840 return false;
1841 }
1842 return true;
1843 }
1844
1845 // vector<bool>
1846
1847 template <class _Allocator>
1848 class vector<bool, _Allocator>;
1849
1850 template <class _Allocator>
1851 struct hash<vector<bool, _Allocator> >;
1852
1853 template <class _Allocator>
1854 struct __has_storage_type<vector<bool, _Allocator> > {
1855 static const bool value = true;
1856 };
1857
1858 template <class _Allocator>
1859 class _LIBCPP_TEMPLATE_VIS vector<bool, _Allocator> {
1860 public:
1861 typedef vector __self;
1862 typedef bool value_type;
1863 typedef _Allocator allocator_type;
1864 typedef allocator_traits<allocator_type> __alloc_traits;
1865 typedef typename __alloc_traits::size_type size_type;
1866 typedef typename __alloc_traits::difference_type difference_type;
1867 typedef size_type __storage_type;
1868 typedef __bit_iterator<vector, false> pointer;
1869 typedef __bit_iterator<vector, true> const_pointer;
1870 typedef pointer iterator;
1871 typedef const_pointer const_iterator;
1872 typedef std::reverse_iterator<iterator> reverse_iterator;
1873 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1874
1875 private:
1876 typedef __rebind_alloc<__alloc_traits, __storage_type> __storage_allocator;
1877 typedef allocator_traits<__storage_allocator> __storage_traits;
1878 typedef typename __storage_traits::pointer __storage_pointer;
1879 typedef typename __storage_traits::const_pointer __const_storage_pointer;
1880
1881 __storage_pointer __begin_;
1882 size_type __size_;
1883 __compressed_pair<size_type, __storage_allocator> __cap_alloc_;
1884
1885 public:
1886 typedef __bit_reference<vector> reference;
1887 #ifdef _LIBCPP_ABI_BITSET_VECTOR_BOOL_CONST_SUBSCRIPT_RETURN_BOOL
1888 using const_reference = bool;
1889 #else
1890 typedef __bit_const_reference<vector> const_reference;
1891 #endif
1892
1893 private:
1894 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type& __cap() _NOEXCEPT { return __cap_alloc_.first(); }
1895 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const size_type& __cap() const _NOEXCEPT {
1896 return __cap_alloc_.first();
1897 }
1898 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __storage_allocator& __alloc() _NOEXCEPT {
1899 return __cap_alloc_.second();
1900 }
1901 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const __storage_allocator& __alloc() const _NOEXCEPT {
1902 return __cap_alloc_.second();
1903 }
1904
1905 static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
1906
1907 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static size_type
1908 __internal_cap_to_external(size_type __n) _NOEXCEPT {
1909 return __n * __bits_per_word;
1910 }
1911 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static size_type
1912 __external_cap_to_internal(size_type __n) _NOEXCEPT {
1913 return (__n - 1) / __bits_per_word + 1;
1914 }
1915
1916 public:
1917 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector()
1918 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
1919
1920 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit vector(const allocator_type& __a)
1921 #if _LIBCPP_STD_VER <= 14
1922 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value);
1923 #else
1924 _NOEXCEPT;
1925 #endif
1926
1927 private:
1928 class __destroy_vector {
1929 public:
1930 _LIBCPP_CONSTEXPR _LIBCPP_HIDE_FROM_ABI __destroy_vector(vector& __vec) : __vec_(__vec) {}
1931
1932 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void operator()() {
1933 if (__vec_.__begin_ != nullptr)
1934 __storage_traits::deallocate(__vec_.__alloc(), __vec_.__begin_, __vec_.__cap());
1935 }
1936
1937 private:
1938 vector& __vec_;
1939 };
1940
1941 public:
1942 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 ~vector() { __destroy_vector (*this)(); }
1943
1944 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit vector(size_type __n);
1945 #if _LIBCPP_STD_VER >= 14
1946 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit vector(size_type __n, const allocator_type& __a);
1947 #endif
1948 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(size_type __n, const value_type& __v);
1949 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1950 vector(size_type __n, const value_type& __v, const allocator_type& __a);
1951 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>
1952 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(_InputIterator __first, _InputIterator __last);
1953 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>
1954 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1955 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a);
1956 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
1957 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(_ForwardIterator __first, _ForwardIterator __last);
1958 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
1959 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1960 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a);
1961
1962 #if _LIBCPP_STD_VER >= 23
1963 template <_ContainerCompatibleRange<bool> _Range>
1964 _LIBCPP_HIDE_FROM_ABI constexpr vector(from_range_t, _Range&& __range, const allocator_type& __a = allocator_type())
1965 : __begin_(nullptr), __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) {
1966 if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
1967 auto __n = static_cast<size_type>(ranges::distance(__range));
1968 __init_with_size(ranges::begin(__range), ranges::end(__range), __n);
1969
1970 } else {
1971 __init_with_sentinel(ranges::begin(__range), ranges::end(__range));
1972 }
1973 }
1974 #endif
1975
1976 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(const vector& __v);
1977 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(const vector& __v, const allocator_type& __a);
1978 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector& operator=(const vector& __v);
1979
1980 #ifndef _LIBCPP_CXX03_LANG
1981 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(initializer_list<value_type> __il);
1982 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1983 vector(initializer_list<value_type> __il, const allocator_type& __a);
1984
1985 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector& operator=(initializer_list<value_type> __il) {
1986 assign(__il.begin(), __il.end());
1987 return *this;
1988 }
1989
1990 #endif // !_LIBCPP_CXX03_LANG
1991
1992 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(vector&& __v)
1993 #if _LIBCPP_STD_VER >= 17
1994 noexcept;
1995 #else
1996 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
1997 #endif
1998 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1999 vector(vector&& __v, const __type_identity_t<allocator_type>& __a);
2000 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector& operator=(vector&& __v)
2001 _NOEXCEPT_(__noexcept_move_assign_container<_Allocator, __alloc_traits>::value);
2002
2003 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>
2004 void _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 assign(_InputIterator __first, _InputIterator __last);
2005 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
2006 void _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 assign(_ForwardIterator __first, _ForwardIterator __last);
2007
2008 #if _LIBCPP_STD_VER >= 23
2009 template <_ContainerCompatibleRange<bool> _Range>
2010 _LIBCPP_HIDE_FROM_ABI constexpr void assign_range(_Range&& __range) {
2011 if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
2012 auto __n = static_cast<size_type>(ranges::distance(__range));
2013 __assign_with_size(ranges::begin(__range), ranges::end(__range), __n);
2014
2015 } else {
2016 __assign_with_sentinel(ranges::begin(__range), ranges::end(__range));
2017 }
2018 }
2019 #endif
2020
2021 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void assign(size_type __n, const value_type& __x);
2022
2023 #ifndef _LIBCPP_CXX03_LANG
2024 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void assign(initializer_list<value_type> __il) {
2025 assign(__il.begin(), __il.end());
2026 }
2027 #endif
2028
2029 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 allocator_type get_allocator() const _NOEXCEPT {
2030 return allocator_type(this->__alloc());
2031 }
2032
2033 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type max_size() const _NOEXCEPT;
2034 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type capacity() const _NOEXCEPT {
2035 return __internal_cap_to_external(__cap());
2036 }
2037 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type size() const _NOEXCEPT { return __size_; }
2038 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool empty() const _NOEXCEPT {
2039 return __size_ == 0;
2040 }
2041 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void reserve(size_type __n);
2042 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void shrink_to_fit() _NOEXCEPT;
2043
2044 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator begin() _NOEXCEPT { return __make_iter(0); }
2045 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator begin() const _NOEXCEPT { return __make_iter(0); }
2046 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator end() _NOEXCEPT { return __make_iter(__size_); }
2047 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator end() const _NOEXCEPT {
2048 return __make_iter(__size_);
2049 }
2050
2051 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reverse_iterator rbegin() _NOEXCEPT {
2052 return reverse_iterator(end());
2053 }
2054 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reverse_iterator rbegin() const _NOEXCEPT {
2055 return const_reverse_iterator(end());
2056 }
2057 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reverse_iterator rend() _NOEXCEPT {
2058 return reverse_iterator(begin());
2059 }
2060 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reverse_iterator rend() const _NOEXCEPT {
2061 return const_reverse_iterator(begin());
2062 }
2063
2064 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator cbegin() const _NOEXCEPT { return __make_iter(0); }
2065 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator cend() const _NOEXCEPT {
2066 return __make_iter(__size_);
2067 }
2068 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reverse_iterator crbegin() const _NOEXCEPT {
2069 return rbegin();
2070 }
2071 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
2072
2073 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference operator[](size_type __n) { return __make_ref(__n); }
2074 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference operator[](size_type __n) const {
2075 return __make_ref(__n);
2076 }
2077 _LIBCPP_HIDE_FROM_ABI reference at(size_type __n);
2078 _LIBCPP_HIDE_FROM_ABI const_reference at(size_type __n) const;
2079
2080 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference front() { return __make_ref(0); }
2081 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference front() const { return __make_ref(0); }
2082 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference back() { return __make_ref(__size_ - 1); }
2083 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference back() const { return __make_ref(__size_ - 1); }
2084
2085 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void push_back(const value_type& __x);
2086 #if _LIBCPP_STD_VER >= 14
2087 template <class... _Args>
2088 # if _LIBCPP_STD_VER >= 17
2089 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference emplace_back(_Args&&... __args)
2090 # else
2091 _LIBCPP_HIDE_FROM_ABI void emplace_back(_Args&&... __args)
2092 # endif
2093 {
2094 push_back(value_type(std::forward<_Args>(__args)...));
2095 # if _LIBCPP_STD_VER >= 17
2096 return this->back();
2097 # endif
2098 }
2099 #endif
2100
2101 #if _LIBCPP_STD_VER >= 23
2102 template <_ContainerCompatibleRange<bool> _Range>
2103 _LIBCPP_HIDE_FROM_ABI constexpr void append_range(_Range&& __range) {
2104 insert_range(end(), std::forward<_Range>(__range));
2105 }
2106 #endif
2107
2108 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void pop_back() { --__size_; }
2109
2110 #if _LIBCPP_STD_VER >= 14
2111 template <class... _Args>
2112 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator emplace(const_iterator __position, _Args&&... __args) {
2113 return insert(__position, value_type(std::forward<_Args>(__args)...));
2114 }
2115 #endif
2116
2117 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator insert(const_iterator __position, const value_type& __x);
2118 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator
2119 insert(const_iterator __position, size_type __n, const value_type& __x);
2120 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>
2121 iterator _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
2122 insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
2123 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
2124 iterator _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
2125 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
2126
2127 #if _LIBCPP_STD_VER >= 23
2128 template <_ContainerCompatibleRange<bool> _Range>
2129 _LIBCPP_HIDE_FROM_ABI constexpr iterator insert_range(const_iterator __position, _Range&& __range) {
2130 if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
2131 auto __n = static_cast<size_type>(ranges::distance(__range));
2132 return __insert_with_size(__position, ranges::begin(__range), ranges::end(__range), __n);
2133
2134 } else {
2135 return __insert_with_sentinel(__position, ranges::begin(__range), ranges::end(__range));
2136 }
2137 }
2138 #endif
2139
2140 #ifndef _LIBCPP_CXX03_LANG
2141 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator
2142 insert(const_iterator __position, initializer_list<value_type> __il) {
2143 return insert(__position, __il.begin(), __il.end());
2144 }
2145 #endif
2146
2147 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator erase(const_iterator __position);
2148 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator erase(const_iterator __first, const_iterator __last);
2149
2150 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void clear() _NOEXCEPT { __size_ = 0; }
2151
2152 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void swap(vector&)
2153 #if _LIBCPP_STD_VER >= 14
2154 _NOEXCEPT;
2155 #else
2156 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>);
2157 #endif
2158 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static void swap(reference __x, reference __y) _NOEXCEPT {
2159 std::swap(__x, __y);
2160 }
2161
2162 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void resize(size_type __sz, value_type __x = false);
2163 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void flip() _NOEXCEPT;
2164
2165 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __invariants() const;
2166
2167 private:
2168 _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI void __throw_length_error() const { std::__throw_length_error("vector"); }
2169
2170 _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI void __throw_out_of_range() const { std::__throw_out_of_range("vector"); }
2171
2172 template <class _InputIterator, class _Sentinel>
2173 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
2174 __init_with_size(_InputIterator __first, _Sentinel __last, size_type __n) {
2175 auto __guard = std::__make_exception_guard(__destroy_vector(*this));
2176
2177 if (__n > 0) {
2178 __vallocate(__n);
2179 __construct_at_end(std::move(__first), std::move(__last), __n);
2180 }
2181
2182 __guard.__complete();
2183 }
2184
2185 template <class _InputIterator, class _Sentinel>
2186 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
2187 __init_with_sentinel(_InputIterator __first, _Sentinel __last) {
2188 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
2189 try {
2190 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
2191 for (; __first != __last; ++__first)
2192 push_back(*__first);
2193 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
2194 } catch (...) {
2195 if (__begin_ != nullptr)
2196 __storage_traits::deallocate(__alloc(), __begin_, __cap());
2197 throw;
2198 }
2199 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
2200 }
2201
2202 template <class _Iterator, class _Sentinel>
2203 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __assign_with_sentinel(_Iterator __first, _Sentinel __last);
2204
2205 template <class _ForwardIterator, class _Sentinel>
2206 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
2207 __assign_with_size(_ForwardIterator __first, _Sentinel __last, difference_type __ns);
2208
2209 template <class _InputIterator, class _Sentinel>
2210 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
2211 __insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last);
2212
2213 template <class _Iterator, class _Sentinel>
2214 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
2215 __insert_with_size(const_iterator __position, _Iterator __first, _Sentinel __last, difference_type __n);
2216
2217 // Allocate space for __n objects
2218 // throws length_error if __n > max_size()
2219 // throws (probably bad_alloc) if memory run out
2220 // Precondition: __begin_ == __end_ == __cap() == 0
2221 // Precondition: __n > 0
2222 // Postcondition: capacity() >= __n
2223 // Postcondition: size() == 0
2224 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __vallocate(size_type __n) {
2225 if (__n > max_size())
2226 __throw_length_error();
2227 auto __allocation = std::__allocate_at_least(__alloc(), __external_cap_to_internal(__n));
2228 __begin_ = __allocation.ptr;
2229 __size_ = 0;
2230 __cap() = __allocation.count;
2231 if (__libcpp_is_constant_evaluated()) {
2232 for (size_type __i = 0; __i != __cap(); ++__i)
2233 std::__construct_at(std::__to_address(__begin_) + __i);
2234 }
2235 }
2236
2237 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __vdeallocate() _NOEXCEPT;
2238 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static size_type __align_it(size_type __new_size) _NOEXCEPT {
2239 return (__new_size + (__bits_per_word - 1)) & ~((size_type)__bits_per_word - 1);
2240 }
2241 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type __recommend(size_type __new_size) const;
2242 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __construct_at_end(size_type __n, bool __x);
2243 template <class _InputIterator, class _Sentinel>
2244 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
2245 __construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n);
2246 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __append(size_type __n, const_reference __x);
2247 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference __make_ref(size_type __pos) _NOEXCEPT {
2248 return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);
2249 }
2250 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference __make_ref(size_type __pos) const _NOEXCEPT {
2251 return __bit_const_reference<vector>(
2252 __begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);
2253 }
2254 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator __make_iter(size_type __pos) _NOEXCEPT {
2255 return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));
2256 }
2257 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator __make_iter(size_type __pos) const _NOEXCEPT {
2258 return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));
2259 }
2260 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT {
2261 return begin() + (__p - cbegin());
2262 }
2263
2264 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __copy_assign_alloc(const vector& __v) {
2265 __copy_assign_alloc(
2266 __v, integral_constant<bool, __storage_traits::propagate_on_container_copy_assignment::value>());
2267 }
2268 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __copy_assign_alloc(const vector& __c, true_type) {
2269 if (__alloc() != __c.__alloc())
2270 __vdeallocate();
2271 __alloc() = __c.__alloc();
2272 }
2273
2274 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __copy_assign_alloc(const vector&, false_type) {}
2275
2276 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign(vector& __c, false_type);
2277 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign(vector& __c, true_type)
2278 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
2279 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign_alloc(vector& __c)
2280 _NOEXCEPT_(!__storage_traits::propagate_on_container_move_assignment::value ||
2281 is_nothrow_move_assignable<allocator_type>::value) {
2282 __move_assign_alloc(
2283 __c, integral_constant<bool, __storage_traits::propagate_on_container_move_assignment::value>());
2284 }
2285 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign_alloc(vector& __c, true_type)
2286 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {
2287 __alloc() = std::move(__c.__alloc());
2288 }
2289
2290 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign_alloc(vector&, false_type) _NOEXCEPT {}
2291
2292 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_t __hash_code() const _NOEXCEPT;
2293
2294 friend class __bit_reference<vector>;
2295 friend class __bit_const_reference<vector>;
2296 friend class __bit_iterator<vector, false>;
2297 friend class __bit_iterator<vector, true>;
2298 friend struct __bit_array<vector>;
2299 friend struct _LIBCPP_TEMPLATE_VIS hash<vector>;
2300 };
2301
2302 template <class _Allocator>
2303 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::__vdeallocate() _NOEXCEPT {
2304 if (this->__begin_ != nullptr) {
2305 __storage_traits::deallocate(this->__alloc(), this->__begin_, __cap());
2306 this->__begin_ = nullptr;
2307 this->__size_ = this->__cap() = 0;
2308 }
2309 }
2310
2311 template <class _Allocator>
2312 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::size_type
2313 vector<bool, _Allocator>::max_size() const _NOEXCEPT {
2314 size_type __amax = __storage_traits::max_size(__alloc());
2315 size_type __nmax = numeric_limits<size_type>::max() / 2; // end() >= begin(), always
2316 if (__nmax / __bits_per_word <= __amax)
2317 return __nmax;
2318 return __internal_cap_to_external(__amax);
2319 }
2320
2321 // Precondition: __new_size > capacity()
2322 template <class _Allocator>
2323 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::size_type
2324 vector<bool, _Allocator>::__recommend(size_type __new_size) const {
2325 const size_type __ms = max_size();
2326 if (__new_size > __ms)
2327 this->__throw_length_error();
2328 const size_type __cap = capacity();
2329 if (__cap >= __ms / 2)
2330 return __ms;
2331 return std::max(2 * __cap, __align_it(__new_size));
2332 }
2333
2334 // Default constructs __n objects starting at __end_
2335 // Precondition: __n > 0
2336 // Precondition: size() + __n <= capacity()
2337 // Postcondition: size() == size() + __n
2338 template <class _Allocator>
2339 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
2340 vector<bool, _Allocator>::__construct_at_end(size_type __n, bool __x) {
2341 size_type __old_size = this->__size_;
2342 this->__size_ += __n;
2343 if (__old_size == 0 || ((__old_size - 1) / __bits_per_word) != ((this->__size_ - 1) / __bits_per_word)) {
2344 if (this->__size_ <= __bits_per_word)
2345 this->__begin_[0] = __storage_type(0);
2346 else
2347 this->__begin_[(this->__size_ - 1) / __bits_per_word] = __storage_type(0);
2348 }
2349 std::fill_n(__make_iter(__old_size), __n, __x);
2350 }
2351
2352 template <class _Allocator>
2353 template <class _InputIterator, class _Sentinel>
2354 _LIBCPP_CONSTEXPR_SINCE_CXX20 void
2355 vector<bool, _Allocator>::__construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n) {
2356 size_type __old_size = this->__size_;
2357 this->__size_ += __n;
2358 if (__old_size == 0 || ((__old_size - 1) / __bits_per_word) != ((this->__size_ - 1) / __bits_per_word)) {
2359 if (this->__size_ <= __bits_per_word)
2360 this->__begin_[0] = __storage_type(0);
2361 else
2362 this->__begin_[(this->__size_ - 1) / __bits_per_word] = __storage_type(0);
2363 }
2364 std::__copy<_ClassicAlgPolicy>(__first, __last, __make_iter(__old_size));
2365 }
2366
2367 template <class _Allocator>
2368 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector()
2369 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
2370 : __begin_(nullptr), __size_(0), __cap_alloc_(0, __default_init_tag()) {}
2371
2372 template <class _Allocator>
2373 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(const allocator_type& __a)
2374 #if _LIBCPP_STD_VER <= 14
2375 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
2376 #else
2377 _NOEXCEPT
2378 #endif
2379 : __begin_(nullptr), __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) {
2380 }
2381
2382 template <class _Allocator>
2383 _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(size_type __n)
2384 : __begin_(nullptr), __size_(0), __cap_alloc_(0, __default_init_tag()) {
2385 if (__n > 0) {
2386 __vallocate(__n);
2387 __construct_at_end(__n, false);
2388 }
2389 }
2390
2391 #if _LIBCPP_STD_VER >= 14
2392 template <class _Allocator>
2393 _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(size_type __n, const allocator_type& __a)
2394 : __begin_(nullptr), __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) {
2395 if (__n > 0) {
2396 __vallocate(__n);
2397 __construct_at_end(__n, false);
2398 }
2399 }
2400 #endif
2401
2402 template <class _Allocator>
2403 _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(size_type __n, const value_type& __x)
2404 : __begin_(nullptr), __size_(0), __cap_alloc_(0, __default_init_tag()) {
2405 if (__n > 0) {
2406 __vallocate(__n);
2407 __construct_at_end(__n, __x);
2408 }
2409 }
2410
2411 template <class _Allocator>
2412 _LIBCPP_CONSTEXPR_SINCE_CXX20
2413 vector<bool, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a)
2414 : __begin_(nullptr), __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) {
2415 if (__n > 0) {
2416 __vallocate(__n);
2417 __construct_at_end(__n, __x);
2418 }
2419 }
2420
2421 template <class _Allocator>
2422 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> >
2423 _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last)
2424 : __begin_(nullptr), __size_(0), __cap_alloc_(0, __default_init_tag()) {
2425 __init_with_sentinel(__first, __last);
2426 }
2427
2428 template <class _Allocator>
2429 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> >
2430 _LIBCPP_CONSTEXPR_SINCE_CXX20
2431 vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a)
2432 : __begin_(nullptr), __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) {
2433 __init_with_sentinel(__first, __last);
2434 }
2435
2436 template <class _Allocator>
2437 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >
2438 _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last)
2439 : __begin_(nullptr), __size_(0), __cap_alloc_(0, __default_init_tag()) {
2440 auto __n = static_cast<size_type>(std::distance(__first, __last));
2441 __init_with_size(__first, __last, __n);
2442 }
2443
2444 template <class _Allocator>
2445 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >
2446 _LIBCPP_CONSTEXPR_SINCE_CXX20
2447 vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a)
2448 : __begin_(nullptr), __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) {
2449 auto __n = static_cast<size_type>(std::distance(__first, __last));
2450 __init_with_size(__first, __last, __n);
2451 }
2452
2453 #ifndef _LIBCPP_CXX03_LANG
2454
2455 template <class _Allocator>
2456 _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(initializer_list<value_type> __il)
2457 : __begin_(nullptr), __size_(0), __cap_alloc_(0, __default_init_tag()) {
2458 size_type __n = static_cast<size_type>(__il.size());
2459 if (__n > 0) {
2460 __vallocate(__n);
2461 __construct_at_end(__il.begin(), __il.end(), __n);
2462 }
2463 }
2464
2465 template <class _Allocator>
2466 _LIBCPP_CONSTEXPR_SINCE_CXX20
2467 vector<bool, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
2468 : __begin_(nullptr), __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) {
2469 size_type __n = static_cast<size_type>(__il.size());
2470 if (__n > 0) {
2471 __vallocate(__n);
2472 __construct_at_end(__il.begin(), __il.end(), __n);
2473 }
2474 }
2475
2476 #endif // _LIBCPP_CXX03_LANG
2477
2478 template <class _Allocator>
2479 _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(const vector& __v)
2480 : __begin_(nullptr),
2481 __size_(0),
2482 __cap_alloc_(0, __storage_traits::select_on_container_copy_construction(__v.__alloc())) {
2483 if (__v.size() > 0) {
2484 __vallocate(__v.size());
2485 __construct_at_end(__v.begin(), __v.end(), __v.size());
2486 }
2487 }
2488
2489 template <class _Allocator>
2490 _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a)
2491 : __begin_(nullptr), __size_(0), __cap_alloc_(0, __a) {
2492 if (__v.size() > 0) {
2493 __vallocate(__v.size());
2494 __construct_at_end(__v.begin(), __v.end(), __v.size());
2495 }
2496 }
2497
2498 template <class _Allocator>
2499 _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>& vector<bool, _Allocator>::operator=(const vector& __v) {
2500 if (this != std::addressof(__v)) {
2501 __copy_assign_alloc(__v);
2502 if (__v.__size_) {
2503 if (__v.__size_ > capacity()) {
2504 __vdeallocate();
2505 __vallocate(__v.__size_);
2506 }
2507 std::copy(__v.__begin_, __v.__begin_ + __external_cap_to_internal(__v.__size_), __begin_);
2508 }
2509 __size_ = __v.__size_;
2510 }
2511 return *this;
2512 }
2513
2514 template <class _Allocator>
2515 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(vector&& __v)
2516 #if _LIBCPP_STD_VER >= 17
2517 _NOEXCEPT
2518 #else
2519 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
2520 #endif
2521 : __begin_(__v.__begin_),
2522 __size_(__v.__size_),
2523 __cap_alloc_(std::move(__v.__cap_alloc_)) {
2524 __v.__begin_ = nullptr;
2525 __v.__size_ = 0;
2526 __v.__cap() = 0;
2527 }
2528
2529 template <class _Allocator>
2530 _LIBCPP_CONSTEXPR_SINCE_CXX20
2531 vector<bool, _Allocator>::vector(vector&& __v, const __type_identity_t<allocator_type>& __a)
2532 : __begin_(nullptr), __size_(0), __cap_alloc_(0, __a) {
2533 if (__a == allocator_type(__v.__alloc())) {
2534 this->__begin_ = __v.__begin_;
2535 this->__size_ = __v.__size_;
2536 this->__cap() = __v.__cap();
2537 __v.__begin_ = nullptr;
2538 __v.__cap() = __v.__size_ = 0;
2539 } else if (__v.size() > 0) {
2540 __vallocate(__v.size());
2541 __construct_at_end(__v.begin(), __v.end(), __v.size());
2542 }
2543 }
2544
2545 template <class _Allocator>
2546 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>&
2547 vector<bool, _Allocator>::operator=(vector&& __v)
2548 _NOEXCEPT_(__noexcept_move_assign_container<_Allocator, __alloc_traits>::value) {
2549 __move_assign(__v, integral_constant<bool, __storage_traits::propagate_on_container_move_assignment::value>());
2550 return *this;
2551 }
2552
2553 template <class _Allocator>
2554 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::__move_assign(vector& __c, false_type) {
2555 if (__alloc() != __c.__alloc())
2556 assign(__c.begin(), __c.end());
2557 else
2558 __move_assign(__c, true_type());
2559 }
2560
2561 template <class _Allocator>
2562 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::__move_assign(vector& __c, true_type)
2563 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {
2564 __vdeallocate();
2565 __move_assign_alloc(__c);
2566 this->__begin_ = __c.__begin_;
2567 this->__size_ = __c.__size_;
2568 this->__cap() = __c.__cap();
2569 __c.__begin_ = nullptr;
2570 __c.__cap() = __c.__size_ = 0;
2571 }
2572
2573 template <class _Allocator>
2574 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::assign(size_type __n, const value_type& __x) {
2575 __size_ = 0;
2576 if (__n > 0) {
2577 size_type __c = capacity();
2578 if (__n <= __c)
2579 __size_ = __n;
2580 else {
2581 vector __v(get_allocator());
2582 __v.reserve(__recommend(__n));
2583 __v.__size_ = __n;
2584 swap(__v);
2585 }
2586 std::fill_n(begin(), __n, __x);
2587 }
2588 }
2589
2590 template <class _Allocator>
2591 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> >
2592 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last) {
2593 __assign_with_sentinel(__first, __last);
2594 }
2595
2596 template <class _Allocator>
2597 template <class _Iterator, class _Sentinel>
2598 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
2599 vector<bool, _Allocator>::__assign_with_sentinel(_Iterator __first, _Sentinel __last) {
2600 clear();
2601 for (; __first != __last; ++__first)
2602 push_back(*__first);
2603 }
2604
2605 template <class _Allocator>
2606 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >
2607 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) {
2608 __assign_with_size(__first, __last, std::distance(__first, __last));
2609 }
2610
2611 template <class _Allocator>
2612 template <class _ForwardIterator, class _Sentinel>
2613 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
2614 vector<bool, _Allocator>::__assign_with_size(_ForwardIterator __first, _Sentinel __last, difference_type __ns) {
2615 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__ns >= 0, "invalid range specified");
2616
2617 clear();
2618
2619 const size_t __n = static_cast<size_type>(__ns);
2620 if (__n) {
2621 if (__n > capacity()) {
2622 __vdeallocate();
2623 __vallocate(__n);
2624 }
2625 __construct_at_end(__first, __last, __n);
2626 }
2627 }
2628
2629 template <class _Allocator>
2630 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::reserve(size_type __n) {
2631 if (__n > capacity()) {
2632 if (__n > max_size())
2633 this->__throw_length_error();
2634 vector __v(this->get_allocator());
2635 __v.__vallocate(__n);
2636 __v.__construct_at_end(this->begin(), this->end(), this->size());
2637 swap(__v);
2638 }
2639 }
2640
2641 template <class _Allocator>
2642 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT {
2643 if (__external_cap_to_internal(size()) > __cap()) {
2644 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
2645 try {
2646 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
2647 vector(*this, allocator_type(__alloc())).swap(*this);
2648 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
2649 } catch (...) {
2650 }
2651 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
2652 }
2653 }
2654
2655 template <class _Allocator>
2656 typename vector<bool, _Allocator>::reference vector<bool, _Allocator>::at(size_type __n) {
2657 if (__n >= size())
2658 this->__throw_out_of_range();
2659 return (*this)[__n];
2660 }
2661
2662 template <class _Allocator>
2663 typename vector<bool, _Allocator>::const_reference vector<bool, _Allocator>::at(size_type __n) const {
2664 if (__n >= size())
2665 this->__throw_out_of_range();
2666 return (*this)[__n];
2667 }
2668
2669 template <class _Allocator>
2670 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::push_back(const value_type& __x) {
2671 if (this->__size_ == this->capacity())
2672 reserve(__recommend(this->__size_ + 1));
2673 ++this->__size_;
2674 back() = __x;
2675 }
2676
2677 template <class _Allocator>
2678 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator
2679 vector<bool, _Allocator>::insert(const_iterator __position, const value_type& __x) {
2680 iterator __r;
2681 if (size() < capacity()) {
2682 const_iterator __old_end = end();
2683 ++__size_;
2684 std::copy_backward(__position, __old_end, end());
2685 __r = __const_iterator_cast(__position);
2686 } else {
2687 vector __v(get_allocator());
2688 __v.reserve(__recommend(__size_ + 1));
2689 __v.__size_ = __size_ + 1;
2690 __r = std::copy(cbegin(), __position, __v.begin());
2691 std::copy_backward(__position, cend(), __v.end());
2692 swap(__v);
2693 }
2694 *__r = __x;
2695 return __r;
2696 }
2697
2698 template <class _Allocator>
2699 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator
2700 vector<bool, _Allocator>::insert(const_iterator __position, size_type __n, const value_type& __x) {
2701 iterator __r;
2702 size_type __c = capacity();
2703 if (__n <= __c && size() <= __c - __n) {
2704 const_iterator __old_end = end();
2705 __size_ += __n;
2706 std::copy_backward(__position, __old_end, end());
2707 __r = __const_iterator_cast(__position);
2708 } else {
2709 vector __v(get_allocator());
2710 __v.reserve(__recommend(__size_ + __n));
2711 __v.__size_ = __size_ + __n;
2712 __r = std::copy(cbegin(), __position, __v.begin());
2713 std::copy_backward(__position, cend(), __v.end());
2714 swap(__v);
2715 }
2716 std::fill_n(__r, __n, __x);
2717 return __r;
2718 }
2719
2720 template <class _Allocator>
2721 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> >
2722 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator
2723 vector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) {
2724 return __insert_with_sentinel(__position, __first, __last);
2725 }
2726
2727 template <class _Allocator>
2728 template <class _InputIterator, class _Sentinel>
2729 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI typename vector<bool, _Allocator>::iterator
2730 vector<bool, _Allocator>::__insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last) {
2731 difference_type __off = __position - begin();
2732 iterator __p = __const_iterator_cast(__position);
2733 iterator __old_end = end();
2734 for (; size() != capacity() && __first != __last; ++__first) {
2735 ++this->__size_;
2736 back() = *__first;
2737 }
2738 vector __v(get_allocator());
2739 if (__first != __last) {
2740 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
2741 try {
2742 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
2743 __v.__assign_with_sentinel(std::move(__first), std::move(__last));
2744 difference_type __old_size = static_cast<difference_type>(__old_end - begin());
2745 difference_type __old_p = __p - begin();
2746 reserve(__recommend(size() + __v.size()));
2747 __p = begin() + __old_p;
2748 __old_end = begin() + __old_size;
2749 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
2750 } catch (...) {
2751 erase(__old_end, end());
2752 throw;
2753 }
2754 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
2755 }
2756 __p = std::rotate(__p, __old_end, end());
2757 insert(__p, __v.begin(), __v.end());
2758 return begin() + __off;
2759 }
2760
2761 template <class _Allocator>
2762 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >
2763 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator
2764 vector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) {
2765 return __insert_with_size(__position, __first, __last, std::distance(__first, __last));
2766 }
2767
2768 template <class _Allocator>
2769 template <class _ForwardIterator, class _Sentinel>
2770 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI typename vector<bool, _Allocator>::iterator
2771 vector<bool, _Allocator>::__insert_with_size(
2772 const_iterator __position, _ForwardIterator __first, _Sentinel __last, difference_type __n_signed) {
2773 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__n_signed >= 0, "invalid range specified");
2774 const size_type __n = static_cast<size_type>(__n_signed);
2775 iterator __r;
2776 size_type __c = capacity();
2777 if (__n <= __c && size() <= __c - __n) {
2778 const_iterator __old_end = end();
2779 __size_ += __n;
2780 std::copy_backward(__position, __old_end, end());
2781 __r = __const_iterator_cast(__position);
2782 } else {
2783 vector __v(get_allocator());
2784 __v.reserve(__recommend(__size_ + __n));
2785 __v.__size_ = __size_ + __n;
2786 __r = std::copy(cbegin(), __position, __v.begin());
2787 std::copy_backward(__position, cend(), __v.end());
2788 swap(__v);
2789 }
2790 std::__copy<_ClassicAlgPolicy>(__first, __last, __r);
2791 return __r;
2792 }
2793
2794 template <class _Allocator>
2795 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator
2796 vector<bool, _Allocator>::erase(const_iterator __position) {
2797 iterator __r = __const_iterator_cast(__position);
2798 std::copy(__position + 1, this->cend(), __r);
2799 --__size_;
2800 return __r;
2801 }
2802
2803 template <class _Allocator>
2804 _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator
2805 vector<bool, _Allocator>::erase(const_iterator __first, const_iterator __last) {
2806 iterator __r = __const_iterator_cast(__first);
2807 difference_type __d = __last - __first;
2808 std::copy(__last, this->cend(), __r);
2809 __size_ -= __d;
2810 return __r;
2811 }
2812
2813 template <class _Allocator>
2814 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::swap(vector& __x)
2815 #if _LIBCPP_STD_VER >= 14
2816 _NOEXCEPT
2817 #else
2818 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>)
2819 #endif
2820 {
2821 std::swap(this->__begin_, __x.__begin_);
2822 std::swap(this->__size_, __x.__size_);
2823 std::swap(this->__cap(), __x.__cap());
2824 std::__swap_allocator(
2825 this->__alloc(), __x.__alloc(), integral_constant<bool, __alloc_traits::propagate_on_container_swap::value>());
2826 }
2827
2828 template <class _Allocator>
2829 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::resize(size_type __sz, value_type __x) {
2830 size_type __cs = size();
2831 if (__cs < __sz) {
2832 iterator __r;
2833 size_type __c = capacity();
2834 size_type __n = __sz - __cs;
2835 if (__n <= __c && __cs <= __c - __n) {
2836 __r = end();
2837 __size_ += __n;
2838 } else {
2839 vector __v(get_allocator());
2840 __v.reserve(__recommend(__size_ + __n));
2841 __v.__size_ = __size_ + __n;
2842 __r = std::copy(cbegin(), cend(), __v.begin());
2843 swap(__v);
2844 }
2845 std::fill_n(__r, __n, __x);
2846 } else
2847 __size_ = __sz;
2848 }
2849
2850 template <class _Allocator>
2851 _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::flip() _NOEXCEPT {
2852 // do middle whole words
2853 size_type __n = __size_;
2854 __storage_pointer __p = __begin_;
2855 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
2856 *__p = ~*__p;
2857 // do last partial word
2858 if (__n > 0) {
2859 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
2860 __storage_type __b = *__p & __m;
2861 *__p &= ~__m;
2862 *__p |= ~__b & __m;
2863 }
2864 }
2865
2866 template <class _Allocator>
2867 _LIBCPP_CONSTEXPR_SINCE_CXX20 bool vector<bool, _Allocator>::__invariants() const {
2868 if (this->__begin_ == nullptr) {
2869 if (this->__size_ != 0 || this->__cap() != 0)
2870 return false;
2871 } else {
2872 if (this->__cap() == 0)
2873 return false;
2874 if (this->__size_ > this->capacity())
2875 return false;
2876 }
2877 return true;
2878 }
2879
2880 template <class _Allocator>
2881 _LIBCPP_CONSTEXPR_SINCE_CXX20 size_t vector<bool, _Allocator>::__hash_code() const _NOEXCEPT {
2882 size_t __h = 0;
2883 // do middle whole words
2884 size_type __n = __size_;
2885 __storage_pointer __p = __begin_;
2886 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
2887 __h ^= *__p;
2888 // do last partial word
2889 if (__n > 0) {
2890 const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
2891 __h ^= *__p & __m;
2892 }
2893 return __h;
2894 }
2895
2896 template <class _Allocator>
2897 struct _LIBCPP_TEMPLATE_VIS hash<vector<bool, _Allocator> >
2898 : public __unary_function<vector<bool, _Allocator>, size_t> {
2899 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_t
2900 operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT {
2901 return __vec.__hash_code();
2902 }
2903 };
2904
2905 template <class _Tp, class _Allocator>
2906 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI bool
2907 operator==(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) {
2908 const typename vector<_Tp, _Allocator>::size_type __sz = __x.size();
2909 return __sz == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
2910 }
2911
2912 #if _LIBCPP_STD_VER <= 17
2913
2914 template <class _Tp, class _Allocator>
2915 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) {
2916 return !(__x == __y);
2917 }
2918
2919 template <class _Tp, class _Allocator>
2920 inline _LIBCPP_HIDE_FROM_ABI bool operator<(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) {
2921 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2922 }
2923
2924 template <class _Tp, class _Allocator>
2925 inline _LIBCPP_HIDE_FROM_ABI bool operator>(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) {
2926 return __y < __x;
2927 }
2928
2929 template <class _Tp, class _Allocator>
2930 inline _LIBCPP_HIDE_FROM_ABI bool operator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) {
2931 return !(__x < __y);
2932 }
2933
2934 template <class _Tp, class _Allocator>
2935 inline _LIBCPP_HIDE_FROM_ABI bool operator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) {
2936 return !(__y < __x);
2937 }
2938
2939 #else // _LIBCPP_STD_VER <= 17
2940
2941 template <class _Tp, class _Allocator>
2942 _LIBCPP_HIDE_FROM_ABI constexpr __synth_three_way_result<_Tp>
2943 operator<=>(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) {
2944 return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
2945 }
2946
2947 #endif // _LIBCPP_STD_VER <= 17
2948
2949 template <class _Tp, class _Allocator>
2950 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI void
2951 swap(vector<_Tp, _Allocator>& __x, vector<_Tp, _Allocator>& __y) _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
2952 __x.swap(__y);
2953 }
2954
2955 #if _LIBCPP_STD_VER >= 20
2956 template <class _Tp, class _Allocator, class _Up>
2957 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::size_type
2958 erase(vector<_Tp, _Allocator>& __c, const _Up& __v) {
2959 auto __old_size = __c.size();
2960 __c.erase(std::remove(__c.begin(), __c.end(), __v), __c.end());
2961 return __old_size - __c.size();
2962 }
2963
2964 template <class _Tp, class _Allocator, class _Predicate>
2965 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::size_type
2966 erase_if(vector<_Tp, _Allocator>& __c, _Predicate __pred) {
2967 auto __old_size = __c.size();
2968 __c.erase(std::remove_if(__c.begin(), __c.end(), __pred), __c.end());
2969 return __old_size - __c.size();
2970 }
2971
2972 template <>
2973 inline constexpr bool __format::__enable_insertable<vector<char>> = true;
2974 # ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
2975 template <>
2976 inline constexpr bool __format::__enable_insertable<vector<wchar_t>> = true;
2977 # endif
2978
2979 #endif // _LIBCPP_STD_VER >= 20
2980
2981 #if _LIBCPP_STD_VER >= 23
2982 template <class _Tp, class _CharT>
2983 // Since is-vector-bool-reference is only used once it's inlined here.
2984 requires same_as<typename _Tp::__container, vector<bool, typename _Tp::__container::allocator_type>>
2985 struct _LIBCPP_TEMPLATE_VIS formatter<_Tp, _CharT> {
2986 private:
2987 formatter<bool, _CharT> __underlying_;
2988
2989 public:
2990 template <class _ParseContext>
2991 _LIBCPP_HIDE_FROM_ABI constexpr typename _ParseContext::iterator parse(_ParseContext& __ctx) {
2992 return __underlying_.parse(__ctx);
2993 }
2994
2995 template <class _FormatContext>
2996 _LIBCPP_HIDE_FROM_ABI typename _FormatContext::iterator format(const _Tp& __ref, _FormatContext& __ctx) const {
2997 return __underlying_.format(__ref, __ctx);
2998 }
2999 };
3000 #endif // _LIBCPP_STD_VER >= 23
3001
3002 _LIBCPP_END_NAMESPACE_STD
3003
3004 #if _LIBCPP_STD_VER >= 17
3005 _LIBCPP_BEGIN_NAMESPACE_STD
3006 namespace pmr {
3007 template <class _ValueT>
3008 using vector _LIBCPP_AVAILABILITY_PMR = std::vector<_ValueT, polymorphic_allocator<_ValueT>>;
3009 } // namespace pmr
3010 _LIBCPP_END_NAMESPACE_STD
3011 #endif
3012
3013 _LIBCPP_POP_MACROS
3014
3015 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
3016 # include <__cxx03/algorithm>
3017 # include <__cxx03/atomic>
3018 # include <__cxx03/concepts>
3019 # include <__cxx03/cstdlib>
3020 # include <__cxx03/iosfwd>
3021 # if !defined(_LIBCPP_HAS_NO_LOCALIZATION)
3022 # include <__cxx03/locale>
3023 # endif
3024 # include <__cxx03/tuple>
3025 # include <__cxx03/type_traits>
3026 # include <__cxx03/typeinfo>
3027 # include <__cxx03/utility>
3028 #endif
3029
3030 #endif // _LIBCPP___CXX03_VECTOR
