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