1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef _LIBCPP___VECTOR_VECTOR_H
10#define _LIBCPP___VECTOR_VECTOR_H
11
12#include <__algorithm/copy.h>
13#include <__algorithm/copy_n.h>
14#include <__algorithm/fill_n.h>
15#include <__algorithm/iterator_operations.h>
16#include <__algorithm/max.h>
17#include <__algorithm/min.h>
18#include <__algorithm/move.h>
19#include <__algorithm/move_backward.h>
20#include <__algorithm/rotate.h>
21#include <__assert>
22#include <__config>
23#include <__debug_utils/sanitizers.h>
24#include <__format/enable_insertable.h>
25#include <__fwd/vector.h>
26#include <__iterator/bounded_iter.h>
27#include <__iterator/concepts.h>
28#include <__iterator/distance.h>
29#include <__iterator/iterator_traits.h>
30#include <__iterator/move_iterator.h>
31#include <__iterator/next.h>
32#include <__iterator/reverse_iterator.h>
33#include <__iterator/wrap_iter.h>
34#include <__memory/addressof.h>
35#include <__memory/allocate_at_least.h>
36#include <__memory/allocator.h>
37#include <__memory/allocator_traits.h>
38#include <__memory/compressed_pair.h>
39#include <__memory/noexcept_move_assign_container.h>
40#include <__memory/pointer_traits.h>
41#include <__memory/swap_allocator.h>
42#include <__memory/temp_value.h>
43#include <__memory/uninitialized_algorithms.h>
44#include <__ranges/access.h>
45#include <__ranges/as_rvalue_view.h>
46#include <__ranges/concepts.h>
47#include <__ranges/container_compatible_range.h>
48#include <__ranges/from_range.h>
49#include <__split_buffer>
50#include <__type_traits/conditional.h>
51#include <__type_traits/enable_if.h>
52#include <__type_traits/is_allocator.h>
53#include <__type_traits/is_constant_evaluated.h>
54#include <__type_traits/is_constructible.h>
55#include <__type_traits/is_nothrow_assignable.h>
56#include <__type_traits/is_nothrow_constructible.h>
57#include <__type_traits/is_pointer.h>
58#include <__type_traits/is_same.h>
59#include <__type_traits/is_trivially_relocatable.h>
60#include <__type_traits/type_identity.h>
61#include <__utility/declval.h>
62#include <__utility/exception_guard.h>
63#include <__utility/forward.h>
64#include <__utility/is_pointer_in_range.h>
65#include <__utility/move.h>
66#include <__utility/pair.h>
67#include <__utility/swap.h>
68#include <initializer_list>
69#include <limits>
70#include <stdexcept>
71
72// These headers define parts of vectors definition, since they define ADL functions or class specializations.
73#include <__vector/comparison.h>
74#include <__vector/container_traits.h>
75#include <__vector/swap.h>
76
77#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
78# pragma GCC system_header
79#endif
80
81_LIBCPP_PUSH_MACROS
82#include <__undef_macros>
83
84_LIBCPP_BEGIN_NAMESPACE_STD
85
86template <class _Tp, class _Allocator /* = allocator<_Tp> */>
87class vector {
88 using _SplitBuffer _LIBCPP_NODEBUG = std::__split_buffer<_Tp, _Allocator, __split_buffer_pointer_layout>;
89
90public:
91 //
92 // Types
93 //
94 using value_type = _Tp;
95 using allocator_type = _Allocator;
96 using __alloc_traits _LIBCPP_NODEBUG = allocator_traits<allocator_type>;
97 using reference = value_type&;
98 using const_reference = const value_type&;
99 using size_type = typename __alloc_traits::size_type;
100 using difference_type = typename __alloc_traits::difference_type;
101 using pointer = typename __alloc_traits::pointer;
102 using const_pointer = typename __alloc_traits::const_pointer;
103#ifdef _LIBCPP_ABI_BOUNDED_ITERATORS_IN_VECTOR
104 // Users might provide custom allocators, and prior to C++20 we have no existing way to detect whether the allocator's
105 // pointer type is contiguous (though it has to be by the Standard). Using the wrapper type ensures the iterator is
106 // considered contiguous.
107 using iterator = __bounded_iter<pointer>;
108 using const_iterator = __bounded_iter<const_pointer>;
109#else
110 using iterator = __wrap_iter<pointer>;
111 using const_iterator = __wrap_iter<const_pointer>;
112#endif
113 using reverse_iterator = std::reverse_iterator<iterator>;
114 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
115
116 // A vector contains the following members which may be trivially relocatable:
117 // - pointer: may be trivially relocatable, so it's checked
118 // - allocator_type: may be trivially relocatable, so it's checked
119 // vector doesn't contain any self-references, so it's trivially relocatable if its members are.
120 using __trivially_relocatable _LIBCPP_NODEBUG = __conditional_t<
121 __libcpp_is_trivially_relocatable<pointer>::value && __libcpp_is_trivially_relocatable<allocator_type>::value,
122 vector,
123 void>;
124
125 static_assert(__check_valid_allocator<allocator_type>::value, "");
126 static_assert(is_same<typename allocator_type::value_type, value_type>::value,
127 "Allocator::value_type must be same type as value_type");
128
129 //
130 // [vector.cons], construct/copy/destroy
131 //
132 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector()
133 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) {}
134 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit vector(const allocator_type& __a)
135#if _LIBCPP_STD_VER <= 14
136 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
137#else
138 noexcept
139#endif
140 : __alloc_(__a) {
141 }
142
143 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit vector(size_type __n) {
144 auto __guard = std::__make_exception_guard(__destroy_vector(*this));
145 if (__n > 0) {
146 __vallocate(__n);
147 __construct_at_end(__n);
148 }
149 __guard.__complete();
150 }
151
152#if _LIBCPP_STD_VER >= 14
153 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit vector(size_type __n, const allocator_type& __a)
154 : __alloc_(__a) {
155 auto __guard = std::__make_exception_guard(__destroy_vector(*this));
156 if (__n > 0) {
157 __vallocate(__n);
158 __construct_at_end(__n);
159 }
160 __guard.__complete();
161 }
162#endif
163
164 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector(size_type __n, const value_type& __x) {
165 auto __guard = std::__make_exception_guard(__destroy_vector(*this));
166 if (__n > 0) {
167 __vallocate(__n);
168 __construct_at_end(__n, __x);
169 }
170 __guard.__complete();
171 }
172
173 template <__enable_if_t<__is_allocator_v<_Allocator>, int> = 0>
174 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
175 vector(size_type __n, const value_type& __x, const allocator_type& __a)
176 : __alloc_(__a) {
177 auto __guard = std::__make_exception_guard(__destroy_vector(*this));
178 if (__n > 0) {
179 __vallocate(__n);
180 __construct_at_end(__n, __x);
181 }
182 __guard.__complete();
183 }
184
185 template <class _InputIterator,
186 __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value &&
187 is_constructible<value_type, typename iterator_traits<_InputIterator>::reference>::value,
188 int> = 0>
189 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector(_InputIterator __first, _InputIterator __last) {
190 __init_with_sentinel(__first, __last);
191 }
192
193 template <class _InputIterator,
194 __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value &&
195 is_constructible<value_type, typename iterator_traits<_InputIterator>::reference>::value,
196 int> = 0>
197 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
198 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a)
199 : __alloc_(__a) {
200 __init_with_sentinel(__first, __last);
201 }
202
203 template <
204 class _ForwardIterator,
205 __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value &&
206 is_constructible<value_type, typename iterator_traits<_ForwardIterator>::reference>::value,
207 int> = 0>
208 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector(_ForwardIterator __first, _ForwardIterator __last) {
209 size_type __n = static_cast<size_type>(std::distance(__first, __last));
210 __init_with_size(__first, __last, __n);
211 }
212
213 template <
214 class _ForwardIterator,
215 __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value &&
216 is_constructible<value_type, typename iterator_traits<_ForwardIterator>::reference>::value,
217 int> = 0>
218 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
219 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a)
220 : __alloc_(__a) {
221 size_type __n = static_cast<size_type>(std::distance(__first, __last));
222 __init_with_size(__first, __last, __n);
223 }
224
225#if _LIBCPP_STD_VER >= 23
226 template <_ContainerCompatibleRange<_Tp> _Range>
227 _LIBCPP_HIDE_FROM_ABI constexpr vector(
228 from_range_t, _Range&& __range, const allocator_type& __alloc = allocator_type())
229 : __alloc_(__alloc) {
230 if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
231 auto __n = static_cast<size_type>(ranges::distance(__range));
232 __init_with_size(ranges::begin(__range), ranges::end(__range), __n);
233
234 } else {
235 __init_with_sentinel(ranges::begin(__range), ranges::end(__range));
236 }
237 }
238#endif
239
240private:
241 class __destroy_vector {
242 public:
243 _LIBCPP_CONSTEXPR _LIBCPP_HIDE_FROM_ABI __destroy_vector(vector& __vec) : __vec_(__vec) {}
244
245 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void operator()() {
246 if (__vec_.__begin_ != nullptr) {
247 __vec_.clear();
248 __vec_.__annotate_delete();
249 __alloc_traits::deallocate(__vec_.__alloc_, __vec_.__begin_, __vec_.capacity());
250 }
251 }
252
253 private:
254 vector& __vec_;
255 };
256
257public:
258 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI ~vector() { __destroy_vector (*this)(); }
259
260 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector(const vector& __x)
261 : __alloc_(__alloc_traits::select_on_container_copy_construction(__x.__alloc_)) {
262 __init_with_size(__x.__begin_, __x.__end_, __x.size());
263 }
264 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
265 vector(const vector& __x, const __type_identity_t<allocator_type>& __a)
266 : __alloc_(__a) {
267 __init_with_size(__x.__begin_, __x.__end_, __x.size());
268 }
269 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector& operator=(const vector& __x);
270
271#ifndef _LIBCPP_CXX03_LANG
272 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector(initializer_list<value_type> __il) {
273 __init_with_size(__il.begin(), __il.end(), __il.size());
274 }
275
276 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
277 vector(initializer_list<value_type> __il, const allocator_type& __a)
278 : __alloc_(__a) {
279 __init_with_size(__il.begin(), __il.end(), __il.size());
280 }
281
282 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector& operator=(initializer_list<value_type> __il) {
283 assign(__il.begin(), __il.end());
284 return *this;
285 }
286#endif // !_LIBCPP_CXX03_LANG
287
288 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector(vector&& __x)
289#if _LIBCPP_STD_VER >= 17
290 noexcept;
291#else
292 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
293#endif
294
295 _LIBCPP_CONSTEXPR_SINCE_CXX20
296 _LIBCPP_HIDE_FROM_ABI vector(vector&& __x, const __type_identity_t<allocator_type>& __a);
297 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector& operator=(vector&& __x)
298 _NOEXCEPT_(__noexcept_move_assign_container<_Allocator, __alloc_traits>::value) {
299 __move_assign(__x, integral_constant<bool, __alloc_traits::propagate_on_container_move_assignment::value>());
300 return *this;
301 }
302
303 template <class _InputIterator,
304 __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value &&
305 is_constructible<value_type, typename iterator_traits<_InputIterator>::reference>::value,
306 int> = 0>
307 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void assign(_InputIterator __first, _InputIterator __last) {
308 __assign_with_sentinel(__first, __last);
309 }
310 template <
311 class _ForwardIterator,
312 __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value &&
313 is_constructible<value_type, typename iterator_traits<_ForwardIterator>::reference>::value,
314 int> = 0>
315 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void assign(_ForwardIterator __first, _ForwardIterator __last) {
316 __assign_with_size<_ClassicAlgPolicy>(__first, __last, std::distance(__first, __last));
317 }
318
319#if _LIBCPP_STD_VER >= 23
320 template <_ContainerCompatibleRange<_Tp> _Range>
321 _LIBCPP_HIDE_FROM_ABI constexpr void assign_range(_Range&& __range) {
322 if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
323 auto __n = static_cast<size_type>(ranges::distance(__range));
324 __assign_with_size<_RangeAlgPolicy>(ranges::begin(__range), ranges::end(__range), __n);
325
326 } else {
327 __assign_with_sentinel(ranges::begin(__range), ranges::end(__range));
328 }
329 }
330#endif
331
332 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const_reference __u);
333
334#ifndef _LIBCPP_CXX03_LANG
335 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void assign(initializer_list<value_type> __il) {
336 assign(__il.begin(), __il.end());
337 }
338#endif
339
340 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
341 return this->__alloc_;
342 }
343
344 //
345 // Iterators
346 //
347 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT {
348 return __make_iter(__add_alignment_assumption(this->__begin_));
349 }
350 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT {
351 return __make_iter(__add_alignment_assumption(this->__begin_));
352 }
353 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT {
354 return __make_iter(__add_alignment_assumption(this->__end_));
355 }
356 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT {
357 return __make_iter(__add_alignment_assumption(this->__end_));
358 }
359
360 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT {
361 return reverse_iterator(end());
362 }
363 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator
364 rbegin() const _NOEXCEPT {
365 return const_reverse_iterator(end());
366 }
367 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT {
368 return reverse_iterator(begin());
369 }
370 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT {
371 return const_reverse_iterator(begin());
372 }
373
374 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT {
375 return begin();
376 }
377 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT {
378 return end();
379 }
380 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator
381 crbegin() const _NOEXCEPT {
382 return rbegin();
383 }
384 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT {
385 return rend();
386 }
387
388 //
389 // [vector.capacity], capacity
390 //
391 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT {
392 return static_cast<size_type>(this->__end_ - this->__begin_);
393 }
394 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type capacity() const _NOEXCEPT {
395 return static_cast<size_type>(this->__cap_ - this->__begin_);
396 }
397 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT {
398 return this->__begin_ == this->__end_;
399 }
400 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT {
401 return std::min<size_type>(__alloc_traits::max_size(this->__alloc_), numeric_limits<difference_type>::max());
402 }
403 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n);
404 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void shrink_to_fit() _NOEXCEPT;
405
406 //
407 // element access
408 //
409 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference operator[](size_type __n) _NOEXCEPT {
410 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__n < size(), "vector[] index out of bounds");
411 return this->__begin_[__n];
412 }
413 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference
414 operator[](size_type __n) const _NOEXCEPT {
415 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__n < size(), "vector[] index out of bounds");
416 return this->__begin_[__n];
417 }
418 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference at(size_type __n) {
419 if (__n >= size())
420 this->__throw_out_of_range();
421 return this->__begin_[__n];
422 }
423 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference at(size_type __n) const {
424 if (__n >= size())
425 this->__throw_out_of_range();
426 return this->__begin_[__n];
427 }
428
429 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference front() _NOEXCEPT {
430 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "front() called on an empty vector");
431 return *this->__begin_;
432 }
433 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference front() const _NOEXCEPT {
434 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "front() called on an empty vector");
435 return *this->__begin_;
436 }
437 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference back() _NOEXCEPT {
438 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "back() called on an empty vector");
439 return *(this->__end_ - 1);
440 }
441 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference back() const _NOEXCEPT {
442 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "back() called on an empty vector");
443 return *(this->__end_ - 1);
444 }
445
446 //
447 // [vector.data], data access
448 //
449 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI value_type* data() _NOEXCEPT {
450 return std::__to_address(this->__begin_);
451 }
452
453 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const value_type* data() const _NOEXCEPT {
454 return std::__to_address(this->__begin_);
455 }
456
457 //
458 // [vector.modifiers], modifiers
459 //
460 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void push_back(const_reference __x) { emplace_back(__x); }
461
462 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void push_back(value_type&& __x) { emplace_back(std::move(__x)); }
463
464 template <class... _Args>
465 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
466#if _LIBCPP_STD_VER >= 17
467 reference emplace_back(_Args&&... __args);
468#else
469 void emplace_back(_Args&&... __args);
470#endif
471
472 template <class... _Args>
473 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __emplace_back_assume_capacity(_Args&&... __args) {
474 _LIBCPP_ASSERT_INTERNAL(
475 size() < capacity(), "We assume that we have enough space to insert an element at the end of the vector");
476 _ConstructTransaction __tx(*this, 1);
477 __alloc_traits::construct(this->__alloc_, std::__to_address(__tx.__pos_), std::forward<_Args>(__args)...);
478 ++__tx.__pos_;
479 }
480
481#if _LIBCPP_STD_VER >= 23
482 template <_ContainerCompatibleRange<_Tp> _Range>
483 _LIBCPP_HIDE_FROM_ABI constexpr void append_range(_Range&& __range) {
484 if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
485 auto __len = ranges::distance(__range);
486 if (__len <= __cap_ - __end_) {
487 __construct_at_end(ranges::begin(__range), ranges::end(__range), __len);
488 } else {
489 _SplitBuffer __buffer(__recommend(new_size: size() + __len), size(), __alloc_);
490 __buffer.__construct_at_end_with_size(ranges::begin(__range), __len);
491 __swap_out_circular_buffer(__buffer);
492 }
493 } else {
494 vector __buffer(__alloc_);
495 for (auto&& __val : __range)
496 __buffer.emplace_back(std::forward<decltype(__val)>(__val));
497 append_range(ranges::as_rvalue_view(__buffer));
498 }
499 }
500#endif
501
502 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void pop_back() {
503 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "vector::pop_back called on an empty vector");
504 this->__destruct_at_end(this->__end_ - 1);
505 }
506
507 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __position, const_reference __x);
508
509 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __position, value_type&& __x);
510 template <class... _Args>
511 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator emplace(const_iterator __position, _Args&&... __args);
512
513 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
514 insert(const_iterator __position, size_type __n, const_reference __x);
515
516 template <class _InputIterator,
517 __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value &&
518 is_constructible< value_type, typename iterator_traits<_InputIterator>::reference>::value,
519 int> = 0>
520 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
521 insert(const_iterator __position, _InputIterator __first, _InputIterator __last) {
522 return __insert_with_sentinel(__position, __first, __last);
523 }
524
525 template <
526 class _ForwardIterator,
527 __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value &&
528 is_constructible< value_type, typename iterator_traits<_ForwardIterator>::reference>::value,
529 int> = 0>
530 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
531 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) {
532 return __insert_with_size<_ClassicAlgPolicy>(__position, __first, __last, std::distance(__first, __last));
533 }
534
535#if _LIBCPP_STD_VER >= 23
536 template <_ContainerCompatibleRange<_Tp> _Range>
537 _LIBCPP_HIDE_FROM_ABI constexpr iterator insert_range(const_iterator __position, _Range&& __range) {
538 if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
539 auto __n = static_cast<size_type>(ranges::distance(__range));
540 return __insert_with_size<_RangeAlgPolicy>(__position, ranges::begin(__range), ranges::end(__range), __n);
541
542 } else {
543 return __insert_with_sentinel(__position, ranges::begin(__range), ranges::end(__range));
544 }
545 }
546#endif
547
548#ifndef _LIBCPP_CXX03_LANG
549 _LIBCPP_CONSTEXPR_SINCE_CXX20
550 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __position, initializer_list<value_type> __il) {
551 return insert(__position, __il.begin(), __il.end());
552 }
553#endif
554
555 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __position);
556 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last);
557
558 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT {
559 size_type __old_size = size();
560 __base_destruct_at_end(new_last: this->__begin_);
561 __annotate_shrink(__old_size);
562 }
563
564 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void resize(size_type __sz);
565 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void resize(size_type __sz, const_reference __x);
566
567 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void swap(vector&)
568#if _LIBCPP_STD_VER >= 14
569 _NOEXCEPT;
570#else
571 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>);
572#endif
573
574 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool __invariants() const;
575
576private:
577 pointer __begin_ = nullptr;
578 pointer __end_ = nullptr;
579 _LIBCPP_COMPRESSED_PAIR(pointer, __cap_ = nullptr, allocator_type, __alloc_);
580
581 // Allocate space for __n objects
582 // throws length_error if __n > max_size()
583 // throws (probably bad_alloc) if memory run out
584 // Precondition: __begin_ == __end_ == __cap_ == nullptr
585 // Precondition: __n > 0
586 // Postcondition: capacity() >= __n
587 // Postcondition: size() == 0
588 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __vallocate(size_type __n) {
589 if (__n > max_size())
590 this->__throw_length_error();
591 auto __allocation = std::__allocate_at_least(this->__alloc_, __n);
592 __begin_ = __allocation.ptr;
593 __end_ = __allocation.ptr;
594 __cap_ = __begin_ + __allocation.count;
595 __annotate_new(current_size: 0);
596 }
597
598 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __vdeallocate() _NOEXCEPT;
599 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type __recommend(size_type __new_size) const;
600 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(size_type __n);
601 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(size_type __n, const_reference __x);
602
603 template <class _InputIterator, class _Sentinel>
604 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
605 __init_with_size(_InputIterator __first, _Sentinel __last, size_type __n) {
606 auto __guard = std::__make_exception_guard(__destroy_vector(*this));
607
608 if (__n > 0) {
609 __vallocate(__n);
610 __construct_at_end(std::move(__first), std::move(__last), __n);
611 }
612
613 __guard.__complete();
614 }
615
616 template <class _InputIterator, class _Sentinel>
617 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
618 __init_with_sentinel(_InputIterator __first, _Sentinel __last) {
619 auto __guard = std::__make_exception_guard(__destroy_vector(*this));
620
621 for (; __first != __last; ++__first)
622 emplace_back(*__first);
623
624 __guard.__complete();
625 }
626
627 template <class _Iterator, class _Sentinel>
628 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __assign_with_sentinel(_Iterator __first, _Sentinel __last);
629
630 // The `_Iterator` in `*_with_size` functions can be input-only only if called from `*_range` (since C++23).
631 // Otherwise, `_Iterator` is a forward iterator.
632
633 template <class _AlgPolicy, class _Iterator, class _Sentinel>
634 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
635 __assign_with_size(_Iterator __first, _Sentinel __last, difference_type __n);
636
637 template <class _AlgPolicy,
638 class _Iterator,
639 __enable_if_t<!is_same<__policy_value_type<_AlgPolicy, _Iterator>, value_type>::value, int> = 0>
640 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
641 __insert_assign_n_unchecked(_Iterator __first, difference_type __n, pointer __position) {
642 for (pointer __end_position = __position + __n; __position != __end_position; ++__position, (void)++__first) {
643 __temp_value<value_type, _Allocator> __tmp(this->__alloc_, *__first);
644 *__position = std::move(__tmp.get());
645 }
646 }
647
648 template <class _AlgPolicy,
649 class _Iterator,
650 __enable_if_t<is_same<__policy_value_type<_AlgPolicy, _Iterator>, value_type>::value, int> = 0>
651 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
652 __insert_assign_n_unchecked(_Iterator __first, difference_type __n, pointer __position) {
653 std::__copy_n<_AlgPolicy>(std::move(__first), __n, __position);
654 }
655
656 template <class _InputIterator, class _Sentinel>
657 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
658 __insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last);
659
660 template <class _AlgPolicy, class _Iterator, class _Sentinel>
661 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
662 __insert_with_size(const_iterator __position, _Iterator __first, _Sentinel __last, difference_type __n);
663
664 template <class _InputIterator, class _Sentinel>
665 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
666 __construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n);
667
668 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator __make_iter(pointer __p) _NOEXCEPT {
669#ifdef _LIBCPP_ABI_BOUNDED_ITERATORS_IN_VECTOR
670 // Bound the iterator according to the capacity, rather than the size.
671 //
672 // Vector guarantees that iterators stay valid as long as no reallocation occurs even if new elements are inserted
673 // into the container; for these cases, we need to make sure that the newly-inserted elements can be accessed
674 // through the bounded iterator without failing checks. The downside is that the bounded iterator won't catch
675 // access that is logically out-of-bounds, i.e., goes beyond the size, but is still within the capacity. With the
676 // current implementation, there is no connection between a bounded iterator and its associated container, so we
677 // don't have a way to update existing valid iterators when the container is resized and thus have to go with
678 // a laxer approach.
679 return std::__make_bounded_iter(__p, this->__begin_, this->__cap_);
680#else
681 return iterator(__p);
682#endif // _LIBCPP_ABI_BOUNDED_ITERATORS_IN_VECTOR
683 }
684
685 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator __make_iter(const_pointer __p) const _NOEXCEPT {
686#ifdef _LIBCPP_ABI_BOUNDED_ITERATORS_IN_VECTOR
687 // Bound the iterator according to the capacity, rather than the size.
688 return std::__make_bounded_iter(__p, const_pointer(this->__begin_), const_pointer(this->__cap_));
689#else
690 return const_iterator(__p);
691#endif // _LIBCPP_ABI_BOUNDED_ITERATORS_IN_VECTOR
692 }
693
694 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __swap_out_circular_buffer(_SplitBuffer& __v);
695 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer
696 __swap_out_circular_buffer(_SplitBuffer& __v, pointer __p);
697 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
698 __move_range(pointer __from_s, pointer __from_e, pointer __to);
699 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign(vector& __c, true_type)
700 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
701 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign(vector& __c, false_type)
702 _NOEXCEPT_(__alloc_traits::is_always_equal::value);
703 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __destruct_at_end(pointer __new_last) _NOEXCEPT {
704 size_type __old_size = size();
705 __base_destruct_at_end(__new_last);
706 __annotate_shrink(__old_size);
707 }
708
709 template <class... _Args>
710 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI inline pointer __emplace_back_slow_path(_Args&&... __args);
711
712 // The following functions are no-ops outside of AddressSanitizer mode.
713 // We call annotations for every allocator, unless explicitly disabled.
714 //
715 // To disable annotations for a particular allocator, change value of
716 // __asan_annotate_container_with_allocator to false.
717 // For more details, see the "Using libc++" documentation page or
718 // the documentation for __sanitizer_annotate_contiguous_container.
719
720 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
721 __annotate_contiguous_container(const void* __old_mid, const void* __new_mid) const {
722 std::__annotate_contiguous_container<_Allocator>(data(), data() + capacity(), __old_mid, __new_mid);
723 }
724
725 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __annotate_new(size_type __current_size) const _NOEXCEPT {
726 __annotate_contiguous_container(old_mid: data() + capacity(), new_mid: data() + __current_size);
727 }
728
729 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __annotate_delete() const _NOEXCEPT {
730 __annotate_contiguous_container(old_mid: data() + size(), new_mid: data() + capacity());
731 }
732
733 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __annotate_increase(size_type __n) const _NOEXCEPT {
734 __annotate_contiguous_container(old_mid: data() + size(), new_mid: data() + size() + __n);
735 }
736
737 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __annotate_shrink(size_type __old_size) const _NOEXCEPT {
738 __annotate_contiguous_container(old_mid: data() + __old_size, new_mid: data() + size());
739 }
740
741 struct _ConstructTransaction {
742 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit _ConstructTransaction(vector& __v, size_type __n)
743 : __v_(__v), __pos_(__v.__end_), __new_end_(__v.__end_ + __n) {
744 __v_.__annotate_increase(__n);
745 }
746
747 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI ~_ConstructTransaction() {
748 __v_.__end_ = __pos_;
749 if (__pos_ != __new_end_) {
750 __v_.__annotate_shrink(__new_end_ - __v_.__begin_);
751 }
752 }
753
754 vector& __v_;
755 pointer __pos_;
756 const_pointer const __new_end_;
757
758 _ConstructTransaction(_ConstructTransaction const&) = delete;
759 _ConstructTransaction& operator=(_ConstructTransaction const&) = delete;
760 };
761
762 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __base_destruct_at_end(pointer __new_last) _NOEXCEPT {
763 pointer __soon_to_be_end = this->__end_;
764 while (__new_last != __soon_to_be_end)
765 __alloc_traits::destroy(this->__alloc_, std::__to_address(--__soon_to_be_end));
766 this->__end_ = __new_last;
767 }
768
769 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const vector& __c) {
770 __copy_assign_alloc(__c, integral_constant<bool, __alloc_traits::propagate_on_container_copy_assignment::value>());
771 }
772
773 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(vector& __c)
774 _NOEXCEPT_(!__alloc_traits::propagate_on_container_move_assignment::value ||
775 is_nothrow_move_assignable<allocator_type>::value) {
776 __move_assign_alloc(__c, integral_constant<bool, __alloc_traits::propagate_on_container_move_assignment::value>());
777 }
778
779 [[__noreturn__]] _LIBCPP_HIDE_FROM_ABI static void __throw_length_error() { std::__throw_length_error(msg: "vector"); }
780
781 [[__noreturn__]] _LIBCPP_HIDE_FROM_ABI static void __throw_out_of_range() { std::__throw_out_of_range(msg: "vector"); }
782
783 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const vector& __c, true_type) {
784 if (this->__alloc_ != __c.__alloc_) {
785 clear();
786 __annotate_delete();
787 __alloc_traits::deallocate(this->__alloc_, this->__begin_, capacity());
788 this->__begin_ = this->__end_ = this->__cap_ = nullptr;
789 }
790 this->__alloc_ = __c.__alloc_;
791 }
792
793 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const vector&, false_type) {}
794
795 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(vector& __c, true_type)
796 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {
797 this->__alloc_ = std::move(__c.__alloc_);
798 }
799
800 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(vector&, false_type) _NOEXCEPT {}
801
802 template <class _Ptr = pointer, __enable_if_t<is_pointer<_Ptr>::value, int> = 0>
803 static _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI _LIBCPP_NO_CFI _Ptr
804 __add_alignment_assumption(_Ptr __p) _NOEXCEPT {
805 if (!__libcpp_is_constant_evaluated()) {
806 return static_cast<pointer>(__builtin_assume_aligned(__p, _LIBCPP_ALIGNOF(decltype(*__p))));
807 }
808 return __p;
809 }
810
811 template <class _Ptr = pointer, __enable_if_t<!is_pointer<_Ptr>::value, int> = 0>
812 static _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI _LIBCPP_NO_CFI _Ptr
813 __add_alignment_assumption(_Ptr __p) _NOEXCEPT {
814 return __p;
815 }
816
817 _LIBCPP_NODEBUG _LIBCPP_ALWAYS_INLINE _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
818 __swap_layouts(_SplitBuffer& __sb) {
819 __sb.__swap_layouts(__begin_, __end_, __cap_);
820 }
821};
822
823#if _LIBCPP_STD_VER >= 17
824template <class _InputIterator,
825 class _Alloc = allocator<__iterator_value_type<_InputIterator>>,
826 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
827 class = enable_if_t<__is_allocator_v<_Alloc>>>
828vector(_InputIterator, _InputIterator) -> vector<__iterator_value_type<_InputIterator>, _Alloc>;
829
830template <class _InputIterator,
831 class _Alloc,
832 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
833 class = enable_if_t<__is_allocator_v<_Alloc>>>
834vector(_InputIterator, _InputIterator, _Alloc) -> vector<__iterator_value_type<_InputIterator>, _Alloc>;
835#endif
836
837#if _LIBCPP_STD_VER >= 23
838template <ranges::input_range _Range,
839 class _Alloc = allocator<ranges::range_value_t<_Range>>,
840 class = enable_if_t<__is_allocator_v<_Alloc>>>
841vector(from_range_t, _Range&&, _Alloc = _Alloc()) -> vector<ranges::range_value_t<_Range>, _Alloc>;
842#endif
843
844// __swap_out_circular_buffer relocates the objects in [__begin_, __end_) into the front of __v and swaps the buffers of
845// *this and __v. It is assumed that __v provides space for exactly (__end_ - __begin_) objects in the front. This
846// function has a strong exception guarantee.
847template <class _Tp, class _Allocator>
848_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::__swap_out_circular_buffer(_SplitBuffer& __v) {
849 __annotate_delete();
850 auto __new_begin = __v.begin() - size();
851 std::__uninitialized_allocator_relocate(
852 this->__alloc_, std::__to_address(__begin_), std::__to_address(__end_), std::__to_address(__new_begin));
853 __v.__set_valid_range(__new_begin, __v.end());
854 __end_ = __begin_; // All the objects have been destroyed by relocating them.
855
856 __swap_layouts(sb&: __v);
857 __v.__set_data(__v.begin());
858 __annotate_new(current_size: size());
859}
860
861// __swap_out_circular_buffer relocates the objects in [__begin_, __p) into the front of __v, the objects in
862// [__p, __end_) into the back of __v and swaps the buffers of *this and __v. It is assumed that __v provides space for
863// exactly (__p - __begin_) objects in the front and space for at least (__end_ - __p) objects in the back. This
864// function has a strong exception guarantee if __begin_ == __p || __end_ == __p.
865template <class _Tp, class _Allocator>
866_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::pointer
867vector<_Tp, _Allocator>::__swap_out_circular_buffer(_SplitBuffer& __v, pointer __p) {
868 __annotate_delete();
869 pointer __ret = __v.begin();
870
871 // Relocate [__p, __end_) first to avoid having a hole in [__begin_, __end_)
872 // in case something in [__begin_, __p) throws.
873 std::__uninitialized_allocator_relocate(
874 this->__alloc_, std::__to_address(__p), std::__to_address(__end_), std::__to_address(__v.end()));
875 auto __relocated_so_far = __end_ - __p;
876 __v.__set_sentinel(__v.end() + __relocated_so_far);
877 __end_ = __p; // The objects in [__p, __end_) have been destroyed by relocating them.
878 auto __new_begin = __v.begin() - (__p - __begin_);
879
880 std::__uninitialized_allocator_relocate(
881 this->__alloc_, std::__to_address(__begin_), std::__to_address(__p), std::__to_address(__new_begin));
882 __v.__set_valid_range(__new_begin, __v.end());
883 __end_ = __begin_; // All the objects have been destroyed by relocating them.
884 __swap_layouts(sb&: __v);
885 __v.__set_data(__v.begin());
886 __annotate_new(current_size: size());
887 return __ret;
888}
889
890template <class _Tp, class _Allocator>
891_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::__vdeallocate() _NOEXCEPT {
892 if (this->__begin_ != nullptr) {
893 clear();
894 __annotate_delete();
895 __alloc_traits::deallocate(this->__alloc_, this->__begin_, capacity());
896 this->__begin_ = this->__end_ = this->__cap_ = nullptr;
897 }
898}
899
900// Precondition: __new_size > capacity()
901template <class _Tp, class _Allocator>
902_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::size_type
903vector<_Tp, _Allocator>::__recommend(size_type __new_size) const {
904 const size_type __ms = max_size();
905 if (__new_size > __ms)
906 this->__throw_length_error();
907 const size_type __cap = capacity();
908 if (__cap >= __ms / 2)
909 return __ms;
910 return std::max<size_type>(2 * __cap, __new_size);
911}
912
913// Default constructs __n objects starting at __end_
914// throws if construction throws
915// Precondition: __n > 0
916// Precondition: size() + __n <= capacity()
917// Postcondition: size() == size() + __n
918template <class _Tp, class _Allocator>
919_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::__construct_at_end(size_type __n) {
920 _ConstructTransaction __tx(*this, __n);
921 const_pointer __new_end = __tx.__new_end_;
922 for (pointer __pos = __tx.__pos_; __pos != __new_end; __tx.__pos_ = ++__pos) {
923 __alloc_traits::construct(this->__alloc_, std::__to_address(__pos));
924 }
925}
926
927// Copy constructs __n objects starting at __end_ from __x
928// throws if construction throws
929// Precondition: __n > 0
930// Precondition: size() + __n <= capacity()
931// Postcondition: size() == old size() + __n
932// Postcondition: [i] == __x for all i in [size() - __n, __n)
933template <class _Tp, class _Allocator>
934_LIBCPP_CONSTEXPR_SINCE_CXX20 inline void
935vector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x) {
936 _ConstructTransaction __tx(*this, __n);
937 const_pointer __new_end = __tx.__new_end_;
938 for (pointer __pos = __tx.__pos_; __pos != __new_end; __tx.__pos_ = ++__pos) {
939 __alloc_traits::construct(this->__alloc_, std::__to_address(__pos), __x);
940 }
941}
942
943template <class _Tp, class _Allocator>
944template <class _InputIterator, class _Sentinel>
945_LIBCPP_CONSTEXPR_SINCE_CXX20 void
946vector<_Tp, _Allocator>::__construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n) {
947 _ConstructTransaction __tx(*this, __n);
948 __tx.__pos_ = std::__uninitialized_allocator_copy(this->__alloc_, std::move(__first), std::move(__last), __tx.__pos_);
949}
950
951template <class _Tp, class _Allocator>
952_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI vector<_Tp, _Allocator>::vector(vector&& __x)
953#if _LIBCPP_STD_VER >= 17
954 noexcept
955#else
956 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
957#endif
958 : __alloc_(std::move(__x.__alloc_)) {
959 this->__begin_ = __x.__begin_;
960 this->__end_ = __x.__end_;
961 this->__cap_ = __x.__cap_;
962 __x.__begin_ = __x.__end_ = __x.__cap_ = nullptr;
963}
964
965template <class _Tp, class _Allocator>
966_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI
967vector<_Tp, _Allocator>::vector(vector&& __x, const __type_identity_t<allocator_type>& __a)
968 : __alloc_(__a) {
969 if (__a == __x.__alloc_) {
970 this->__begin_ = __x.__begin_;
971 this->__end_ = __x.__end_;
972 this->__cap_ = __x.__cap_;
973 __x.__begin_ = __x.__end_ = __x.__cap_ = nullptr;
974 } else {
975 typedef move_iterator<iterator> _Ip;
976 __init_with_size(_Ip(__x.begin()), _Ip(__x.end()), __x.size());
977 }
978}
979
980template <class _Tp, class _Allocator>
981_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::__move_assign(vector& __c, false_type)
982 _NOEXCEPT_(__alloc_traits::is_always_equal::value) {
983 if (this->__alloc_ != __c.__alloc_) {
984 typedef move_iterator<iterator> _Ip;
985 assign(_Ip(__c.begin()), _Ip(__c.end()));
986 } else
987 __move_assign(__c, true_type());
988}
989
990template <class _Tp, class _Allocator>
991_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::__move_assign(vector& __c, true_type)
992 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {
993 __vdeallocate();
994 __move_assign_alloc(__c); // this can throw
995 this->__begin_ = __c.__begin_;
996 this->__end_ = __c.__end_;
997 this->__cap_ = __c.__cap_;
998 __c.__begin_ = __c.__end_ = __c.__cap_ = nullptr;
999}
1000
1001template <class _Tp, class _Allocator>
1002_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI vector<_Tp, _Allocator>&
1003vector<_Tp, _Allocator>::operator=(const vector& __x) {
1004 if (this != std::addressof(__x)) {
1005 __copy_assign_alloc(__x);
1006 assign(__x.__begin_, __x.__end_);
1007 }
1008 return *this;
1009}
1010
1011template <class _Tp, class _Allocator>
1012template <class _Iterator, class _Sentinel>
1013_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
1014vector<_Tp, _Allocator>::__assign_with_sentinel(_Iterator __first, _Sentinel __last) {
1015 pointer __cur = __begin_;
1016 for (; __first != __last && __cur != __end_; ++__first, (void)++__cur)
1017 *__cur = *__first;
1018 if (__cur != __end_) {
1019 __destruct_at_end(new_last: __cur);
1020 } else {
1021 for (; __first != __last; ++__first)
1022 emplace_back(*__first);
1023 }
1024}
1025
1026template <class _Tp, class _Allocator>
1027template <class _AlgPolicy, class _Iterator, class _Sentinel>
1028_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
1029vector<_Tp, _Allocator>::__assign_with_size(_Iterator __first, _Sentinel __last, difference_type __n) {
1030 size_type __new_size = static_cast<size_type>(__n);
1031 if (__new_size <= capacity()) {
1032 auto const __size = size();
1033 if (__new_size > __size) {
1034 auto __mid = std::__copy_n<_AlgPolicy>(std::move(__first), __size, this->__begin_).first;
1035 __construct_at_end(std::move(__mid), std::move(__last), __new_size - __size);
1036 } else {
1037 pointer __m = std::__copy(std::move(__first), __last, this->__begin_).second;
1038 this->__destruct_at_end(__m);
1039 }
1040 } else {
1041 __vdeallocate();
1042 __vallocate(n: __recommend(__new_size));
1043 __construct_at_end(std::move(__first), std::move(__last), __new_size);
1044 }
1045}
1046
1047template <class _Tp, class _Allocator>
1048_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::assign(size_type __n, const_reference __u) {
1049 if (__n <= capacity()) {
1050 size_type __s = size();
1051 std::fill_n(this->__begin_, std::min(__n, __s), __u);
1052 if (__n > __s)
1053 __construct_at_end(__n - __s, __u);
1054 else
1055 this->__destruct_at_end(this->__begin_ + __n);
1056 } else {
1057 __vdeallocate();
1058 __vallocate(n: __recommend(new_size: static_cast<size_type>(__n)));
1059 __construct_at_end(__n, __u);
1060 }
1061}
1062
1063template <class _Tp, class _Allocator>
1064_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::reserve(size_type __n) {
1065 if (__n > capacity()) {
1066 if (__n > max_size())
1067 this->__throw_length_error();
1068 _SplitBuffer __v(__n, size(), this->__alloc_);
1069 __swap_out_circular_buffer(__v);
1070 }
1071}
1072
1073template <class _Tp, class _Allocator>
1074_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT {
1075 if (capacity() > size()) {
1076#if _LIBCPP_HAS_EXCEPTIONS
1077 try {
1078#endif // _LIBCPP_HAS_EXCEPTIONS
1079 _SplitBuffer __v(size(), size(), this->__alloc_);
1080 // The Standard mandates shrink_to_fit() does not increase the capacity.
1081 // With equal capacity keep the existing buffer. This avoids extra work
1082 // due to swapping the elements.
1083 if (__v.capacity() < capacity())
1084 __swap_out_circular_buffer(__v);
1085#if _LIBCPP_HAS_EXCEPTIONS
1086 } catch (...) {
1087 }
1088#endif // _LIBCPP_HAS_EXCEPTIONS
1089 }
1090}
1091
1092template <class _Tp, class _Allocator>
1093template <class... _Args>
1094_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::pointer
1095vector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args) {
1096 _SplitBuffer __v(__recommend(new_size: size() + 1), size(), this->__alloc_);
1097 // __v.emplace_back(std::forward<_Args>(__args)...);
1098 pointer __end = __v.end();
1099 __alloc_traits::construct(this->__alloc_, std::__to_address(__end), std::forward<_Args>(__args)...);
1100 __v.__set_sentinel(++__end);
1101 __swap_out_circular_buffer(__v);
1102 return this->__end_;
1103}
1104
1105// This makes the compiler inline `__else()` if `__cond` is known to be false. Currently LLVM doesn't do that without
1106// the `__builtin_constant_p`, since it considers `__else` unlikely even through it's known to be run.
1107// See https://llvm.org/PR154292
1108template <class _If, class _Else>
1109_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void __if_likely_else(bool __cond, _If __if, _Else __else) {
1110 if (__builtin_constant_p(__cond)) {
1111 if (__cond)
1112 __if();
1113 else
1114 __else();
1115 } else {
1116 if (__cond) [[__likely__]]
1117 __if();
1118 else
1119 __else();
1120 }
1121}
1122
1123template <class _Tp, class _Allocator>
1124template <class... _Args>
1125_LIBCPP_CONSTEXPR_SINCE_CXX20 inline
1126#if _LIBCPP_STD_VER >= 17
1127 typename vector<_Tp, _Allocator>::reference
1128#else
1129 void
1130#endif
1131 vector<_Tp, _Allocator>::emplace_back(_Args&&... __args) {
1132 pointer __end = this->__end_;
1133 std::__if_likely_else(
1134 __end < this->__cap_,
1135 [&] {
1136 __emplace_back_assume_capacity(std::forward<_Args>(__args)...);
1137 ++__end;
1138 },
1139 [&] { __end = __emplace_back_slow_path(std::forward<_Args>(__args)...); });
1140
1141 this->__end_ = __end;
1142#if _LIBCPP_STD_VER >= 17
1143 return *(__end - 1);
1144#endif
1145}
1146
1147template <class _Tp, class _Allocator>
1148_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::iterator
1149vector<_Tp, _Allocator>::erase(const_iterator __position) {
1150 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
1151 __position != end(), "vector::erase(iterator) called with a non-dereferenceable iterator");
1152 difference_type __ps = __position - cbegin();
1153 pointer __p = this->__begin_ + __ps;
1154 this->__destruct_at_end(std::move(__p + 1, this->__end_, __p));
1155 return __make_iter(__p);
1156}
1157
1158template <class _Tp, class _Allocator>
1159_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator
1160vector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last) {
1161 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__first <= __last, "vector::erase(first, last) called with invalid range");
1162 pointer __p = this->__begin_ + (__first - begin());
1163 if (__first != __last) {
1164 this->__destruct_at_end(std::move(__p + (__last - __first), this->__end_, __p));
1165 }
1166 return __make_iter(__p);
1167}
1168
1169template <class _Tp, class _Allocator>
1170_LIBCPP_CONSTEXPR_SINCE_CXX20 void
1171vector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to) {
1172 pointer __old_last = this->__end_;
1173 difference_type __n = __old_last - __to;
1174 {
1175 pointer __i = __from_s + __n;
1176 _ConstructTransaction __tx(*this, __from_e - __i);
1177 for (pointer __pos = __tx.__pos_; __i < __from_e; ++__i, (void)++__pos, __tx.__pos_ = __pos) {
1178 __alloc_traits::construct(this->__alloc_, std::__to_address(__pos), std::move(*__i));
1179 }
1180 }
1181 std::move_backward(__from_s, __from_s + __n, __old_last);
1182}
1183
1184template <class _Tp, class _Allocator>
1185_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator
1186vector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x) {
1187 pointer __p = this->__begin_ + (__position - begin());
1188 if (this->__end_ < this->__cap_) {
1189 if (__p == this->__end_) {
1190 __emplace_back_assume_capacity(__x);
1191 } else {
1192 __move_range(from_s: __p, from_e: this->__end_, to: __p + 1);
1193 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1194 if (std::__is_pointer_in_range(std::__to_address(__p), std::__to_address(__end_), std::addressof(__x)))
1195 ++__xr;
1196 *__p = *__xr;
1197 }
1198 } else {
1199 _SplitBuffer __v(__recommend(new_size: size() + 1), __p - this->__begin_, this->__alloc_);
1200 __v.emplace_back(__x);
1201 __p = __swap_out_circular_buffer(__v, __p);
1202 }
1203 return __make_iter(__p);
1204}
1205
1206template <class _Tp, class _Allocator>
1207_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator
1208vector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x) {
1209 pointer __p = this->__begin_ + (__position - begin());
1210 if (this->__end_ < this->__cap_) {
1211 if (__p == this->__end_) {
1212 __emplace_back_assume_capacity(std::move(__x));
1213 } else {
1214 __move_range(from_s: __p, from_e: this->__end_, to: __p + 1);
1215 *__p = std::move(__x);
1216 }
1217 } else {
1218 _SplitBuffer __v(__recommend(new_size: size() + 1), __p - this->__begin_, this->__alloc_);
1219 __v.emplace_back(std::move(__x));
1220 __p = __swap_out_circular_buffer(__v, __p);
1221 }
1222 return __make_iter(__p);
1223}
1224
1225template <class _Tp, class _Allocator>
1226template <class... _Args>
1227_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator
1228vector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args) {
1229 pointer __p = this->__begin_ + (__position - begin());
1230 if (this->__end_ < this->__cap_) {
1231 if (__p == this->__end_) {
1232 __emplace_back_assume_capacity(std::forward<_Args>(__args)...);
1233 } else {
1234 __temp_value<value_type, _Allocator> __tmp(this->__alloc_, std::forward<_Args>(__args)...);
1235 __move_range(from_s: __p, from_e: this->__end_, to: __p + 1);
1236 *__p = std::move(__tmp.get());
1237 }
1238 } else {
1239 _SplitBuffer __v(__recommend(new_size: size() + 1), __p - this->__begin_, this->__alloc_);
1240 __v.emplace_back(std::forward<_Args>(__args)...);
1241 __p = __swap_out_circular_buffer(__v, __p);
1242 }
1243 return __make_iter(__p);
1244}
1245
1246template <class _Tp, class _Allocator>
1247_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator
1248vector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x) {
1249 pointer __p = this->__begin_ + (__position - begin());
1250 if (__n > 0) {
1251 if (__n <= static_cast<size_type>(this->__cap_ - this->__end_)) {
1252 size_type __old_n = __n;
1253 pointer __old_last = this->__end_;
1254 if (__n > static_cast<size_type>(this->__end_ - __p)) {
1255 size_type __cx = __n - (this->__end_ - __p);
1256 __construct_at_end(__cx, __x);
1257 __n -= __cx;
1258 }
1259 if (__n > 0) {
1260 __move_range(from_s: __p, from_e: __old_last, to: __p + __old_n);
1261 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1262 if (std::__is_pointer_in_range(std::__to_address(__p), std::__to_address(__end_), std::addressof(__x)))
1263 __xr += __old_n;
1264 std::fill_n(__p, __n, *__xr);
1265 }
1266 } else {
1267 _SplitBuffer __v(__recommend(new_size: size() + __n), __p - this->__begin_, this->__alloc_);
1268 __v.__construct_at_end(__n, __x);
1269 __p = __swap_out_circular_buffer(__v, __p);
1270 }
1271 }
1272 return __make_iter(__p);
1273}
1274
1275template <class _Tp, class _Allocator>
1276template <class _InputIterator, class _Sentinel>
1277_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::iterator
1278vector<_Tp, _Allocator>::__insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last) {
1279 difference_type __off = __position - begin();
1280 pointer __p = this->__begin_ + __off;
1281 pointer __old_last = this->__end_;
1282 for (; this->__end_ != this->__cap_ && __first != __last; ++__first)
1283 __emplace_back_assume_capacity(*__first);
1284
1285 if (__first == __last)
1286 (void)std::rotate(__p, __old_last, this->__end_);
1287 else {
1288 _SplitBuffer __v(__alloc_);
1289 auto __guard = std::__make_exception_guard(
1290 _AllocatorDestroyRangeReverse<allocator_type, pointer>(__alloc_, __old_last, this->__end_));
1291 __v.__construct_at_end_with_sentinel(std::move(__first), std::move(__last));
1292 _SplitBuffer __merged(
1293 __recommend(new_size: size() + __v.size()), __off, __alloc_); // has `__off` positions available at the front
1294 std::__uninitialized_allocator_relocate(
1295 __alloc_, std::__to_address(__old_last), std::__to_address(this->__end_), std::__to_address(__merged.end()));
1296 __guard.__complete(); // Release the guard once objects in [__old_last_, __end_) have been successfully relocated.
1297 __merged.__set_sentinel(__merged.end() + (this->__end_ - __old_last));
1298 this->__end_ = __old_last;
1299 std::__uninitialized_allocator_relocate(
1300 __alloc_, std::__to_address(__v.begin()), std::__to_address(__v.end()), std::__to_address(__merged.end()));
1301 __merged.__set_sentinel(__merged.size() + __v.size());
1302 __v.__set_sentinel(__v.begin());
1303 __p = __swap_out_circular_buffer(__merged, __p);
1304 }
1305 return __make_iter(__p);
1306}
1307
1308template <class _Tp, class _Allocator>
1309template <class _AlgPolicy, class _Iterator, class _Sentinel>
1310_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::iterator
1311vector<_Tp, _Allocator>::__insert_with_size(
1312 const_iterator __position, _Iterator __first, _Sentinel __last, difference_type __n) {
1313 pointer __p = this->__begin_ + (__position - begin());
1314 if (__n > 0) {
1315 if (__n <= this->__cap_ - this->__end_) {
1316 pointer __old_last = this->__end_;
1317 difference_type __dx = this->__end_ - __p;
1318 if (__n > __dx) {
1319#if _LIBCPP_STD_VER >= 23
1320 if constexpr (!forward_iterator<_Iterator>) {
1321 __construct_at_end(std::move(__first), std::move(__last), __n);
1322 std::rotate(__p, __old_last, this->__end_);
1323 } else
1324#endif
1325 {
1326 _Iterator __m = std::next(__first, __dx);
1327 __construct_at_end(__m, __last, __n - __dx);
1328 if (__dx > 0) {
1329 __move_range(from_s: __p, from_e: __old_last, to: __p + __n);
1330 __insert_assign_n_unchecked<_AlgPolicy>(__first, __dx, __p);
1331 }
1332 }
1333 } else {
1334 __move_range(from_s: __p, from_e: __old_last, to: __p + __n);
1335 __insert_assign_n_unchecked<_AlgPolicy>(std::move(__first), __n, __p);
1336 }
1337 } else {
1338 _SplitBuffer __v(__recommend(new_size: size() + __n), __p - this->__begin_, this->__alloc_);
1339 __v.__construct_at_end_with_size(std::move(__first), __n);
1340 __p = __swap_out_circular_buffer(__v, __p);
1341 }
1342 }
1343 return __make_iter(__p);
1344}
1345
1346template <class _Tp, class _Allocator>
1347_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::resize(size_type __new_size) {
1348 size_type __current_size = size();
1349 if (__current_size < __new_size) {
1350 if (__new_size <= capacity()) {
1351 __construct_at_end(__new_size - __current_size);
1352 } else {
1353 _SplitBuffer __v(__recommend(__new_size), __current_size, __alloc_);
1354 __v.__construct_at_end(__new_size - __current_size);
1355 __swap_out_circular_buffer(__v);
1356 }
1357 } else if (__current_size > __new_size) {
1358 this->__destruct_at_end(this->__begin_ + __new_size);
1359 }
1360}
1361
1362template <class _Tp, class _Allocator>
1363_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::resize(size_type __new_size, const_reference __x) {
1364 size_type __current_size = size();
1365 if (__current_size < __new_size) {
1366 if (__new_size <= capacity())
1367 __construct_at_end(__new_size - __current_size, __x);
1368 else {
1369 _SplitBuffer __v(__recommend(__new_size), __current_size, __alloc_);
1370 __v.__construct_at_end(__new_size - __current_size, __x);
1371 __swap_out_circular_buffer(__v);
1372 }
1373 } else if (__current_size > __new_size) {
1374 this->__destruct_at_end(this->__begin_ + __new_size);
1375 }
1376}
1377
1378template <class _Tp, class _Allocator>
1379_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::swap(vector& __x)
1380#if _LIBCPP_STD_VER >= 14
1381 _NOEXCEPT
1382#else
1383 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>)
1384#endif
1385{
1386 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1387 __alloc_traits::propagate_on_container_swap::value || this->__alloc_ == __x.__alloc_,
1388 "vector::swap: Either propagate_on_container_swap must be true"
1389 " or the allocators must compare equal");
1390 std::swap(this->__begin_, __x.__begin_);
1391 std::swap(this->__end_, __x.__end_);
1392 std::swap(this->__cap_, __x.__cap_);
1393 std::__swap_allocator(this->__alloc_, __x.__alloc_);
1394}
1395
1396template <class _Tp, class _Allocator>
1397_LIBCPP_CONSTEXPR_SINCE_CXX20 bool vector<_Tp, _Allocator>::__invariants() const {
1398 if (this->__begin_ == nullptr) {
1399 if (this->__end_ != nullptr || this->__cap_ != nullptr)
1400 return false;
1401 } else {
1402 if (this->__begin_ > this->__end_)
1403 return false;
1404 if (this->__begin_ == this->__cap_)
1405 return false;
1406 if (this->__end_ > this->__cap_)
1407 return false;
1408 }
1409 return true;
1410}
1411
1412#if _LIBCPP_STD_VER >= 20
1413template <>
1414inline constexpr bool __format::__enable_insertable<vector<char>> = true;
1415# if _LIBCPP_HAS_WIDE_CHARACTERS
1416template <>
1417inline constexpr bool __format::__enable_insertable<vector<wchar_t>> = true;
1418# endif
1419#endif // _LIBCPP_STD_VER >= 20
1420
1421_LIBCPP_END_NAMESPACE_STD
1422
1423_LIBCPP_POP_MACROS
1424
1425#endif // _LIBCPP___VECTOR_VECTOR_H
1426