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