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