libstdc++
stl_vector.h
Go to the documentation of this file.
1// Vector implementation -*- C++ -*-
2
3// Copyright (C) 2001-2024 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/*
26 *
27 * Copyright (c) 1994
28 * Hewlett-Packard Company
29 *
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Hewlett-Packard Company makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
37 *
38 *
39 * Copyright (c) 1996
40 * Silicon Graphics Computer Systems, Inc.
41 *
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Silicon Graphics makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
49 */
50
51/** @file bits/stl_vector.h
52 * This is an internal header file, included by other library headers.
53 * Do not attempt to use it directly. @headername{vector}
54 */
55
56#ifndef _STL_VECTOR_H
57#define _STL_VECTOR_H 1
58
60#include <bits/functexcept.h>
61#include <bits/concept_check.h>
62#if __cplusplus >= 201103L
63#include <initializer_list>
64#endif
65#if __cplusplus >= 202002L
66# include <compare>
67#endif
68#if __cplusplus > 202002L
69# include <bits/ranges_algobase.h> // ranges::copy
70# include <bits/ranges_util.h> // ranges::subrange
71#endif
72
73#include <debug/assertions.h>
74
75#if _GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR
76extern "C" void
77__sanitizer_annotate_contiguous_container(const void*, const void*,
78 const void*, const void*);
79#endif
80
81namespace std _GLIBCXX_VISIBILITY(default)
82{
83_GLIBCXX_BEGIN_NAMESPACE_VERSION
84_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
85
86 /// See bits/stl_deque.h's _Deque_base for an explanation.
87 template<typename _Tp, typename _Alloc>
89 {
91 rebind<_Tp>::other _Tp_alloc_type;
92 typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer
93 pointer;
94
95 struct _Vector_impl_data
96 {
97 pointer _M_start;
98 pointer _M_finish;
99 pointer _M_end_of_storage;
100
101 _GLIBCXX20_CONSTEXPR
102 _Vector_impl_data() _GLIBCXX_NOEXCEPT
103 : _M_start(), _M_finish(), _M_end_of_storage()
104 { }
105
106#if __cplusplus >= 201103L
107 _GLIBCXX20_CONSTEXPR
108 _Vector_impl_data(_Vector_impl_data&& __x) noexcept
109 : _M_start(__x._M_start), _M_finish(__x._M_finish),
110 _M_end_of_storage(__x._M_end_of_storage)
111 { __x._M_start = __x._M_finish = __x._M_end_of_storage = pointer(); }
112#endif
113
114 _GLIBCXX20_CONSTEXPR
115 void
116 _M_copy_data(_Vector_impl_data const& __x) _GLIBCXX_NOEXCEPT
117 {
118 _M_start = __x._M_start;
119 _M_finish = __x._M_finish;
120 _M_end_of_storage = __x._M_end_of_storage;
121 }
122
123 _GLIBCXX20_CONSTEXPR
124 void
125 _M_swap_data(_Vector_impl_data& __x) _GLIBCXX_NOEXCEPT
126 {
127 // Do not use std::swap(_M_start, __x._M_start), etc as it loses
128 // information used by TBAA.
129 _Vector_impl_data __tmp;
130 __tmp._M_copy_data(*this);
131 _M_copy_data(__x);
132 __x._M_copy_data(__tmp);
133 }
134 };
135
136 struct _Vector_impl
137 : public _Tp_alloc_type, public _Vector_impl_data
138 {
139 _GLIBCXX20_CONSTEXPR
140 _Vector_impl() _GLIBCXX_NOEXCEPT_IF(
142#if __cpp_lib_concepts
143 requires is_default_constructible_v<_Tp_alloc_type>
144#endif
145 : _Tp_alloc_type()
146 { }
147
148 _GLIBCXX20_CONSTEXPR
149 _Vector_impl(_Tp_alloc_type const& __a) _GLIBCXX_NOEXCEPT
150 : _Tp_alloc_type(__a)
151 { }
152
153#if __cplusplus >= 201103L
154 // Not defaulted, to enforce noexcept(true) even when
155 // !is_nothrow_move_constructible<_Tp_alloc_type>.
156 _GLIBCXX20_CONSTEXPR
157 _Vector_impl(_Vector_impl&& __x) noexcept
158 : _Tp_alloc_type(std::move(__x)), _Vector_impl_data(std::move(__x))
159 { }
160
161 _GLIBCXX20_CONSTEXPR
162 _Vector_impl(_Tp_alloc_type&& __a) noexcept
163 : _Tp_alloc_type(std::move(__a))
164 { }
165
166 _GLIBCXX20_CONSTEXPR
167 _Vector_impl(_Tp_alloc_type&& __a, _Vector_impl&& __rv) noexcept
168 : _Tp_alloc_type(std::move(__a)), _Vector_impl_data(std::move(__rv))
169 { }
170#endif
171
172#if _GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR
173 template<typename = _Tp_alloc_type>
174 struct _Asan
175 {
177 ::size_type size_type;
178
179 static _GLIBCXX20_CONSTEXPR void
180 _S_shrink(_Vector_impl&, size_type) { }
181 static _GLIBCXX20_CONSTEXPR void
182 _S_on_dealloc(_Vector_impl&) { }
183
184 typedef _Vector_impl& _Reinit;
185
186 struct _Grow
187 {
188 _GLIBCXX20_CONSTEXPR _Grow(_Vector_impl&, size_type) { }
189 _GLIBCXX20_CONSTEXPR void _M_grew(size_type) { }
190 };
191 };
192
193 // Enable ASan annotations for memory obtained from std::allocator.
194 template<typename _Up>
195 struct _Asan<allocator<_Up> >
196 {
198 ::size_type size_type;
199
200 // Adjust ASan annotation for [_M_start, _M_end_of_storage) to
201 // mark end of valid region as __curr instead of __prev.
202 static _GLIBCXX20_CONSTEXPR void
203 _S_adjust(_Vector_impl& __impl, pointer __prev, pointer __curr)
204 {
205#if __cpp_lib_is_constant_evaluated
206 if (std::is_constant_evaluated())
207 return;
208#endif
209 __sanitizer_annotate_contiguous_container(__impl._M_start,
210 __impl._M_end_of_storage, __prev, __curr);
211 }
212
213 static _GLIBCXX20_CONSTEXPR void
214 _S_grow(_Vector_impl& __impl, size_type __n)
215 { _S_adjust(__impl, __impl._M_finish, __impl._M_finish + __n); }
216
217 static _GLIBCXX20_CONSTEXPR void
218 _S_shrink(_Vector_impl& __impl, size_type __n)
219 { _S_adjust(__impl, __impl._M_finish + __n, __impl._M_finish); }
220
221 static _GLIBCXX20_CONSTEXPR void
222 _S_on_dealloc(_Vector_impl& __impl)
223 {
224 if (__impl._M_start)
225 _S_adjust(__impl, __impl._M_finish, __impl._M_end_of_storage);
226 }
227
228 // Used on reallocation to tell ASan unused capacity is invalid.
229 struct _Reinit
230 {
231 explicit _GLIBCXX20_CONSTEXPR
232 _Reinit(_Vector_impl& __impl) : _M_impl(__impl)
233 {
234 // Mark unused capacity as valid again before deallocating it.
235 _S_on_dealloc(_M_impl);
236 }
237
238 _GLIBCXX20_CONSTEXPR
239 ~_Reinit()
240 {
241 // Mark unused capacity as invalid after reallocation.
242 if (_M_impl._M_start)
243 _S_adjust(_M_impl, _M_impl._M_end_of_storage,
244 _M_impl._M_finish);
245 }
246
247 _Vector_impl& _M_impl;
248
249#if __cplusplus >= 201103L
250 _Reinit(const _Reinit&) = delete;
251 _Reinit& operator=(const _Reinit&) = delete;
252#endif
253 };
254
255 // Tell ASan when unused capacity is initialized to be valid.
256 struct _Grow
257 {
258 _GLIBCXX20_CONSTEXPR
259 _Grow(_Vector_impl& __impl, size_type __n)
260 : _M_impl(__impl), _M_n(__n)
261 { _S_grow(_M_impl, __n); }
262
263 _GLIBCXX20_CONSTEXPR
264 ~_Grow() { if (_M_n) _S_shrink(_M_impl, _M_n); }
265
266 _GLIBCXX20_CONSTEXPR
267 void _M_grew(size_type __n) { _M_n -= __n; }
268
269#if __cplusplus >= 201103L
270 _Grow(const _Grow&) = delete;
271 _Grow& operator=(const _Grow&) = delete;
272#endif
273 private:
274 _Vector_impl& _M_impl;
275 size_type _M_n;
276 };
277 };
278
279#define _GLIBCXX_ASAN_ANNOTATE_REINIT \
280 typename _Base::_Vector_impl::template _Asan<>::_Reinit const \
281 __attribute__((__unused__)) __reinit_guard(this->_M_impl)
282#define _GLIBCXX_ASAN_ANNOTATE_GROW(n) \
283 typename _Base::_Vector_impl::template _Asan<>::_Grow \
284 __attribute__((__unused__)) __grow_guard(this->_M_impl, (n))
285#define _GLIBCXX_ASAN_ANNOTATE_GREW(n) __grow_guard._M_grew(n)
286#define _GLIBCXX_ASAN_ANNOTATE_SHRINK(n) \
287 _Base::_Vector_impl::template _Asan<>::_S_shrink(this->_M_impl, n)
288#define _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC \
289 _Base::_Vector_impl::template _Asan<>::_S_on_dealloc(this->_M_impl)
290#else // ! (_GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR)
291#define _GLIBCXX_ASAN_ANNOTATE_REINIT
292#define _GLIBCXX_ASAN_ANNOTATE_GROW(n)
293#define _GLIBCXX_ASAN_ANNOTATE_GREW(n)
294#define _GLIBCXX_ASAN_ANNOTATE_SHRINK(n)
295#define _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC
296#endif // _GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR
297 };
298
299 public:
300 typedef _Alloc allocator_type;
301
302 _GLIBCXX20_CONSTEXPR
303 _Tp_alloc_type&
304 _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
305 { return this->_M_impl; }
306
307 _GLIBCXX20_CONSTEXPR
308 const _Tp_alloc_type&
309 _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
310 { return this->_M_impl; }
311
312 _GLIBCXX20_CONSTEXPR
313 allocator_type
314 get_allocator() const _GLIBCXX_NOEXCEPT
315 { return allocator_type(_M_get_Tp_allocator()); }
316
317#if __cplusplus >= 201103L
318 _Vector_base() = default;
319#else
320 _Vector_base() { }
321#endif
322
323 _GLIBCXX20_CONSTEXPR
324 _Vector_base(const allocator_type& __a) _GLIBCXX_NOEXCEPT
325 : _M_impl(__a) { }
326
327 // Kept for ABI compatibility.
328#if !_GLIBCXX_INLINE_VERSION
329 _GLIBCXX20_CONSTEXPR
330 _Vector_base(size_t __n)
331 : _M_impl()
332 { _M_create_storage(__n); }
333#endif
334
335 _GLIBCXX20_CONSTEXPR
336 _Vector_base(size_t __n, const allocator_type& __a)
337 : _M_impl(__a)
338 { _M_create_storage(__n); }
339
340#if __cplusplus >= 201103L
341 _Vector_base(_Vector_base&&) = default;
342
343 // Kept for ABI compatibility.
344# if !_GLIBCXX_INLINE_VERSION
345 _GLIBCXX20_CONSTEXPR
346 _Vector_base(_Tp_alloc_type&& __a) noexcept
347 : _M_impl(std::move(__a)) { }
348
349 _GLIBCXX20_CONSTEXPR
350 _Vector_base(_Vector_base&& __x, const allocator_type& __a)
351 : _M_impl(__a)
352 {
353 if (__x.get_allocator() == __a)
354 this->_M_impl._M_swap_data(__x._M_impl);
355 else
356 {
357 size_t __n = __x._M_impl._M_finish - __x._M_impl._M_start;
358 _M_create_storage(__n);
359 }
360 }
361# endif
362
363 _GLIBCXX20_CONSTEXPR
364 _Vector_base(const allocator_type& __a, _Vector_base&& __x)
365 : _M_impl(_Tp_alloc_type(__a), std::move(__x._M_impl))
366 { }
367#endif
368
369 _GLIBCXX20_CONSTEXPR
370 ~_Vector_base() _GLIBCXX_NOEXCEPT
371 {
372 _M_deallocate(_M_impl._M_start,
373 _M_impl._M_end_of_storage - _M_impl._M_start);
374 }
375
376 public:
377 _Vector_impl _M_impl;
378
379 _GLIBCXX20_CONSTEXPR
380 pointer
381 _M_allocate(size_t __n)
382 {
384 return __n != 0 ? _Tr::allocate(_M_impl, __n) : pointer();
385 }
386
387 _GLIBCXX20_CONSTEXPR
388 void
389 _M_deallocate(pointer __p, size_t __n)
390 {
392 if (__p)
393 _Tr::deallocate(_M_impl, __p, __n);
394 }
395
396 protected:
397
398 _GLIBCXX20_CONSTEXPR
399 void
400 _M_create_storage(size_t __n)
401 {
402 this->_M_impl._M_start = this->_M_allocate(__n);
403 this->_M_impl._M_finish = this->_M_impl._M_start;
404 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
405 }
406
407#if __glibcxx_ranges_to_container // C++ >= 23
408 // Called by insert_range, and indirectly by assign_range, append_range.
409 // Initializes new elements in storage at __ptr and updates __ptr to
410 // point after the last new element.
411 // Provides strong exception safety guarantee.
412 // Requires [ptr, ptr+distance(rg)) is a valid range.
413 template<ranges::input_range _Rg>
414 constexpr void
415 _M_append_range_to(_Rg&& __rg, pointer& __ptr)
416 {
417 __ptr = std::__uninitialized_copy_a(ranges::begin(__rg),
418 ranges::end(__rg),
419 __ptr, _M_get_Tp_allocator());
420 }
421
422 // Called by assign_range, append_range, insert_range.
423 // Requires capacity() >= size()+distance(rg).
424 template<ranges::input_range _Rg>
425 constexpr void
426 _M_append_range(_Rg&& __rg)
427 { _M_append_range_to(std::forward<_Rg>(__rg), _M_impl._M_finish); }
428#endif
429 };
430
431 /**
432 * @brief A standard container which offers fixed time access to
433 * individual elements in any order.
434 *
435 * @ingroup sequences
436 * @headerfile vector
437 * @since C++98
438 *
439 * @tparam _Tp Type of element.
440 * @tparam _Alloc Allocator type, defaults to allocator<_Tp>.
441 *
442 * Meets the requirements of a <a href="tables.html#65">container</a>, a
443 * <a href="tables.html#66">reversible container</a>, and a
444 * <a href="tables.html#67">sequence</a>, including the
445 * <a href="tables.html#68">optional sequence requirements</a> with the
446 * %exception of @c push_front and @c pop_front.
447 *
448 * In some terminology a %vector can be described as a dynamic
449 * C-style array, it offers fast and efficient access to individual
450 * elements in any order and saves the user from worrying about
451 * memory and size allocation. Subscripting ( @c [] ) access is
452 * also provided as with C-style arrays.
453 */
454 template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
455 class vector : protected _Vector_base<_Tp, _Alloc>
456 {
457#ifdef _GLIBCXX_CONCEPT_CHECKS
458 // Concept requirements.
459 typedef typename _Alloc::value_type _Alloc_value_type;
460# if __cplusplus < 201103L
461 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
462# endif
463 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
464#endif
465
466#if __cplusplus >= 201103L
467 static_assert(is_same<typename remove_cv<_Tp>::type, _Tp>::value,
468 "std::vector must have a non-const, non-volatile value_type");
469# if __cplusplus > 201703L || defined __STRICT_ANSI__
471 "std::vector must have the same value_type as its allocator");
472# endif
473#endif
474
476 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
478
479 public:
480 typedef _Tp value_type;
481 typedef typename _Base::pointer pointer;
482 typedef typename _Alloc_traits::const_pointer const_pointer;
483 typedef typename _Alloc_traits::reference reference;
484 typedef typename _Alloc_traits::const_reference const_reference;
485 typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
486 typedef __gnu_cxx::__normal_iterator<const_pointer, vector>
487 const_iterator;
490 typedef size_t size_type;
491 typedef ptrdiff_t difference_type;
492 typedef _Alloc allocator_type;
493
494 private:
495#if __cplusplus >= 201103L
496 static constexpr bool
497 _S_nothrow_relocate(true_type)
498 {
499 return noexcept(std::__relocate_a(std::declval<pointer>(),
500 std::declval<pointer>(),
501 std::declval<pointer>(),
502 std::declval<_Tp_alloc_type&>()));
503 }
504
505 static constexpr bool
506 _S_nothrow_relocate(false_type)
507 { return false; }
508
509 static constexpr bool
510 _S_use_relocate()
511 {
512 // Instantiating std::__relocate_a might cause an error outside the
513 // immediate context (in __relocate_object_a's noexcept-specifier),
514 // so only do it if we know the type can be move-inserted into *this.
515 return _S_nothrow_relocate(__is_move_insertable<_Tp_alloc_type>{});
516 }
517
518 static pointer
519 _S_do_relocate(pointer __first, pointer __last, pointer __result,
520 _Tp_alloc_type& __alloc, true_type) noexcept
521 {
522 return std::__relocate_a(__first, __last, __result, __alloc);
523 }
524
525 static pointer
526 _S_do_relocate(pointer, pointer, pointer __result,
527 _Tp_alloc_type&, false_type) noexcept
528 { return __result; }
529
530 static _GLIBCXX20_CONSTEXPR pointer
531 _S_relocate(pointer __first, pointer __last, pointer __result,
532 _Tp_alloc_type& __alloc) noexcept
533 {
534#if __cpp_if_constexpr
535 // All callers have already checked _S_use_relocate() so just do it.
536 return std::__relocate_a(__first, __last, __result, __alloc);
537#else
538 using __do_it = __bool_constant<_S_use_relocate()>;
539 return _S_do_relocate(__first, __last, __result, __alloc, __do_it{});
540#endif
541 }
542#endif // C++11
543
544 protected:
545 using _Base::_M_allocate;
546 using _Base::_M_deallocate;
547 using _Base::_M_impl;
548 using _Base::_M_get_Tp_allocator;
549
550 public:
551 // [23.2.4.1] construct/copy/destroy
552 // (assign() and get_allocator() are also listed in this section)
553
554 /**
555 * @brief Creates a %vector with no elements.
556 */
557#if __cplusplus >= 201103L
558 vector() = default;
559#else
560 vector() { }
561#endif
562
563 /**
564 * @brief Creates a %vector with no elements.
565 * @param __a An allocator object.
566 */
567 explicit
568 _GLIBCXX20_CONSTEXPR
569 vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT
570 : _Base(__a) { }
571
572#if __cplusplus >= 201103L
573 /**
574 * @brief Creates a %vector with default constructed elements.
575 * @param __n The number of elements to initially create.
576 * @param __a An allocator.
577 *
578 * This constructor fills the %vector with @a __n default
579 * constructed elements.
580 */
581 explicit
582 _GLIBCXX20_CONSTEXPR
583 vector(size_type __n, const allocator_type& __a = allocator_type())
584 : _Base(_S_check_init_len(__n, __a), __a)
585 { _M_default_initialize(__n); }
586
587 /**
588 * @brief Creates a %vector with copies of an exemplar element.
589 * @param __n The number of elements to initially create.
590 * @param __value An element to copy.
591 * @param __a An allocator.
592 *
593 * This constructor fills the %vector with @a __n copies of @a __value.
594 */
595 _GLIBCXX20_CONSTEXPR
596 vector(size_type __n, const value_type& __value,
597 const allocator_type& __a = allocator_type())
598 : _Base(_S_check_init_len(__n, __a), __a)
599 { _M_fill_initialize(__n, __value); }
600#else
601 /**
602 * @brief Creates a %vector with copies of an exemplar element.
603 * @param __n The number of elements to initially create.
604 * @param __value An element to copy.
605 * @param __a An allocator.
606 *
607 * This constructor fills the %vector with @a __n copies of @a __value.
608 */
609 explicit
610 vector(size_type __n, const value_type& __value = value_type(),
611 const allocator_type& __a = allocator_type())
612 : _Base(_S_check_init_len(__n, __a), __a)
613 { _M_fill_initialize(__n, __value); }
614#endif
615
616 /**
617 * @brief %Vector copy constructor.
618 * @param __x A %vector of identical element and allocator types.
619 *
620 * All the elements of @a __x are copied, but any unused capacity in
621 * @a __x will not be copied
622 * (i.e. capacity() == size() in the new %vector).
623 *
624 * The newly-created %vector uses a copy of the allocator object used
625 * by @a __x (unless the allocator traits dictate a different object).
626 */
627 _GLIBCXX20_CONSTEXPR
628 vector(const vector& __x)
629 : _Base(__x.size(),
630 _Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()))
631 {
632 this->_M_impl._M_finish =
633 std::__uninitialized_copy_a(__x.begin(), __x.end(),
634 this->_M_impl._M_start,
635 _M_get_Tp_allocator());
636 }
637
638#if __cplusplus >= 201103L
639 /**
640 * @brief %Vector move constructor.
641 *
642 * The newly-created %vector contains the exact contents of the
643 * moved instance.
644 * The contents of the moved instance are a valid, but unspecified
645 * %vector.
646 */
647 vector(vector&&) noexcept = default;
648
649 /// Copy constructor with alternative allocator
650 _GLIBCXX20_CONSTEXPR
651 vector(const vector& __x, const __type_identity_t<allocator_type>& __a)
652 : _Base(__x.size(), __a)
653 {
654 this->_M_impl._M_finish =
655 std::__uninitialized_copy_a(__x.begin(), __x.end(),
656 this->_M_impl._M_start,
657 _M_get_Tp_allocator());
658 }
659
660 private:
661 _GLIBCXX20_CONSTEXPR
662 vector(vector&& __rv, const allocator_type& __m, true_type) noexcept
663 : _Base(__m, std::move(__rv))
664 { }
665
666 _GLIBCXX20_CONSTEXPR
667 vector(vector&& __rv, const allocator_type& __m, false_type)
668 : _Base(__m)
669 {
670 if (__rv.get_allocator() == __m)
671 this->_M_impl._M_swap_data(__rv._M_impl);
672 else if (!__rv.empty())
673 {
674 this->_M_create_storage(__rv.size());
675 this->_M_impl._M_finish =
676 std::__uninitialized_move_a(__rv.begin(), __rv.end(),
677 this->_M_impl._M_start,
678 _M_get_Tp_allocator());
679 __rv.clear();
680 }
681 }
682
683 public:
684 /// Move constructor with alternative allocator
685 _GLIBCXX20_CONSTEXPR
686 vector(vector&& __rv, const __type_identity_t<allocator_type>& __m)
687 noexcept( noexcept(
688 vector(std::declval<vector&&>(), std::declval<const allocator_type&>(),
689 std::declval<typename _Alloc_traits::is_always_equal>())) )
690 : vector(std::move(__rv), __m, typename _Alloc_traits::is_always_equal{})
691 { }
692
693 /**
694 * @brief Builds a %vector from an initializer list.
695 * @param __l An initializer_list.
696 * @param __a An allocator.
697 *
698 * Create a %vector consisting of copies of the elements in the
699 * initializer_list @a __l.
700 *
701 * This will call the element type's copy constructor N times
702 * (where N is @a __l.size()) and do no memory reallocation.
703 */
704 _GLIBCXX20_CONSTEXPR
706 const allocator_type& __a = allocator_type())
707 : _Base(__a)
708 {
709 _M_range_initialize(__l.begin(), __l.end(),
711 }
712#endif
713
714 /**
715 * @brief Builds a %vector from a range.
716 * @param __first An input iterator.
717 * @param __last An input iterator.
718 * @param __a An allocator.
719 *
720 * Create a %vector consisting of copies of the elements from
721 * [first,last).
722 *
723 * If the iterators are forward, bidirectional, or
724 * random-access, then this will call the elements' copy
725 * constructor N times (where N is distance(first,last)) and do
726 * no memory reallocation. But if only input iterators are
727 * used, then this will do at most 2N calls to the copy
728 * constructor, and logN memory reallocations.
729 */
730#if __cplusplus >= 201103L
731 template<typename _InputIterator,
732 typename = std::_RequireInputIter<_InputIterator>>
733 _GLIBCXX20_CONSTEXPR
734 vector(_InputIterator __first, _InputIterator __last,
735 const allocator_type& __a = allocator_type())
736 : _Base(__a)
737 {
738 _M_range_initialize(__first, __last,
739 std::__iterator_category(__first));
740 }
741#else
742 template<typename _InputIterator>
743 vector(_InputIterator __first, _InputIterator __last,
744 const allocator_type& __a = allocator_type())
745 : _Base(__a)
746 {
747 // Check whether it's an integral type. If so, it's not an iterator.
748 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
749 _M_initialize_dispatch(__first, __last, _Integral());
750 }
751#endif
752
753#if __glibcxx_ranges_to_container // C++ >= 23
754 /**
755 * @brief Construct a vector from a range.
756 * @since C++23
757 */
758 template<__detail::__container_compatible_range<_Tp> _Rg>
759 constexpr
760 vector(from_range_t, _Rg&& __rg, const _Alloc& __a = _Alloc())
761 : _Base(__a)
762 {
763 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
764 {
765 const auto __n = size_type(ranges::distance(__rg));
766 pointer __start =
767 this->_M_allocate(_S_check_init_len(__n,
768 _M_get_Tp_allocator()));
769 _Guard_alloc __guard(__start, __n, *this);
770 this->_M_impl._M_finish = this->_M_impl._M_start = __start;
771 this->_M_impl._M_end_of_storage = __start + __n;
772 _Base::_M_append_range(__rg);
773 (void) __guard._M_release();
774 }
775 else
776 {
777 // If an exception is thrown ~_Base() will deallocate storage,
778 // but will not destroy elements. This RAII type destroys them.
779 struct _Clear
780 {
781 ~_Clear() { if (_M_this) _M_this->clear(); }
782 vector* _M_this;
783 } __guard{this};
784
785 auto __first = ranges::begin(__rg);
786 const auto __last = ranges::end(__rg);
787 for (; __first != __last; ++__first)
788 emplace_back(*__first);
789 __guard._M_this = nullptr;
790 }
791 }
792#endif
793
794 /**
795 * The dtor only erases the elements, and note that if the
796 * elements themselves are pointers, the pointed-to memory is
797 * not touched in any way. Managing the pointer is the user's
798 * responsibility.
799 */
800 _GLIBCXX20_CONSTEXPR
801 ~vector() _GLIBCXX_NOEXCEPT
802 {
803 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
804 _M_get_Tp_allocator());
805 _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC;
806 }
807
808 /**
809 * @brief %Vector assignment operator.
810 * @param __x A %vector of identical element and allocator types.
811 *
812 * All the elements of @a __x are copied, but any unused capacity in
813 * @a __x will not be copied.
814 *
815 * Whether the allocator is copied depends on the allocator traits.
816 */
817 _GLIBCXX20_CONSTEXPR
818 vector&
819 operator=(const vector& __x);
820
821#if __cplusplus >= 201103L
822 /**
823 * @brief %Vector move assignment operator.
824 * @param __x A %vector of identical element and allocator types.
825 *
826 * The contents of @a __x are moved into this %vector (without copying,
827 * if the allocators permit it).
828 * Afterwards @a __x is a valid, but unspecified %vector.
829 *
830 * Whether the allocator is moved depends on the allocator traits.
831 */
832 _GLIBCXX20_CONSTEXPR
833 vector&
834 operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
835 {
836 constexpr bool __move_storage =
837 _Alloc_traits::_S_propagate_on_move_assign()
838 || _Alloc_traits::_S_always_equal();
839 _M_move_assign(std::move(__x), __bool_constant<__move_storage>());
840 return *this;
841 }
842
843 /**
844 * @brief %Vector list assignment operator.
845 * @param __l An initializer_list.
846 *
847 * This function fills a %vector with copies of the elements in the
848 * initializer list @a __l.
849 *
850 * Note that the assignment completely changes the %vector and
851 * that the resulting %vector's size is the same as the number
852 * of elements assigned.
853 */
854 _GLIBCXX20_CONSTEXPR
855 vector&
857 {
858 this->_M_assign_aux(__l.begin(), __l.end(),
860 return *this;
861 }
862#endif
863
864 /**
865 * @brief Assigns a given value to a %vector.
866 * @param __n Number of elements to be assigned.
867 * @param __val Value to be assigned.
868 *
869 * This function fills a %vector with @a __n copies of the given
870 * value. Note that the assignment completely changes the
871 * %vector and that the resulting %vector's size is the same as
872 * the number of elements assigned.
873 */
874 _GLIBCXX20_CONSTEXPR
875 void
876 assign(size_type __n, const value_type& __val)
877 { _M_fill_assign(__n, __val); }
878
879 /**
880 * @brief Assigns a range to a %vector.
881 * @param __first An input iterator.
882 * @param __last An input iterator.
883 *
884 * This function fills a %vector with copies of the elements in the
885 * range [__first,__last).
886 *
887 * Note that the assignment completely changes the %vector and
888 * that the resulting %vector's size is the same as the number
889 * of elements assigned.
890 */
891#if __cplusplus >= 201103L
892 template<typename _InputIterator,
893 typename = std::_RequireInputIter<_InputIterator>>
894 _GLIBCXX20_CONSTEXPR
895 void
896 assign(_InputIterator __first, _InputIterator __last)
897 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
898#else
899 template<typename _InputIterator>
900 void
901 assign(_InputIterator __first, _InputIterator __last)
902 {
903 // Check whether it's an integral type. If so, it's not an iterator.
904 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
905 _M_assign_dispatch(__first, __last, _Integral());
906 }
907#endif
908
909#if __cplusplus >= 201103L
910 /**
911 * @brief Assigns an initializer list to a %vector.
912 * @param __l An initializer_list.
913 *
914 * This function fills a %vector with copies of the elements in the
915 * initializer list @a __l.
916 *
917 * Note that the assignment completely changes the %vector and
918 * that the resulting %vector's size is the same as the number
919 * of elements assigned.
920 */
921 _GLIBCXX20_CONSTEXPR
922 void
924 {
925 this->_M_assign_aux(__l.begin(), __l.end(),
927 }
928#endif
929
930#if __glibcxx_ranges_to_container // C++ >= 23
931 /**
932 * @brief Assign a range to the vector.
933 * @since C++23
934 */
935 template<__detail::__container_compatible_range<_Tp> _Rg>
936 constexpr void
937 assign_range(_Rg&& __rg)
938 {
939 static_assert(assignable_from<_Tp&, ranges::range_reference_t<_Rg>>);
940
941 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
942 {
943 const auto __n = size_type(ranges::distance(__rg));
944 if (__n <= size())
945 {
946 auto __res = ranges::copy(__rg, this->_M_impl._M_start);
947 _M_erase_at_end(__res.out);
948 return;
949 }
950
951 reserve(__n);
952 auto __first = ranges::copy_n(ranges::begin(__rg), size(),
953 this->_M_impl._M_start).in;
954 [[maybe_unused]] const auto __diff = __n - size();
955 _GLIBCXX_ASAN_ANNOTATE_GROW(__diff);
956 _Base::_M_append_range(ranges::subrange(std::move(__first),
957 ranges::end(__rg)));
958 _GLIBCXX_ASAN_ANNOTATE_GREW(__diff);
959 }
960 else // input_range<_Rg> && !sized_range<_Rg>
961 {
962 auto __first = ranges::begin(__rg);
963 const auto __last = ranges::end(__rg);
964 pointer __ptr = this->_M_impl._M_start;
965 pointer const __end = this->_M_impl._M_finish;
966
967 while (__ptr < __end && __first != __last)
968 {
969 *__ptr = *__first;
970 ++__ptr;
971 ++__first;
972 }
973
974 if (__first == __last)
975 _M_erase_at_end(__ptr);
976 else
977 {
978 do
979 emplace_back(*__first);
980 while (++__first != __last);
981 }
982 }
983 }
984#endif // ranges_to_container
985
986 /// Get a copy of the memory allocation object.
987 using _Base::get_allocator;
988
989 // iterators
990 /**
991 * Returns a read/write iterator that points to the first
992 * element in the %vector. Iteration is done in ordinary
993 * element order.
994 */
995 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
996 iterator
997 begin() _GLIBCXX_NOEXCEPT
998 { return iterator(this->_M_impl._M_start); }
999
1000 /**
1001 * Returns a read-only (constant) iterator that points to the
1002 * first element in the %vector. Iteration is done in ordinary
1003 * element order.
1004 */
1005 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1006 const_iterator
1007 begin() const _GLIBCXX_NOEXCEPT
1008 { return const_iterator(this->_M_impl._M_start); }
1009
1010 /**
1011 * Returns a read/write iterator that points one past the last
1012 * element in the %vector. Iteration is done in ordinary
1013 * element order.
1014 */
1015 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1016 iterator
1017 end() _GLIBCXX_NOEXCEPT
1018 { return iterator(this->_M_impl._M_finish); }
1019
1020 /**
1021 * Returns a read-only (constant) iterator that points one past
1022 * the last element in the %vector. Iteration is done in
1023 * ordinary element order.
1024 */
1025 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1026 const_iterator
1027 end() const _GLIBCXX_NOEXCEPT
1028 { return const_iterator(this->_M_impl._M_finish); }
1029
1030 /**
1031 * Returns a read/write reverse iterator that points to the
1032 * last element in the %vector. Iteration is done in reverse
1033 * element order.
1034 */
1035 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1037 rbegin() _GLIBCXX_NOEXCEPT
1038 { return reverse_iterator(end()); }
1039
1040 /**
1041 * Returns a read-only (constant) reverse iterator that points
1042 * to the last element in the %vector. Iteration is done in
1043 * reverse element order.
1044 */
1045 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1046 const_reverse_iterator
1047 rbegin() const _GLIBCXX_NOEXCEPT
1048 { return const_reverse_iterator(end()); }
1049
1050 /**
1051 * Returns a read/write reverse iterator that points to one
1052 * before the first element in the %vector. Iteration is done
1053 * in reverse element order.
1054 */
1055 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1057 rend() _GLIBCXX_NOEXCEPT
1058 { return reverse_iterator(begin()); }
1059
1060 /**
1061 * Returns a read-only (constant) reverse iterator that points
1062 * to one before the first element in the %vector. Iteration
1063 * is done in reverse element order.
1064 */
1065 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1066 const_reverse_iterator
1067 rend() const _GLIBCXX_NOEXCEPT
1068 { return const_reverse_iterator(begin()); }
1069
1070#if __cplusplus >= 201103L
1071 /**
1072 * Returns a read-only (constant) iterator that points to the
1073 * first element in the %vector. Iteration is done in ordinary
1074 * element order.
1075 */
1076 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1077 const_iterator
1078 cbegin() const noexcept
1079 { return const_iterator(this->_M_impl._M_start); }
1080
1081 /**
1082 * Returns a read-only (constant) iterator that points one past
1083 * the last element in the %vector. Iteration is done in
1084 * ordinary element order.
1085 */
1086 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1087 const_iterator
1088 cend() const noexcept
1089 { return const_iterator(this->_M_impl._M_finish); }
1090
1091 /**
1092 * Returns a read-only (constant) reverse iterator that points
1093 * to the last element in the %vector. Iteration is done in
1094 * reverse element order.
1095 */
1096 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1097 const_reverse_iterator
1098 crbegin() const noexcept
1099 { return const_reverse_iterator(end()); }
1100
1101 /**
1102 * Returns a read-only (constant) reverse iterator that points
1103 * to one before the first element in the %vector. Iteration
1104 * is done in reverse element order.
1105 */
1106 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1107 const_reverse_iterator
1108 crend() const noexcept
1109 { return const_reverse_iterator(begin()); }
1110#endif
1111
1112 // [23.2.4.2] capacity
1113 /** Returns the number of elements in the %vector. */
1114 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1115 size_type
1116 size() const _GLIBCXX_NOEXCEPT
1117 { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
1118
1119 /** Returns the size() of the largest possible %vector. */
1120 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1121 size_type
1122 max_size() const _GLIBCXX_NOEXCEPT
1123 { return _S_max_size(_M_get_Tp_allocator()); }
1124
1125#if __cplusplus >= 201103L
1126 /**
1127 * @brief Resizes the %vector to the specified number of elements.
1128 * @param __new_size Number of elements the %vector should contain.
1129 *
1130 * This function will %resize the %vector to the specified
1131 * number of elements. If the number is smaller than the
1132 * %vector's current size the %vector is truncated, otherwise
1133 * default constructed elements are appended.
1134 */
1135 _GLIBCXX20_CONSTEXPR
1136 void
1137 resize(size_type __new_size)
1138 {
1139 if (__new_size > size())
1140 _M_default_append(__new_size - size());
1141 else if (__new_size < size())
1142 _M_erase_at_end(this->_M_impl._M_start + __new_size);
1143 }
1144
1145 /**
1146 * @brief Resizes the %vector to the specified number of elements.
1147 * @param __new_size Number of elements the %vector should contain.
1148 * @param __x Data with which new elements should be populated.
1149 *
1150 * This function will %resize the %vector to the specified
1151 * number of elements. If the number is smaller than the
1152 * %vector's current size the %vector is truncated, otherwise
1153 * the %vector is extended and new elements are populated with
1154 * given data.
1155 */
1156 _GLIBCXX20_CONSTEXPR
1157 void
1158 resize(size_type __new_size, const value_type& __x)
1159 {
1160 if (__new_size > size())
1161 _M_fill_insert(end(), __new_size - size(), __x);
1162 else if (__new_size < size())
1163 _M_erase_at_end(this->_M_impl._M_start + __new_size);
1164 }
1165#else
1166 /**
1167 * @brief Resizes the %vector to the specified number of elements.
1168 * @param __new_size Number of elements the %vector should contain.
1169 * @param __x Data with which new elements should be populated.
1170 *
1171 * This function will %resize the %vector to the specified
1172 * number of elements. If the number is smaller than the
1173 * %vector's current size the %vector is truncated, otherwise
1174 * the %vector is extended and new elements are populated with
1175 * given data.
1176 */
1177 _GLIBCXX20_CONSTEXPR
1178 void
1179 resize(size_type __new_size, value_type __x = value_type())
1180 {
1181 if (__new_size > size())
1182 _M_fill_insert(end(), __new_size - size(), __x);
1183 else if (__new_size < size())
1184 _M_erase_at_end(this->_M_impl._M_start + __new_size);
1185 }
1186#endif
1187
1188#if __cplusplus >= 201103L
1189 /** A non-binding request to reduce capacity() to size(). */
1190 _GLIBCXX20_CONSTEXPR
1191 void
1193 { _M_shrink_to_fit(); }
1194#endif
1195
1196 /**
1197 * Returns the total number of elements that the %vector can
1198 * hold before needing to allocate more memory.
1199 */
1200 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1201 size_type
1202 capacity() const _GLIBCXX_NOEXCEPT
1203 {
1204 return size_type(this->_M_impl._M_end_of_storage
1205 - this->_M_impl._M_start);
1206 }
1207
1208 /**
1209 * Returns true if the %vector is empty. (Thus begin() would
1210 * equal end().)
1211 */
1212 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1213 bool
1214 empty() const _GLIBCXX_NOEXCEPT
1215 { return begin() == end(); }
1216
1217 /**
1218 * @brief Attempt to preallocate enough memory for specified number of
1219 * elements.
1220 * @param __n Number of elements required.
1221 * @throw std::length_error If @a n exceeds @c max_size().
1222 *
1223 * This function attempts to reserve enough memory for the
1224 * %vector to hold the specified number of elements. If the
1225 * number requested is more than max_size(), length_error is
1226 * thrown.
1227 *
1228 * The advantage of this function is that if optimal code is a
1229 * necessity and the user can determine the number of elements
1230 * that will be required, the user can reserve the memory in
1231 * %advance, and thus prevent a possible reallocation of memory
1232 * and copying of %vector data.
1233 */
1234 _GLIBCXX20_CONSTEXPR
1235 void
1236 reserve(size_type __n);
1237
1238 // element access
1239 /**
1240 * @brief Subscript access to the data contained in the %vector.
1241 * @param __n The index of the element for which data should be
1242 * accessed.
1243 * @return Read/write reference to data.
1244 *
1245 * This operator allows for easy, array-style, data access.
1246 * Note that data access with this operator is unchecked and
1247 * out_of_range lookups are not defined. (For checked lookups
1248 * see at().)
1249 */
1250 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1251 reference
1252 operator[](size_type __n) _GLIBCXX_NOEXCEPT
1253 {
1254 __glibcxx_requires_subscript(__n);
1255 return *(this->_M_impl._M_start + __n);
1256 }
1257
1258 /**
1259 * @brief Subscript access to the data contained in the %vector.
1260 * @param __n The index of the element for which data should be
1261 * accessed.
1262 * @return Read-only (constant) reference to data.
1263 *
1264 * This operator allows for easy, array-style, data access.
1265 * Note that data access with this operator is unchecked and
1266 * out_of_range lookups are not defined. (For checked lookups
1267 * see at().)
1268 */
1269 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1270 const_reference
1271 operator[](size_type __n) const _GLIBCXX_NOEXCEPT
1272 {
1273 __glibcxx_requires_subscript(__n);
1274 return *(this->_M_impl._M_start + __n);
1275 }
1276
1277 protected:
1278 /// Safety check used only from at().
1279 _GLIBCXX20_CONSTEXPR
1280 void
1281 _M_range_check(size_type __n) const
1282 {
1283 if (__n >= this->size())
1284 __throw_out_of_range_fmt(__N("vector::_M_range_check: __n "
1285 "(which is %zu) >= this->size() "
1286 "(which is %zu)"),
1287 __n, this->size());
1288 }
1289
1290 public:
1291 /**
1292 * @brief Provides access to the data contained in the %vector.
1293 * @param __n The index of the element for which data should be
1294 * accessed.
1295 * @return Read/write reference to data.
1296 * @throw std::out_of_range If @a __n is an invalid index.
1297 *
1298 * This function provides for safer data access. The parameter
1299 * is first checked that it is in the range of the vector. The
1300 * function throws out_of_range if the check fails.
1301 */
1302 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1303 reference
1304 at(size_type __n)
1305 {
1306 _M_range_check(__n);
1307 return (*this)[__n];
1308 }
1309
1310 /**
1311 * @brief Provides access to the data contained in the %vector.
1312 * @param __n The index of the element for which data should be
1313 * accessed.
1314 * @return Read-only (constant) reference to data.
1315 * @throw std::out_of_range If @a __n is an invalid index.
1316 *
1317 * This function provides for safer data access. The parameter
1318 * is first checked that it is in the range of the vector. The
1319 * function throws out_of_range if the check fails.
1320 */
1321 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1322 const_reference
1323 at(size_type __n) const
1324 {
1325 _M_range_check(__n);
1326 return (*this)[__n];
1327 }
1328
1329 /**
1330 * Returns a read/write reference to the data at the first
1331 * element of the %vector.
1332 */
1333 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1334 reference
1335 front() _GLIBCXX_NOEXCEPT
1336 {
1337 __glibcxx_requires_nonempty();
1338 return *begin();
1339 }
1340
1341 /**
1342 * Returns a read-only (constant) reference to the data at the first
1343 * element of the %vector.
1344 */
1345 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1346 const_reference
1347 front() const _GLIBCXX_NOEXCEPT
1348 {
1349 __glibcxx_requires_nonempty();
1350 return *begin();
1351 }
1352
1353 /**
1354 * Returns a read/write reference to the data at the last
1355 * element of the %vector.
1356 */
1357 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1358 reference
1359 back() _GLIBCXX_NOEXCEPT
1360 {
1361 __glibcxx_requires_nonempty();
1362 return *(end() - 1);
1363 }
1364
1365 /**
1366 * Returns a read-only (constant) reference to the data at the
1367 * last element of the %vector.
1368 */
1369 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1370 const_reference
1371 back() const _GLIBCXX_NOEXCEPT
1372 {
1373 __glibcxx_requires_nonempty();
1374 return *(end() - 1);
1375 }
1376
1377 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1378 // DR 464. Suggestion for new member functions in standard containers.
1379 // data access
1380 /**
1381 * Returns a pointer such that [data(), data() + size()) is a valid
1382 * range. For a non-empty %vector, data() == &front().
1383 */
1384 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1385 _Tp*
1386 data() _GLIBCXX_NOEXCEPT
1387 { return _M_data_ptr(this->_M_impl._M_start); }
1388
1389 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1390 const _Tp*
1391 data() const _GLIBCXX_NOEXCEPT
1392 { return _M_data_ptr(this->_M_impl._M_start); }
1393
1394 // [23.2.4.3] modifiers
1395 /**
1396 * @brief Add data to the end of the %vector.
1397 * @param __x Data to be added.
1398 *
1399 * This is a typical stack operation. The function creates an
1400 * element at the end of the %vector and assigns the given data
1401 * to it. Due to the nature of a %vector this operation can be
1402 * done in constant time if the %vector has preallocated space
1403 * available.
1404 */
1405 _GLIBCXX20_CONSTEXPR
1406 void
1407 push_back(const value_type& __x)
1408 {
1409 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
1410 {
1411 _GLIBCXX_ASAN_ANNOTATE_GROW(1);
1412 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
1413 __x);
1414 ++this->_M_impl._M_finish;
1415 _GLIBCXX_ASAN_ANNOTATE_GREW(1);
1416 }
1417 else
1418 _M_realloc_append(__x);
1419 }
1420
1421#if __cplusplus >= 201103L
1422 _GLIBCXX20_CONSTEXPR
1423 void
1424 push_back(value_type&& __x)
1425 { emplace_back(std::move(__x)); }
1426
1427 template<typename... _Args>
1428#if __cplusplus > 201402L
1429 _GLIBCXX20_CONSTEXPR
1430 reference
1431#else
1432 void
1433#endif
1434 emplace_back(_Args&&... __args);
1435#endif
1436
1437 /**
1438 * @brief Removes last element.
1439 *
1440 * This is a typical stack operation. It shrinks the %vector by one.
1441 *
1442 * Note that no data is returned, and if the last element's
1443 * data is needed, it should be retrieved before pop_back() is
1444 * called.
1445 */
1446 _GLIBCXX20_CONSTEXPR
1447 void
1448 pop_back() _GLIBCXX_NOEXCEPT
1449 {
1450 __glibcxx_requires_nonempty();
1451 --this->_M_impl._M_finish;
1452 _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
1453 _GLIBCXX_ASAN_ANNOTATE_SHRINK(1);
1454 }
1455
1456#if __cplusplus >= 201103L
1457 /**
1458 * @brief Inserts an object in %vector before specified iterator.
1459 * @param __position A const_iterator into the %vector.
1460 * @param __args Arguments.
1461 * @return An iterator that points to the inserted data.
1462 *
1463 * This function will insert an object of type T constructed
1464 * with T(std::forward<Args>(args)...) before the specified location.
1465 * Note that this kind of operation could be expensive for a %vector
1466 * and if it is frequently used the user should consider using
1467 * std::list.
1468 */
1469 template<typename... _Args>
1470 _GLIBCXX20_CONSTEXPR
1471 iterator
1472 emplace(const_iterator __position, _Args&&... __args)
1473 { return _M_emplace_aux(__position, std::forward<_Args>(__args)...); }
1474
1475 /**
1476 * @brief Inserts given value into %vector before specified iterator.
1477 * @param __position A const_iterator into the %vector.
1478 * @param __x Data to be inserted.
1479 * @return An iterator that points to the inserted data.
1480 *
1481 * This function will insert a copy of the given value before
1482 * the specified location. Note that this kind of operation
1483 * could be expensive for a %vector and if it is frequently
1484 * used the user should consider using std::list.
1485 */
1486 _GLIBCXX20_CONSTEXPR
1487 iterator
1488 insert(const_iterator __position, const value_type& __x);
1489#else
1490 /**
1491 * @brief Inserts given value into %vector before specified iterator.
1492 * @param __position An iterator into the %vector.
1493 * @param __x Data to be inserted.
1494 * @return An iterator that points to the inserted data.
1495 *
1496 * This function will insert a copy of the given value before
1497 * the specified location. Note that this kind of operation
1498 * could be expensive for a %vector and if it is frequently
1499 * used the user should consider using std::list.
1500 */
1501 iterator
1502 insert(iterator __position, const value_type& __x);
1503#endif
1504
1505#if __cplusplus >= 201103L
1506 /**
1507 * @brief Inserts given rvalue into %vector before specified iterator.
1508 * @param __position A const_iterator into the %vector.
1509 * @param __x Data to be inserted.
1510 * @return An iterator that points to the inserted data.
1511 *
1512 * This function will insert a copy of the given rvalue before
1513 * the specified location. Note that this kind of operation
1514 * could be expensive for a %vector and if it is frequently
1515 * used the user should consider using std::list.
1516 */
1517 _GLIBCXX20_CONSTEXPR
1518 iterator
1519 insert(const_iterator __position, value_type&& __x)
1520 { return _M_insert_rval(__position, std::move(__x)); }
1521
1522 /**
1523 * @brief Inserts an initializer_list into the %vector.
1524 * @param __position An iterator into the %vector.
1525 * @param __l An initializer_list.
1526 *
1527 * This function will insert copies of the data in the
1528 * initializer_list @a l into the %vector before the location
1529 * specified by @a position.
1530 *
1531 * Note that this kind of operation could be expensive for a
1532 * %vector and if it is frequently used the user should
1533 * consider using std::list.
1534 */
1535 _GLIBCXX20_CONSTEXPR
1536 iterator
1537 insert(const_iterator __position, initializer_list<value_type> __l)
1538 {
1539 auto __offset = __position - cbegin();
1540 _M_range_insert(begin() + __offset, __l.begin(), __l.end(),
1542 return begin() + __offset;
1543 }
1544#endif
1545
1546#if __cplusplus >= 201103L
1547 /**
1548 * @brief Inserts a number of copies of given data into the %vector.
1549 * @param __position A const_iterator into the %vector.
1550 * @param __n Number of elements to be inserted.
1551 * @param __x Data to be inserted.
1552 * @return An iterator that points to the inserted data.
1553 *
1554 * This function will insert a specified number of copies of
1555 * the given data before the location specified by @a position.
1556 *
1557 * Note that this kind of operation could be expensive for a
1558 * %vector and if it is frequently used the user should
1559 * consider using std::list.
1560 */
1561 _GLIBCXX20_CONSTEXPR
1562 iterator
1563 insert(const_iterator __position, size_type __n, const value_type& __x)
1564 {
1565 difference_type __offset = __position - cbegin();
1566 _M_fill_insert(begin() + __offset, __n, __x);
1567 return begin() + __offset;
1568 }
1569#else
1570 /**
1571 * @brief Inserts a number of copies of given data into the %vector.
1572 * @param __position An iterator into the %vector.
1573 * @param __n Number of elements to be inserted.
1574 * @param __x Data to be inserted.
1575 *
1576 * This function will insert a specified number of copies of
1577 * the given data before the location specified by @a position.
1578 *
1579 * Note that this kind of operation could be expensive for a
1580 * %vector and if it is frequently used the user should
1581 * consider using std::list.
1582 */
1583 void
1584 insert(iterator __position, size_type __n, const value_type& __x)
1585 { _M_fill_insert(__position, __n, __x); }
1586#endif
1587
1588#if __cplusplus >= 201103L
1589 /**
1590 * @brief Inserts a range into the %vector.
1591 * @param __position A const_iterator into the %vector.
1592 * @param __first An input iterator.
1593 * @param __last An input iterator.
1594 * @return An iterator that points to the inserted data.
1595 *
1596 * This function will insert copies of the data in the range
1597 * [__first,__last) into the %vector before the location specified
1598 * by @a pos.
1599 *
1600 * Note that this kind of operation could be expensive for a
1601 * %vector and if it is frequently used the user should
1602 * consider using std::list.
1603 */
1604 template<typename _InputIterator,
1605 typename = std::_RequireInputIter<_InputIterator>>
1606 _GLIBCXX20_CONSTEXPR
1607 iterator
1608 insert(const_iterator __position, _InputIterator __first,
1609 _InputIterator __last)
1610 {
1611 difference_type __offset = __position - cbegin();
1612 _M_range_insert(begin() + __offset, __first, __last,
1613 std::__iterator_category(__first));
1614 return begin() + __offset;
1615 }
1616#else
1617 /**
1618 * @brief Inserts a range into the %vector.
1619 * @param __position An iterator into the %vector.
1620 * @param __first An input iterator.
1621 * @param __last An input iterator.
1622 *
1623 * This function will insert copies of the data in the range
1624 * [__first,__last) into the %vector before the location specified
1625 * by @a pos.
1626 *
1627 * Note that this kind of operation could be expensive for a
1628 * %vector and if it is frequently used the user should
1629 * consider using std::list.
1630 */
1631 template<typename _InputIterator>
1632 void
1633 insert(iterator __position, _InputIterator __first,
1634 _InputIterator __last)
1635 {
1636 // Check whether it's an integral type. If so, it's not an iterator.
1637 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1638 _M_insert_dispatch(__position, __first, __last, _Integral());
1639 }
1640#endif
1641
1642#if __glibcxx_ranges_to_container // C++ >= 23
1643 /**
1644 * @brief Insert a range into the vector.
1645 * @since C++23
1646 */
1647 template<__detail::__container_compatible_range<_Tp> _Rg>
1648 constexpr iterator
1649 insert_range(const_iterator __pos, _Rg&& __rg);
1650
1651 /**
1652 * @brief Append a range at the end of the vector.
1653 * @since C++23
1654 */
1655 template<__detail::__container_compatible_range<_Tp> _Rg>
1656 constexpr void
1657 append_range(_Rg&& __rg)
1658 {
1659 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
1660 {
1661 const auto __n = size_type(ranges::distance(__rg));
1662 reserve(size() + __n);
1663 _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
1664 _Base::_M_append_range(__rg);
1665 _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
1666 }
1667 else
1668 {
1669 auto __first = ranges::begin(__rg);
1670 const auto __last = ranges::end(__rg);
1671 for (; __first != __last; ++__first)
1672 emplace_back(*__first);
1673 }
1674 }
1675#endif // ranges_to_container
1676
1677 /**
1678 * @brief Remove element at given position.
1679 * @param __position Iterator pointing to element to be erased.
1680 * @return An iterator pointing to the next element (or end()).
1681 *
1682 * This function will erase the element at the given position and thus
1683 * shorten the %vector by one.
1684 *
1685 * Note This operation could be expensive and if it is
1686 * frequently used the user should consider using std::list.
1687 * The user is also cautioned that this function only erases
1688 * the element, and that if the element is itself a pointer,
1689 * the pointed-to memory is not touched in any way. Managing
1690 * the pointer is the user's responsibility.
1691 */
1692 _GLIBCXX20_CONSTEXPR
1693 iterator
1694#if __cplusplus >= 201103L
1695 erase(const_iterator __position)
1696 { return _M_erase(begin() + (__position - cbegin())); }
1697#else
1698 erase(iterator __position)
1699 { return _M_erase(__position); }
1700#endif
1701
1702 /**
1703 * @brief Remove a range of elements.
1704 * @param __first Iterator pointing to the first element to be erased.
1705 * @param __last Iterator pointing to one past the last element to be
1706 * erased.
1707 * @return An iterator pointing to the element pointed to by @a __last
1708 * prior to erasing (or end()).
1709 *
1710 * This function will erase the elements in the range
1711 * [__first,__last) and shorten the %vector accordingly.
1712 *
1713 * Note This operation could be expensive and if it is
1714 * frequently used the user should consider using std::list.
1715 * The user is also cautioned that this function only erases
1716 * the elements, and that if the elements themselves are
1717 * pointers, the pointed-to memory is not touched in any way.
1718 * Managing the pointer is the user's responsibility.
1719 */
1720 _GLIBCXX20_CONSTEXPR
1721 iterator
1722#if __cplusplus >= 201103L
1723 erase(const_iterator __first, const_iterator __last)
1724 {
1725 const auto __beg = begin();
1726 const auto __cbeg = cbegin();
1727 return _M_erase(__beg + (__first - __cbeg), __beg + (__last - __cbeg));
1728 }
1729#else
1730 erase(iterator __first, iterator __last)
1731 { return _M_erase(__first, __last); }
1732#endif
1733
1734 /**
1735 * @brief Swaps data with another %vector.
1736 * @param __x A %vector of the same element and allocator types.
1737 *
1738 * This exchanges the elements between two vectors in constant time.
1739 * (Three pointers, so it should be quite fast.)
1740 * Note that the global std::swap() function is specialized such that
1741 * std::swap(v1,v2) will feed to this function.
1742 *
1743 * Whether the allocators are swapped depends on the allocator traits.
1744 */
1745 _GLIBCXX20_CONSTEXPR
1746 void
1747 swap(vector& __x) _GLIBCXX_NOEXCEPT
1748 {
1749#if __cplusplus >= 201103L
1750 __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value
1751 || _M_get_Tp_allocator() == __x._M_get_Tp_allocator());
1752#endif
1753 this->_M_impl._M_swap_data(__x._M_impl);
1754 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1755 __x._M_get_Tp_allocator());
1756 }
1757
1758 /**
1759 * Erases all the elements. Note that this function only erases the
1760 * elements, and that if the elements themselves are pointers, the
1761 * pointed-to memory is not touched in any way. Managing the pointer is
1762 * the user's responsibility.
1763 */
1764 _GLIBCXX20_CONSTEXPR
1765 void
1766 clear() _GLIBCXX_NOEXCEPT
1767 { _M_erase_at_end(this->_M_impl._M_start); }
1768
1769 private:
1770 // RAII guard for allocated storage.
1771 struct _Guard_alloc
1772 {
1773 pointer _M_storage; // Storage to deallocate
1774 size_type _M_len;
1775 _Base& _M_vect;
1776
1777 _GLIBCXX20_CONSTEXPR
1778 _Guard_alloc(pointer __s, size_type __l, _Base& __vect)
1779 : _M_storage(__s), _M_len(__l), _M_vect(__vect)
1780 { }
1781
1782 _GLIBCXX20_CONSTEXPR
1783 ~_Guard_alloc()
1784 {
1785 if (_M_storage)
1786 _M_vect._M_deallocate(_M_storage, _M_len);
1787 }
1788
1789 _GLIBCXX20_CONSTEXPR
1790 pointer
1791 _M_release()
1792 {
1793 pointer __res = _M_storage;
1794 _M_storage = pointer();
1795 return __res;
1796 }
1797
1798 private:
1799 _Guard_alloc(const _Guard_alloc&);
1800 };
1801
1802 protected:
1803 /**
1804 * Memory expansion handler. Uses the member allocation function to
1805 * obtain @a n bytes of memory, and then copies [first,last) into it.
1806 */
1807 template<typename _ForwardIterator>
1808 _GLIBCXX20_CONSTEXPR
1809 pointer
1811 _ForwardIterator __first, _ForwardIterator __last)
1812 {
1813 _Guard_alloc __guard(this->_M_allocate(__n), __n, *this);
1814 std::__uninitialized_copy_a
1815 (__first, __last, __guard._M_storage, _M_get_Tp_allocator());
1816 return __guard._M_release();
1817 }
1818
1819
1820 // Internal constructor functions follow.
1821
1822 // Called by the range constructor to implement [23.1.1]/9
1823
1824#if __cplusplus < 201103L
1825 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1826 // 438. Ambiguity in the "do the right thing" clause
1827 template<typename _Integer>
1828 void
1829 _M_initialize_dispatch(_Integer __int_n, _Integer __value, __true_type)
1830 {
1831 const size_type __n = static_cast<size_type>(__int_n);
1832 pointer __start =
1833 _M_allocate(_S_check_init_len(__n, _M_get_Tp_allocator()));
1834 this->_M_impl._M_start = __start;
1835 this->_M_impl._M_end_of_storage = __start + __n;
1836 _M_fill_initialize(__n, __value);
1837 }
1838
1839 // Called by the range constructor to implement [23.1.1]/9
1840 template<typename _InputIterator>
1841 void
1842 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1843 __false_type)
1844 {
1845 _M_range_initialize(__first, __last,
1846 std::__iterator_category(__first));
1847 }
1848#endif
1849
1850 // Called by the second initialize_dispatch above
1851 template<typename _InputIterator>
1852 _GLIBCXX20_CONSTEXPR
1853 void
1854 _M_range_initialize(_InputIterator __first, _InputIterator __last,
1856 {
1857 __try {
1858 for (; __first != __last; ++__first)
1859#if __cplusplus >= 201103L
1860 emplace_back(*__first);
1861#else
1862 push_back(*__first);
1863#endif
1864 } __catch(...) {
1865 clear();
1866 __throw_exception_again;
1867 }
1868 }
1869
1870 // Called by the second initialize_dispatch above
1871 template<typename _ForwardIterator>
1872 _GLIBCXX20_CONSTEXPR
1873 void
1874 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
1876 {
1877 const size_type __n = std::distance(__first, __last);
1878 pointer __start =
1879 this->_M_allocate(_S_check_init_len(__n, _M_get_Tp_allocator()));
1880 _Guard_alloc __guard(__start, __n, *this);
1881 this->_M_impl._M_finish = std::__uninitialized_copy_a
1882 (__first, __last, __start, _M_get_Tp_allocator());
1883 this->_M_impl._M_start = __start;
1884 (void) __guard._M_release();
1885 this->_M_impl._M_end_of_storage = __start + __n;
1886 }
1887
1888 // Called by the first initialize_dispatch above and by the
1889 // vector(n,value,a) constructor.
1890 _GLIBCXX20_CONSTEXPR
1891 void
1892 _M_fill_initialize(size_type __n, const value_type& __value)
1893 {
1894 this->_M_impl._M_finish =
1895 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
1896 _M_get_Tp_allocator());
1897 }
1898
1899#if __cplusplus >= 201103L
1900 // Called by the vector(n) constructor.
1901 _GLIBCXX20_CONSTEXPR
1902 void
1903 _M_default_initialize(size_type __n)
1904 {
1905 this->_M_impl._M_finish =
1906 std::__uninitialized_default_n_a(this->_M_impl._M_start, __n,
1907 _M_get_Tp_allocator());
1908 }
1909#endif
1910
1911 // Internal assign functions follow. The *_aux functions do the actual
1912 // assignment work for the range versions.
1913
1914 // Called by the range assign to implement [23.1.1]/9
1915
1916 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1917 // 438. Ambiguity in the "do the right thing" clause
1918 template<typename _Integer>
1919 _GLIBCXX20_CONSTEXPR
1920 void
1921 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1922 { _M_fill_assign(__n, __val); }
1923
1924 // Called by the range assign to implement [23.1.1]/9
1925 template<typename _InputIterator>
1926 _GLIBCXX20_CONSTEXPR
1927 void
1928 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1929 __false_type)
1930 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
1931
1932 // Called by the second assign_dispatch above
1933 template<typename _InputIterator>
1934 _GLIBCXX20_CONSTEXPR
1935 void
1936 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1938
1939 // Called by the second assign_dispatch above
1940 template<typename _ForwardIterator>
1941 _GLIBCXX20_CONSTEXPR
1942 void
1943 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1945
1946 // Called by assign(n,t), and the range assign when it turns out
1947 // to be the same thing.
1948 _GLIBCXX20_CONSTEXPR
1949 void
1950 _M_fill_assign(size_type __n, const value_type& __val);
1951
1952 // Internal insert functions follow.
1953
1954 // Called by the range insert to implement [23.1.1]/9
1955
1956 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1957 // 438. Ambiguity in the "do the right thing" clause
1958 template<typename _Integer>
1959 _GLIBCXX20_CONSTEXPR
1960 void
1961 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
1962 __true_type)
1963 { _M_fill_insert(__pos, __n, __val); }
1964
1965 // Called by the range insert to implement [23.1.1]/9
1966 template<typename _InputIterator>
1967 _GLIBCXX20_CONSTEXPR
1968 void
1969 _M_insert_dispatch(iterator __pos, _InputIterator __first,
1970 _InputIterator __last, __false_type)
1971 {
1972 _M_range_insert(__pos, __first, __last,
1973 std::__iterator_category(__first));
1974 }
1975
1976 // Called by the second insert_dispatch above
1977 template<typename _InputIterator>
1978 _GLIBCXX20_CONSTEXPR
1979 void
1980 _M_range_insert(iterator __pos, _InputIterator __first,
1981 _InputIterator __last, std::input_iterator_tag);
1982
1983 // Called by the second insert_dispatch above
1984 template<typename _ForwardIterator>
1985 _GLIBCXX20_CONSTEXPR
1986 void
1987 _M_range_insert(iterator __pos, _ForwardIterator __first,
1988 _ForwardIterator __last, std::forward_iterator_tag);
1989
1990 // Called by insert(p,n,x), and the range insert when it turns out to be
1991 // the same thing.
1992 _GLIBCXX20_CONSTEXPR
1993 void
1994 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
1995
1996#if __cplusplus >= 201103L
1997 // Called by resize(n).
1998 _GLIBCXX20_CONSTEXPR
1999 void
2000 _M_default_append(size_type __n);
2001
2002 _GLIBCXX20_CONSTEXPR
2003 bool
2004 _M_shrink_to_fit();
2005#endif
2006
2007#if __cplusplus < 201103L
2008 // Called by insert(p,x)
2009 void
2010 _M_insert_aux(iterator __position, const value_type& __x);
2011
2012 void
2013 _M_realloc_insert(iterator __position, const value_type& __x);
2014
2015 void
2016 _M_realloc_append(const value_type& __x);
2017#else
2018 // A value_type object constructed with _Alloc_traits::construct()
2019 // and destroyed with _Alloc_traits::destroy().
2020 struct _Temporary_value
2021 {
2022 template<typename... _Args>
2023 _GLIBCXX20_CONSTEXPR explicit
2024 _Temporary_value(vector* __vec, _Args&&... __args) : _M_this(__vec)
2025 {
2026 _Alloc_traits::construct(_M_this->_M_impl, _M_ptr(),
2027 std::forward<_Args>(__args)...);
2028 }
2029
2030 _GLIBCXX20_CONSTEXPR
2031 ~_Temporary_value()
2032 { _Alloc_traits::destroy(_M_this->_M_impl, _M_ptr()); }
2033
2034 _GLIBCXX20_CONSTEXPR value_type&
2035 _M_val() noexcept { return _M_storage._M_val; }
2036
2037 private:
2038 _GLIBCXX20_CONSTEXPR _Tp*
2039 _M_ptr() noexcept { return std::__addressof(_M_storage._M_val); }
2040
2041 union _Storage
2042 {
2043 constexpr _Storage() : _M_byte() { }
2044 _GLIBCXX20_CONSTEXPR ~_Storage() { }
2045 _Storage& operator=(const _Storage&) = delete;
2046 unsigned char _M_byte;
2047 _Tp _M_val;
2048 };
2049
2050 vector* _M_this;
2051 _Storage _M_storage;
2052 };
2053
2054 // Called by insert(p,x) and other functions when insertion needs to
2055 // reallocate or move existing elements. _Arg is either _Tp& or _Tp.
2056 template<typename _Arg>
2057 _GLIBCXX20_CONSTEXPR
2058 void
2059 _M_insert_aux(iterator __position, _Arg&& __arg);
2060
2061 template<typename... _Args>
2062 _GLIBCXX20_CONSTEXPR
2063 void
2064 _M_realloc_insert(iterator __position, _Args&&... __args);
2065
2066 template<typename... _Args>
2067 _GLIBCXX20_CONSTEXPR
2068 void
2069 _M_realloc_append(_Args&&... __args);
2070
2071 // Either move-construct at the end, or forward to _M_insert_aux.
2072 _GLIBCXX20_CONSTEXPR
2073 iterator
2074 _M_insert_rval(const_iterator __position, value_type&& __v);
2075
2076 // Try to emplace at the end, otherwise forward to _M_insert_aux.
2077 template<typename... _Args>
2078 _GLIBCXX20_CONSTEXPR
2079 iterator
2080 _M_emplace_aux(const_iterator __position, _Args&&... __args);
2081
2082 // Emplacing an rvalue of the correct type can use _M_insert_rval.
2083 _GLIBCXX20_CONSTEXPR
2084 iterator
2085 _M_emplace_aux(const_iterator __position, value_type&& __v)
2086 { return _M_insert_rval(__position, std::move(__v)); }
2087#endif
2088
2089 // Called by _M_fill_insert, _M_insert_aux etc.
2090 _GLIBCXX20_CONSTEXPR
2091 size_type
2092 _M_check_len(size_type __n, const char* __s) const
2093 {
2094 if (max_size() - size() < __n)
2095 __throw_length_error(__N(__s));
2096
2097 const size_type __len = size() + (std::max)(size(), __n);
2098 return (__len < size() || __len > max_size()) ? max_size() : __len;
2099 }
2100
2101 // Called by constructors to check initial size.
2102 static _GLIBCXX20_CONSTEXPR size_type
2103 _S_check_init_len(size_type __n, const allocator_type& __a)
2104 {
2105 if (__n > _S_max_size(_Tp_alloc_type(__a)))
2106 __throw_length_error(
2107 __N("cannot create std::vector larger than max_size()"));
2108 return __n;
2109 }
2110
2111 static _GLIBCXX20_CONSTEXPR size_type
2112 _S_max_size(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
2113 {
2114 // std::distance(begin(), end()) cannot be greater than PTRDIFF_MAX,
2115 // and realistically we can't store more than PTRDIFF_MAX/sizeof(T)
2116 // (even if std::allocator_traits::max_size says we can).
2117 const size_t __diffmax
2118 = __gnu_cxx::__numeric_traits<ptrdiff_t>::__max / sizeof(_Tp);
2119 const size_t __allocmax = _Alloc_traits::max_size(__a);
2120 return (std::min)(__diffmax, __allocmax);
2121 }
2122
2123 // Internal erase functions follow.
2124
2125 // Called by erase(q1,q2), clear(), resize(), _M_fill_assign,
2126 // _M_assign_aux.
2127 _GLIBCXX20_CONSTEXPR
2128 void
2129 _M_erase_at_end(pointer __pos) _GLIBCXX_NOEXCEPT
2130 {
2131 if (size_type __n = this->_M_impl._M_finish - __pos)
2132 {
2133 std::_Destroy(__pos, this->_M_impl._M_finish,
2134 _M_get_Tp_allocator());
2135 this->_M_impl._M_finish = __pos;
2136 _GLIBCXX_ASAN_ANNOTATE_SHRINK(__n);
2137 }
2138 }
2139
2140 _GLIBCXX20_CONSTEXPR
2141 iterator
2142 _M_erase(iterator __position);
2143
2144 _GLIBCXX20_CONSTEXPR
2145 iterator
2146 _M_erase(iterator __first, iterator __last);
2147
2148#if __cplusplus >= 201103L
2149 private:
2150 // Constant-time move assignment when source object's memory can be
2151 // moved, either because the source's allocator will move too
2152 // or because the allocators are equal.
2153 _GLIBCXX20_CONSTEXPR
2154 void
2155 _M_move_assign(vector&& __x, true_type) noexcept
2156 {
2157 vector __tmp(get_allocator());
2158 this->_M_impl._M_swap_data(__x._M_impl);
2159 __tmp._M_impl._M_swap_data(__x._M_impl);
2160 std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
2161 }
2162
2163 // Do move assignment when it might not be possible to move source
2164 // object's memory, resulting in a linear-time operation.
2165 _GLIBCXX20_CONSTEXPR
2166 void
2167 _M_move_assign(vector&& __x, false_type)
2168 {
2169 if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
2170 _M_move_assign(std::move(__x), true_type());
2171 else
2172 {
2173 // The rvalue's allocator cannot be moved and is not equal,
2174 // so we need to individually move each element.
2175 this->_M_assign_aux(std::make_move_iterator(__x.begin()),
2176 std::make_move_iterator(__x.end()),
2178 __x.clear();
2179 }
2180 }
2181#endif
2182
2183 template<typename _Up>
2184 _GLIBCXX20_CONSTEXPR
2185 _Up*
2186 _M_data_ptr(_Up* __ptr) const _GLIBCXX_NOEXCEPT
2187 { return __ptr; }
2188
2189#if __cplusplus >= 201103L
2190 template<typename _Ptr>
2191 _GLIBCXX20_CONSTEXPR
2192 typename std::pointer_traits<_Ptr>::element_type*
2193 _M_data_ptr(_Ptr __ptr) const
2194 { return empty() ? nullptr : std::__to_address(__ptr); }
2195#else
2196 template<typename _Ptr>
2197 value_type*
2198 _M_data_ptr(_Ptr __ptr) const
2199 { return empty() ? (value_type*)0 : __ptr.operator->(); }
2200#endif
2201 };
2202
2203#if __cpp_deduction_guides >= 201606
2204 template<typename _InputIterator, typename _ValT
2205 = typename iterator_traits<_InputIterator>::value_type,
2206 typename _Allocator = allocator<_ValT>,
2207 typename = _RequireInputIter<_InputIterator>,
2208 typename = _RequireAllocator<_Allocator>>
2209 vector(_InputIterator, _InputIterator, _Allocator = _Allocator())
2210 -> vector<_ValT, _Allocator>;
2211
2212#if __glibcxx_ranges_to_container // C++ >= 23
2213 template<ranges::input_range _Rg,
2214 typename _Alloc = allocator<ranges::range_value_t<_Rg>>>
2215 vector(from_range_t, _Rg&&, _Alloc = _Alloc())
2216 -> vector<ranges::range_value_t<_Rg>, _Alloc>;
2217#endif
2218#endif
2219
2220 /**
2221 * @brief Vector equality comparison.
2222 * @param __x A %vector.
2223 * @param __y A %vector of the same type as @a __x.
2224 * @return True iff the size and elements of the vectors are equal.
2225 *
2226 * This is an equivalence relation. It is linear in the size of the
2227 * vectors. Vectors are considered equivalent if their sizes are equal,
2228 * and if corresponding elements compare equal.
2229 */
2230 template<typename _Tp, typename _Alloc>
2231 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2232 inline bool
2233 operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
2234 { return (__x.size() == __y.size()
2235 && std::equal(__x.begin(), __x.end(), __y.begin())); }
2236
2237#if __cpp_lib_three_way_comparison // >= C++20
2238 /**
2239 * @brief Vector ordering relation.
2240 * @param __x A `vector`.
2241 * @param __y A `vector` of the same type as `__x`.
2242 * @return A value indicating whether `__x` is less than, equal to,
2243 * greater than, or incomparable with `__y`.
2244 *
2245 * See `std::lexicographical_compare_three_way()` for how the determination
2246 * is made. This operator is used to synthesize relational operators like
2247 * `<` and `>=` etc.
2248 */
2249 template<typename _Tp, typename _Alloc>
2250 [[nodiscard]]
2251 constexpr __detail::__synth3way_t<_Tp>
2252 operator<=>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
2253 {
2255 __y.begin(), __y.end(),
2256 __detail::__synth3way);
2257 }
2258#else
2259 /**
2260 * @brief Vector ordering relation.
2261 * @param __x A %vector.
2262 * @param __y A %vector of the same type as @a __x.
2263 * @return True iff @a __x is lexicographically less than @a __y.
2264 *
2265 * This is a total ordering relation. It is linear in the size of the
2266 * vectors. The elements must be comparable with @c <.
2267 *
2268 * See std::lexicographical_compare() for how the determination is made.
2269 */
2270 template<typename _Tp, typename _Alloc>
2271 _GLIBCXX_NODISCARD inline bool
2272 operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
2273 { return std::lexicographical_compare(__x.begin(), __x.end(),
2274 __y.begin(), __y.end()); }
2275
2276 /// Based on operator==
2277 template<typename _Tp, typename _Alloc>
2278 _GLIBCXX_NODISCARD inline bool
2279 operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
2280 { return !(__x == __y); }
2281
2282 /// Based on operator<
2283 template<typename _Tp, typename _Alloc>
2284 _GLIBCXX_NODISCARD inline bool
2285 operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
2286 { return __y < __x; }
2287
2288 /// Based on operator<
2289 template<typename _Tp, typename _Alloc>
2290 _GLIBCXX_NODISCARD inline bool
2291 operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
2292 { return !(__y < __x); }
2293
2294 /// Based on operator<
2295 template<typename _Tp, typename _Alloc>
2296 _GLIBCXX_NODISCARD inline bool
2297 operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
2298 { return !(__x < __y); }
2299#endif // three-way comparison
2300
2301 /// See std::vector::swap().
2302 template<typename _Tp, typename _Alloc>
2303 _GLIBCXX20_CONSTEXPR
2304 inline void
2306 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
2307 { __x.swap(__y); }
2308
2309_GLIBCXX_END_NAMESPACE_CONTAINER
2310
2311#if __cplusplus >= 201703L
2312 namespace __detail::__variant
2313 {
2314 template<typename> struct _Never_valueless_alt; // see <variant>
2315
2316 // Provide the strong exception-safety guarantee when emplacing a
2317 // vector into a variant, but only if move assignment cannot throw.
2318 template<typename _Tp, typename _Alloc>
2319 struct _Never_valueless_alt<_GLIBCXX_STD_C::vector<_Tp, _Alloc>>
2320 : std::is_nothrow_move_assignable<_GLIBCXX_STD_C::vector<_Tp, _Alloc>>
2321 { };
2322 } // namespace __detail::__variant
2323#endif // C++17
2324
2325_GLIBCXX_END_NAMESPACE_VERSION
2326} // namespace std
2327
2328#endif /* _STL_VECTOR_H */
constexpr bool operator<=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:859
constexpr bool operator>=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:873
constexpr bool operator>(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:866
__bool_constant< true > true_type
The type used as a compile-time boolean with true value.
Definition type_traits:116
__bool_constant< false > false_type
The type used as a compile-time boolean with false value.
Definition type_traits:119
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:127
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition move.h:51
constexpr auto lexicographical_compare_three_way(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _Comp __comp) -> decltype(__comp(*__first1, *__first2))
Performs dictionary comparison on ranges.
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
ISO C++ entities toplevel namespace is std.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
constexpr void _Destroy(_ForwardIterator __first, _ForwardIterator __last)
initializer_list
is_nothrow_default_constructible
Definition type_traits:1237
is_nothrow_move_assignable
Definition type_traits:1323
typename __detected_or_t< is_empty< _Alloc >, __equal, _Alloc >::type is_always_equal
Whether all instances of the allocator type compare equal.
The standard allocator, as per C++03 [20.4.1].
Definition allocator.h:132
Marking input iterators.
Forward iterators support a superset of input iterator operations.
Random-access iterators support a superset of bidirectional iterator operations.
Common iterator class.
See bits/stl_deque.h's _Deque_base for an explanation.
Definition stl_vector.h:89
A standard container which offers fixed time access to individual elements in any order.
Definition stl_vector.h:456
constexpr iterator insert(const_iterator __position, const value_type &__x)
Inserts given value into vector before specified iterator.
Definition vector.tcc:135
constexpr void push_back(const value_type &__x)
Add data to the end of the vector.
constexpr void resize(size_type __new_size, const value_type &__x)
Resizes the vector to the specified number of elements.
constexpr vector & operator=(initializer_list< value_type > __l)
Vector list assignment operator.
Definition stl_vector.h:856
constexpr reverse_iterator rbegin() noexcept
constexpr iterator end() noexcept
constexpr vector(const vector &__x)
Vector copy constructor.
Definition stl_vector.h:628
vector()=default
Creates a vector with no elements.
constexpr iterator emplace(const_iterator __position, _Args &&... __args)
Inserts an object in vector before specified iterator.
constexpr iterator insert(const_iterator __position, value_type &&__x)
Inserts given rvalue into vector before specified iterator.
constexpr const_reverse_iterator rend() const noexcept
constexpr iterator begin() noexcept
Definition stl_vector.h:997
constexpr size_type capacity() const noexcept
constexpr iterator insert(const_iterator __position, initializer_list< value_type > __l)
Inserts an initializer_list into the vector.
constexpr ~vector() noexcept
Definition stl_vector.h:801
constexpr const_iterator begin() const noexcept
constexpr void assign(_InputIterator __first, _InputIterator __last)
Assigns a range to a vector.
Definition stl_vector.h:896
constexpr void assign(size_type __n, const value_type &__val)
Assigns a given value to a vector.
Definition stl_vector.h:876
constexpr iterator erase(const_iterator __first, const_iterator __last)
Remove a range of elements.
constexpr void swap(vector &__x) noexcept
Swaps data with another vector.
constexpr vector(vector &&__rv, const __type_identity_t< allocator_type > &__m) noexcept(noexcept(vector(std::declval< vector && >(), std::declval< const allocator_type & >(), std::declval< typename _Alloc_traits::is_always_equal >())))
Move constructor with alternative allocator.
Definition stl_vector.h:686
constexpr _Tp * data() noexcept
constexpr vector(size_type __n, const allocator_type &__a=allocator_type())
Creates a vector with default constructed elements.
Definition stl_vector.h:583
constexpr const_reference front() const noexcept
constexpr vector & operator=(const vector &__x)
Vector assignment operator.
constexpr void pop_back() noexcept
Removes last element.
constexpr vector & operator=(vector &&__x) noexcept(_Alloc_traits::_S_nothrow_move())
Vector move assignment operator.
Definition stl_vector.h:834
constexpr const_reference back() const noexcept
constexpr void reserve(size_type __n)
Attempt to preallocate enough memory for specified number of elements.
Definition vector.tcc:68
constexpr reference at(size_type __n)
Provides access to the data contained in the vector.
constexpr void resize(size_type __new_size)
Resizes the vector to the specified number of elements.
constexpr void _M_range_check(size_type __n) const
Safety check used only from at().
constexpr reference front() noexcept
constexpr iterator insert(const_iterator __position, size_type __n, const value_type &__x)
Inserts a number of copies of given data into the vector.
constexpr const_reference operator[](size_type __n) const noexcept
Subscript access to the data contained in the vector.
constexpr vector(const allocator_type &__a) noexcept
Creates a vector with no elements.
Definition stl_vector.h:569
constexpr iterator erase(const_iterator __position)
Remove element at given position.
constexpr pointer _M_allocate_and_copy(size_type __n, _ForwardIterator __first, _ForwardIterator __last)
constexpr bool empty() const noexcept
constexpr reverse_iterator rend() noexcept
constexpr const_reverse_iterator rbegin() const noexcept
constexpr const_reverse_iterator crbegin() const noexcept
constexpr const_reference at(size_type __n) const
Provides access to the data contained in the vector.
constexpr const_iterator cbegin() const noexcept
constexpr vector(_InputIterator __first, _InputIterator __last, const allocator_type &__a=allocator_type())
Builds a vector from a range.
Definition stl_vector.h:734
constexpr vector(initializer_list< value_type > __l, const allocator_type &__a=allocator_type())
Builds a vector from an initializer list.
Definition stl_vector.h:705
constexpr const_iterator end() const noexcept
vector(vector &&) noexcept=default
Vector move constructor.
constexpr iterator insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
Inserts a range into the vector.
constexpr void clear() noexcept
constexpr void assign(initializer_list< value_type > __l)
Assigns an initializer list to a vector.
Definition stl_vector.h:923
constexpr allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
Definition stl_vector.h:314
constexpr size_type size() const noexcept
constexpr vector(size_type __n, const value_type &__value, const allocator_type &__a=allocator_type())
Creates a vector with copies of an exemplar element.
Definition stl_vector.h:596
constexpr reference back() noexcept
constexpr const_reverse_iterator crend() const noexcept
constexpr const_iterator cend() const noexcept
constexpr reference operator[](size_type __n) noexcept
Subscript access to the data contained in the vector.
constexpr void shrink_to_fit()
constexpr size_type max_size() const noexcept
Uniform interface to C++98 and C++11 allocators.
static constexpr size_type max_size(const _Tp_alloc_type &__a) noexcept
The maximum supported allocation size.