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<__wrap_iter<pointer> >;
108 using const_iterator = __bounded_iter<__wrap_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(
680 std::__wrap_iter<pointer>(__p),
681 std::__wrap_iter<pointer>(this->__begin_),
682 std::__wrap_iter<pointer>(this->__cap_));
683#else
684 return iterator(__p);
685#endif // _LIBCPP_ABI_BOUNDED_ITERATORS_IN_VECTOR
686 }
687
688 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator __make_iter(const_pointer __p) const _NOEXCEPT {
689#ifdef _LIBCPP_ABI_BOUNDED_ITERATORS_IN_VECTOR
690 // Bound the iterator according to the capacity, rather than the size.
691 return std::__make_bounded_iter(
692 std::__wrap_iter<const_pointer>(__p),
693 std::__wrap_iter<const_pointer>(this->__begin_),
694 std::__wrap_iter<const_pointer>(this->__cap_));
695#else
696 return const_iterator(__p);
697#endif // _LIBCPP_ABI_BOUNDED_ITERATORS_IN_VECTOR
698 }
699
700 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __swap_out_circular_buffer(_SplitBuffer& __v);
701 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer
702 __swap_out_circular_buffer(_SplitBuffer& __v, pointer __p);
703 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
704 __move_range(pointer __from_s, pointer __from_e, pointer __to);
705 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign(vector& __c, true_type)
706 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
707 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign(vector& __c, false_type)
708 _NOEXCEPT_(__alloc_traits::is_always_equal::value);
709 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __destruct_at_end(pointer __new_last) _NOEXCEPT {
710 size_type __old_size = size();
711 __base_destruct_at_end(__new_last);
712 __annotate_shrink(__old_size);
713 }
714
715 template <class... _Args>
716 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI inline pointer __emplace_back_slow_path(_Args&&... __args);
717
718 // The following functions are no-ops outside of AddressSanitizer mode.
719 // We call annotations for every allocator, unless explicitly disabled.
720 //
721 // To disable annotations for a particular allocator, change value of
722 // __asan_annotate_container_with_allocator to false.
723 // For more details, see the "Using libc++" documentation page or
724 // the documentation for __sanitizer_annotate_contiguous_container.
725
726 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
727 __annotate_contiguous_container(const void* __old_mid, const void* __new_mid) const {
728 std::__annotate_contiguous_container<_Allocator>(data(), data() + capacity(), __old_mid, __new_mid);
729 }
730
731 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __annotate_new(size_type __current_size) const _NOEXCEPT {
732 __annotate_contiguous_container(old_mid: data() + capacity(), new_mid: data() + __current_size);
733 }
734
735 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __annotate_delete() const _NOEXCEPT {
736 __annotate_contiguous_container(old_mid: data() + size(), new_mid: data() + capacity());
737 }
738
739 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __annotate_increase(size_type __n) const _NOEXCEPT {
740 __annotate_contiguous_container(old_mid: data() + size(), new_mid: data() + size() + __n);
741 }
742
743 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __annotate_shrink(size_type __old_size) const _NOEXCEPT {
744 __annotate_contiguous_container(old_mid: data() + __old_size, new_mid: data() + size());
745 }
746
747 struct _ConstructTransaction {
748 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit _ConstructTransaction(vector& __v, size_type __n)
749 : __v_(__v), __pos_(__v.__end_), __new_end_(__v.__end_ + __n) {
750 __v_.__annotate_increase(__n);
751 }
752
753 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI ~_ConstructTransaction() {
754 __v_.__end_ = __pos_;
755 if (__pos_ != __new_end_) {
756 __v_.__annotate_shrink(__new_end_ - __v_.__begin_);
757 }
758 }
759
760 vector& __v_;
761 pointer __pos_;
762 const_pointer const __new_end_;
763
764 _ConstructTransaction(_ConstructTransaction const&) = delete;
765 _ConstructTransaction& operator=(_ConstructTransaction const&) = delete;
766 };
767
768 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __base_destruct_at_end(pointer __new_last) _NOEXCEPT {
769 pointer __soon_to_be_end = this->__end_;
770 while (__new_last != __soon_to_be_end)
771 __alloc_traits::destroy(this->__alloc_, std::__to_address(--__soon_to_be_end));
772 this->__end_ = __new_last;
773 }
774
775 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const vector& __c) {
776 __copy_assign_alloc(__c, integral_constant<bool, __alloc_traits::propagate_on_container_copy_assignment::value>());
777 }
778
779 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(vector& __c)
780 _NOEXCEPT_(!__alloc_traits::propagate_on_container_move_assignment::value ||
781 is_nothrow_move_assignable<allocator_type>::value) {
782 __move_assign_alloc(__c, integral_constant<bool, __alloc_traits::propagate_on_container_move_assignment::value>());
783 }
784
785 [[__noreturn__]] _LIBCPP_HIDE_FROM_ABI static void __throw_length_error() { std::__throw_length_error(msg: "vector"); }
786
787 [[__noreturn__]] _LIBCPP_HIDE_FROM_ABI static void __throw_out_of_range() { std::__throw_out_of_range(msg: "vector"); }
788
789 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const vector& __c, true_type) {
790 if (this->__alloc_ != __c.__alloc_) {
791 clear();
792 __annotate_delete();
793 __alloc_traits::deallocate(this->__alloc_, this->__begin_, capacity());
794 this->__begin_ = this->__end_ = this->__cap_ = nullptr;
795 }
796 this->__alloc_ = __c.__alloc_;
797 }
798
799 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const vector&, false_type) {}
800
801 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(vector& __c, true_type)
802 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {
803 this->__alloc_ = std::move(__c.__alloc_);
804 }
805
806 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(vector&, false_type) _NOEXCEPT {}
807
808 template <class _Ptr = pointer, __enable_if_t<is_pointer<_Ptr>::value, int> = 0>
809 static _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI _LIBCPP_NO_CFI _Ptr
810 __add_alignment_assumption(_Ptr __p) _NOEXCEPT {
811 if (!__libcpp_is_constant_evaluated()) {
812 return static_cast<pointer>(__builtin_assume_aligned(__p, _LIBCPP_ALIGNOF(decltype(*__p))));
813 }
814 return __p;
815 }
816
817 template <class _Ptr = pointer, __enable_if_t<!is_pointer<_Ptr>::value, int> = 0>
818 static _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI _LIBCPP_NO_CFI _Ptr
819 __add_alignment_assumption(_Ptr __p) _NOEXCEPT {
820 return __p;
821 }
822
823 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __swap_layouts(_SplitBuffer& __sb) {
824 auto __vector_begin = __begin_;
825 auto __vector_sentinel = __end_;
826 auto __vector_cap = __cap_;
827
828 auto __sb_begin = __sb.begin();
829 auto __sb_sentinel = __sb.__raw_sentinel();
830 auto __sb_cap = __sb.__raw_capacity();
831
832 // TODO: replace with __set_valid_range and __set_capacity when vector supports it.
833 __begin_ = __sb_begin;
834 __end_ = __sb_sentinel;
835 __cap_ = __sb_cap;
836
837 __sb.__set_valid_range(__vector_begin, __vector_sentinel);
838 __sb.__set_capacity(__vector_cap);
839 }
840};
841
842#if _LIBCPP_STD_VER >= 17
843template <class _InputIterator,
844 class _Alloc = allocator<__iterator_value_type<_InputIterator>>,
845 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
846 class = enable_if_t<__is_allocator_v<_Alloc>>>
847vector(_InputIterator, _InputIterator) -> vector<__iterator_value_type<_InputIterator>, _Alloc>;
848
849template <class _InputIterator,
850 class _Alloc,
851 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
852 class = enable_if_t<__is_allocator_v<_Alloc>>>
853vector(_InputIterator, _InputIterator, _Alloc) -> vector<__iterator_value_type<_InputIterator>, _Alloc>;
854#endif
855
856#if _LIBCPP_STD_VER >= 23
857template <ranges::input_range _Range,
858 class _Alloc = allocator<ranges::range_value_t<_Range>>,
859 class = enable_if_t<__is_allocator_v<_Alloc>>>
860vector(from_range_t, _Range&&, _Alloc = _Alloc()) -> vector<ranges::range_value_t<_Range>, _Alloc>;
861#endif
862
863// __swap_out_circular_buffer relocates the objects in [__begin_, __end_) into the front of __v and swaps the buffers of
864// *this and __v. It is assumed that __v provides space for exactly (__end_ - __begin_) objects in the front. This
865// function has a strong exception guarantee.
866template <class _Tp, class _Allocator>
867_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::__swap_out_circular_buffer(_SplitBuffer& __v) {
868 __annotate_delete();
869 auto __new_begin = __v.begin() - size();
870 std::__uninitialized_allocator_relocate(
871 this->__alloc_, std::__to_address(__begin_), std::__to_address(__end_), std::__to_address(__new_begin));
872 __v.__set_valid_range(__new_begin, __v.end());
873 __end_ = __begin_; // All the objects have been destroyed by relocating them.
874
875 __swap_layouts(sb&: __v);
876 __v.__set_data(__v.begin());
877 __annotate_new(current_size: size());
878}
879
880// __swap_out_circular_buffer relocates the objects in [__begin_, __p) into the front of __v, the objects in
881// [__p, __end_) into the back of __v and swaps the buffers of *this and __v. It is assumed that __v provides space for
882// exactly (__p - __begin_) objects in the front and space for at least (__end_ - __p) objects in the back. This
883// function has a strong exception guarantee if __begin_ == __p || __end_ == __p.
884template <class _Tp, class _Allocator>
885_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::pointer
886vector<_Tp, _Allocator>::__swap_out_circular_buffer(_SplitBuffer& __v, pointer __p) {
887 __annotate_delete();
888 pointer __ret = __v.begin();
889
890 // Relocate [__p, __end_) first to avoid having a hole in [__begin_, __end_)
891 // in case something in [__begin_, __p) throws.
892 std::__uninitialized_allocator_relocate(
893 this->__alloc_, std::__to_address(__p), std::__to_address(__end_), std::__to_address(__v.end()));
894 auto __relocated_so_far = __end_ - __p;
895 __v.__set_sentinel(__v.end() + __relocated_so_far);
896 __end_ = __p; // The objects in [__p, __end_) have been destroyed by relocating them.
897 auto __new_begin = __v.begin() - (__p - __begin_);
898
899 std::__uninitialized_allocator_relocate(
900 this->__alloc_, std::__to_address(__begin_), std::__to_address(__p), std::__to_address(__new_begin));
901 __v.__set_valid_range(__new_begin, __v.end());
902 __end_ = __begin_; // All the objects have been destroyed by relocating them.
903 __swap_layouts(sb&: __v);
904 __v.__set_data(__v.begin());
905 __annotate_new(current_size: size());
906 return __ret;
907}
908
909template <class _Tp, class _Allocator>
910_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::__vdeallocate() _NOEXCEPT {
911 if (this->__begin_ != nullptr) {
912 clear();
913 __annotate_delete();
914 __alloc_traits::deallocate(this->__alloc_, this->__begin_, capacity());
915 this->__begin_ = this->__end_ = this->__cap_ = nullptr;
916 }
917}
918
919// Precondition: __new_size > capacity()
920template <class _Tp, class _Allocator>
921_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::size_type
922vector<_Tp, _Allocator>::__recommend(size_type __new_size) const {
923 const size_type __ms = max_size();
924 if (__new_size > __ms)
925 this->__throw_length_error();
926 const size_type __cap = capacity();
927 if (__cap >= __ms / 2)
928 return __ms;
929 return std::max<size_type>(2 * __cap, __new_size);
930}
931
932// Default constructs __n objects starting at __end_
933// throws if construction throws
934// Precondition: __n > 0
935// Precondition: size() + __n <= capacity()
936// Postcondition: size() == size() + __n
937template <class _Tp, class _Allocator>
938_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::__construct_at_end(size_type __n) {
939 _ConstructTransaction __tx(*this, __n);
940 const_pointer __new_end = __tx.__new_end_;
941 for (pointer __pos = __tx.__pos_; __pos != __new_end; __tx.__pos_ = ++__pos) {
942 __alloc_traits::construct(this->__alloc_, std::__to_address(__pos));
943 }
944}
945
946// Copy constructs __n objects starting at __end_ from __x
947// throws if construction throws
948// Precondition: __n > 0
949// Precondition: size() + __n <= capacity()
950// Postcondition: size() == old size() + __n
951// Postcondition: [i] == __x for all i in [size() - __n, __n)
952template <class _Tp, class _Allocator>
953_LIBCPP_CONSTEXPR_SINCE_CXX20 inline void
954vector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x) {
955 _ConstructTransaction __tx(*this, __n);
956 const_pointer __new_end = __tx.__new_end_;
957 for (pointer __pos = __tx.__pos_; __pos != __new_end; __tx.__pos_ = ++__pos) {
958 __alloc_traits::construct(this->__alloc_, std::__to_address(__pos), __x);
959 }
960}
961
962template <class _Tp, class _Allocator>
963template <class _InputIterator, class _Sentinel>
964_LIBCPP_CONSTEXPR_SINCE_CXX20 void
965vector<_Tp, _Allocator>::__construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n) {
966 _ConstructTransaction __tx(*this, __n);
967 __tx.__pos_ = std::__uninitialized_allocator_copy(this->__alloc_, std::move(__first), std::move(__last), __tx.__pos_);
968}
969
970template <class _Tp, class _Allocator>
971_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI vector<_Tp, _Allocator>::vector(vector&& __x)
972#if _LIBCPP_STD_VER >= 17
973 noexcept
974#else
975 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
976#endif
977 : __alloc_(std::move(__x.__alloc_)) {
978 this->__begin_ = __x.__begin_;
979 this->__end_ = __x.__end_;
980 this->__cap_ = __x.__cap_;
981 __x.__begin_ = __x.__end_ = __x.__cap_ = nullptr;
982}
983
984template <class _Tp, class _Allocator>
985_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI
986vector<_Tp, _Allocator>::vector(vector&& __x, const __type_identity_t<allocator_type>& __a)
987 : __alloc_(__a) {
988 if (__a == __x.__alloc_) {
989 this->__begin_ = __x.__begin_;
990 this->__end_ = __x.__end_;
991 this->__cap_ = __x.__cap_;
992 __x.__begin_ = __x.__end_ = __x.__cap_ = nullptr;
993 } else {
994 typedef move_iterator<iterator> _Ip;
995 __init_with_size(_Ip(__x.begin()), _Ip(__x.end()), __x.size());
996 }
997}
998
999template <class _Tp, class _Allocator>
1000_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::__move_assign(vector& __c, false_type)
1001 _NOEXCEPT_(__alloc_traits::is_always_equal::value) {
1002 if (this->__alloc_ != __c.__alloc_) {
1003 typedef move_iterator<iterator> _Ip;
1004 assign(_Ip(__c.begin()), _Ip(__c.end()));
1005 } else
1006 __move_assign(__c, true_type());
1007}
1008
1009template <class _Tp, class _Allocator>
1010_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::__move_assign(vector& __c, true_type)
1011 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {
1012 __vdeallocate();
1013 __move_assign_alloc(__c); // this can throw
1014 this->__begin_ = __c.__begin_;
1015 this->__end_ = __c.__end_;
1016 this->__cap_ = __c.__cap_;
1017 __c.__begin_ = __c.__end_ = __c.__cap_ = nullptr;
1018}
1019
1020template <class _Tp, class _Allocator>
1021_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI vector<_Tp, _Allocator>&
1022vector<_Tp, _Allocator>::operator=(const vector& __x) {
1023 if (this != std::addressof(__x)) {
1024 __copy_assign_alloc(__x);
1025 assign(__x.__begin_, __x.__end_);
1026 }
1027 return *this;
1028}
1029
1030template <class _Tp, class _Allocator>
1031template <class _Iterator, class _Sentinel>
1032_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
1033vector<_Tp, _Allocator>::__assign_with_sentinel(_Iterator __first, _Sentinel __last) {
1034 pointer __cur = __begin_;
1035 for (; __first != __last && __cur != __end_; ++__first, (void)++__cur)
1036 *__cur = *__first;
1037 if (__cur != __end_) {
1038 __destruct_at_end(new_last: __cur);
1039 } else {
1040 for (; __first != __last; ++__first)
1041 emplace_back(*__first);
1042 }
1043}
1044
1045template <class _Tp, class _Allocator>
1046template <class _AlgPolicy, class _Iterator, class _Sentinel>
1047_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
1048vector<_Tp, _Allocator>::__assign_with_size(_Iterator __first, _Sentinel __last, difference_type __n) {
1049 size_type __new_size = static_cast<size_type>(__n);
1050 if (__new_size <= capacity()) {
1051 auto const __size = size();
1052 if (__new_size > __size) {
1053 auto __mid = std::__copy_n<_AlgPolicy>(std::move(__first), __size, this->__begin_).first;
1054 __construct_at_end(std::move(__mid), std::move(__last), __new_size - __size);
1055 } else {
1056 pointer __m = std::__copy(std::move(__first), __last, this->__begin_).second;
1057 this->__destruct_at_end(__m);
1058 }
1059 } else {
1060 __vdeallocate();
1061 __vallocate(n: __recommend(__new_size));
1062 __construct_at_end(std::move(__first), std::move(__last), __new_size);
1063 }
1064}
1065
1066template <class _Tp, class _Allocator>
1067_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::assign(size_type __n, const_reference __u) {
1068 if (__n <= capacity()) {
1069 size_type __s = size();
1070 std::fill_n(this->__begin_, std::min(__n, __s), __u);
1071 if (__n > __s)
1072 __construct_at_end(__n - __s, __u);
1073 else
1074 this->__destruct_at_end(this->__begin_ + __n);
1075 } else {
1076 __vdeallocate();
1077 __vallocate(n: __recommend(new_size: static_cast<size_type>(__n)));
1078 __construct_at_end(__n, __u);
1079 }
1080}
1081
1082template <class _Tp, class _Allocator>
1083_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::reserve(size_type __n) {
1084 if (__n > capacity()) {
1085 if (__n > max_size())
1086 this->__throw_length_error();
1087 _SplitBuffer __v(__n, size(), this->__alloc_);
1088 __swap_out_circular_buffer(__v);
1089 }
1090}
1091
1092template <class _Tp, class _Allocator>
1093_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT {
1094 if (capacity() > size()) {
1095#if _LIBCPP_HAS_EXCEPTIONS
1096 try {
1097#endif // _LIBCPP_HAS_EXCEPTIONS
1098 _SplitBuffer __v(size(), size(), this->__alloc_);
1099 // The Standard mandates shrink_to_fit() does not increase the capacity.
1100 // With equal capacity keep the existing buffer. This avoids extra work
1101 // due to swapping the elements.
1102 if (__v.capacity() < capacity())
1103 __swap_out_circular_buffer(__v);
1104#if _LIBCPP_HAS_EXCEPTIONS
1105 } catch (...) {
1106 }
1107#endif // _LIBCPP_HAS_EXCEPTIONS
1108 }
1109}
1110
1111template <class _Tp, class _Allocator>
1112template <class... _Args>
1113_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::pointer
1114vector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args) {
1115 _SplitBuffer __v(__recommend(new_size: size() + 1), size(), this->__alloc_);
1116 // __v.emplace_back(std::forward<_Args>(__args)...);
1117 pointer __end = __v.end();
1118 __alloc_traits::construct(this->__alloc_, std::__to_address(__end), std::forward<_Args>(__args)...);
1119 __v.__set_sentinel(++__end);
1120 __swap_out_circular_buffer(__v);
1121 return this->__end_;
1122}
1123
1124// This makes the compiler inline `__else()` if `__cond` is known to be false. Currently LLVM doesn't do that without
1125// the `__builtin_constant_p`, since it considers `__else` unlikely even through it's known to be run.
1126// See https://llvm.org/PR154292
1127template <class _If, class _Else>
1128_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void __if_likely_else(bool __cond, _If __if, _Else __else) {
1129 if (__builtin_constant_p(__cond)) {
1130 if (__cond)
1131 __if();
1132 else
1133 __else();
1134 } else {
1135 if (__cond) [[__likely__]]
1136 __if();
1137 else
1138 __else();
1139 }
1140}
1141
1142template <class _Tp, class _Allocator>
1143template <class... _Args>
1144_LIBCPP_CONSTEXPR_SINCE_CXX20 inline
1145#if _LIBCPP_STD_VER >= 17
1146 typename vector<_Tp, _Allocator>::reference
1147#else
1148 void
1149#endif
1150 vector<_Tp, _Allocator>::emplace_back(_Args&&... __args) {
1151 pointer __end = this->__end_;
1152 std::__if_likely_else(
1153 __end < this->__cap_,
1154 [&] {
1155 __emplace_back_assume_capacity(std::forward<_Args>(__args)...);
1156 ++__end;
1157 },
1158 [&] { __end = __emplace_back_slow_path(std::forward<_Args>(__args)...); });
1159
1160 this->__end_ = __end;
1161#if _LIBCPP_STD_VER >= 17
1162 return *(__end - 1);
1163#endif
1164}
1165
1166template <class _Tp, class _Allocator>
1167_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::iterator
1168vector<_Tp, _Allocator>::erase(const_iterator __position) {
1169 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
1170 __position != end(), "vector::erase(iterator) called with a non-dereferenceable iterator");
1171 difference_type __ps = __position - cbegin();
1172 pointer __p = this->__begin_ + __ps;
1173 this->__destruct_at_end(std::move(__p + 1, this->__end_, __p));
1174 return __make_iter(__p);
1175}
1176
1177template <class _Tp, class _Allocator>
1178_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator
1179vector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last) {
1180 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__first <= __last, "vector::erase(first, last) called with invalid range");
1181 pointer __p = this->__begin_ + (__first - begin());
1182 if (__first != __last) {
1183 this->__destruct_at_end(std::move(__p + (__last - __first), this->__end_, __p));
1184 }
1185 return __make_iter(__p);
1186}
1187
1188template <class _Tp, class _Allocator>
1189_LIBCPP_CONSTEXPR_SINCE_CXX20 void
1190vector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to) {
1191 pointer __old_last = this->__end_;
1192 difference_type __n = __old_last - __to;
1193 {
1194 pointer __i = __from_s + __n;
1195 _ConstructTransaction __tx(*this, __from_e - __i);
1196 for (pointer __pos = __tx.__pos_; __i < __from_e; ++__i, (void)++__pos, __tx.__pos_ = __pos) {
1197 __alloc_traits::construct(this->__alloc_, std::__to_address(__pos), std::move(*__i));
1198 }
1199 }
1200 std::move_backward(__from_s, __from_s + __n, __old_last);
1201}
1202
1203template <class _Tp, class _Allocator>
1204_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator
1205vector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x) {
1206 pointer __p = this->__begin_ + (__position - begin());
1207 if (this->__end_ < this->__cap_) {
1208 if (__p == this->__end_) {
1209 __emplace_back_assume_capacity(__x);
1210 } else {
1211 __move_range(from_s: __p, from_e: this->__end_, to: __p + 1);
1212 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1213 if (std::__is_pointer_in_range(std::__to_address(__p), std::__to_address(__end_), std::addressof(__x)))
1214 ++__xr;
1215 *__p = *__xr;
1216 }
1217 } else {
1218 _SplitBuffer __v(__recommend(new_size: size() + 1), __p - this->__begin_, this->__alloc_);
1219 __v.emplace_back(__x);
1220 __p = __swap_out_circular_buffer(__v, __p);
1221 }
1222 return __make_iter(__p);
1223}
1224
1225template <class _Tp, class _Allocator>
1226_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator
1227vector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x) {
1228 pointer __p = this->__begin_ + (__position - begin());
1229 if (this->__end_ < this->__cap_) {
1230 if (__p == this->__end_) {
1231 __emplace_back_assume_capacity(std::move(__x));
1232 } else {
1233 __move_range(from_s: __p, from_e: this->__end_, to: __p + 1);
1234 *__p = std::move(__x);
1235 }
1236 } else {
1237 _SplitBuffer __v(__recommend(new_size: size() + 1), __p - this->__begin_, this->__alloc_);
1238 __v.emplace_back(std::move(__x));
1239 __p = __swap_out_circular_buffer(__v, __p);
1240 }
1241 return __make_iter(__p);
1242}
1243
1244template <class _Tp, class _Allocator>
1245template <class... _Args>
1246_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator
1247vector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args) {
1248 pointer __p = this->__begin_ + (__position - begin());
1249 if (this->__end_ < this->__cap_) {
1250 if (__p == this->__end_) {
1251 __emplace_back_assume_capacity(std::forward<_Args>(__args)...);
1252 } else {
1253 __temp_value<value_type, _Allocator> __tmp(this->__alloc_, std::forward<_Args>(__args)...);
1254 __move_range(from_s: __p, from_e: this->__end_, to: __p + 1);
1255 *__p = std::move(__tmp.get());
1256 }
1257 } else {
1258 _SplitBuffer __v(__recommend(new_size: size() + 1), __p - this->__begin_, this->__alloc_);
1259 __v.emplace_back(std::forward<_Args>(__args)...);
1260 __p = __swap_out_circular_buffer(__v, __p);
1261 }
1262 return __make_iter(__p);
1263}
1264
1265template <class _Tp, class _Allocator>
1266_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator
1267vector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x) {
1268 pointer __p = this->__begin_ + (__position - begin());
1269 if (__n > 0) {
1270 if (__n <= static_cast<size_type>(this->__cap_ - this->__end_)) {
1271 size_type __old_n = __n;
1272 pointer __old_last = this->__end_;
1273 if (__n > static_cast<size_type>(this->__end_ - __p)) {
1274 size_type __cx = __n - (this->__end_ - __p);
1275 __construct_at_end(__cx, __x);
1276 __n -= __cx;
1277 }
1278 if (__n > 0) {
1279 __move_range(from_s: __p, from_e: __old_last, to: __p + __old_n);
1280 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1281 if (std::__is_pointer_in_range(std::__to_address(__p), std::__to_address(__end_), std::addressof(__x)))
1282 __xr += __old_n;
1283 std::fill_n(__p, __n, *__xr);
1284 }
1285 } else {
1286 _SplitBuffer __v(__recommend(new_size: size() + __n), __p - this->__begin_, this->__alloc_);
1287 __v.__construct_at_end(__n, __x);
1288 __p = __swap_out_circular_buffer(__v, __p);
1289 }
1290 }
1291 return __make_iter(__p);
1292}
1293
1294template <class _Tp, class _Allocator>
1295template <class _InputIterator, class _Sentinel>
1296_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::iterator
1297vector<_Tp, _Allocator>::__insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last) {
1298 difference_type __off = __position - begin();
1299 pointer __p = this->__begin_ + __off;
1300 pointer __old_last = this->__end_;
1301 for (; this->__end_ != this->__cap_ && __first != __last; ++__first)
1302 __emplace_back_assume_capacity(*__first);
1303
1304 if (__first == __last)
1305 (void)std::rotate(__p, __old_last, this->__end_);
1306 else {
1307 _SplitBuffer __v(__alloc_);
1308 auto __guard = std::__make_exception_guard(
1309 _AllocatorDestroyRangeReverse<allocator_type, pointer>(__alloc_, __old_last, this->__end_));
1310 __v.__construct_at_end_with_sentinel(std::move(__first), std::move(__last));
1311 _SplitBuffer __merged(
1312 __recommend(new_size: size() + __v.size()), __off, __alloc_); // has `__off` positions available at the front
1313 std::__uninitialized_allocator_relocate(
1314 __alloc_, std::__to_address(__old_last), std::__to_address(this->__end_), std::__to_address(__merged.end()));
1315 __guard.__complete(); // Release the guard once objects in [__old_last_, __end_) have been successfully relocated.
1316 __merged.__set_sentinel(__merged.end() + (this->__end_ - __old_last));
1317 this->__end_ = __old_last;
1318 std::__uninitialized_allocator_relocate(
1319 __alloc_, std::__to_address(__v.begin()), std::__to_address(__v.end()), std::__to_address(__merged.end()));
1320 __merged.__set_sentinel(__merged.size() + __v.size());
1321 __v.__set_sentinel(__v.begin());
1322 __p = __swap_out_circular_buffer(__merged, __p);
1323 }
1324 return __make_iter(__p);
1325}
1326
1327template <class _Tp, class _Allocator>
1328template <class _AlgPolicy, class _Iterator, class _Sentinel>
1329_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::iterator
1330vector<_Tp, _Allocator>::__insert_with_size(
1331 const_iterator __position, _Iterator __first, _Sentinel __last, difference_type __n) {
1332 pointer __p = this->__begin_ + (__position - begin());
1333 if (__n > 0) {
1334 if (__n <= this->__cap_ - this->__end_) {
1335 pointer __old_last = this->__end_;
1336 difference_type __dx = this->__end_ - __p;
1337 if (__n > __dx) {
1338#if _LIBCPP_STD_VER >= 23
1339 if constexpr (!forward_iterator<_Iterator>) {
1340 __construct_at_end(std::move(__first), std::move(__last), __n);
1341 std::rotate(__p, __old_last, this->__end_);
1342 } else
1343#endif
1344 {
1345 _Iterator __m = std::next(__first, __dx);
1346 __construct_at_end(__m, __last, __n - __dx);
1347 if (__dx > 0) {
1348 __move_range(from_s: __p, from_e: __old_last, to: __p + __n);
1349 __insert_assign_n_unchecked<_AlgPolicy>(__first, __dx, __p);
1350 }
1351 }
1352 } else {
1353 __move_range(from_s: __p, from_e: __old_last, to: __p + __n);
1354 __insert_assign_n_unchecked<_AlgPolicy>(std::move(__first), __n, __p);
1355 }
1356 } else {
1357 _SplitBuffer __v(__recommend(new_size: size() + __n), __p - this->__begin_, this->__alloc_);
1358 __v.__construct_at_end_with_size(std::move(__first), __n);
1359 __p = __swap_out_circular_buffer(__v, __p);
1360 }
1361 }
1362 return __make_iter(__p);
1363}
1364
1365template <class _Tp, class _Allocator>
1366_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::resize(size_type __new_size) {
1367 size_type __current_size = size();
1368 if (__current_size < __new_size) {
1369 if (__new_size <= capacity()) {
1370 __construct_at_end(__new_size - __current_size);
1371 } else {
1372 _SplitBuffer __v(__recommend(__new_size), __current_size, __alloc_);
1373 __v.__construct_at_end(__new_size - __current_size);
1374 __swap_out_circular_buffer(__v);
1375 }
1376 } else if (__current_size > __new_size) {
1377 this->__destruct_at_end(this->__begin_ + __new_size);
1378 }
1379}
1380
1381template <class _Tp, class _Allocator>
1382_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::resize(size_type __new_size, const_reference __x) {
1383 size_type __current_size = size();
1384 if (__current_size < __new_size) {
1385 if (__new_size <= capacity())
1386 __construct_at_end(__new_size - __current_size, __x);
1387 else {
1388 _SplitBuffer __v(__recommend(__new_size), __current_size, __alloc_);
1389 __v.__construct_at_end(__new_size - __current_size, __x);
1390 __swap_out_circular_buffer(__v);
1391 }
1392 } else if (__current_size > __new_size) {
1393 this->__destruct_at_end(this->__begin_ + __new_size);
1394 }
1395}
1396
1397template <class _Tp, class _Allocator>
1398_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::swap(vector& __x)
1399#if _LIBCPP_STD_VER >= 14
1400 _NOEXCEPT
1401#else
1402 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>)
1403#endif
1404{
1405 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1406 __alloc_traits::propagate_on_container_swap::value || this->__alloc_ == __x.__alloc_,
1407 "vector::swap: Either propagate_on_container_swap must be true"
1408 " or the allocators must compare equal");
1409 std::swap(this->__begin_, __x.__begin_);
1410 std::swap(this->__end_, __x.__end_);
1411 std::swap(this->__cap_, __x.__cap_);
1412 std::__swap_allocator(this->__alloc_, __x.__alloc_);
1413}
1414
1415template <class _Tp, class _Allocator>
1416_LIBCPP_CONSTEXPR_SINCE_CXX20 bool vector<_Tp, _Allocator>::__invariants() const {
1417 if (this->__begin_ == nullptr) {
1418 if (this->__end_ != nullptr || this->__cap_ != nullptr)
1419 return false;
1420 } else {
1421 if (this->__begin_ > this->__end_)
1422 return false;
1423 if (this->__begin_ == this->__cap_)
1424 return false;
1425 if (this->__end_ > this->__cap_)
1426 return false;
1427 }
1428 return true;
1429}
1430
1431#if _LIBCPP_STD_VER >= 20
1432template <>
1433inline constexpr bool __format::__enable_insertable<vector<char>> = true;
1434# if _LIBCPP_HAS_WIDE_CHARACTERS
1435template <>
1436inline constexpr bool __format::__enable_insertable<vector<wchar_t>> = true;
1437# endif
1438#endif // _LIBCPP_STD_VER >= 20
1439
1440_LIBCPP_END_NAMESPACE_STD
1441
1442_LIBCPP_POP_MACROS
1443
1444#endif // _LIBCPP___VECTOR_VECTOR_H
1445