94 rebind<_Tp>::other _Tp_alloc_type;
95 typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer
98 struct _Vector_impl_data
102 pointer _M_end_of_storage;
105 _Vector_impl_data() _GLIBCXX_NOEXCEPT
106 : _M_start(), _M_finish(), _M_end_of_storage()
109#if __cplusplus >= 201103L
111 _Vector_impl_data(_Vector_impl_data&& __x) noexcept
112 : _M_start(__x._M_start), _M_finish(__x._M_finish),
113 _M_end_of_storage(__x._M_end_of_storage)
114 { __x._M_start = __x._M_finish = __x._M_end_of_storage = pointer(); }
119 _M_copy_data(_Vector_impl_data
const& __x) _GLIBCXX_NOEXCEPT
121 _M_start = __x._M_start;
122 _M_finish = __x._M_finish;
123 _M_end_of_storage = __x._M_end_of_storage;
128 _M_swap_data(_Vector_impl_data& __x) _GLIBCXX_NOEXCEPT
132 _Vector_impl_data __tmp;
133 __tmp._M_copy_data(*
this);
135 __x._M_copy_data(__tmp);
140 :
public _Tp_alloc_type,
public _Vector_impl_data
143 _Vector_impl() _GLIBCXX_NOEXCEPT_IF(
145#if __cpp_lib_concepts
146 requires is_default_constructible_v<_Tp_alloc_type>
152 _Vector_impl(_Tp_alloc_type
const& __a) _GLIBCXX_NOEXCEPT
153 : _Tp_alloc_type(__a)
156#if __cplusplus >= 201103L
160 _Vector_impl(_Vector_impl&& __x) noexcept
165 _Vector_impl(_Tp_alloc_type&& __a) noexcept
170 _Vector_impl(_Tp_alloc_type&& __a, _Vector_impl&& __rv) noexcept
175#if _GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR
176 template<
typename = _Tp_alloc_type>
182 static _GLIBCXX20_CONSTEXPR
void
184 static _GLIBCXX20_CONSTEXPR
void
185 _S_on_dealloc(_Vector_impl&) { }
187 typedef _Vector_impl& _Reinit;
191 _GLIBCXX20_CONSTEXPR _Grow(_Vector_impl&,
size_type) { }
192 _GLIBCXX20_CONSTEXPR
void _M_grew(
size_type) { }
197 template<
typename _Up>
205 static _GLIBCXX20_CONSTEXPR
void
206 _S_adjust(_Vector_impl& __impl, pointer __prev, pointer __curr)
208#if __cpp_lib_is_constant_evaluated
209 if (std::is_constant_evaluated())
212 __sanitizer_annotate_contiguous_container(__impl._M_start,
213 __impl._M_end_of_storage, __prev, __curr);
216 static _GLIBCXX20_CONSTEXPR
void
217 _S_grow(_Vector_impl& __impl,
size_type __n)
218 { _S_adjust(__impl, __impl._M_finish, __impl._M_finish + __n); }
220 static _GLIBCXX20_CONSTEXPR
void
221 _S_shrink(_Vector_impl& __impl,
size_type __n)
222 { _S_adjust(__impl, __impl._M_finish + __n, __impl._M_finish); }
224 static _GLIBCXX20_CONSTEXPR
void
225 _S_on_dealloc(_Vector_impl& __impl)
228 _S_adjust(__impl, __impl._M_finish, __impl._M_end_of_storage);
234 explicit _GLIBCXX20_CONSTEXPR
235 _Reinit(_Vector_impl& __impl) : _M_impl(__impl)
238 _S_on_dealloc(_M_impl);
245 if (_M_impl._M_start)
246 _S_adjust(_M_impl, _M_impl._M_end_of_storage,
250 _Vector_impl& _M_impl;
252#if __cplusplus >= 201103L
253 _Reinit(
const _Reinit&) =
delete;
254 _Reinit& operator=(
const _Reinit&) =
delete;
262 _Grow(_Vector_impl& __impl,
size_type __n)
263 : _M_impl(__impl), _M_n(__n)
264 { _S_grow(_M_impl, __n); }
267 ~_Grow() {
if (_M_n) _S_shrink(_M_impl, _M_n); }
270 void _M_grew(
size_type __n) { _M_n -= __n; }
272#if __cplusplus >= 201103L
273 _Grow(
const _Grow&) =
delete;
274 _Grow& operator=(
const _Grow&) =
delete;
277 _Vector_impl& _M_impl;
282#define _GLIBCXX_ASAN_ANNOTATE_REINIT \
283 typename _Base::_Vector_impl::template _Asan<>::_Reinit const \
284 __attribute__((__unused__)) __reinit_guard(this->_M_impl)
285#define _GLIBCXX_ASAN_ANNOTATE_GROW(n) \
286 typename _Base::_Vector_impl::template _Asan<>::_Grow \
287 __attribute__((__unused__)) __grow_guard(this->_M_impl, (n))
288#define _GLIBCXX_ASAN_ANNOTATE_GREW(n) __grow_guard._M_grew(n)
289#define _GLIBCXX_ASAN_ANNOTATE_SHRINK(n) \
290 _Base::_Vector_impl::template _Asan<>::_S_shrink(this->_M_impl, n)
291#define _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC \
292 _Base::_Vector_impl::template _Asan<>::_S_on_dealloc(this->_M_impl)
294#define _GLIBCXX_ASAN_ANNOTATE_REINIT
295#define _GLIBCXX_ASAN_ANNOTATE_GROW(n)
296#define _GLIBCXX_ASAN_ANNOTATE_GREW(n)
297#define _GLIBCXX_ASAN_ANNOTATE_SHRINK(n)
298#define _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC
303 typedef _Alloc allocator_type;
307 _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
308 {
return this->_M_impl; }
311 const _Tp_alloc_type&
312 _M_get_Tp_allocator()
const _GLIBCXX_NOEXCEPT
313 {
return this->_M_impl; }
318 {
return allocator_type(_M_get_Tp_allocator()); }
320#if __cplusplus >= 201103L
327 _Vector_base(
const allocator_type& __a) _GLIBCXX_NOEXCEPT
331#if !_GLIBCXX_INLINE_VERSION
333 _Vector_base(
size_t __n)
335 { _M_create_storage(__n); }
339 _Vector_base(
size_t __n,
const allocator_type& __a)
341 { _M_create_storage(__n); }
343#if __cplusplus >= 201103L
344 _Vector_base(_Vector_base&&) =
default;
347# if !_GLIBCXX_INLINE_VERSION
349 _Vector_base(_Tp_alloc_type&& __a) noexcept
353 _Vector_base(_Vector_base&& __x,
const allocator_type& __a)
356 if (__x.get_allocator() == __a)
357 this->_M_impl._M_swap_data(__x._M_impl);
360 size_t __n = __x._M_impl._M_finish - __x._M_impl._M_start;
361 _M_create_storage(__n);
367 _Vector_base(
const allocator_type& __a, _Vector_base&& __x)
368 : _M_impl(_Tp_alloc_type(__a), std::
move(__x._M_impl))
373 ~_Vector_base() _GLIBCXX_NOEXCEPT
375 _M_deallocate(_M_impl._M_start,
376 _M_impl._M_end_of_storage - _M_impl._M_start);
380 _Vector_impl _M_impl;
384 _M_allocate(
size_t __n)
386 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
387 return __n != 0 ? _Tr::allocate(_M_impl, __n) : pointer();
392 _M_deallocate(pointer __p,
size_t __n)
394 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
396 _Tr::deallocate(_M_impl, __p, __n);
403 _M_create_storage(
size_t __n)
405 this->_M_impl._M_start = this->_M_allocate(__n);
406 this->_M_impl._M_finish = this->_M_impl._M_start;
407 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
410#if __glibcxx_containers_ranges
416 template<ranges::input_range _Rg>
418 _M_append_range_to(_Rg&& __rg, pointer& __ptr)
420 __ptr = std::__uninitialized_copy_a(ranges::begin(__rg),
422 __ptr, _M_get_Tp_allocator());
427 template<ranges::input_range _Rg>
429 _M_append_range(_Rg&& __rg)
458 class vector :
protected _Vector_base<_Tp, _Alloc>
460#ifdef _GLIBCXX_CONCEPT_CHECKS
462 typedef typename _Alloc::value_type _Alloc_value_type;
463# if __cplusplus < 201103L
464 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
466 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
469#if __cplusplus >= 201103L
471 "std::vector must have a non-const, non-volatile value_type");
472# if __cplusplus > 201703L || defined __STRICT_ANSI__
474 "std::vector must have the same value_type as its allocator");
478 typedef _Vector_base<_Tp, _Alloc> _Base;
479 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
483 typedef _Tp value_type;
484 typedef typename _Base::pointer pointer;
485 typedef typename _Alloc_traits::const_pointer const_pointer;
486 typedef typename _Alloc_traits::reference reference;
487 typedef typename _Alloc_traits::const_reference const_reference;
488 typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
489 typedef __gnu_cxx::__normal_iterator<const_pointer, vector>
493 typedef size_t size_type;
494 typedef ptrdiff_t difference_type;
495 typedef _Alloc allocator_type;
498#if __cplusplus >= 201103L
499 static constexpr bool
508 static constexpr bool
512 static constexpr bool
518 return _S_nothrow_relocate(__is_move_insertable<_Tp_alloc_type>{});
522 _S_do_relocate(pointer __first, pointer __last, pointer __result,
523 _Tp_alloc_type& __alloc,
true_type)
noexcept
525 return std::__relocate_a(__first, __last, __result, __alloc);
529 _S_do_relocate(pointer, pointer, pointer __result,
533 static _GLIBCXX20_CONSTEXPR pointer
534 _S_relocate(pointer __first, pointer __last, pointer __result,
535 _Tp_alloc_type& __alloc)
noexcept
537#if __cpp_if_constexpr
539 return std::__relocate_a(__first, __last, __result, __alloc);
541 using __do_it = __bool_constant<_S_use_relocate()>;
542 return _S_do_relocate(__first, __last, __result, __alloc, __do_it{});
548 using _Base::_M_allocate;
549 using _Base::_M_deallocate;
550 using _Base::_M_impl;
551 using _Base::_M_get_Tp_allocator;
560#if __cplusplus >= 201103L
572 vector(
const allocator_type& __a) _GLIBCXX_NOEXCEPT
575#if __cplusplus >= 201103L
586 vector(size_type __n,
const allocator_type& __a = allocator_type())
587 : _Base(_S_check_init_len(__n, __a), __a)
588 { _M_default_initialize(__n); }
599 vector(size_type __n,
const value_type& __value,
600 const allocator_type& __a = allocator_type())
601 : _Base(_S_check_init_len(__n, __a), __a)
602 { _M_fill_initialize(__n, __value); }
614 const allocator_type& __a = allocator_type())
615 : _Base(_S_check_init_len(__n, __a), __a)
616 { _M_fill_initialize(__n, __value); }
633 _Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()))
635 this->_M_impl._M_finish =
636 std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
637 this->_M_impl._M_start,
638 _M_get_Tp_allocator());
641#if __cplusplus >= 201103L
654 vector(const
vector& __x, const __type_identity_t<allocator_type>& __a)
655 : _Base(__x.
size(), __a)
657 this->_M_impl._M_finish =
658 std::__uninitialized_copy_a(__x.begin(), __x.end(),
659 this->_M_impl._M_start,
660 _M_get_Tp_allocator());
670 vector(vector&& __rv,
const allocator_type& __m, false_type)
673 if (__rv.get_allocator() == __m)
674 this->_M_impl._M_swap_data(__rv._M_impl);
675 else if (!__rv.empty())
677 this->_M_create_storage(__rv.size());
678 this->_M_impl._M_finish =
679 std::__uninitialized_move_a(__rv.begin(), __rv.end(),
680 this->_M_impl._M_start,
681 _M_get_Tp_allocator());
693 :
vector(
std::
move(__rv), __m, typename _Alloc_traits::is_always_equal{})
709 const allocator_type& __a = allocator_type())
712 _M_range_initialize_n(__l.begin(), __l.end(), __l.size());
732#if __cplusplus >= 201103L
733 template<
typename _InputIterator,
734 typename = std::_RequireInputIter<_InputIterator>>
736 vector(_InputIterator __first, _InputIterator __last,
737 const allocator_type& __a = allocator_type())
740#if __glibcxx_concepts
741 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>
742 || forward_iterator<_InputIterator>)
745 =
static_cast<size_type
>(ranges::distance(__first, __last));
746 _M_range_initialize_n(__first, __last, __n);
751 _M_range_initialize(__first, __last,
755 template<
typename _InputIterator>
756 vector(_InputIterator __first, _InputIterator __last,
757 const allocator_type& __a = allocator_type())
761 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
762 _M_initialize_dispatch(__first, __last, _Integral());
766#if __glibcxx_containers_ranges
772 template<__detail::__container_compatible_range<_Tp> _Rg>
774 vector(from_range_t, _Rg&& __rg,
const _Alloc& __a = _Alloc())
777 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
779 const auto __n =
static_cast<size_type
>(ranges::distance(__rg));
780 _M_range_initialize_n(ranges::begin(__rg), ranges::end(__rg),
785 auto __first = ranges::begin(__rg);
786 const auto __last = ranges::end(__rg);
787 for (; __first != __last; ++__first)
788 emplace_back(*__first);
802 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
803 _M_get_Tp_allocator());
804 _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC;
820#if __cplusplus >= 201103L
835 constexpr bool __move_storage =
836 _Alloc_traits::_S_propagate_on_move_assign()
837 || _Alloc_traits::_S_always_equal();
838 _M_move_assign(
std::move(__x), __bool_constant<__move_storage>());
857 this->_M_assign_aux(__l.begin(), __l.end(),
875 assign(size_type __n,
const value_type& __val)
876 { _M_fill_assign(__n, __val); }
890#if __cplusplus >= 201103L
891 template<
typename _InputIterator,
892 typename = std::_RequireInputIter<_InputIterator>>
895 assign(_InputIterator __first, _InputIterator __last)
898 template<
typename _InputIterator>
900 assign(_InputIterator __first, _InputIterator __last)
903 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
904 _M_assign_dispatch(__first, __last, _Integral());
908#if __cplusplus >= 201103L
924 this->_M_assign_aux(__l.begin(), __l.end(),
929#if __glibcxx_containers_ranges
936 template<__detail::__container_compatible_range<_Tp> _Rg>
938 assign_range(_Rg&& __rg)
940 static_assert(assignable_from<_Tp&, ranges::range_reference_t<_Rg>>);
942 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
944 const auto __n =
size_type(ranges::distance(__rg));
947 auto __res = ranges::copy(__rg, this->_M_impl._M_start);
948 _M_erase_at_end(__res.out);
953 auto __first = ranges::copy_n(ranges::begin(__rg),
size(),
954 this->_M_impl._M_start).in;
955 [[maybe_unused]]
const auto __diff = __n -
size();
956 _GLIBCXX_ASAN_ANNOTATE_GROW(__diff);
957 _Base::_M_append_range(ranges::subrange(
std::move(__first),
959 _GLIBCXX_ASAN_ANNOTATE_GREW(__diff);
963 auto __first = ranges::begin(__rg);
964 const auto __last = ranges::end(__rg);
965 pointer __ptr = this->_M_impl._M_start;
966 pointer
const __end = this->_M_impl._M_finish;
968 while (__ptr < __end && __first != __last)
975 if (__first == __last)
976 _M_erase_at_end(__ptr);
980 emplace_back(*__first);
981 while (++__first != __last);
988 using _Base::get_allocator;
996 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
999 {
return iterator(this->_M_impl._M_start); }
1006 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1009 {
return const_iterator(this->_M_impl._M_start); }
1016 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1019 {
return iterator(this->_M_impl._M_finish); }
1026 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1029 {
return const_iterator(this->_M_impl._M_finish); }
1036 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1039 {
return reverse_iterator(
end()); }
1046 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1047 const_reverse_iterator
1049 {
return const_reverse_iterator(
end()); }
1056 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1059 {
return reverse_iterator(
begin()); }
1066 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1067 const_reverse_iterator
1069 {
return const_reverse_iterator(
begin()); }
1071#if __cplusplus >= 201103L
1077 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1080 {
return const_iterator(this->_M_impl._M_start); }
1087 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1090 {
return const_iterator(this->_M_impl._M_finish); }
1097 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1098 const_reverse_iterator
1100 {
return const_reverse_iterator(
end()); }
1107 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1108 const_reverse_iterator
1110 {
return const_reverse_iterator(
begin()); }
1115 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1119 ptrdiff_t __dif = this->_M_impl._M_finish - this->_M_impl._M_start;
1121 __builtin_unreachable ();
1122 return size_type(__dif);
1126 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1129 {
return _S_max_size(_M_get_Tp_allocator()); }
1131#if __cplusplus >= 201103L
1141 _GLIBCXX20_CONSTEXPR
1145 if (__new_size >
size())
1146 _M_default_append(__new_size -
size());
1147 else if (__new_size <
size())
1148 _M_erase_at_end(this->_M_impl._M_start + __new_size);
1162 _GLIBCXX20_CONSTEXPR
1164 resize(size_type __new_size,
const value_type& __x)
1166 if (__new_size >
size())
1167 _M_fill_insert(
end(), __new_size -
size(), __x);
1168 else if (__new_size <
size())
1169 _M_erase_at_end(this->_M_impl._M_start + __new_size);
1183 _GLIBCXX20_CONSTEXPR
1187 if (__new_size >
size())
1188 _M_fill_insert(
end(), __new_size -
size(), __x);
1189 else if (__new_size <
size())
1190 _M_erase_at_end(this->_M_impl._M_start + __new_size);
1194#if __cplusplus >= 201103L
1196 _GLIBCXX20_CONSTEXPR
1199 { _M_shrink_to_fit(); }
1206 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1210 ptrdiff_t __dif = this->_M_impl._M_end_of_storage
1211 - this->_M_impl._M_start;
1213 __builtin_unreachable ();
1214 return size_type(__dif);
1221 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1243 _GLIBCXX20_CONSTEXPR
1259 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1263 __glibcxx_requires_subscript(__n);
1264 return *(this->_M_impl._M_start + __n);
1278 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1282 __glibcxx_requires_subscript(__n);
1283 return *(this->_M_impl._M_start + __n);
1288 _GLIBCXX20_CONSTEXPR
1292 if (__n >= this->
size())
1293 __throw_out_of_range_fmt(__N(
"vector::_M_range_check: __n "
1294 "(which is %zu) >= this->size() "
1311 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1316 return (*
this)[__n];
1330 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1335 return (*
this)[__n];
1342 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1346 __glibcxx_requires_nonempty();
1354 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1358 __glibcxx_requires_nonempty();
1366 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1370 __glibcxx_requires_nonempty();
1371 return *(
end() - 1);
1378 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1382 __glibcxx_requires_nonempty();
1383 return *(
end() - 1);
1393 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1396 {
return _M_data_ptr(this->_M_impl._M_start); }
1398 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1400 data() const _GLIBCXX_NOEXCEPT
1401 {
return _M_data_ptr(this->_M_impl._M_start); }
1414 _GLIBCXX20_CONSTEXPR
1418 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
1420 _GLIBCXX_ASAN_ANNOTATE_GROW(1);
1421 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
1423 ++this->_M_impl._M_finish;
1424 _GLIBCXX_ASAN_ANNOTATE_GREW(1);
1427 _M_realloc_append(__x);
1430#if __cplusplus >= 201103L
1431 _GLIBCXX20_CONSTEXPR
1436 template<
typename... _Args>
1437#if __cplusplus > 201402L
1438 _GLIBCXX20_CONSTEXPR
1443 emplace_back(_Args&&... __args);
1455 _GLIBCXX20_CONSTEXPR
1459 __glibcxx_requires_nonempty();
1460 --this->_M_impl._M_finish;
1461 _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
1462 _GLIBCXX_ASAN_ANNOTATE_SHRINK(1);
1465#if __cplusplus >= 201103L
1478 template<
typename... _Args>
1479 _GLIBCXX20_CONSTEXPR
1481 emplace(const_iterator __position, _Args&&... __args)
1495 _GLIBCXX20_CONSTEXPR
1497 insert(const_iterator __position,
const value_type& __x);
1511 insert(iterator __position,
const value_type& __x);
1514#if __cplusplus >= 201103L
1526 _GLIBCXX20_CONSTEXPR
1528 insert(const_iterator __position, value_type&& __x)
1529 {
return _M_insert_rval(__position,
std::move(__x)); }
1544 _GLIBCXX20_CONSTEXPR
1548 auto __offset = __position -
cbegin();
1549 _M_range_insert(
begin() + __offset, __l.begin(), __l.end(),
1551 return begin() + __offset;
1555#if __cplusplus >= 201103L
1570 _GLIBCXX20_CONSTEXPR
1572 insert(const_iterator __position, size_type __n,
const value_type& __x)
1574 difference_type __offset = __position -
cbegin();
1575 _M_fill_insert(
begin() + __offset, __n, __x);
1576 return begin() + __offset;
1594 { _M_fill_insert(__position, __n, __x); }
1597#if __cplusplus >= 201103L
1613 template<
typename _InputIterator,
1614 typename = std::_RequireInputIter<_InputIterator>>
1615 _GLIBCXX20_CONSTEXPR
1617 insert(const_iterator __position, _InputIterator __first,
1618 _InputIterator __last)
1620 difference_type __offset = __position -
cbegin();
1621 _M_range_insert(
begin() + __offset, __first, __last,
1623 return begin() + __offset;
1640 template<
typename _InputIterator>
1643 _InputIterator __last)
1646 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1647 _M_insert_dispatch(__position, __first, __last, _Integral());
1651#if __glibcxx_containers_ranges
1660 template<__detail::__container_compatible_range<_Tp> _Rg>
1662 insert_range(const_iterator __pos, _Rg&& __rg);
1669 template<__detail::__container_compatible_range<_Tp> _Rg>
1671 append_range(_Rg&& __rg)
1676 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
1678 const auto __n = size_type(ranges::distance(__rg));
1685 const auto __sz =
size();
1686 const auto __capacity =
capacity();
1687 if ((__capacity - __sz) >= __n)
1689 _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
1690 _Base::_M_append_range(__rg);
1691 _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
1695 const size_type __len = _M_check_len(__n,
"vector::append_range");
1697 pointer __old_start = this->_M_impl._M_start;
1698 pointer __old_finish = this->_M_impl._M_finish;
1700 allocator_type& __a = _M_get_Tp_allocator();
1701 const pointer __start = this->_M_allocate(__len);
1702 const pointer __mid = __start + __sz;
1703 const pointer __back = __mid + __n;
1704 _Guard_alloc __guard(__start, __len, *
this);
1705 std::__uninitialized_copy_a(ranges::begin(__rg),
1709 if constexpr (_S_use_relocate())
1710 _S_relocate(__old_start, __old_finish, __start, __a);
1716 pointer _M_first, _M_last;
1717 _Tp_alloc_type& _M_alloc;
1720 _Guard_elts(pointer __f, pointer __l, _Tp_alloc_type& __a)
1721 : _M_first(__f), _M_last(__l), _M_alloc(__a)
1728 _Guard_elts(_Guard_elts&&) =
delete;
1730 _Guard_elts __guard_elts{__mid, __back, __a};
1732 std::__uninitialized_move_a(__old_start, __old_finish,
1736 __guard_elts._M_first = __old_start;
1737 __guard_elts._M_last = __old_finish;
1741 __guard._M_storage = __old_start;
1742 __guard._M_len = __capacity;
1744 this->_M_impl._M_start = __start;
1745 this->_M_impl._M_finish = __back;
1746 this->_M_impl._M_end_of_storage = __start + __len;
1750 auto __first = ranges::begin(__rg);
1751 const auto __last = ranges::end(__rg);
1755 __first != __last && __free > 0;
1756 ++__first, (void) --__free)
1757 emplace_back(*__first);
1759 if (__first == __last)
1763 vector __tmp(_M_get_Tp_allocator());
1764 for (; __first != __last; ++__first)
1765 __tmp.emplace_back(*__first);
1766 reserve(_M_check_len(__tmp.size(),
"vector::append_range"));
1767 ranges::subrange __r(std::make_move_iterator(__tmp.begin()),
1768 std::make_move_iterator(__tmp.end()));
1789 _GLIBCXX20_CONSTEXPR
1791#if __cplusplus >= 201103L
1793 {
return _M_erase(
begin() + (__position -
cbegin())); }
1796 {
return _M_erase(__position); }
1817 _GLIBCXX20_CONSTEXPR
1819#if __cplusplus >= 201103L
1820 erase(const_iterator __first, const_iterator __last)
1822 const auto __beg =
begin();
1823 const auto __cbeg =
cbegin();
1824 return _M_erase(__beg + (__first - __cbeg), __beg + (__last - __cbeg));
1828 {
return _M_erase(__first, __last); }
1842 _GLIBCXX20_CONSTEXPR
1846#if __cplusplus >= 201103L
1847 __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value
1848 || _M_get_Tp_allocator() == __x._M_get_Tp_allocator());
1850 this->_M_impl._M_swap_data(__x._M_impl);
1851 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1852 __x._M_get_Tp_allocator());
1861 _GLIBCXX20_CONSTEXPR
1864 { _M_erase_at_end(this->_M_impl._M_start); }
1874 _GLIBCXX20_CONSTEXPR
1875 _Guard_alloc(pointer __s,
size_type __l, _Base& __vect)
1876 : _M_storage(__s), _M_len(__l), _M_vect(__vect)
1879 _GLIBCXX20_CONSTEXPR
1883 _M_vect._M_deallocate(_M_storage, _M_len);
1886 _GLIBCXX20_CONSTEXPR
1890 pointer __res = _M_storage;
1891 _M_storage = pointer();
1896 _Guard_alloc(
const _Guard_alloc&);
1904 template<
typename _ForwardIterator>
1905 _GLIBCXX20_CONSTEXPR
1908 _ForwardIterator __first, _ForwardIterator __last)
1910 _Guard_alloc __guard(this->_M_allocate(__n), __n, *
this);
1911 std::__uninitialized_copy_a
1912 (__first, __last, __guard._M_storage, _M_get_Tp_allocator());
1913 return __guard._M_release();
1921#if __cplusplus < 201103L
1924 template<
typename _Integer>
1926 _M_initialize_dispatch(_Integer __int_n, _Integer __value, __true_type)
1930 _M_allocate(_S_check_init_len(__n, _M_get_Tp_allocator()));
1931 this->_M_impl._M_start = __start;
1932 this->_M_impl._M_end_of_storage = __start + __n;
1933 _M_fill_initialize(__n, __value);
1937 template<
typename _InputIterator>
1939 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1942 _M_range_initialize(__first, __last,
1948 template<
typename _InputIterator>
1949 _GLIBCXX20_CONSTEXPR
1951 _M_range_initialize(_InputIterator __first, _InputIterator __last,
1952 std::input_iterator_tag)
1955 for (; __first != __last; ++__first)
1956#
if __cplusplus >= 201103L
1957 emplace_back(*__first);
1963 __throw_exception_again;
1968 template<
typename _ForwardIterator>
1969 _GLIBCXX20_CONSTEXPR
1971 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
1972 std::forward_iterator_tag)
1974 _M_range_initialize_n(__first, __last,
1978 template<
typename _Iterator,
typename _Sentinel>
1979 _GLIBCXX20_CONSTEXPR
1981 _M_range_initialize_n(_Iterator __first, _Sentinel __last,
1984 pointer __start = this->_M_impl._M_start =
1985 this->_M_allocate(_S_check_init_len(__n, _M_get_Tp_allocator()));
1986 this->_M_impl._M_end_of_storage = __start + __n;
1987 this->_M_impl._M_finish
1988 = std::__uninitialized_copy_a(_GLIBCXX_MOVE(__first), __last,
1989 __start, _M_get_Tp_allocator());
1994 _GLIBCXX20_CONSTEXPR
1996 _M_fill_initialize(size_type __n,
const value_type& __value)
1998 this->_M_impl._M_finish =
1999 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
2000 _M_get_Tp_allocator());
2003#if __cplusplus >= 201103L
2005 _GLIBCXX20_CONSTEXPR
2007 _M_default_initialize(size_type __n)
2009 this->_M_impl._M_finish =
2010 std::__uninitialized_default_n_a(this->_M_impl._M_start, __n,
2011 _M_get_Tp_allocator());
2022 template<
typename _Integer>
2023 _GLIBCXX20_CONSTEXPR
2025 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
2026 { _M_fill_assign(__n, __val); }
2029 template<
typename _InputIterator>
2030 _GLIBCXX20_CONSTEXPR
2032 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
2037 template<
typename _InputIterator>
2038 _GLIBCXX20_CONSTEXPR
2040 _M_assign_aux(_InputIterator __first, _InputIterator __last,
2041 std::input_iterator_tag);
2044 template<
typename _ForwardIterator>
2045 _GLIBCXX20_CONSTEXPR
2047 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
2048 std::forward_iterator_tag);
2052 _GLIBCXX20_CONSTEXPR
2054 _M_fill_assign(size_type __n,
const value_type& __val);
2062 template<
typename _Integer>
2063 _GLIBCXX20_CONSTEXPR
2065 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
2067 { _M_fill_insert(__pos, __n, __val); }
2070 template<
typename _InputIterator>
2071 _GLIBCXX20_CONSTEXPR
2073 _M_insert_dispatch(iterator __pos, _InputIterator __first,
2074 _InputIterator __last, __false_type)
2076 _M_range_insert(__pos, __first, __last,
2081 template<
typename _InputIterator>
2082 _GLIBCXX20_CONSTEXPR
2084 _M_range_insert(iterator __pos, _InputIterator __first,
2085 _InputIterator __last, std::input_iterator_tag);
2088 template<
typename _ForwardIterator>
2089 _GLIBCXX20_CONSTEXPR
2091 _M_range_insert(iterator __pos, _ForwardIterator __first,
2092 _ForwardIterator __last, std::forward_iterator_tag);
2096 _GLIBCXX20_CONSTEXPR
2098 _M_fill_insert(iterator __pos, size_type __n,
const value_type& __x);
2100#if __cplusplus >= 201103L
2102 _GLIBCXX20_CONSTEXPR
2104 _M_default_append(size_type __n);
2106 _GLIBCXX20_CONSTEXPR
2111#if __cplusplus < 201103L
2114 _M_insert_aux(iterator __position,
const value_type& __x);
2117 _M_realloc_insert(iterator __position,
const value_type& __x);
2120 _M_realloc_append(
const value_type& __x);
2124 struct _Temporary_value
2126 template<
typename... _Args>
2127 _GLIBCXX20_CONSTEXPR
explicit
2128 _Temporary_value(
vector* __vec, _Args&&... __args) : _M_this(__vec)
2130 _Alloc_traits::construct(_M_this->_M_impl, _M_ptr(),
2134 _GLIBCXX20_CONSTEXPR
2136 { _Alloc_traits::destroy(_M_this->_M_impl, _M_ptr()); }
2138 _GLIBCXX20_CONSTEXPR value_type&
2139 _M_val() noexcept {
return _M_storage._M_val; }
2142 _GLIBCXX20_CONSTEXPR _Tp*
2147 constexpr _Storage() : _M_byte() { }
2148 _GLIBCXX20_CONSTEXPR ~_Storage() { }
2149 _Storage& operator=(
const _Storage&) =
delete;
2150 unsigned char _M_byte;
2155 _Storage _M_storage;
2160 template<
typename _Arg>
2161 _GLIBCXX20_CONSTEXPR
2163 _M_insert_aux(iterator __position, _Arg&& __arg);
2165 template<
typename... _Args>
2166 _GLIBCXX20_CONSTEXPR
2168 _M_realloc_insert(iterator __position, _Args&&... __args);
2170 template<
typename... _Args>
2171 _GLIBCXX20_CONSTEXPR
2173 _M_realloc_append(_Args&&... __args);
2176 _GLIBCXX20_CONSTEXPR
2178 _M_insert_rval(const_iterator __position, value_type&& __v);
2181 template<
typename... _Args>
2182 _GLIBCXX20_CONSTEXPR
2184 _M_emplace_aux(const_iterator __position, _Args&&... __args);
2187 _GLIBCXX20_CONSTEXPR
2189 _M_emplace_aux(const_iterator __position, value_type&& __v)
2190 {
return _M_insert_rval(__position,
std::move(__v)); }
2194 _GLIBCXX20_CONSTEXPR
2196 _M_check_len(size_type __n,
const char* __s)
const
2199 __throw_length_error(__N(__s));
2206 static _GLIBCXX20_CONSTEXPR size_type
2207 _S_check_init_len(size_type __n,
const allocator_type& __a)
2209 if (__n > _S_max_size(_Tp_alloc_type(__a)))
2210 __throw_length_error(
2211 __N(
"cannot create std::vector larger than max_size()"));
2215 static _GLIBCXX20_CONSTEXPR size_type
2216 _S_max_size(
const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
2221 const size_t __diffmax
2222 = __gnu_cxx::__numeric_traits<ptrdiff_t>::__max /
sizeof(_Tp);
2224 return (
std::min)(__diffmax, __allocmax);
2231 _GLIBCXX20_CONSTEXPR
2233 _M_erase_at_end(pointer __pos) _GLIBCXX_NOEXCEPT
2235 if (size_type __n = this->_M_impl._M_finish - __pos)
2238 _M_get_Tp_allocator());
2239 this->_M_impl._M_finish = __pos;
2240 _GLIBCXX_ASAN_ANNOTATE_SHRINK(__n);
2244 _GLIBCXX20_CONSTEXPR
2246 _M_erase(iterator __position);
2248 _GLIBCXX20_CONSTEXPR
2250 _M_erase(iterator __first, iterator __last);
2252#if __cplusplus >= 201103L
2257 _GLIBCXX20_CONSTEXPR
2262 this->_M_impl._M_swap_data(__x._M_impl);
2263 __tmp._M_impl._M_swap_data(__x._M_impl);
2264 std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
2269 _GLIBCXX20_CONSTEXPR
2273 if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
2279 this->_M_assign_aux(std::make_move_iterator(__x.begin()),
2280 std::make_move_iterator(__x.end()),
2281 std::random_access_iterator_tag());
2287 template<
typename _Up>
2288 _GLIBCXX20_CONSTEXPR
2290 _M_data_ptr(_Up* __ptr)
const _GLIBCXX_NOEXCEPT
2293#if __cplusplus >= 201103L
2294 template<
typename _Ptr>
2295 _GLIBCXX20_CONSTEXPR
2296 typename std::pointer_traits<_Ptr>::element_type*
2297 _M_data_ptr(_Ptr __ptr)
const
2298 {
return empty() ? nullptr : std::__to_address(__ptr); }
2300 template<
typename _Ptr>
2302 _M_data_ptr(_Ptr __ptr)
const
2303 {
return empty() ? (value_type*)0 : __ptr.operator->(); }