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