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