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