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