libstdc++
stl_vector.h
Go to the documentation of this file.
1// Vector implementation -*- C++ -*-
2
3// Copyright (C) 2001-2025 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>(),
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(
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 {
1118 ptrdiff_t __dif = this->_M_impl._M_finish - this->_M_impl._M_start;
1119 if (__dif < 0)
1120 __builtin_unreachable ();
1121 return size_type(__dif);
1122 }
1123
1124 /** Returns the size() of the largest possible %vector. */
1125 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1126 size_type
1127 max_size() const _GLIBCXX_NOEXCEPT
1128 { return _S_max_size(_M_get_Tp_allocator()); }
1129
1130#if __cplusplus >= 201103L
1131 /**
1132 * @brief Resizes the %vector to the specified number of elements.
1133 * @param __new_size Number of elements the %vector should contain.
1134 *
1135 * This function will %resize the %vector to the specified
1136 * number of elements. If the number is smaller than the
1137 * %vector's current size the %vector is truncated, otherwise
1138 * default constructed elements are appended.
1139 */
1140 _GLIBCXX20_CONSTEXPR
1141 void
1142 resize(size_type __new_size)
1143 {
1144 if (__new_size > size())
1145 _M_default_append(__new_size - size());
1146 else if (__new_size < size())
1147 _M_erase_at_end(this->_M_impl._M_start + __new_size);
1148 }
1149
1150 /**
1151 * @brief Resizes the %vector to the specified number of elements.
1152 * @param __new_size Number of elements the %vector should contain.
1153 * @param __x Data with which new elements should be populated.
1154 *
1155 * This function will %resize the %vector to the specified
1156 * number of elements. If the number is smaller than the
1157 * %vector's current size the %vector is truncated, otherwise
1158 * the %vector is extended and new elements are populated with
1159 * given data.
1160 */
1161 _GLIBCXX20_CONSTEXPR
1162 void
1163 resize(size_type __new_size, const value_type& __x)
1164 {
1165 if (__new_size > size())
1166 _M_fill_insert(end(), __new_size - size(), __x);
1167 else if (__new_size < size())
1168 _M_erase_at_end(this->_M_impl._M_start + __new_size);
1169 }
1170#else
1171 /**
1172 * @brief Resizes the %vector to the specified number of elements.
1173 * @param __new_size Number of elements the %vector should contain.
1174 * @param __x Data with which new elements should be populated.
1175 *
1176 * This function will %resize the %vector to the specified
1177 * number of elements. If the number is smaller than the
1178 * %vector's current size the %vector is truncated, otherwise
1179 * the %vector is extended and new elements are populated with
1180 * given data.
1181 */
1182 _GLIBCXX20_CONSTEXPR
1183 void
1184 resize(size_type __new_size, value_type __x = value_type())
1185 {
1186 if (__new_size > size())
1187 _M_fill_insert(end(), __new_size - size(), __x);
1188 else if (__new_size < size())
1189 _M_erase_at_end(this->_M_impl._M_start + __new_size);
1190 }
1191#endif
1192
1193#if __cplusplus >= 201103L
1194 /** A non-binding request to reduce capacity() to size(). */
1195 _GLIBCXX20_CONSTEXPR
1196 void
1198 { _M_shrink_to_fit(); }
1199#endif
1200
1201 /**
1202 * Returns the total number of elements that the %vector can
1203 * hold before needing to allocate more memory.
1204 */
1205 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1206 size_type
1207 capacity() const _GLIBCXX_NOEXCEPT
1208 {
1209 ptrdiff_t __dif = this->_M_impl._M_end_of_storage
1210 - this->_M_impl._M_start;
1211 if (__dif < 0)
1212 __builtin_unreachable ();
1213 return size_type(__dif);
1214 }
1215
1216 /**
1217 * Returns true if the %vector is empty. (Thus begin() would
1218 * equal end().)
1219 */
1220 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1221 bool
1222 empty() const _GLIBCXX_NOEXCEPT
1223 { return begin() == end(); }
1224
1225 /**
1226 * @brief Attempt to preallocate enough memory for specified number of
1227 * elements.
1228 * @param __n Number of elements required.
1229 * @throw std::length_error If @a n exceeds @c max_size().
1230 *
1231 * This function attempts to reserve enough memory for the
1232 * %vector to hold the specified number of elements. If the
1233 * number requested is more than max_size(), length_error is
1234 * thrown.
1235 *
1236 * The advantage of this function is that if optimal code is a
1237 * necessity and the user can determine the number of elements
1238 * that will be required, the user can reserve the memory in
1239 * %advance, and thus prevent a possible reallocation of memory
1240 * and copying of %vector data.
1241 */
1242 _GLIBCXX20_CONSTEXPR
1243 void
1244 reserve(size_type __n);
1245
1246 // element access
1247 /**
1248 * @brief Subscript access to the data contained in the %vector.
1249 * @param __n The index of the element for which data should be
1250 * accessed.
1251 * @return Read/write reference to data.
1252 *
1253 * This operator allows for easy, array-style, data access.
1254 * Note that data access with this operator is unchecked and
1255 * out_of_range lookups are not defined. (For checked lookups
1256 * see at().)
1257 */
1258 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1259 reference
1260 operator[](size_type __n) _GLIBCXX_NOEXCEPT
1261 {
1262 __glibcxx_requires_subscript(__n);
1263 return *(this->_M_impl._M_start + __n);
1264 }
1265
1266 /**
1267 * @brief Subscript access to the data contained in the %vector.
1268 * @param __n The index of the element for which data should be
1269 * accessed.
1270 * @return Read-only (constant) reference to data.
1271 *
1272 * This operator allows for easy, array-style, data access.
1273 * Note that data access with this operator is unchecked and
1274 * out_of_range lookups are not defined. (For checked lookups
1275 * see at().)
1276 */
1277 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1278 const_reference
1279 operator[](size_type __n) const _GLIBCXX_NOEXCEPT
1280 {
1281 __glibcxx_requires_subscript(__n);
1282 return *(this->_M_impl._M_start + __n);
1283 }
1284
1285 protected:
1286 /// Safety check used only from at().
1287 _GLIBCXX20_CONSTEXPR
1288 void
1289 _M_range_check(size_type __n) const
1290 {
1291 if (__n >= this->size())
1292 __throw_out_of_range_fmt(__N("vector::_M_range_check: __n "
1293 "(which is %zu) >= this->size() "
1294 "(which is %zu)"),
1295 __n, this->size());
1296 }
1297
1298 public:
1299 /**
1300 * @brief Provides access to the data contained in the %vector.
1301 * @param __n The index of the element for which data should be
1302 * accessed.
1303 * @return Read/write reference to data.
1304 * @throw std::out_of_range If @a __n is an invalid index.
1305 *
1306 * This function provides for safer data access. The parameter
1307 * is first checked that it is in the range of the vector. The
1308 * function throws out_of_range if the check fails.
1309 */
1310 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1311 reference
1312 at(size_type __n)
1313 {
1314 _M_range_check(__n);
1315 return (*this)[__n];
1316 }
1317
1318 /**
1319 * @brief Provides access to the data contained in the %vector.
1320 * @param __n The index of the element for which data should be
1321 * accessed.
1322 * @return Read-only (constant) reference to data.
1323 * @throw std::out_of_range If @a __n is an invalid index.
1324 *
1325 * This function provides for safer data access. The parameter
1326 * is first checked that it is in the range of the vector. The
1327 * function throws out_of_range if the check fails.
1328 */
1329 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1330 const_reference
1331 at(size_type __n) const
1332 {
1333 _M_range_check(__n);
1334 return (*this)[__n];
1335 }
1336
1337 /**
1338 * Returns a read/write reference to the data at the first
1339 * element of the %vector.
1340 */
1341 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1342 reference
1343 front() _GLIBCXX_NOEXCEPT
1344 {
1345 __glibcxx_requires_nonempty();
1346 return *begin();
1347 }
1348
1349 /**
1350 * Returns a read-only (constant) reference to the data at the first
1351 * element of the %vector.
1352 */
1353 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1354 const_reference
1355 front() const _GLIBCXX_NOEXCEPT
1356 {
1357 __glibcxx_requires_nonempty();
1358 return *begin();
1359 }
1360
1361 /**
1362 * Returns a read/write reference to the data at the last
1363 * element of the %vector.
1364 */
1365 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1366 reference
1367 back() _GLIBCXX_NOEXCEPT
1368 {
1369 __glibcxx_requires_nonempty();
1370 return *(end() - 1);
1371 }
1372
1373 /**
1374 * Returns a read-only (constant) reference to the data at the
1375 * last element of the %vector.
1376 */
1377 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1378 const_reference
1379 back() const _GLIBCXX_NOEXCEPT
1380 {
1381 __glibcxx_requires_nonempty();
1382 return *(end() - 1);
1383 }
1384
1385 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1386 // DR 464. Suggestion for new member functions in standard containers.
1387 // data access
1388 /**
1389 * Returns a pointer such that [data(), data() + size()) is a valid
1390 * range. For a non-empty %vector, data() == &front().
1391 */
1392 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1393 _Tp*
1394 data() _GLIBCXX_NOEXCEPT
1395 { return _M_data_ptr(this->_M_impl._M_start); }
1396
1397 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1398 const _Tp*
1399 data() const _GLIBCXX_NOEXCEPT
1400 { return _M_data_ptr(this->_M_impl._M_start); }
1401
1402 // [23.2.4.3] modifiers
1403 /**
1404 * @brief Add data to the end of the %vector.
1405 * @param __x Data to be added.
1406 *
1407 * This is a typical stack operation. The function creates an
1408 * element at the end of the %vector and assigns the given data
1409 * to it. Due to the nature of a %vector this operation can be
1410 * done in constant time if the %vector has preallocated space
1411 * available.
1412 */
1413 _GLIBCXX20_CONSTEXPR
1414 void
1415 push_back(const value_type& __x)
1416 {
1417 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
1418 {
1419 _GLIBCXX_ASAN_ANNOTATE_GROW(1);
1420 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
1421 __x);
1422 ++this->_M_impl._M_finish;
1423 _GLIBCXX_ASAN_ANNOTATE_GREW(1);
1424 }
1425 else
1426 _M_realloc_append(__x);
1427 }
1428
1429#if __cplusplus >= 201103L
1430 _GLIBCXX20_CONSTEXPR
1431 void
1432 push_back(value_type&& __x)
1433 { emplace_back(std::move(__x)); }
1434
1435 template<typename... _Args>
1436#if __cplusplus > 201402L
1437 _GLIBCXX20_CONSTEXPR
1438 reference
1439#else
1440 void
1441#endif
1442 emplace_back(_Args&&... __args);
1443#endif
1444
1445 /**
1446 * @brief Removes last element.
1447 *
1448 * This is a typical stack operation. It shrinks the %vector by one.
1449 *
1450 * Note that no data is returned, and if the last element's
1451 * data is needed, it should be retrieved before pop_back() is
1452 * called.
1453 */
1454 _GLIBCXX20_CONSTEXPR
1455 void
1456 pop_back() _GLIBCXX_NOEXCEPT
1457 {
1458 __glibcxx_requires_nonempty();
1459 --this->_M_impl._M_finish;
1460 _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
1461 _GLIBCXX_ASAN_ANNOTATE_SHRINK(1);
1462 }
1463
1464#if __cplusplus >= 201103L
1465 /**
1466 * @brief Inserts an object in %vector before specified iterator.
1467 * @param __position A const_iterator into the %vector.
1468 * @param __args Arguments.
1469 * @return An iterator that points to the inserted data.
1470 *
1471 * This function will insert an object of type T constructed
1472 * with T(std::forward<Args>(args)...) before the specified location.
1473 * Note that this kind of operation could be expensive for a %vector
1474 * and if it is frequently used the user should consider using
1475 * std::list.
1476 */
1477 template<typename... _Args>
1478 _GLIBCXX20_CONSTEXPR
1479 iterator
1480 emplace(const_iterator __position, _Args&&... __args)
1481 { return _M_emplace_aux(__position, std::forward<_Args>(__args)...); }
1482
1483 /**
1484 * @brief Inserts given value into %vector before specified iterator.
1485 * @param __position A const_iterator into the %vector.
1486 * @param __x Data to be inserted.
1487 * @return An iterator that points to the inserted data.
1488 *
1489 * This function will insert a copy of the given value before
1490 * the specified location. Note that this kind of operation
1491 * could be expensive for a %vector and if it is frequently
1492 * used the user should consider using std::list.
1493 */
1494 _GLIBCXX20_CONSTEXPR
1495 iterator
1496 insert(const_iterator __position, const value_type& __x);
1497#else
1498 /**
1499 * @brief Inserts given value into %vector before specified iterator.
1500 * @param __position An iterator into the %vector.
1501 * @param __x Data to be inserted.
1502 * @return An iterator that points to the inserted data.
1503 *
1504 * This function will insert a copy of the given value before
1505 * the specified location. Note that this kind of operation
1506 * could be expensive for a %vector and if it is frequently
1507 * used the user should consider using std::list.
1508 */
1509 iterator
1510 insert(iterator __position, const value_type& __x);
1511#endif
1512
1513#if __cplusplus >= 201103L
1514 /**
1515 * @brief Inserts given rvalue into %vector before specified iterator.
1516 * @param __position A const_iterator into the %vector.
1517 * @param __x Data to be inserted.
1518 * @return An iterator that points to the inserted data.
1519 *
1520 * This function will insert a copy of the given rvalue before
1521 * the specified location. Note that this kind of operation
1522 * could be expensive for a %vector and if it is frequently
1523 * used the user should consider using std::list.
1524 */
1525 _GLIBCXX20_CONSTEXPR
1526 iterator
1527 insert(const_iterator __position, value_type&& __x)
1528 { return _M_insert_rval(__position, std::move(__x)); }
1529
1530 /**
1531 * @brief Inserts an initializer_list into the %vector.
1532 * @param __position An iterator into the %vector.
1533 * @param __l An initializer_list.
1534 *
1535 * This function will insert copies of the data in the
1536 * initializer_list @a l into the %vector before the location
1537 * specified by @a position.
1538 *
1539 * Note that this kind of operation could be expensive for a
1540 * %vector and if it is frequently used the user should
1541 * consider using std::list.
1542 */
1543 _GLIBCXX20_CONSTEXPR
1544 iterator
1545 insert(const_iterator __position, initializer_list<value_type> __l)
1546 {
1547 auto __offset = __position - cbegin();
1548 _M_range_insert(begin() + __offset, __l.begin(), __l.end(),
1550 return begin() + __offset;
1551 }
1552#endif
1553
1554#if __cplusplus >= 201103L
1555 /**
1556 * @brief Inserts a number of copies of given data into the %vector.
1557 * @param __position A const_iterator into the %vector.
1558 * @param __n Number of elements to be inserted.
1559 * @param __x Data to be inserted.
1560 * @return An iterator that points to the inserted data.
1561 *
1562 * This function will insert a specified number of copies of
1563 * the given data before the location specified by @a position.
1564 *
1565 * Note that this kind of operation could be expensive for a
1566 * %vector and if it is frequently used the user should
1567 * consider using std::list.
1568 */
1569 _GLIBCXX20_CONSTEXPR
1570 iterator
1571 insert(const_iterator __position, size_type __n, const value_type& __x)
1572 {
1573 difference_type __offset = __position - cbegin();
1574 _M_fill_insert(begin() + __offset, __n, __x);
1575 return begin() + __offset;
1576 }
1577#else
1578 /**
1579 * @brief Inserts a number of copies of given data into the %vector.
1580 * @param __position An iterator into the %vector.
1581 * @param __n Number of elements to be inserted.
1582 * @param __x Data to be inserted.
1583 *
1584 * This function will insert a specified number of copies of
1585 * the given data before the location specified by @a position.
1586 *
1587 * Note that this kind of operation could be expensive for a
1588 * %vector and if it is frequently used the user should
1589 * consider using std::list.
1590 */
1591 void
1592 insert(iterator __position, size_type __n, const value_type& __x)
1593 { _M_fill_insert(__position, __n, __x); }
1594#endif
1595
1596#if __cplusplus >= 201103L
1597 /**
1598 * @brief Inserts a range into the %vector.
1599 * @param __position A const_iterator into the %vector.
1600 * @param __first An input iterator.
1601 * @param __last An input iterator.
1602 * @return An iterator that points to the inserted data.
1603 *
1604 * This function will insert copies of the data in the range
1605 * [__first,__last) into the %vector before the location specified
1606 * by @a pos.
1607 *
1608 * Note that this kind of operation could be expensive for a
1609 * %vector and if it is frequently used the user should
1610 * consider using std::list.
1611 */
1612 template<typename _InputIterator,
1613 typename = std::_RequireInputIter<_InputIterator>>
1614 _GLIBCXX20_CONSTEXPR
1615 iterator
1616 insert(const_iterator __position, _InputIterator __first,
1617 _InputIterator __last)
1618 {
1619 difference_type __offset = __position - cbegin();
1620 _M_range_insert(begin() + __offset, __first, __last,
1621 std::__iterator_category(__first));
1622 return begin() + __offset;
1623 }
1624#else
1625 /**
1626 * @brief Inserts a range into the %vector.
1627 * @param __position An iterator into the %vector.
1628 * @param __first An input iterator.
1629 * @param __last An input iterator.
1630 *
1631 * This function will insert copies of the data in the range
1632 * [__first,__last) into the %vector before the location specified
1633 * by @a pos.
1634 *
1635 * Note that this kind of operation could be expensive for a
1636 * %vector and if it is frequently used the user should
1637 * consider using std::list.
1638 */
1639 template<typename _InputIterator>
1640 void
1641 insert(iterator __position, _InputIterator __first,
1642 _InputIterator __last)
1643 {
1644 // Check whether it's an integral type. If so, it's not an iterator.
1645 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1646 _M_insert_dispatch(__position, __first, __last, _Integral());
1647 }
1648#endif
1649
1650#if __glibcxx_ranges_to_container // C++ >= 23
1651 /**
1652 * @brief Insert a range into the vector.
1653 * @since C++23
1654 */
1655 template<__detail::__container_compatible_range<_Tp> _Rg>
1656 constexpr iterator
1657 insert_range(const_iterator __pos, _Rg&& __rg);
1658
1659 /**
1660 * @brief Append a range at the end of the vector.
1661 * @since C++23
1662 */
1663 template<__detail::__container_compatible_range<_Tp> _Rg>
1664 constexpr void
1665 append_range(_Rg&& __rg)
1666 {
1667 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
1668 {
1669 const auto __n = size_type(ranges::distance(__rg));
1670 reserve(size() + __n);
1671 _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
1672 _Base::_M_append_range(__rg);
1673 _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
1674 }
1675 else
1676 {
1677 auto __first = ranges::begin(__rg);
1678 const auto __last = ranges::end(__rg);
1679 for (; __first != __last; ++__first)
1680 emplace_back(*__first);
1681 }
1682 }
1683#endif // ranges_to_container
1684
1685 /**
1686 * @brief Remove element at given position.
1687 * @param __position Iterator pointing to element to be erased.
1688 * @return An iterator pointing to the next element (or end()).
1689 *
1690 * This function will erase the element at the given position and thus
1691 * shorten the %vector by one.
1692 *
1693 * Note This operation could be expensive and if it is
1694 * frequently used the user should consider using std::list.
1695 * The user is also cautioned that this function only erases
1696 * the element, and that if the element is itself a pointer,
1697 * the pointed-to memory is not touched in any way. Managing
1698 * the pointer is the user's responsibility.
1699 */
1700 _GLIBCXX20_CONSTEXPR
1701 iterator
1702#if __cplusplus >= 201103L
1703 erase(const_iterator __position)
1704 { return _M_erase(begin() + (__position - cbegin())); }
1705#else
1706 erase(iterator __position)
1707 { return _M_erase(__position); }
1708#endif
1709
1710 /**
1711 * @brief Remove a range of elements.
1712 * @param __first Iterator pointing to the first element to be erased.
1713 * @param __last Iterator pointing to one past the last element to be
1714 * erased.
1715 * @return An iterator pointing to the element pointed to by @a __last
1716 * prior to erasing (or end()).
1717 *
1718 * This function will erase the elements in the range
1719 * [__first,__last) and shorten the %vector accordingly.
1720 *
1721 * Note This operation could be expensive and if it is
1722 * frequently used the user should consider using std::list.
1723 * The user is also cautioned that this function only erases
1724 * the elements, and that if the elements themselves are
1725 * pointers, the pointed-to memory is not touched in any way.
1726 * Managing the pointer is the user's responsibility.
1727 */
1728 _GLIBCXX20_CONSTEXPR
1729 iterator
1730#if __cplusplus >= 201103L
1731 erase(const_iterator __first, const_iterator __last)
1732 {
1733 const auto __beg = begin();
1734 const auto __cbeg = cbegin();
1735 return _M_erase(__beg + (__first - __cbeg), __beg + (__last - __cbeg));
1736 }
1737#else
1738 erase(iterator __first, iterator __last)
1739 { return _M_erase(__first, __last); }
1740#endif
1741
1742 /**
1743 * @brief Swaps data with another %vector.
1744 * @param __x A %vector of the same element and allocator types.
1745 *
1746 * This exchanges the elements between two vectors in constant time.
1747 * (Three pointers, so it should be quite fast.)
1748 * Note that the global std::swap() function is specialized such that
1749 * std::swap(v1,v2) will feed to this function.
1750 *
1751 * Whether the allocators are swapped depends on the allocator traits.
1752 */
1753 _GLIBCXX20_CONSTEXPR
1754 void
1755 swap(vector& __x) _GLIBCXX_NOEXCEPT
1756 {
1757#if __cplusplus >= 201103L
1758 __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value
1759 || _M_get_Tp_allocator() == __x._M_get_Tp_allocator());
1760#endif
1761 this->_M_impl._M_swap_data(__x._M_impl);
1762 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1763 __x._M_get_Tp_allocator());
1764 }
1765
1766 /**
1767 * Erases all the elements. Note that this function only erases the
1768 * elements, and that if the elements themselves are pointers, the
1769 * pointed-to memory is not touched in any way. Managing the pointer is
1770 * the user's responsibility.
1771 */
1772 _GLIBCXX20_CONSTEXPR
1773 void
1774 clear() _GLIBCXX_NOEXCEPT
1775 { _M_erase_at_end(this->_M_impl._M_start); }
1776
1777 private:
1778 // RAII guard for allocated storage.
1779 struct _Guard_alloc
1780 {
1781 pointer _M_storage; // Storage to deallocate
1782 size_type _M_len;
1783 _Base& _M_vect;
1784
1785 _GLIBCXX20_CONSTEXPR
1786 _Guard_alloc(pointer __s, size_type __l, _Base& __vect)
1787 : _M_storage(__s), _M_len(__l), _M_vect(__vect)
1788 { }
1789
1790 _GLIBCXX20_CONSTEXPR
1791 ~_Guard_alloc()
1792 {
1793 if (_M_storage)
1794 _M_vect._M_deallocate(_M_storage, _M_len);
1795 }
1796
1797 _GLIBCXX20_CONSTEXPR
1798 pointer
1799 _M_release()
1800 {
1801 pointer __res = _M_storage;
1802 _M_storage = pointer();
1803 return __res;
1804 }
1805
1806 private:
1807 _Guard_alloc(const _Guard_alloc&);
1808 };
1809
1810 protected:
1811 /**
1812 * Memory expansion handler. Uses the member allocation function to
1813 * obtain @a n bytes of memory, and then copies [first,last) into it.
1814 */
1815 template<typename _ForwardIterator>
1816 _GLIBCXX20_CONSTEXPR
1817 pointer
1819 _ForwardIterator __first, _ForwardIterator __last)
1820 {
1821 _Guard_alloc __guard(this->_M_allocate(__n), __n, *this);
1822 std::__uninitialized_copy_a
1823 (__first, __last, __guard._M_storage, _M_get_Tp_allocator());
1824 return __guard._M_release();
1825 }
1826
1827
1828 // Internal constructor functions follow.
1829
1830 // Called by the range constructor to implement [23.1.1]/9
1831
1832#if __cplusplus < 201103L
1833 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1834 // 438. Ambiguity in the "do the right thing" clause
1835 template<typename _Integer>
1836 void
1837 _M_initialize_dispatch(_Integer __int_n, _Integer __value, __true_type)
1838 {
1839 const size_type __n = static_cast<size_type>(__int_n);
1840 pointer __start =
1841 _M_allocate(_S_check_init_len(__n, _M_get_Tp_allocator()));
1842 this->_M_impl._M_start = __start;
1843 this->_M_impl._M_end_of_storage = __start + __n;
1844 _M_fill_initialize(__n, __value);
1845 }
1846
1847 // Called by the range constructor to implement [23.1.1]/9
1848 template<typename _InputIterator>
1849 void
1850 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1851 __false_type)
1852 {
1853 _M_range_initialize(__first, __last,
1854 std::__iterator_category(__first));
1855 }
1856#endif
1857
1858 // Called by the second initialize_dispatch above
1859 template<typename _InputIterator>
1860 _GLIBCXX20_CONSTEXPR
1861 void
1862 _M_range_initialize(_InputIterator __first, _InputIterator __last,
1864 {
1865 __try {
1866 for (; __first != __last; ++__first)
1867#if __cplusplus >= 201103L
1868 emplace_back(*__first);
1869#else
1870 push_back(*__first);
1871#endif
1872 } __catch(...) {
1873 clear();
1874 __throw_exception_again;
1875 }
1876 }
1877
1878 // Called by the second initialize_dispatch above
1879 template<typename _ForwardIterator>
1880 _GLIBCXX20_CONSTEXPR
1881 void
1882 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
1884 {
1885 const size_type __n = std::distance(__first, __last);
1886 pointer __start =
1887 this->_M_allocate(_S_check_init_len(__n, _M_get_Tp_allocator()));
1888 _Guard_alloc __guard(__start, __n, *this);
1889 this->_M_impl._M_finish = std::__uninitialized_copy_a
1890 (__first, __last, __start, _M_get_Tp_allocator());
1891 this->_M_impl._M_start = __start;
1892 (void) __guard._M_release();
1893 this->_M_impl._M_end_of_storage = __start + __n;
1894 }
1895
1896 // Called by the first initialize_dispatch above and by the
1897 // vector(n,value,a) constructor.
1898 _GLIBCXX20_CONSTEXPR
1899 void
1900 _M_fill_initialize(size_type __n, const value_type& __value)
1901 {
1902 this->_M_impl._M_finish =
1903 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
1904 _M_get_Tp_allocator());
1905 }
1906
1907#if __cplusplus >= 201103L
1908 // Called by the vector(n) constructor.
1909 _GLIBCXX20_CONSTEXPR
1910 void
1911 _M_default_initialize(size_type __n)
1912 {
1913 this->_M_impl._M_finish =
1914 std::__uninitialized_default_n_a(this->_M_impl._M_start, __n,
1915 _M_get_Tp_allocator());
1916 }
1917#endif
1918
1919 // Internal assign functions follow. The *_aux functions do the actual
1920 // assignment work for the range versions.
1921
1922 // Called by the range assign to implement [23.1.1]/9
1923
1924 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1925 // 438. Ambiguity in the "do the right thing" clause
1926 template<typename _Integer>
1927 _GLIBCXX20_CONSTEXPR
1928 void
1929 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1930 { _M_fill_assign(__n, __val); }
1931
1932 // Called by the range assign to implement [23.1.1]/9
1933 template<typename _InputIterator>
1934 _GLIBCXX20_CONSTEXPR
1935 void
1936 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1937 __false_type)
1938 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
1939
1940 // Called by the second assign_dispatch above
1941 template<typename _InputIterator>
1942 _GLIBCXX20_CONSTEXPR
1943 void
1944 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1946
1947 // Called by the second assign_dispatch above
1948 template<typename _ForwardIterator>
1949 _GLIBCXX20_CONSTEXPR
1950 void
1951 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1953
1954 // Called by assign(n,t), and the range assign when it turns out
1955 // to be the same thing.
1956 _GLIBCXX20_CONSTEXPR
1957 void
1958 _M_fill_assign(size_type __n, const value_type& __val);
1959
1960 // Internal insert functions follow.
1961
1962 // Called by the range insert to implement [23.1.1]/9
1963
1964 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1965 // 438. Ambiguity in the "do the right thing" clause
1966 template<typename _Integer>
1967 _GLIBCXX20_CONSTEXPR
1968 void
1969 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
1970 __true_type)
1971 { _M_fill_insert(__pos, __n, __val); }
1972
1973 // Called by the range insert to implement [23.1.1]/9
1974 template<typename _InputIterator>
1975 _GLIBCXX20_CONSTEXPR
1976 void
1977 _M_insert_dispatch(iterator __pos, _InputIterator __first,
1978 _InputIterator __last, __false_type)
1979 {
1980 _M_range_insert(__pos, __first, __last,
1981 std::__iterator_category(__first));
1982 }
1983
1984 // Called by the second insert_dispatch above
1985 template<typename _InputIterator>
1986 _GLIBCXX20_CONSTEXPR
1987 void
1988 _M_range_insert(iterator __pos, _InputIterator __first,
1989 _InputIterator __last, std::input_iterator_tag);
1990
1991 // Called by the second insert_dispatch above
1992 template<typename _ForwardIterator>
1993 _GLIBCXX20_CONSTEXPR
1994 void
1995 _M_range_insert(iterator __pos, _ForwardIterator __first,
1996 _ForwardIterator __last, std::forward_iterator_tag);
1997
1998 // Called by insert(p,n,x), and the range insert when it turns out to be
1999 // the same thing.
2000 _GLIBCXX20_CONSTEXPR
2001 void
2002 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
2003
2004#if __cplusplus >= 201103L
2005 // Called by resize(n).
2006 _GLIBCXX20_CONSTEXPR
2007 void
2008 _M_default_append(size_type __n);
2009
2010 _GLIBCXX20_CONSTEXPR
2011 bool
2012 _M_shrink_to_fit();
2013#endif
2014
2015#if __cplusplus < 201103L
2016 // Called by insert(p,x)
2017 void
2018 _M_insert_aux(iterator __position, const value_type& __x);
2019
2020 void
2021 _M_realloc_insert(iterator __position, const value_type& __x);
2022
2023 void
2024 _M_realloc_append(const value_type& __x);
2025#else
2026 // A value_type object constructed with _Alloc_traits::construct()
2027 // and destroyed with _Alloc_traits::destroy().
2028 struct _Temporary_value
2029 {
2030 template<typename... _Args>
2031 _GLIBCXX20_CONSTEXPR explicit
2032 _Temporary_value(vector* __vec, _Args&&... __args) : _M_this(__vec)
2033 {
2034 _Alloc_traits::construct(_M_this->_M_impl, _M_ptr(),
2035 std::forward<_Args>(__args)...);
2036 }
2037
2038 _GLIBCXX20_CONSTEXPR
2039 ~_Temporary_value()
2040 { _Alloc_traits::destroy(_M_this->_M_impl, _M_ptr()); }
2041
2042 _GLIBCXX20_CONSTEXPR value_type&
2043 _M_val() noexcept { return _M_storage._M_val; }
2044
2045 private:
2046 _GLIBCXX20_CONSTEXPR _Tp*
2047 _M_ptr() noexcept { return std::__addressof(_M_storage._M_val); }
2048
2049 union _Storage
2050 {
2051 constexpr _Storage() : _M_byte() { }
2052 _GLIBCXX20_CONSTEXPR ~_Storage() { }
2053 _Storage& operator=(const _Storage&) = delete;
2054 unsigned char _M_byte;
2055 _Tp _M_val;
2056 };
2057
2058 vector* _M_this;
2059 _Storage _M_storage;
2060 };
2061
2062 // Called by insert(p,x) and other functions when insertion needs to
2063 // reallocate or move existing elements. _Arg is either _Tp& or _Tp.
2064 template<typename _Arg>
2065 _GLIBCXX20_CONSTEXPR
2066 void
2067 _M_insert_aux(iterator __position, _Arg&& __arg);
2068
2069 template<typename... _Args>
2070 _GLIBCXX20_CONSTEXPR
2071 void
2072 _M_realloc_insert(iterator __position, _Args&&... __args);
2073
2074 template<typename... _Args>
2075 _GLIBCXX20_CONSTEXPR
2076 void
2077 _M_realloc_append(_Args&&... __args);
2078
2079 // Either move-construct at the end, or forward to _M_insert_aux.
2080 _GLIBCXX20_CONSTEXPR
2081 iterator
2082 _M_insert_rval(const_iterator __position, value_type&& __v);
2083
2084 // Try to emplace at the end, otherwise forward to _M_insert_aux.
2085 template<typename... _Args>
2086 _GLIBCXX20_CONSTEXPR
2087 iterator
2088 _M_emplace_aux(const_iterator __position, _Args&&... __args);
2089
2090 // Emplacing an rvalue of the correct type can use _M_insert_rval.
2091 _GLIBCXX20_CONSTEXPR
2092 iterator
2093 _M_emplace_aux(const_iterator __position, value_type&& __v)
2094 { return _M_insert_rval(__position, std::move(__v)); }
2095#endif
2096
2097 // Called by _M_fill_insert, _M_insert_aux etc.
2098 _GLIBCXX20_CONSTEXPR
2099 size_type
2100 _M_check_len(size_type __n, const char* __s) const
2101 {
2102 if (max_size() - size() < __n)
2103 __throw_length_error(__N(__s));
2104
2105 const size_type __len = size() + (std::max)(size(), __n);
2106 return (__len < size() || __len > max_size()) ? max_size() : __len;
2107 }
2108
2109 // Called by constructors to check initial size.
2110 static _GLIBCXX20_CONSTEXPR size_type
2111 _S_check_init_len(size_type __n, const allocator_type& __a)
2112 {
2113 if (__n > _S_max_size(_Tp_alloc_type(__a)))
2114 __throw_length_error(
2115 __N("cannot create std::vector larger than max_size()"));
2116 return __n;
2117 }
2118
2119 static _GLIBCXX20_CONSTEXPR size_type
2120 _S_max_size(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
2121 {
2122 // std::distance(begin(), end()) cannot be greater than PTRDIFF_MAX,
2123 // and realistically we can't store more than PTRDIFF_MAX/sizeof(T)
2124 // (even if std::allocator_traits::max_size says we can).
2125 const size_t __diffmax
2126 = __gnu_cxx::__numeric_traits<ptrdiff_t>::__max / sizeof(_Tp);
2127 const size_t __allocmax = _Alloc_traits::max_size(__a);
2128 return (std::min)(__diffmax, __allocmax);
2129 }
2130
2131 // Internal erase functions follow.
2132
2133 // Called by erase(q1,q2), clear(), resize(), _M_fill_assign,
2134 // _M_assign_aux.
2135 _GLIBCXX20_CONSTEXPR
2136 void
2137 _M_erase_at_end(pointer __pos) _GLIBCXX_NOEXCEPT
2138 {
2139 if (size_type __n = this->_M_impl._M_finish - __pos)
2140 {
2141 std::_Destroy(__pos, this->_M_impl._M_finish,
2142 _M_get_Tp_allocator());
2143 this->_M_impl._M_finish = __pos;
2144 _GLIBCXX_ASAN_ANNOTATE_SHRINK(__n);
2145 }
2146 }
2147
2148 _GLIBCXX20_CONSTEXPR
2149 iterator
2150 _M_erase(iterator __position);
2151
2152 _GLIBCXX20_CONSTEXPR
2153 iterator
2154 _M_erase(iterator __first, iterator __last);
2155
2156#if __cplusplus >= 201103L
2157 private:
2158 // Constant-time move assignment when source object's memory can be
2159 // moved, either because the source's allocator will move too
2160 // or because the allocators are equal.
2161 _GLIBCXX20_CONSTEXPR
2162 void
2163 _M_move_assign(vector&& __x, true_type) noexcept
2164 {
2165 vector __tmp(get_allocator());
2166 this->_M_impl._M_swap_data(__x._M_impl);
2167 __tmp._M_impl._M_swap_data(__x._M_impl);
2168 std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
2169 }
2170
2171 // Do move assignment when it might not be possible to move source
2172 // object's memory, resulting in a linear-time operation.
2173 _GLIBCXX20_CONSTEXPR
2174 void
2175 _M_move_assign(vector&& __x, false_type)
2176 {
2177 if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
2178 _M_move_assign(std::move(__x), true_type());
2179 else
2180 {
2181 // The rvalue's allocator cannot be moved and is not equal,
2182 // so we need to individually move each element.
2183 this->_M_assign_aux(std::make_move_iterator(__x.begin()),
2184 std::make_move_iterator(__x.end()),
2186 __x.clear();
2187 }
2188 }
2189#endif
2190
2191 template<typename _Up>
2192 _GLIBCXX20_CONSTEXPR
2193 _Up*
2194 _M_data_ptr(_Up* __ptr) const _GLIBCXX_NOEXCEPT
2195 { return __ptr; }
2196
2197#if __cplusplus >= 201103L
2198 template<typename _Ptr>
2199 _GLIBCXX20_CONSTEXPR
2200 typename std::pointer_traits<_Ptr>::element_type*
2201 _M_data_ptr(_Ptr __ptr) const
2202 { return empty() ? nullptr : std::__to_address(__ptr); }
2203#else
2204 template<typename _Ptr>
2205 value_type*
2206 _M_data_ptr(_Ptr __ptr) const
2207 { return empty() ? (value_type*)0 : __ptr.operator->(); }
2208#endif
2209 };
2210
2211#if __cpp_deduction_guides >= 201606
2212 template<typename _InputIterator, typename _ValT
2213 = typename iterator_traits<_InputIterator>::value_type,
2214 typename _Allocator = allocator<_ValT>,
2215 typename = _RequireInputIter<_InputIterator>,
2216 typename = _RequireAllocator<_Allocator>>
2217 vector(_InputIterator, _InputIterator, _Allocator = _Allocator())
2218 -> vector<_ValT, _Allocator>;
2219
2220#if __glibcxx_ranges_to_container // C++ >= 23
2221 template<ranges::input_range _Rg,
2222 typename _Alloc = allocator<ranges::range_value_t<_Rg>>>
2223 vector(from_range_t, _Rg&&, _Alloc = _Alloc())
2224 -> vector<ranges::range_value_t<_Rg>, _Alloc>;
2225#endif
2226#endif
2227
2228 /**
2229 * @brief Vector equality comparison.
2230 * @param __x A %vector.
2231 * @param __y A %vector of the same type as @a __x.
2232 * @return True iff the size and elements of the vectors are equal.
2233 *
2234 * This is an equivalence relation. It is linear in the size of the
2235 * vectors. Vectors are considered equivalent if their sizes are equal,
2236 * and if corresponding elements compare equal.
2237 */
2238 template<typename _Tp, typename _Alloc>
2239 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2240 inline bool
2241 operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
2242 { return (__x.size() == __y.size()
2243 && std::equal(__x.begin(), __x.end(), __y.begin())); }
2244
2245#if __cpp_lib_three_way_comparison // >= C++20
2246 /**
2247 * @brief Vector ordering relation.
2248 * @param __x A `vector`.
2249 * @param __y A `vector` of the same type as `__x`.
2250 * @return A value indicating whether `__x` is less than, equal to,
2251 * greater than, or incomparable with `__y`.
2252 *
2253 * See `std::lexicographical_compare_three_way()` for how the determination
2254 * is made. This operator is used to synthesize relational operators like
2255 * `<` and `>=` etc.
2256 */
2257 template<typename _Tp, typename _Alloc>
2258 [[nodiscard]]
2259 constexpr __detail::__synth3way_t<_Tp>
2260 operator<=>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
2261 {
2263 __y.begin(), __y.end(),
2264 __detail::__synth3way);
2265 }
2266#else
2267 /**
2268 * @brief Vector ordering relation.
2269 * @param __x A %vector.
2270 * @param __y A %vector of the same type as @a __x.
2271 * @return True iff @a __x is lexicographically less than @a __y.
2272 *
2273 * This is a total ordering relation. It is linear in the size of the
2274 * vectors. The elements must be comparable with @c <.
2275 *
2276 * See std::lexicographical_compare() for how the determination is made.
2277 */
2278 template<typename _Tp, typename _Alloc>
2279 _GLIBCXX_NODISCARD inline bool
2280 operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
2281 { return std::lexicographical_compare(__x.begin(), __x.end(),
2282 __y.begin(), __y.end()); }
2283
2284 /// Based on operator==
2285 template<typename _Tp, typename _Alloc>
2286 _GLIBCXX_NODISCARD inline bool
2287 operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
2288 { return !(__x == __y); }
2289
2290 /// Based on operator<
2291 template<typename _Tp, typename _Alloc>
2292 _GLIBCXX_NODISCARD inline bool
2293 operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
2294 { return __y < __x; }
2295
2296 /// Based on operator<
2297 template<typename _Tp, typename _Alloc>
2298 _GLIBCXX_NODISCARD inline bool
2299 operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
2300 { return !(__y < __x); }
2301
2302 /// Based on operator<
2303 template<typename _Tp, typename _Alloc>
2304 _GLIBCXX_NODISCARD inline bool
2305 operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
2306 { return !(__x < __y); }
2307#endif // three-way comparison
2308
2309 /// See std::vector::swap().
2310 template<typename _Tp, typename _Alloc>
2311 _GLIBCXX20_CONSTEXPR
2312 inline void
2314 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
2315 { __x.swap(__y); }
2316
2317_GLIBCXX_END_NAMESPACE_CONTAINER
2318
2319#if __cplusplus >= 201703L
2320 namespace __detail::__variant
2321 {
2322 template<typename> struct _Never_valueless_alt; // see <variant>
2323
2324 // Provide the strong exception-safety guarantee when emplacing a
2325 // vector into a variant, but only if move assignment cannot throw.
2326 template<typename _Tp, typename _Alloc>
2327 struct _Never_valueless_alt<_GLIBCXX_STD_C::vector<_Tp, _Alloc>>
2328 : std::is_nothrow_move_assignable<_GLIBCXX_STD_C::vector<_Tp, _Alloc>>
2329 { };
2330 } // namespace __detail::__variant
2331#endif // C++17
2332
2333_GLIBCXX_END_NAMESPACE_VERSION
2334} // namespace std
2335
2336#endif /* _STL_VECTOR_H */
strong_ordering operator(const error_code &__lhs, const error_code &__rhs) noexcept
Definition system_error:318
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
auto declval() noexcept -> decltype(__declval< _Tp >(0))
Definition type_traits:2608
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:138
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition move.h:52
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition move.h:72
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:1244
is_nothrow_move_assignable
Definition type_traits:1330
static constexpr size_type max_size(const _Alloc &__a) noexcept
The standard allocator, as per C++03 [20.4.1].
Definition memoryfwd.h:67
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.