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