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 #if __cpp_lib_concepts
140  requires is_default_constructible_v<_Tp_alloc_type>
141 #endif
142  : _Tp_alloc_type()
143  { }
144 
145  _GLIBCXX20_CONSTEXPR
146  _Vector_impl(_Tp_alloc_type const& __a) _GLIBCXX_NOEXCEPT
147  : _Tp_alloc_type(__a)
148  { }
149 
150 #if __cplusplus >= 201103L
151  // Not defaulted, to enforce noexcept(true) even when
152  // !is_nothrow_move_constructible<_Tp_alloc_type>.
153  _GLIBCXX20_CONSTEXPR
154  _Vector_impl(_Vector_impl&& __x) noexcept
155  : _Tp_alloc_type(std::move(__x)), _Vector_impl_data(std::move(__x))
156  { }
157 
158  _GLIBCXX20_CONSTEXPR
159  _Vector_impl(_Tp_alloc_type&& __a) noexcept
160  : _Tp_alloc_type(std::move(__a))
161  { }
162 
163  _GLIBCXX20_CONSTEXPR
164  _Vector_impl(_Tp_alloc_type&& __a, _Vector_impl&& __rv) noexcept
165  : _Tp_alloc_type(std::move(__a)), _Vector_impl_data(std::move(__rv))
166  { }
167 #endif
168 
169 #if _GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR
170  template<typename = _Tp_alloc_type>
171  struct _Asan
172  {
174  ::size_type size_type;
175 
176  static _GLIBCXX20_CONSTEXPR void
177  _S_shrink(_Vector_impl&, size_type) { }
178  static _GLIBCXX20_CONSTEXPR void
179  _S_on_dealloc(_Vector_impl&) { }
180 
181  typedef _Vector_impl& _Reinit;
182 
183  struct _Grow
184  {
185  _GLIBCXX20_CONSTEXPR _Grow(_Vector_impl&, size_type) { }
186  _GLIBCXX20_CONSTEXPR void _M_grew(size_type) { }
187  };
188  };
189 
190  // Enable ASan annotations for memory obtained from std::allocator.
191  template<typename _Up>
192  struct _Asan<allocator<_Up> >
193  {
195  ::size_type size_type;
196 
197  // Adjust ASan annotation for [_M_start, _M_end_of_storage) to
198  // mark end of valid region as __curr instead of __prev.
199  static _GLIBCXX20_CONSTEXPR void
200  _S_adjust(_Vector_impl& __impl, pointer __prev, pointer __curr)
201  {
202 #if __cpp_lib_is_constant_evaluated
204  return;
205 #endif
206  __sanitizer_annotate_contiguous_container(__impl._M_start,
207  __impl._M_end_of_storage, __prev, __curr);
208  }
209 
210  static _GLIBCXX20_CONSTEXPR void
211  _S_grow(_Vector_impl& __impl, size_type __n)
212  { _S_adjust(__impl, __impl._M_finish, __impl._M_finish + __n); }
213 
214  static _GLIBCXX20_CONSTEXPR void
215  _S_shrink(_Vector_impl& __impl, size_type __n)
216  { _S_adjust(__impl, __impl._M_finish + __n, __impl._M_finish); }
217 
218  static _GLIBCXX20_CONSTEXPR void
219  _S_on_dealloc(_Vector_impl& __impl)
220  {
221  if (__impl._M_start)
222  _S_adjust(__impl, __impl._M_finish, __impl._M_end_of_storage);
223  }
224 
225  // Used on reallocation to tell ASan unused capacity is invalid.
226  struct _Reinit
227  {
228  explicit _GLIBCXX20_CONSTEXPR
229  _Reinit(_Vector_impl& __impl) : _M_impl(__impl)
230  {
231  // Mark unused capacity as valid again before deallocating it.
232  _S_on_dealloc(_M_impl);
233  }
234 
235  _GLIBCXX20_CONSTEXPR
236  ~_Reinit()
237  {
238  // Mark unused capacity as invalid after reallocation.
239  if (_M_impl._M_start)
240  _S_adjust(_M_impl, _M_impl._M_end_of_storage,
241  _M_impl._M_finish);
242  }
243 
244  _Vector_impl& _M_impl;
245 
246 #if __cplusplus >= 201103L
247  _Reinit(const _Reinit&) = delete;
248  _Reinit& operator=(const _Reinit&) = delete;
249 #endif
250  };
251 
252  // Tell ASan when unused capacity is initialized to be valid.
253  struct _Grow
254  {
255  _GLIBCXX20_CONSTEXPR
256  _Grow(_Vector_impl& __impl, size_type __n)
257  : _M_impl(__impl), _M_n(__n)
258  { _S_grow(_M_impl, __n); }
259 
260  _GLIBCXX20_CONSTEXPR
261  ~_Grow() { if (_M_n) _S_shrink(_M_impl, _M_n); }
262 
263  _GLIBCXX20_CONSTEXPR
264  void _M_grew(size_type __n) { _M_n -= __n; }
265 
266 #if __cplusplus >= 201103L
267  _Grow(const _Grow&) = delete;
268  _Grow& operator=(const _Grow&) = delete;
269 #endif
270  private:
271  _Vector_impl& _M_impl;
272  size_type _M_n;
273  };
274  };
275 
276 #define _GLIBCXX_ASAN_ANNOTATE_REINIT \
277  typename _Base::_Vector_impl::template _Asan<>::_Reinit const \
278  __attribute__((__unused__)) __reinit_guard(this->_M_impl)
279 #define _GLIBCXX_ASAN_ANNOTATE_GROW(n) \
280  typename _Base::_Vector_impl::template _Asan<>::_Grow \
281  __attribute__((__unused__)) __grow_guard(this->_M_impl, (n))
282 #define _GLIBCXX_ASAN_ANNOTATE_GREW(n) __grow_guard._M_grew(n)
283 #define _GLIBCXX_ASAN_ANNOTATE_SHRINK(n) \
284  _Base::_Vector_impl::template _Asan<>::_S_shrink(this->_M_impl, n)
285 #define _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC \
286  _Base::_Vector_impl::template _Asan<>::_S_on_dealloc(this->_M_impl)
287 #else // ! (_GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR)
288 #define _GLIBCXX_ASAN_ANNOTATE_REINIT
289 #define _GLIBCXX_ASAN_ANNOTATE_GROW(n)
290 #define _GLIBCXX_ASAN_ANNOTATE_GREW(n)
291 #define _GLIBCXX_ASAN_ANNOTATE_SHRINK(n)
292 #define _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC
293 #endif // _GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR
294  };
295 
296  public:
297  typedef _Alloc allocator_type;
298 
299  _GLIBCXX20_CONSTEXPR
300  _Tp_alloc_type&
301  _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
302  { return this->_M_impl; }
303 
304  _GLIBCXX20_CONSTEXPR
305  const _Tp_alloc_type&
306  _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
307  { return this->_M_impl; }
308 
309  _GLIBCXX20_CONSTEXPR
310  allocator_type
311  get_allocator() const _GLIBCXX_NOEXCEPT
312  { return allocator_type(_M_get_Tp_allocator()); }
313 
314 #if __cplusplus >= 201103L
315  _Vector_base() = default;
316 #else
317  _Vector_base() { }
318 #endif
319 
320  _GLIBCXX20_CONSTEXPR
321  _Vector_base(const allocator_type& __a) _GLIBCXX_NOEXCEPT
322  : _M_impl(__a) { }
323 
324  // Kept for ABI compatibility.
325 #if !_GLIBCXX_INLINE_VERSION
326  _GLIBCXX20_CONSTEXPR
327  _Vector_base(size_t __n)
328  : _M_impl()
329  { _M_create_storage(__n); }
330 #endif
331 
332  _GLIBCXX20_CONSTEXPR
333  _Vector_base(size_t __n, const allocator_type& __a)
334  : _M_impl(__a)
335  { _M_create_storage(__n); }
336 
337 #if __cplusplus >= 201103L
338  _Vector_base(_Vector_base&&) = default;
339 
340  // Kept for ABI compatibility.
341 # if !_GLIBCXX_INLINE_VERSION
342  _GLIBCXX20_CONSTEXPR
343  _Vector_base(_Tp_alloc_type&& __a) noexcept
344  : _M_impl(std::move(__a)) { }
345 
346  _GLIBCXX20_CONSTEXPR
347  _Vector_base(_Vector_base&& __x, const allocator_type& __a)
348  : _M_impl(__a)
349  {
350  if (__x.get_allocator() == __a)
351  this->_M_impl._M_swap_data(__x._M_impl);
352  else
353  {
354  size_t __n = __x._M_impl._M_finish - __x._M_impl._M_start;
355  _M_create_storage(__n);
356  }
357  }
358 # endif
359 
360  _GLIBCXX20_CONSTEXPR
361  _Vector_base(const allocator_type& __a, _Vector_base&& __x)
362  : _M_impl(_Tp_alloc_type(__a), std::move(__x._M_impl))
363  { }
364 #endif
365 
366  _GLIBCXX20_CONSTEXPR
367  ~_Vector_base() _GLIBCXX_NOEXCEPT
368  {
369  _M_deallocate(_M_impl._M_start,
370  _M_impl._M_end_of_storage - _M_impl._M_start);
371  }
372 
373  public:
374  _Vector_impl _M_impl;
375 
376  _GLIBCXX20_CONSTEXPR
377  pointer
378  _M_allocate(size_t __n)
379  {
381  return __n != 0 ? _Tr::allocate(_M_impl, __n) : pointer();
382  }
383 
384  _GLIBCXX20_CONSTEXPR
385  void
386  _M_deallocate(pointer __p, size_t __n)
387  {
389  if (__p)
390  _Tr::deallocate(_M_impl, __p, __n);
391  }
392 
393  protected:
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  { return size_type(this->_M_impl._M_end_of_storage
1080  - this->_M_impl._M_start); }
1081 
1082  /**
1083  * Returns true if the %vector is empty. (Thus begin() would
1084  * equal end().)
1085  */
1086  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1087  bool
1088  empty() const _GLIBCXX_NOEXCEPT
1089  { return begin() == end(); }
1090 
1091  /**
1092  * @brief Attempt to preallocate enough memory for specified number of
1093  * elements.
1094  * @param __n Number of elements required.
1095  * @throw std::length_error If @a n exceeds @c max_size().
1096  *
1097  * This function attempts to reserve enough memory for the
1098  * %vector to hold the specified number of elements. If the
1099  * number requested is more than max_size(), length_error is
1100  * thrown.
1101  *
1102  * The advantage of this function is that if optimal code is a
1103  * necessity and the user can determine the number of elements
1104  * that will be required, the user can reserve the memory in
1105  * %advance, and thus prevent a possible reallocation of memory
1106  * and copying of %vector data.
1107  */
1108  _GLIBCXX20_CONSTEXPR
1109  void
1110  reserve(size_type __n);
1111 
1112  // element access
1113  /**
1114  * @brief Subscript access to the data contained in the %vector.
1115  * @param __n The index of the element for which data should be
1116  * accessed.
1117  * @return Read/write reference to data.
1118  *
1119  * This operator allows for easy, array-style, data access.
1120  * Note that data access with this operator is unchecked and
1121  * out_of_range lookups are not defined. (For checked lookups
1122  * see at().)
1123  */
1124  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1125  reference
1126  operator[](size_type __n) _GLIBCXX_NOEXCEPT
1127  {
1128  __glibcxx_requires_subscript(__n);
1129  return *(this->_M_impl._M_start + __n);
1130  }
1131 
1132  /**
1133  * @brief Subscript access to the data contained in the %vector.
1134  * @param __n The index of the element for which data should be
1135  * accessed.
1136  * @return Read-only (constant) reference to data.
1137  *
1138  * This operator allows for easy, array-style, data access.
1139  * Note that data access with this operator is unchecked and
1140  * out_of_range lookups are not defined. (For checked lookups
1141  * see at().)
1142  */
1143  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1144  const_reference
1145  operator[](size_type __n) const _GLIBCXX_NOEXCEPT
1146  {
1147  __glibcxx_requires_subscript(__n);
1148  return *(this->_M_impl._M_start + __n);
1149  }
1150 
1151  protected:
1152  /// Safety check used only from at().
1153  _GLIBCXX20_CONSTEXPR
1154  void
1155  _M_range_check(size_type __n) const
1156  {
1157  if (__n >= this->size())
1158  __throw_out_of_range_fmt(__N("vector::_M_range_check: __n "
1159  "(which is %zu) >= this->size() "
1160  "(which is %zu)"),
1161  __n, this->size());
1162  }
1163 
1164  public:
1165  /**
1166  * @brief Provides access to the data contained in the %vector.
1167  * @param __n The index of the element for which data should be
1168  * accessed.
1169  * @return Read/write reference to data.
1170  * @throw std::out_of_range If @a __n is an invalid index.
1171  *
1172  * This function provides for safer data access. The parameter
1173  * is first checked that it is in the range of the vector. The
1174  * function throws out_of_range if the check fails.
1175  */
1176  _GLIBCXX20_CONSTEXPR
1177  reference
1178  at(size_type __n)
1179  {
1180  _M_range_check(__n);
1181  return (*this)[__n];
1182  }
1183 
1184  /**
1185  * @brief Provides access to the data contained in the %vector.
1186  * @param __n The index of the element for which data should be
1187  * accessed.
1188  * @return Read-only (constant) reference to data.
1189  * @throw std::out_of_range If @a __n is an invalid index.
1190  *
1191  * This function provides for safer data access. The parameter
1192  * is first checked that it is in the range of the vector. The
1193  * function throws out_of_range if the check fails.
1194  */
1195  _GLIBCXX20_CONSTEXPR
1196  const_reference
1197  at(size_type __n) const
1198  {
1199  _M_range_check(__n);
1200  return (*this)[__n];
1201  }
1202 
1203  /**
1204  * Returns a read/write reference to the data at the first
1205  * element of the %vector.
1206  */
1207  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1208  reference
1209  front() _GLIBCXX_NOEXCEPT
1210  {
1211  __glibcxx_requires_nonempty();
1212  return *begin();
1213  }
1214 
1215  /**
1216  * Returns a read-only (constant) reference to the data at the first
1217  * element of the %vector.
1218  */
1219  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1220  const_reference
1221  front() const _GLIBCXX_NOEXCEPT
1222  {
1223  __glibcxx_requires_nonempty();
1224  return *begin();
1225  }
1226 
1227  /**
1228  * Returns a read/write reference to the data at the last
1229  * element of the %vector.
1230  */
1231  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1232  reference
1233  back() _GLIBCXX_NOEXCEPT
1234  {
1235  __glibcxx_requires_nonempty();
1236  return *(end() - 1);
1237  }
1238 
1239  /**
1240  * Returns a read-only (constant) reference to the data at the
1241  * last element of the %vector.
1242  */
1243  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1244  const_reference
1245  back() const _GLIBCXX_NOEXCEPT
1246  {
1247  __glibcxx_requires_nonempty();
1248  return *(end() - 1);
1249  }
1250 
1251  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1252  // DR 464. Suggestion for new member functions in standard containers.
1253  // data access
1254  /**
1255  * Returns a pointer such that [data(), data() + size()) is a valid
1256  * range. For a non-empty %vector, data() == &front().
1257  */
1258  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1259  _Tp*
1260  data() _GLIBCXX_NOEXCEPT
1261  { return _M_data_ptr(this->_M_impl._M_start); }
1262 
1263  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1264  const _Tp*
1265  data() const _GLIBCXX_NOEXCEPT
1266  { return _M_data_ptr(this->_M_impl._M_start); }
1267 
1268  // [23.2.4.3] modifiers
1269  /**
1270  * @brief Add data to the end of the %vector.
1271  * @param __x Data to be added.
1272  *
1273  * This is a typical stack operation. The function creates an
1274  * element at the end of the %vector and assigns the given data
1275  * to it. Due to the nature of a %vector this operation can be
1276  * done in constant time if the %vector has preallocated space
1277  * available.
1278  */
1279  _GLIBCXX20_CONSTEXPR
1280  void
1281  push_back(const value_type& __x)
1282  {
1283  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
1284  {
1285  _GLIBCXX_ASAN_ANNOTATE_GROW(1);
1286  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
1287  __x);
1288  ++this->_M_impl._M_finish;
1289  _GLIBCXX_ASAN_ANNOTATE_GREW(1);
1290  }
1291  else
1292  _M_realloc_insert(end(), __x);
1293  }
1294 
1295 #if __cplusplus >= 201103L
1296  _GLIBCXX20_CONSTEXPR
1297  void
1298  push_back(value_type&& __x)
1299  { emplace_back(std::move(__x)); }
1300 
1301  template<typename... _Args>
1302 #if __cplusplus > 201402L
1303  _GLIBCXX20_CONSTEXPR
1304  reference
1305 #else
1306  void
1307 #endif
1308  emplace_back(_Args&&... __args);
1309 #endif
1310 
1311  /**
1312  * @brief Removes last element.
1313  *
1314  * This is a typical stack operation. It shrinks the %vector by one.
1315  *
1316  * Note that no data is returned, and if the last element's
1317  * data is needed, it should be retrieved before pop_back() is
1318  * called.
1319  */
1320  _GLIBCXX20_CONSTEXPR
1321  void
1322  pop_back() _GLIBCXX_NOEXCEPT
1323  {
1324  __glibcxx_requires_nonempty();
1325  --this->_M_impl._M_finish;
1326  _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
1327  _GLIBCXX_ASAN_ANNOTATE_SHRINK(1);
1328  }
1329 
1330 #if __cplusplus >= 201103L
1331  /**
1332  * @brief Inserts an object in %vector before specified iterator.
1333  * @param __position A const_iterator into the %vector.
1334  * @param __args Arguments.
1335  * @return An iterator that points to the inserted data.
1336  *
1337  * This function will insert an object of type T constructed
1338  * with T(std::forward<Args>(args)...) before the specified location.
1339  * Note that this kind of operation could be expensive for a %vector
1340  * and if it is frequently used the user should consider using
1341  * std::list.
1342  */
1343  template<typename... _Args>
1344  _GLIBCXX20_CONSTEXPR
1345  iterator
1346  emplace(const_iterator __position, _Args&&... __args)
1347  { return _M_emplace_aux(__position, std::forward<_Args>(__args)...); }
1348 
1349  /**
1350  * @brief Inserts given value into %vector before specified iterator.
1351  * @param __position A const_iterator into the %vector.
1352  * @param __x Data to be inserted.
1353  * @return An iterator that points to the inserted data.
1354  *
1355  * This function will insert a copy of the given value before
1356  * the specified location. Note that this kind of operation
1357  * could be expensive for a %vector and if it is frequently
1358  * used the user should consider using std::list.
1359  */
1360  _GLIBCXX20_CONSTEXPR
1361  iterator
1362  insert(const_iterator __position, const value_type& __x);
1363 #else
1364  /**
1365  * @brief Inserts given value into %vector before specified iterator.
1366  * @param __position An iterator into the %vector.
1367  * @param __x Data to be inserted.
1368  * @return An iterator that points to the inserted data.
1369  *
1370  * This function will insert a copy of the given value before
1371  * the specified location. Note that this kind of operation
1372  * could be expensive for a %vector and if it is frequently
1373  * used the user should consider using std::list.
1374  */
1375  iterator
1376  insert(iterator __position, const value_type& __x);
1377 #endif
1378 
1379 #if __cplusplus >= 201103L
1380  /**
1381  * @brief Inserts given rvalue into %vector before specified iterator.
1382  * @param __position A const_iterator into the %vector.
1383  * @param __x Data to be inserted.
1384  * @return An iterator that points to the inserted data.
1385  *
1386  * This function will insert a copy of the given rvalue before
1387  * the specified location. Note that this kind of operation
1388  * could be expensive for a %vector and if it is frequently
1389  * used the user should consider using std::list.
1390  */
1391  _GLIBCXX20_CONSTEXPR
1392  iterator
1393  insert(const_iterator __position, value_type&& __x)
1394  { return _M_insert_rval(__position, std::move(__x)); }
1395 
1396  /**
1397  * @brief Inserts an initializer_list into the %vector.
1398  * @param __position An iterator into the %vector.
1399  * @param __l An initializer_list.
1400  *
1401  * This function will insert copies of the data in the
1402  * initializer_list @a l into the %vector before the location
1403  * specified by @a position.
1404  *
1405  * Note that this kind of operation could be expensive for a
1406  * %vector and if it is frequently used the user should
1407  * consider using std::list.
1408  */
1409  _GLIBCXX20_CONSTEXPR
1410  iterator
1411  insert(const_iterator __position, initializer_list<value_type> __l)
1412  {
1413  auto __offset = __position - cbegin();
1414  _M_range_insert(begin() + __offset, __l.begin(), __l.end(),
1416  return begin() + __offset;
1417  }
1418 #endif
1419 
1420 #if __cplusplus >= 201103L
1421  /**
1422  * @brief Inserts a number of copies of given data into the %vector.
1423  * @param __position A const_iterator into the %vector.
1424  * @param __n Number of elements to be inserted.
1425  * @param __x Data to be inserted.
1426  * @return An iterator that points to the inserted data.
1427  *
1428  * This function will insert a specified number of copies of
1429  * the given data before the location specified by @a position.
1430  *
1431  * Note that this kind of operation could be expensive for a
1432  * %vector and if it is frequently used the user should
1433  * consider using std::list.
1434  */
1435  _GLIBCXX20_CONSTEXPR
1436  iterator
1437  insert(const_iterator __position, size_type __n, const value_type& __x)
1438  {
1439  difference_type __offset = __position - cbegin();
1440  _M_fill_insert(begin() + __offset, __n, __x);
1441  return begin() + __offset;
1442  }
1443 #else
1444  /**
1445  * @brief Inserts a number of copies of given data into the %vector.
1446  * @param __position An iterator into the %vector.
1447  * @param __n Number of elements to be inserted.
1448  * @param __x Data to be inserted.
1449  *
1450  * This function will insert a specified number of copies of
1451  * the given data before the location specified by @a position.
1452  *
1453  * Note that this kind of operation could be expensive for a
1454  * %vector and if it is frequently used the user should
1455  * consider using std::list.
1456  */
1457  void
1458  insert(iterator __position, size_type __n, const value_type& __x)
1459  { _M_fill_insert(__position, __n, __x); }
1460 #endif
1461 
1462 #if __cplusplus >= 201103L
1463  /**
1464  * @brief Inserts a range into the %vector.
1465  * @param __position A const_iterator into the %vector.
1466  * @param __first An input iterator.
1467  * @param __last An input iterator.
1468  * @return An iterator that points to the inserted data.
1469  *
1470  * This function will insert copies of the data in the range
1471  * [__first,__last) into the %vector before the location specified
1472  * by @a pos.
1473  *
1474  * Note that this kind of operation could be expensive for a
1475  * %vector and if it is frequently used the user should
1476  * consider using std::list.
1477  */
1478  template<typename _InputIterator,
1479  typename = std::_RequireInputIter<_InputIterator>>
1480  _GLIBCXX20_CONSTEXPR
1481  iterator
1482  insert(const_iterator __position, _InputIterator __first,
1483  _InputIterator __last)
1484  {
1485  difference_type __offset = __position - cbegin();
1486  _M_range_insert(begin() + __offset, __first, __last,
1487  std::__iterator_category(__first));
1488  return begin() + __offset;
1489  }
1490 #else
1491  /**
1492  * @brief Inserts a range into the %vector.
1493  * @param __position An iterator into the %vector.
1494  * @param __first An input iterator.
1495  * @param __last An input iterator.
1496  *
1497  * This function will insert copies of the data in the range
1498  * [__first,__last) into the %vector before the location specified
1499  * by @a pos.
1500  *
1501  * Note that this kind of operation could be expensive for a
1502  * %vector and if it is frequently used the user should
1503  * consider using std::list.
1504  */
1505  template<typename _InputIterator>
1506  void
1507  insert(iterator __position, _InputIterator __first,
1508  _InputIterator __last)
1509  {
1510  // Check whether it's an integral type. If so, it's not an iterator.
1511  typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1512  _M_insert_dispatch(__position, __first, __last, _Integral());
1513  }
1514 #endif
1515 
1516  /**
1517  * @brief Remove element at given position.
1518  * @param __position Iterator pointing to element to be erased.
1519  * @return An iterator pointing to the next element (or end()).
1520  *
1521  * This function will erase the element at the given position and thus
1522  * shorten the %vector by one.
1523  *
1524  * Note This operation could be expensive and if it is
1525  * frequently used the user should consider using std::list.
1526  * The user is also cautioned that this function only erases
1527  * the element, and that if the element is itself a pointer,
1528  * the pointed-to memory is not touched in any way. Managing
1529  * the pointer is the user's responsibility.
1530  */
1531  _GLIBCXX20_CONSTEXPR
1532  iterator
1533 #if __cplusplus >= 201103L
1534  erase(const_iterator __position)
1535  { return _M_erase(begin() + (__position - cbegin())); }
1536 #else
1537  erase(iterator __position)
1538  { return _M_erase(__position); }
1539 #endif
1540 
1541  /**
1542  * @brief Remove a range of elements.
1543  * @param __first Iterator pointing to the first element to be erased.
1544  * @param __last Iterator pointing to one past the last element to be
1545  * erased.
1546  * @return An iterator pointing to the element pointed to by @a __last
1547  * prior to erasing (or end()).
1548  *
1549  * This function will erase the elements in the range
1550  * [__first,__last) and shorten the %vector accordingly.
1551  *
1552  * Note This operation could be expensive and if it is
1553  * frequently used the user should consider using std::list.
1554  * The user is also cautioned that this function only erases
1555  * the elements, and that if the elements themselves are
1556  * pointers, the pointed-to memory is not touched in any way.
1557  * Managing the pointer is the user's responsibility.
1558  */
1559  _GLIBCXX20_CONSTEXPR
1560  iterator
1561 #if __cplusplus >= 201103L
1562  erase(const_iterator __first, const_iterator __last)
1563  {
1564  const auto __beg = begin();
1565  const auto __cbeg = cbegin();
1566  return _M_erase(__beg + (__first - __cbeg), __beg + (__last - __cbeg));
1567  }
1568 #else
1569  erase(iterator __first, iterator __last)
1570  { return _M_erase(__first, __last); }
1571 #endif
1572 
1573  /**
1574  * @brief Swaps data with another %vector.
1575  * @param __x A %vector of the same element and allocator types.
1576  *
1577  * This exchanges the elements between two vectors in constant time.
1578  * (Three pointers, so it should be quite fast.)
1579  * Note that the global std::swap() function is specialized such that
1580  * std::swap(v1,v2) will feed to this function.
1581  *
1582  * Whether the allocators are swapped depends on the allocator traits.
1583  */
1584  _GLIBCXX20_CONSTEXPR
1585  void
1586  swap(vector& __x) _GLIBCXX_NOEXCEPT
1587  {
1588 #if __cplusplus >= 201103L
1589  __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value
1590  || _M_get_Tp_allocator() == __x._M_get_Tp_allocator());
1591 #endif
1592  this->_M_impl._M_swap_data(__x._M_impl);
1593  _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1594  __x._M_get_Tp_allocator());
1595  }
1596 
1597  /**
1598  * Erases all the elements. Note that this function only erases the
1599  * elements, and that if the elements themselves are pointers, the
1600  * pointed-to memory is not touched in any way. Managing the pointer is
1601  * the user's responsibility.
1602  */
1603  _GLIBCXX20_CONSTEXPR
1604  void
1605  clear() _GLIBCXX_NOEXCEPT
1606  { _M_erase_at_end(this->_M_impl._M_start); }
1607 
1608  protected:
1609  /**
1610  * Memory expansion handler. Uses the member allocation function to
1611  * obtain @a n bytes of memory, and then copies [first,last) into it.
1612  */
1613  template<typename _ForwardIterator>
1614  _GLIBCXX20_CONSTEXPR
1615  pointer
1616  _M_allocate_and_copy(size_type __n,
1617  _ForwardIterator __first, _ForwardIterator __last)
1618  {
1619  pointer __result = this->_M_allocate(__n);
1620  __try
1621  {
1622  std::__uninitialized_copy_a(__first, __last, __result,
1623  _M_get_Tp_allocator());
1624  return __result;
1625  }
1626  __catch(...)
1627  {
1628  _M_deallocate(__result, __n);
1629  __throw_exception_again;
1630  }
1631  }
1632 
1633 
1634  // Internal constructor functions follow.
1635 
1636  // Called by the range constructor to implement [23.1.1]/9
1637 
1638 #if __cplusplus < 201103L
1639  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1640  // 438. Ambiguity in the "do the right thing" clause
1641  template<typename _Integer>
1642  void
1643  _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type)
1644  {
1645  this->_M_impl._M_start = _M_allocate(_S_check_init_len(
1646  static_cast<size_type>(__n), _M_get_Tp_allocator()));
1647  this->_M_impl._M_end_of_storage =
1648  this->_M_impl._M_start + static_cast<size_type>(__n);
1649  _M_fill_initialize(static_cast<size_type>(__n), __value);
1650  }
1651 
1652  // Called by the range constructor to implement [23.1.1]/9
1653  template<typename _InputIterator>
1654  void
1655  _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1656  __false_type)
1657  {
1658  _M_range_initialize(__first, __last,
1659  std::__iterator_category(__first));
1660  }
1661 #endif
1662 
1663  // Called by the second initialize_dispatch above
1664  template<typename _InputIterator>
1665  _GLIBCXX20_CONSTEXPR
1666  void
1667  _M_range_initialize(_InputIterator __first, _InputIterator __last,
1669  {
1670  __try {
1671  for (; __first != __last; ++__first)
1672 #if __cplusplus >= 201103L
1673  emplace_back(*__first);
1674 #else
1675  push_back(*__first);
1676 #endif
1677  } __catch(...) {
1678  clear();
1679  __throw_exception_again;
1680  }
1681  }
1682 
1683  // Called by the second initialize_dispatch above
1684  template<typename _ForwardIterator>
1685  _GLIBCXX20_CONSTEXPR
1686  void
1687  _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
1689  {
1690  const size_type __n = std::distance(__first, __last);
1691  this->_M_impl._M_start
1692  = this->_M_allocate(_S_check_init_len(__n, _M_get_Tp_allocator()));
1693  this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
1694  this->_M_impl._M_finish =
1695  std::__uninitialized_copy_a(__first, __last,
1696  this->_M_impl._M_start,
1697  _M_get_Tp_allocator());
1698  }
1699 
1700  // Called by the first initialize_dispatch above and by the
1701  // vector(n,value,a) constructor.
1702  _GLIBCXX20_CONSTEXPR
1703  void
1704  _M_fill_initialize(size_type __n, const value_type& __value)
1705  {
1706  this->_M_impl._M_finish =
1707  std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
1708  _M_get_Tp_allocator());
1709  }
1710 
1711 #if __cplusplus >= 201103L
1712  // Called by the vector(n) constructor.
1713  _GLIBCXX20_CONSTEXPR
1714  void
1715  _M_default_initialize(size_type __n)
1716  {
1717  this->_M_impl._M_finish =
1718  std::__uninitialized_default_n_a(this->_M_impl._M_start, __n,
1719  _M_get_Tp_allocator());
1720  }
1721 #endif
1722 
1723  // Internal assign functions follow. The *_aux functions do the actual
1724  // assignment work for the range versions.
1725 
1726  // Called by the range assign to implement [23.1.1]/9
1727 
1728  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1729  // 438. Ambiguity in the "do the right thing" clause
1730  template<typename _Integer>
1731  _GLIBCXX20_CONSTEXPR
1732  void
1733  _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1734  { _M_fill_assign(__n, __val); }
1735 
1736  // Called by the range assign to implement [23.1.1]/9
1737  template<typename _InputIterator>
1738  _GLIBCXX20_CONSTEXPR
1739  void
1740  _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1741  __false_type)
1742  { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
1743 
1744  // Called by the second assign_dispatch above
1745  template<typename _InputIterator>
1746  _GLIBCXX20_CONSTEXPR
1747  void
1748  _M_assign_aux(_InputIterator __first, _InputIterator __last,
1750 
1751  // Called by the second assign_dispatch above
1752  template<typename _ForwardIterator>
1753  _GLIBCXX20_CONSTEXPR
1754  void
1755  _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1757 
1758  // Called by assign(n,t), and the range assign when it turns out
1759  // to be the same thing.
1760  _GLIBCXX20_CONSTEXPR
1761  void
1762  _M_fill_assign(size_type __n, const value_type& __val);
1763 
1764  // Internal insert functions follow.
1765 
1766  // Called by the range insert to implement [23.1.1]/9
1767 
1768  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1769  // 438. Ambiguity in the "do the right thing" clause
1770  template<typename _Integer>
1771  _GLIBCXX20_CONSTEXPR
1772  void
1773  _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
1774  __true_type)
1775  { _M_fill_insert(__pos, __n, __val); }
1776 
1777  // Called by the range insert to implement [23.1.1]/9
1778  template<typename _InputIterator>
1779  _GLIBCXX20_CONSTEXPR
1780  void
1781  _M_insert_dispatch(iterator __pos, _InputIterator __first,
1782  _InputIterator __last, __false_type)
1783  {
1784  _M_range_insert(__pos, __first, __last,
1785  std::__iterator_category(__first));
1786  }
1787 
1788  // Called by the second insert_dispatch above
1789  template<typename _InputIterator>
1790  _GLIBCXX20_CONSTEXPR
1791  void
1792  _M_range_insert(iterator __pos, _InputIterator __first,
1793  _InputIterator __last, std::input_iterator_tag);
1794 
1795  // Called by the second insert_dispatch above
1796  template<typename _ForwardIterator>
1797  _GLIBCXX20_CONSTEXPR
1798  void
1799  _M_range_insert(iterator __pos, _ForwardIterator __first,
1800  _ForwardIterator __last, std::forward_iterator_tag);
1801 
1802  // Called by insert(p,n,x), and the range insert when it turns out to be
1803  // the same thing.
1804  _GLIBCXX20_CONSTEXPR
1805  void
1806  _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
1807 
1808 #if __cplusplus >= 201103L
1809  // Called by resize(n).
1810  _GLIBCXX20_CONSTEXPR
1811  void
1812  _M_default_append(size_type __n);
1813 
1814  _GLIBCXX20_CONSTEXPR
1815  bool
1816  _M_shrink_to_fit();
1817 #endif
1818 
1819 #if __cplusplus < 201103L
1820  // Called by insert(p,x)
1821  void
1822  _M_insert_aux(iterator __position, const value_type& __x);
1823 
1824  void
1825  _M_realloc_insert(iterator __position, const value_type& __x);
1826 #else
1827  // A value_type object constructed with _Alloc_traits::construct()
1828  // and destroyed with _Alloc_traits::destroy().
1829  struct _Temporary_value
1830  {
1831  template<typename... _Args>
1832  _GLIBCXX20_CONSTEXPR explicit
1833  _Temporary_value(vector* __vec, _Args&&... __args) : _M_this(__vec)
1834  {
1835  _Alloc_traits::construct(_M_this->_M_impl, _M_ptr(),
1836  std::forward<_Args>(__args)...);
1837  }
1838 
1839  _GLIBCXX20_CONSTEXPR
1840  ~_Temporary_value()
1841  { _Alloc_traits::destroy(_M_this->_M_impl, _M_ptr()); }
1842 
1843  _GLIBCXX20_CONSTEXPR value_type&
1844  _M_val() noexcept { return _M_storage._M_val; }
1845 
1846  private:
1847  _GLIBCXX20_CONSTEXPR _Tp*
1848  _M_ptr() noexcept { return std::__addressof(_M_storage._M_val); }
1849 
1850  union _Storage
1851  {
1852  constexpr _Storage() : _M_byte() { }
1853  _GLIBCXX20_CONSTEXPR ~_Storage() { }
1854  _Storage& operator=(const _Storage&) = delete;
1855  unsigned char _M_byte;
1856  _Tp _M_val;
1857  };
1858 
1859  vector* _M_this;
1860  _Storage _M_storage;
1861  };
1862 
1863  // Called by insert(p,x) and other functions when insertion needs to
1864  // reallocate or move existing elements. _Arg is either _Tp& or _Tp.
1865  template<typename _Arg>
1866  _GLIBCXX20_CONSTEXPR
1867  void
1868  _M_insert_aux(iterator __position, _Arg&& __arg);
1869 
1870  template<typename... _Args>
1871  _GLIBCXX20_CONSTEXPR
1872  void
1873  _M_realloc_insert(iterator __position, _Args&&... __args);
1874 
1875  // Either move-construct at the end, or forward to _M_insert_aux.
1876  _GLIBCXX20_CONSTEXPR
1877  iterator
1878  _M_insert_rval(const_iterator __position, value_type&& __v);
1879 
1880  // Try to emplace at the end, otherwise forward to _M_insert_aux.
1881  template<typename... _Args>
1882  _GLIBCXX20_CONSTEXPR
1883  iterator
1884  _M_emplace_aux(const_iterator __position, _Args&&... __args);
1885 
1886  // Emplacing an rvalue of the correct type can use _M_insert_rval.
1887  _GLIBCXX20_CONSTEXPR
1888  iterator
1889  _M_emplace_aux(const_iterator __position, value_type&& __v)
1890  { return _M_insert_rval(__position, std::move(__v)); }
1891 #endif
1892 
1893  // Called by _M_fill_insert, _M_insert_aux etc.
1894  _GLIBCXX20_CONSTEXPR
1895  size_type
1896  _M_check_len(size_type __n, const char* __s) const
1897  {
1898  if (max_size() - size() < __n)
1899  __throw_length_error(__N(__s));
1900 
1901  const size_type __len = size() + (std::max)(size(), __n);
1902  return (__len < size() || __len > max_size()) ? max_size() : __len;
1903  }
1904 
1905  // Called by constructors to check initial size.
1906  static _GLIBCXX20_CONSTEXPR size_type
1907  _S_check_init_len(size_type __n, const allocator_type& __a)
1908  {
1909  if (__n > _S_max_size(_Tp_alloc_type(__a)))
1910  __throw_length_error(
1911  __N("cannot create std::vector larger than max_size()"));
1912  return __n;
1913  }
1914 
1915  static _GLIBCXX20_CONSTEXPR size_type
1916  _S_max_size(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
1917  {
1918  // std::distance(begin(), end()) cannot be greater than PTRDIFF_MAX,
1919  // and realistically we can't store more than PTRDIFF_MAX/sizeof(T)
1920  // (even if std::allocator_traits::max_size says we can).
1921  const size_t __diffmax
1922  = __gnu_cxx::__numeric_traits<ptrdiff_t>::__max / sizeof(_Tp);
1923  const size_t __allocmax = _Alloc_traits::max_size(__a);
1924  return (std::min)(__diffmax, __allocmax);
1925  }
1926 
1927  // Internal erase functions follow.
1928 
1929  // Called by erase(q1,q2), clear(), resize(), _M_fill_assign,
1930  // _M_assign_aux.
1931  _GLIBCXX20_CONSTEXPR
1932  void
1933  _M_erase_at_end(pointer __pos) _GLIBCXX_NOEXCEPT
1934  {
1935  if (size_type __n = this->_M_impl._M_finish - __pos)
1936  {
1937  std::_Destroy(__pos, this->_M_impl._M_finish,
1938  _M_get_Tp_allocator());
1939  this->_M_impl._M_finish = __pos;
1940  _GLIBCXX_ASAN_ANNOTATE_SHRINK(__n);
1941  }
1942  }
1943 
1944  _GLIBCXX20_CONSTEXPR
1945  iterator
1946  _M_erase(iterator __position);
1947 
1948  _GLIBCXX20_CONSTEXPR
1949  iterator
1950  _M_erase(iterator __first, iterator __last);
1951 
1952 #if __cplusplus >= 201103L
1953  private:
1954  // Constant-time move assignment when source object's memory can be
1955  // moved, either because the source's allocator will move too
1956  // or because the allocators are equal.
1957  _GLIBCXX20_CONSTEXPR
1958  void
1959  _M_move_assign(vector&& __x, true_type) noexcept
1960  {
1961  vector __tmp(get_allocator());
1962  this->_M_impl._M_swap_data(__x._M_impl);
1963  __tmp._M_impl._M_swap_data(__x._M_impl);
1964  std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
1965  }
1966 
1967  // Do move assignment when it might not be possible to move source
1968  // object's memory, resulting in a linear-time operation.
1969  _GLIBCXX20_CONSTEXPR
1970  void
1971  _M_move_assign(vector&& __x, false_type)
1972  {
1973  if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
1974  _M_move_assign(std::move(__x), true_type());
1975  else
1976  {
1977  // The rvalue's allocator cannot be moved and is not equal,
1978  // so we need to individually move each element.
1979  this->_M_assign_aux(std::make_move_iterator(__x.begin()),
1980  std::make_move_iterator(__x.end()),
1982  __x.clear();
1983  }
1984  }
1985 #endif
1986 
1987  template<typename _Up>
1988  _GLIBCXX20_CONSTEXPR
1989  _Up*
1990  _M_data_ptr(_Up* __ptr) const _GLIBCXX_NOEXCEPT
1991  { return __ptr; }
1992 
1993 #if __cplusplus >= 201103L
1994  template<typename _Ptr>
1995  _GLIBCXX20_CONSTEXPR
1996  typename std::pointer_traits<_Ptr>::element_type*
1997  _M_data_ptr(_Ptr __ptr) const
1998  { return empty() ? nullptr : std::__to_address(__ptr); }
1999 #else
2000  template<typename _Up>
2001  _Up*
2002  _M_data_ptr(_Up* __ptr) _GLIBCXX_NOEXCEPT
2003  { return __ptr; }
2004 
2005  template<typename _Ptr>
2006  value_type*
2007  _M_data_ptr(_Ptr __ptr)
2008  { return empty() ? (value_type*)0 : __ptr.operator->(); }
2009 
2010  template<typename _Ptr>
2011  const value_type*
2012  _M_data_ptr(_Ptr __ptr) const
2013  { return empty() ? (const value_type*)0 : __ptr.operator->(); }
2014 #endif
2015  };
2016 
2017 #if __cpp_deduction_guides >= 201606
2018  template<typename _InputIterator, typename _ValT
2019  = typename iterator_traits<_InputIterator>::value_type,
2020  typename _Allocator = allocator<_ValT>,
2021  typename = _RequireInputIter<_InputIterator>,
2022  typename = _RequireAllocator<_Allocator>>
2023  vector(_InputIterator, _InputIterator, _Allocator = _Allocator())
2024  -> vector<_ValT, _Allocator>;
2025 #endif
2026 
2027  /**
2028  * @brief Vector equality comparison.
2029  * @param __x A %vector.
2030  * @param __y A %vector of the same type as @a __x.
2031  * @return True iff the size and elements of the vectors are equal.
2032  *
2033  * This is an equivalence relation. It is linear in the size of the
2034  * vectors. Vectors are considered equivalent if their sizes are equal,
2035  * and if corresponding elements compare equal.
2036  */
2037  template<typename _Tp, typename _Alloc>
2038  _GLIBCXX20_CONSTEXPR
2039  inline bool
2040  operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
2041  { return (__x.size() == __y.size()
2042  && std::equal(__x.begin(), __x.end(), __y.begin())); }
2043 
2044 #if __cpp_lib_three_way_comparison
2045  /**
2046  * @brief Vector ordering relation.
2047  * @param __x A `vector`.
2048  * @param __y A `vector` of the same type as `__x`.
2049  * @return A value indicating whether `__x` is less than, equal to,
2050  * greater than, or incomparable with `__y`.
2051  *
2052  * See `std::lexicographical_compare_three_way()` for how the determination
2053  * is made. This operator is used to synthesize relational operators like
2054  * `<` and `>=` etc.
2055  */
2056  template<typename _Tp, typename _Alloc>
2057  _GLIBCXX20_CONSTEXPR
2058  inline __detail::__synth3way_t<_Tp>
2059  operator<=>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
2060  {
2061  return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
2062  __y.begin(), __y.end(),
2063  __detail::__synth3way);
2064  }
2065 #else
2066  /**
2067  * @brief Vector ordering relation.
2068  * @param __x A %vector.
2069  * @param __y A %vector of the same type as @a __x.
2070  * @return True iff @a __x is lexicographically less than @a __y.
2071  *
2072  * This is a total ordering relation. It is linear in the size of the
2073  * vectors. The elements must be comparable with @c <.
2074  *
2075  * See std::lexicographical_compare() for how the determination is made.
2076  */
2077  template<typename _Tp, typename _Alloc>
2078  inline bool
2079  operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
2080  { return std::lexicographical_compare(__x.begin(), __x.end(),
2081  __y.begin(), __y.end()); }
2082 
2083  /// Based on operator==
2084  template<typename _Tp, typename _Alloc>
2085  inline bool
2086  operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
2087  { return !(__x == __y); }
2088 
2089  /// Based on operator<
2090  template<typename _Tp, typename _Alloc>
2091  inline bool
2092  operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
2093  { return __y < __x; }
2094 
2095  /// Based on operator<
2096  template<typename _Tp, typename _Alloc>
2097  inline bool
2098  operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
2099  { return !(__y < __x); }
2100 
2101  /// Based on operator<
2102  template<typename _Tp, typename _Alloc>
2103  inline bool
2104  operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
2105  { return !(__x < __y); }
2106 #endif // three-way comparison
2107 
2108  /// See std::vector::swap().
2109  template<typename _Tp, typename _Alloc>
2110  _GLIBCXX20_CONSTEXPR
2111  inline void
2113  _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
2114  { __x.swap(__y); }
2115 
2116 _GLIBCXX_END_NAMESPACE_CONTAINER
2117 
2118 #if __cplusplus >= 201703L
2119  namespace __detail::__variant
2120  {
2121  template<typename> struct _Never_valueless_alt; // see <variant>
2122 
2123  // Provide the strong exception-safety guarantee when emplacing a
2124  // vector into a variant, but only if move assignment cannot throw.
2125  template<typename _Tp, typename _Alloc>
2126  struct _Never_valueless_alt<_GLIBCXX_STD_C::vector<_Tp, _Alloc>>
2127  : std::is_nothrow_move_assignable<_GLIBCXX_STD_C::vector<_Tp, _Alloc>>
2128  { };
2129  } // namespace __detail::__variant
2130 #endif // C++17
2131 
2132 _GLIBCXX_END_NAMESPACE_VERSION
2133 } // namespace std
2134 
2135 #endif /* _STL_VECTOR_H */
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
Definition: type_traits:82
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
Definition: type_traits:85
constexpr bool is_constant_evaluated() noexcept
Returns true only when called during constant evaluation.
Definition: type_traits:3649
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:51
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:97
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
Definition: any:429
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:257
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:233
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
ISO C++ entities toplevel namespace is std.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
constexpr void _Destroy(_ForwardIterator __first, _ForwardIterator __last)
initializer_list
integral_constant
Definition: type_traits:63
is_same
Definition: type_traits:1399
is_nothrow_default_constructible
Definition: type_traits:1124
is_nothrow_move_assignable
Definition: type_traits:1210
The standard allocator, as per C++03 [20.4.1].
Definition: allocator.h:131
Marking input iterators.
Forward iterators support a superset of input iterator operations.
Random-access iterators support a superset of bidirectional iterator operations.
Common iterator class.
See bits/stl_deque.h's _Deque_base for an explanation.
Definition: stl_vector.h:86
A standard container which offers fixed time access to individual elements in any order.
Definition: stl_vector.h:429
constexpr iterator insert(const_iterator __position, const value_type &__x)
Inserts given value into vector before specified iterator.
Definition: vector.tcc:135
constexpr void push_back(const value_type &__x)
Add data to the end of the vector.
Definition: stl_vector.h:1281
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
constexpr reverse_iterator rbegin() noexcept
Definition: stl_vector.h:913
constexpr iterator end() noexcept
Definition: stl_vector.h:893
constexpr vector(const vector &__x)
Vector copy constructor.
Definition: stl_vector.h:601
vector()=default
Creates a vector with no elements.
constexpr iterator emplace(const_iterator __position, _Args &&... __args)
Inserts an object in vector before specified iterator.
Definition: stl_vector.h:1346
constexpr iterator insert(const_iterator __position, value_type &&__x)
Inserts given rvalue into vector before specified iterator.
Definition: stl_vector.h:1393
constexpr const_reverse_iterator rend() const noexcept
Definition: stl_vector.h:943
constexpr iterator begin() noexcept
Definition: stl_vector.h:873
constexpr size_type capacity() const noexcept
Definition: stl_vector.h:1078
constexpr iterator insert(const_iterator __position, initializer_list< value_type > __l)
Inserts an initializer_list into the vector.
Definition: stl_vector.h:1411
constexpr ~vector() noexcept
Definition: stl_vector.h:733
constexpr const_iterator begin() const noexcept
Definition: stl_vector.h:883
constexpr void assign(_InputIterator __first, _InputIterator __last)
Assigns a range to a vector.
Definition: stl_vector.h:828
constexpr void assign(size_type __n, const value_type &__val)
Assigns a given value to a vector.
Definition: stl_vector.h:808
constexpr iterator erase(const_iterator __first, const_iterator __last)
Remove a range of elements.
Definition: stl_vector.h:1562
constexpr void swap(vector &__x) noexcept
Swaps data with another vector.
Definition: stl_vector.h:1586
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
constexpr vector(size_type __n, const allocator_type &__a=allocator_type())
Creates a vector with default constructed elements.
Definition: stl_vector.h:556
constexpr const_reference front() const noexcept
Definition: stl_vector.h:1221
constexpr vector & operator=(initializer_list< value_type > __l)
Vector list assignment operator.
Definition: stl_vector.h:788
constexpr _Tp * data() noexcept
Definition: stl_vector.h:1260
constexpr void pop_back() noexcept
Removes last element.
Definition: stl_vector.h:1322
constexpr const_reference back() const noexcept
Definition: stl_vector.h:1245
constexpr void reserve(size_type __n)
Attempt to preallocate enough memory for specified number of elements.
Definition: vector.tcc:68
constexpr reference at(size_type __n)
Provides access to the data contained in the vector.
Definition: stl_vector.h:1178
constexpr void resize(size_type __new_size)
Resizes the vector to the specified number of elements.
Definition: stl_vector.h:1013
constexpr void _M_range_check(size_type __n) const
Safety check used only from at().
Definition: stl_vector.h:1155
constexpr reference front() noexcept
Definition: stl_vector.h:1209
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:1437
constexpr const_reference operator[](size_type __n) const noexcept
Subscript access to the data contained in the vector.
Definition: stl_vector.h:1145
constexpr vector(const allocator_type &__a) noexcept
Creates a vector with no elements.
Definition: stl_vector.h:542
constexpr iterator erase(const_iterator __position)
Remove element at given position.
Definition: stl_vector.h:1534
constexpr pointer _M_allocate_and_copy(size_type __n, _ForwardIterator __first, _ForwardIterator __last)
Definition: stl_vector.h:1616
constexpr bool empty() const noexcept
Definition: stl_vector.h:1088
constexpr reverse_iterator rend() noexcept
Definition: stl_vector.h:933
constexpr const_reverse_iterator rbegin() const noexcept
Definition: stl_vector.h:923
constexpr const_reverse_iterator crbegin() const noexcept
Definition: stl_vector.h:974
constexpr vector & operator=(vector &&__x) noexcept(_Alloc_traits::_S_nothrow_move())
Vector move assignment operator.
Definition: stl_vector.h:766
constexpr const_reference at(size_type __n) const
Provides access to the data contained in the vector.
Definition: stl_vector.h:1197
constexpr const_iterator cbegin() const noexcept
Definition: stl_vector.h:954
constexpr vector(_InputIterator __first, _InputIterator __last, const allocator_type &__a=allocator_type())
Builds a vector from a range.
Definition: stl_vector.h:707
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 const_iterator end() const noexcept
Definition: stl_vector.h:903
vector(vector &&) noexcept=default
Vector move constructor.
constexpr iterator insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
Inserts a range into the vector.
Definition: stl_vector.h:1482
constexpr void clear() noexcept
Definition: stl_vector.h:1605
constexpr void assign(initializer_list< value_type > __l)
Assigns an initializer list to a vector.
Definition: stl_vector.h:855
constexpr allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
Definition: stl_vector.h:311
constexpr size_type size() const noexcept
Definition: stl_vector.h:992
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 vector & operator=(const vector &__x)
Vector assignment operator.
Definition: vector.tcc:211
constexpr reference back() noexcept
Definition: stl_vector.h:1233
constexpr const_reverse_iterator crend() const noexcept
Definition: stl_vector.h:984
constexpr const_iterator cend() const noexcept
Definition: stl_vector.h:964
constexpr reference operator[](size_type __n) noexcept
Subscript access to the data contained in the vector.
Definition: stl_vector.h:1126
constexpr void shrink_to_fit()
Definition: stl_vector.h:1068
constexpr size_type max_size() const noexcept
Definition: stl_vector.h:998
Uniform interface to C++98 and C++11 allocators.
static constexpr size_type max_size(const _Tp_alloc_type &__a) noexcept
The maximum supported allocation size.