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