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