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