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