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