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