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