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 __use_relocate =
428  noexcept(std::__relocate_a(std::declval<pointer>(),
429  std::declval<pointer>(),
430  std::declval<pointer>(),
431  std::declval<_Tp_alloc_type&>()));
432 #endif
433 
434  protected:
435  using _Base::_M_allocate;
436  using _Base::_M_deallocate;
437  using _Base::_M_impl;
438  using _Base::_M_get_Tp_allocator;
439 
440  public:
441  // [23.2.4.1] construct/copy/destroy
442  // (assign() and get_allocator() are also listed in this section)
443 
444  /**
445  * @brief Creates a %vector with no elements.
446  */
447 #if __cplusplus >= 201103L
448  vector() = default;
449 #else
450  vector() { }
451 #endif
452 
453  /**
454  * @brief Creates a %vector with no elements.
455  * @param __a An allocator object.
456  */
457  explicit
458  vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT
459  : _Base(__a) { }
460 
461 #if __cplusplus >= 201103L
462  /**
463  * @brief Creates a %vector with default constructed elements.
464  * @param __n The number of elements to initially create.
465  * @param __a An allocator.
466  *
467  * This constructor fills the %vector with @a __n default
468  * constructed elements.
469  */
470  explicit
471  vector(size_type __n, const allocator_type& __a = allocator_type())
472  : _Base(_S_check_init_len(__n, __a), __a)
473  { _M_default_initialize(__n); }
474 
475  /**
476  * @brief Creates a %vector with copies of an exemplar element.
477  * @param __n The number of elements to initially create.
478  * @param __value An element to copy.
479  * @param __a An allocator.
480  *
481  * This constructor fills the %vector with @a __n copies of @a __value.
482  */
483  vector(size_type __n, const value_type& __value,
484  const allocator_type& __a = allocator_type())
485  : _Base(_S_check_init_len(__n, __a), __a)
486  { _M_fill_initialize(__n, __value); }
487 #else
488  /**
489  * @brief Creates a %vector with copies of an exemplar element.
490  * @param __n The number of elements to initially create.
491  * @param __value An element to copy.
492  * @param __a An allocator.
493  *
494  * This constructor fills the %vector with @a __n copies of @a __value.
495  */
496  explicit
497  vector(size_type __n, const value_type& __value = value_type(),
498  const allocator_type& __a = allocator_type())
499  : _Base(_S_check_init_len(__n, __a), __a)
500  { _M_fill_initialize(__n, __value); }
501 #endif
502 
503  /**
504  * @brief %Vector copy constructor.
505  * @param __x A %vector of identical element and allocator types.
506  *
507  * All the elements of @a __x are copied, but any unused capacity in
508  * @a __x will not be copied
509  * (i.e. capacity() == size() in the new %vector).
510  *
511  * The newly-created %vector uses a copy of the allocator object used
512  * by @a __x (unless the allocator traits dictate a different object).
513  */
514  vector(const vector& __x)
515  : _Base(__x.size(),
516  _Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()))
517  {
518  this->_M_impl._M_finish =
519  std::__uninitialized_copy_a(__x.begin(), __x.end(),
520  this->_M_impl._M_start,
521  _M_get_Tp_allocator());
522  }
523 
524 #if __cplusplus >= 201103L
525  /**
526  * @brief %Vector move constructor.
527  *
528  * The newly-created %vector contains the exact contents of the
529  * moved instance.
530  * The contents of the moved instance are a valid, but unspecified
531  * %vector.
532  */
533  vector(vector&&) noexcept = default;
534 
535  /// Copy constructor with alternative allocator
536  vector(const vector& __x, const allocator_type& __a)
537  : _Base(__x.size(), __a)
538  {
539  this->_M_impl._M_finish =
540  std::__uninitialized_copy_a(__x.begin(), __x.end(),
541  this->_M_impl._M_start,
542  _M_get_Tp_allocator());
543  }
544 
545  private:
546  vector(vector&& __rv, const allocator_type& __m, true_type) noexcept
547  : _Base(__m, std::move(__rv))
548  { }
549 
550  vector(vector&& __rv, const allocator_type& __m, false_type)
551  : _Base(__m)
552  {
553  if (__rv.get_allocator() == __m)
554  this->_M_impl._M_swap_data(__rv._M_impl);
555  else if (!__rv.empty())
556  {
557  this->_M_create_storage(__rv.size());
558  this->_M_impl._M_finish =
559  std::__uninitialized_move_a(__rv.begin(), __rv.end(),
560  this->_M_impl._M_start,
561  _M_get_Tp_allocator());
562  __rv.clear();
563  }
564  }
565 
566  public:
567  /// Move constructor with alternative allocator
568  vector(vector&& __rv, const allocator_type& __m)
569  noexcept( noexcept(
570  vector(std::declval<vector&&>(), std::declval<const allocator_type&>(),
571  std::declval<typename _Alloc_traits::is_always_equal>())) )
572  : vector(std::move(__rv), __m, typename _Alloc_traits::is_always_equal{})
573  { }
574 
575  /**
576  * @brief Builds a %vector from an initializer list.
577  * @param __l An initializer_list.
578  * @param __a An allocator.
579  *
580  * Create a %vector consisting of copies of the elements in the
581  * initializer_list @a __l.
582  *
583  * This will call the element type's copy constructor N times
584  * (where N is @a __l.size()) and do no memory reallocation.
585  */
587  const allocator_type& __a = allocator_type())
588  : _Base(__a)
589  {
590  _M_range_initialize(__l.begin(), __l.end(),
592  }
593 #endif
594 
595  /**
596  * @brief Builds a %vector from a range.
597  * @param __first An input iterator.
598  * @param __last An input iterator.
599  * @param __a An allocator.
600  *
601  * Create a %vector consisting of copies of the elements from
602  * [first,last).
603  *
604  * If the iterators are forward, bidirectional, or
605  * random-access, then this will call the elements' copy
606  * constructor N times (where N is distance(first,last)) and do
607  * no memory reallocation. But if only input iterators are
608  * used, then this will do at most 2N calls to the copy
609  * constructor, and logN memory reallocations.
610  */
611 #if __cplusplus >= 201103L
612  template<typename _InputIterator,
613  typename = std::_RequireInputIter<_InputIterator>>
614  vector(_InputIterator __first, _InputIterator __last,
615  const allocator_type& __a = allocator_type())
616  : _Base(__a)
617  {
618  _M_range_initialize(__first, __last,
619  std::__iterator_category(__first));
620  }
621 #else
622  template<typename _InputIterator>
623  vector(_InputIterator __first, _InputIterator __last,
624  const allocator_type& __a = allocator_type())
625  : _Base(__a)
626  {
627  // Check whether it's an integral type. If so, it's not an iterator.
628  typedef typename std::__is_integer<_InputIterator>::__type _Integral;
629  _M_initialize_dispatch(__first, __last, _Integral());
630  }
631 #endif
632 
633  /**
634  * The dtor only erases the elements, and note that if the
635  * elements themselves are pointers, the pointed-to memory is
636  * not touched in any way. Managing the pointer is the user's
637  * responsibility.
638  */
639  ~vector() _GLIBCXX_NOEXCEPT
640  {
641  std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
642  _M_get_Tp_allocator());
643  _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC;
644  }
645 
646  /**
647  * @brief %Vector assignment operator.
648  * @param __x A %vector of identical element and allocator types.
649  *
650  * All the elements of @a __x are copied, but any unused capacity in
651  * @a __x will not be copied.
652  *
653  * Whether the allocator is copied depends on the allocator traits.
654  */
655  vector&
656  operator=(const vector& __x);
657 
658 #if __cplusplus >= 201103L
659  /**
660  * @brief %Vector move assignment operator.
661  * @param __x A %vector of identical element and allocator types.
662  *
663  * The contents of @a __x are moved into this %vector (without copying,
664  * if the allocators permit it).
665  * Afterwards @a __x is a valid, but unspecified %vector.
666  *
667  * Whether the allocator is moved depends on the allocator traits.
668  */
669  vector&
670  operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
671  {
672  constexpr bool __move_storage =
673  _Alloc_traits::_S_propagate_on_move_assign()
674  || _Alloc_traits::_S_always_equal();
675  _M_move_assign(std::move(__x), __bool_constant<__move_storage>());
676  return *this;
677  }
678 
679  /**
680  * @brief %Vector list assignment operator.
681  * @param __l An initializer_list.
682  *
683  * This function fills a %vector with copies of the elements in the
684  * initializer list @a __l.
685  *
686  * Note that the assignment completely changes the %vector and
687  * that the resulting %vector's size is the same as the number
688  * of elements assigned.
689  */
690  vector&
692  {
693  this->_M_assign_aux(__l.begin(), __l.end(),
695  return *this;
696  }
697 #endif
698 
699  /**
700  * @brief Assigns a given value to a %vector.
701  * @param __n Number of elements to be assigned.
702  * @param __val Value to be assigned.
703  *
704  * This function fills a %vector with @a __n copies of the given
705  * value. Note that the assignment completely changes the
706  * %vector and that the resulting %vector's size is the same as
707  * the number of elements assigned.
708  */
709  void
710  assign(size_type __n, const value_type& __val)
711  { _M_fill_assign(__n, __val); }
712 
713  /**
714  * @brief Assigns a range to a %vector.
715  * @param __first An input iterator.
716  * @param __last An input iterator.
717  *
718  * This function fills a %vector with copies of the elements in the
719  * range [__first,__last).
720  *
721  * Note that the assignment completely changes the %vector and
722  * that the resulting %vector's size is the same as the number
723  * of elements assigned.
724  */
725 #if __cplusplus >= 201103L
726  template<typename _InputIterator,
727  typename = std::_RequireInputIter<_InputIterator>>
728  void
729  assign(_InputIterator __first, _InputIterator __last)
730  { _M_assign_dispatch(__first, __last, __false_type()); }
731 #else
732  template<typename _InputIterator>
733  void
734  assign(_InputIterator __first, _InputIterator __last)
735  {
736  // Check whether it's an integral type. If so, it's not an iterator.
737  typedef typename std::__is_integer<_InputIterator>::__type _Integral;
738  _M_assign_dispatch(__first, __last, _Integral());
739  }
740 #endif
741 
742 #if __cplusplus >= 201103L
743  /**
744  * @brief Assigns an initializer list to a %vector.
745  * @param __l An initializer_list.
746  *
747  * This function fills a %vector with copies of the elements in the
748  * initializer list @a __l.
749  *
750  * Note that the assignment completely changes the %vector and
751  * that the resulting %vector's size is the same as the number
752  * of elements assigned.
753  */
754  void
756  {
757  this->_M_assign_aux(__l.begin(), __l.end(),
759  }
760 #endif
761 
762  /// Get a copy of the memory allocation object.
763  using _Base::get_allocator;
764 
765  // iterators
766  /**
767  * Returns a read/write iterator that points to the first
768  * element in the %vector. Iteration is done in ordinary
769  * element order.
770  */
771  iterator
772  begin() _GLIBCXX_NOEXCEPT
773  { return iterator(this->_M_impl._M_start); }
774 
775  /**
776  * Returns a read-only (constant) iterator that points to the
777  * first element in the %vector. Iteration is done in ordinary
778  * element order.
779  */
780  const_iterator
781  begin() const _GLIBCXX_NOEXCEPT
782  { return const_iterator(this->_M_impl._M_start); }
783 
784  /**
785  * Returns a read/write iterator that points one past the last
786  * element in the %vector. Iteration is done in ordinary
787  * element order.
788  */
789  iterator
790  end() _GLIBCXX_NOEXCEPT
791  { return iterator(this->_M_impl._M_finish); }
792 
793  /**
794  * Returns a read-only (constant) iterator that points one past
795  * the last element in the %vector. Iteration is done in
796  * ordinary element order.
797  */
798  const_iterator
799  end() const _GLIBCXX_NOEXCEPT
800  { return const_iterator(this->_M_impl._M_finish); }
801 
802  /**
803  * Returns a read/write reverse iterator that points to the
804  * last element in the %vector. Iteration is done in reverse
805  * element order.
806  */
807  reverse_iterator
808  rbegin() _GLIBCXX_NOEXCEPT
809  { return reverse_iterator(end()); }
810 
811  /**
812  * Returns a read-only (constant) reverse iterator that points
813  * to the last element in the %vector. Iteration is done in
814  * reverse element order.
815  */
816  const_reverse_iterator
817  rbegin() const _GLIBCXX_NOEXCEPT
818  { return const_reverse_iterator(end()); }
819 
820  /**
821  * Returns a read/write reverse iterator that points to one
822  * before the first element in the %vector. Iteration is done
823  * in reverse element order.
824  */
825  reverse_iterator
826  rend() _GLIBCXX_NOEXCEPT
827  { return reverse_iterator(begin()); }
828 
829  /**
830  * Returns a read-only (constant) reverse iterator that points
831  * to one before the first element in the %vector. Iteration
832  * is done in reverse element order.
833  */
834  const_reverse_iterator
835  rend() const _GLIBCXX_NOEXCEPT
836  { return const_reverse_iterator(begin()); }
837 
838 #if __cplusplus >= 201103L
839  /**
840  * Returns a read-only (constant) iterator that points to the
841  * first element in the %vector. Iteration is done in ordinary
842  * element order.
843  */
844  const_iterator
845  cbegin() const noexcept
846  { return const_iterator(this->_M_impl._M_start); }
847 
848  /**
849  * Returns a read-only (constant) iterator that points one past
850  * the last element in the %vector. Iteration is done in
851  * ordinary element order.
852  */
853  const_iterator
854  cend() const noexcept
855  { return const_iterator(this->_M_impl._M_finish); }
856 
857  /**
858  * Returns a read-only (constant) reverse iterator that points
859  * to the last element in the %vector. Iteration is done in
860  * reverse element order.
861  */
862  const_reverse_iterator
863  crbegin() const noexcept
864  { return const_reverse_iterator(end()); }
865 
866  /**
867  * Returns a read-only (constant) reverse iterator that points
868  * to one before the first element in the %vector. Iteration
869  * is done in reverse element order.
870  */
871  const_reverse_iterator
872  crend() const noexcept
873  { return const_reverse_iterator(begin()); }
874 #endif
875 
876  // [23.2.4.2] capacity
877  /** Returns the number of elements in the %vector. */
878  size_type
879  size() const _GLIBCXX_NOEXCEPT
880  { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
881 
882  /** Returns the size() of the largest possible %vector. */
883  size_type
884  max_size() const _GLIBCXX_NOEXCEPT
885  { return _S_max_size(_M_get_Tp_allocator()); }
886 
887 #if __cplusplus >= 201103L
888  /**
889  * @brief Resizes the %vector to the specified number of elements.
890  * @param __new_size Number of elements the %vector should contain.
891  *
892  * This function will %resize the %vector to the specified
893  * number of elements. If the number is smaller than the
894  * %vector's current size the %vector is truncated, otherwise
895  * default constructed elements are appended.
896  */
897  void
898  resize(size_type __new_size)
899  {
900  if (__new_size > size())
901  _M_default_append(__new_size - size());
902  else if (__new_size < size())
903  _M_erase_at_end(this->_M_impl._M_start + __new_size);
904  }
905 
906  /**
907  * @brief Resizes the %vector to the specified number of elements.
908  * @param __new_size Number of elements the %vector should contain.
909  * @param __x Data with which new elements should be populated.
910  *
911  * This function will %resize the %vector to the specified
912  * number of elements. If the number is smaller than the
913  * %vector's current size the %vector is truncated, otherwise
914  * the %vector is extended and new elements are populated with
915  * given data.
916  */
917  void
918  resize(size_type __new_size, const value_type& __x)
919  {
920  if (__new_size > size())
921  _M_fill_insert(end(), __new_size - size(), __x);
922  else if (__new_size < size())
923  _M_erase_at_end(this->_M_impl._M_start + __new_size);
924  }
925 #else
926  /**
927  * @brief Resizes the %vector to the specified number of elements.
928  * @param __new_size Number of elements the %vector should contain.
929  * @param __x Data with which new elements should be populated.
930  *
931  * This function will %resize the %vector to the specified
932  * number of elements. If the number is smaller than the
933  * %vector's current size the %vector is truncated, otherwise
934  * the %vector is extended and new elements are populated with
935  * given data.
936  */
937  void
938  resize(size_type __new_size, value_type __x = value_type())
939  {
940  if (__new_size > size())
941  _M_fill_insert(end(), __new_size - size(), __x);
942  else if (__new_size < size())
943  _M_erase_at_end(this->_M_impl._M_start + __new_size);
944  }
945 #endif
946 
947 #if __cplusplus >= 201103L
948  /** A non-binding request to reduce capacity() to size(). */
949  void
951  { _M_shrink_to_fit(); }
952 #endif
953 
954  /**
955  * Returns the total number of elements that the %vector can
956  * hold before needing to allocate more memory.
957  */
958  size_type
959  capacity() const _GLIBCXX_NOEXCEPT
960  { return size_type(this->_M_impl._M_end_of_storage
961  - this->_M_impl._M_start); }
962 
963  /**
964  * Returns true if the %vector is empty. (Thus begin() would
965  * equal end().)
966  */
967  bool
968  empty() const _GLIBCXX_NOEXCEPT
969  { return begin() == end(); }
970 
971  /**
972  * @brief Attempt to preallocate enough memory for specified number of
973  * elements.
974  * @param __n Number of elements required.
975  * @throw std::length_error If @a n exceeds @c max_size().
976  *
977  * This function attempts to reserve enough memory for the
978  * %vector to hold the specified number of elements. If the
979  * number requested is more than max_size(), length_error is
980  * thrown.
981  *
982  * The advantage of this function is that if optimal code is a
983  * necessity and the user can determine the number of elements
984  * that will be required, the user can reserve the memory in
985  * %advance, and thus prevent a possible reallocation of memory
986  * and copying of %vector data.
987  */
988  void
989  reserve(size_type __n);
990 
991  // element access
992  /**
993  * @brief Subscript access to the data contained in the %vector.
994  * @param __n The index of the element for which data should be
995  * accessed.
996  * @return Read/write reference to data.
997  *
998  * This operator allows for easy, array-style, data access.
999  * Note that data access with this operator is unchecked and
1000  * out_of_range lookups are not defined. (For checked lookups
1001  * see at().)
1002  */
1003  reference
1004  operator[](size_type __n) _GLIBCXX_NOEXCEPT
1005  {
1006  __glibcxx_requires_subscript(__n);
1007  return *(this->_M_impl._M_start + __n);
1008  }
1009 
1010  /**
1011  * @brief Subscript access to the data contained in the %vector.
1012  * @param __n The index of the element for which data should be
1013  * accessed.
1014  * @return Read-only (constant) reference to data.
1015  *
1016  * This operator allows for easy, array-style, data access.
1017  * Note that data access with this operator is unchecked and
1018  * out_of_range lookups are not defined. (For checked lookups
1019  * see at().)
1020  */
1021  const_reference
1022  operator[](size_type __n) const _GLIBCXX_NOEXCEPT
1023  {
1024  __glibcxx_requires_subscript(__n);
1025  return *(this->_M_impl._M_start + __n);
1026  }
1027 
1028  protected:
1029  /// Safety check used only from at().
1030  void
1031  _M_range_check(size_type __n) const
1032  {
1033  if (__n >= this->size())
1034  __throw_out_of_range_fmt(__N("vector::_M_range_check: __n "
1035  "(which is %zu) >= this->size() "
1036  "(which is %zu)"),
1037  __n, this->size());
1038  }
1039 
1040  public:
1041  /**
1042  * @brief Provides access to the data contained in the %vector.
1043  * @param __n The index of the element for which data should be
1044  * accessed.
1045  * @return Read/write reference to data.
1046  * @throw std::out_of_range If @a __n is an invalid index.
1047  *
1048  * This function provides for safer data access. The parameter
1049  * is first checked that it is in the range of the vector. The
1050  * function throws out_of_range if the check fails.
1051  */
1052  reference
1053  at(size_type __n)
1054  {
1055  _M_range_check(__n);
1056  return (*this)[__n];
1057  }
1058 
1059  /**
1060  * @brief Provides access to the data contained in the %vector.
1061  * @param __n The index of the element for which data should be
1062  * accessed.
1063  * @return Read-only (constant) reference to data.
1064  * @throw std::out_of_range If @a __n is an invalid index.
1065  *
1066  * This function provides for safer data access. The parameter
1067  * is first checked that it is in the range of the vector. The
1068  * function throws out_of_range if the check fails.
1069  */
1070  const_reference
1071  at(size_type __n) const
1072  {
1073  _M_range_check(__n);
1074  return (*this)[__n];
1075  }
1076 
1077  /**
1078  * Returns a read/write reference to the data at the first
1079  * element of the %vector.
1080  */
1081  reference
1082  front() _GLIBCXX_NOEXCEPT
1083  {
1084  __glibcxx_requires_nonempty();
1085  return *begin();
1086  }
1087 
1088  /**
1089  * Returns a read-only (constant) reference to the data at the first
1090  * element of the %vector.
1091  */
1092  const_reference
1093  front() const _GLIBCXX_NOEXCEPT
1094  {
1095  __glibcxx_requires_nonempty();
1096  return *begin();
1097  }
1098 
1099  /**
1100  * Returns a read/write reference to the data at the last
1101  * element of the %vector.
1102  */
1103  reference
1104  back() _GLIBCXX_NOEXCEPT
1105  {
1106  __glibcxx_requires_nonempty();
1107  return *(end() - 1);
1108  }
1109 
1110  /**
1111  * Returns a read-only (constant) reference to the data at the
1112  * last element of the %vector.
1113  */
1114  const_reference
1115  back() const _GLIBCXX_NOEXCEPT
1116  {
1117  __glibcxx_requires_nonempty();
1118  return *(end() - 1);
1119  }
1120 
1121  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1122  // DR 464. Suggestion for new member functions in standard containers.
1123  // data access
1124  /**
1125  * Returns a pointer such that [data(), data() + size()) is a valid
1126  * range. For a non-empty %vector, data() == &front().
1127  */
1128  _Tp*
1129  data() _GLIBCXX_NOEXCEPT
1130  { return _M_data_ptr(this->_M_impl._M_start); }
1131 
1132  const _Tp*
1133  data() const _GLIBCXX_NOEXCEPT
1134  { return _M_data_ptr(this->_M_impl._M_start); }
1135 
1136  // [23.2.4.3] modifiers
1137  /**
1138  * @brief Add data to the end of the %vector.
1139  * @param __x Data to be added.
1140  *
1141  * This is a typical stack operation. The function creates an
1142  * element at the end of the %vector and assigns the given data
1143  * to it. Due to the nature of a %vector this operation can be
1144  * done in constant time if the %vector has preallocated space
1145  * available.
1146  */
1147  void
1148  push_back(const value_type& __x)
1149  {
1150  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
1151  {
1152  _GLIBCXX_ASAN_ANNOTATE_GROW(1);
1153  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
1154  __x);
1155  ++this->_M_impl._M_finish;
1156  _GLIBCXX_ASAN_ANNOTATE_GREW(1);
1157  }
1158  else
1159  _M_realloc_insert(end(), __x);
1160  }
1161 
1162 #if __cplusplus >= 201103L
1163  void
1164  push_back(value_type&& __x)
1165  { emplace_back(std::move(__x)); }
1166 
1167  template<typename... _Args>
1168 #if __cplusplus > 201402L
1169  reference
1170 #else
1171  void
1172 #endif
1173  emplace_back(_Args&&... __args);
1174 #endif
1175 
1176  /**
1177  * @brief Removes last element.
1178  *
1179  * This is a typical stack operation. It shrinks the %vector by one.
1180  *
1181  * Note that no data is returned, and if the last element's
1182  * data is needed, it should be retrieved before pop_back() is
1183  * called.
1184  */
1185  void
1186  pop_back() _GLIBCXX_NOEXCEPT
1187  {
1188  __glibcxx_requires_nonempty();
1189  --this->_M_impl._M_finish;
1190  _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
1191  _GLIBCXX_ASAN_ANNOTATE_SHRINK(1);
1192  }
1193 
1194 #if __cplusplus >= 201103L
1195  /**
1196  * @brief Inserts an object in %vector before specified iterator.
1197  * @param __position A const_iterator into the %vector.
1198  * @param __args Arguments.
1199  * @return An iterator that points to the inserted data.
1200  *
1201  * This function will insert an object of type T constructed
1202  * with T(std::forward<Args>(args)...) before the specified location.
1203  * Note that this kind of operation could be expensive for a %vector
1204  * and if it is frequently used the user should consider using
1205  * std::list.
1206  */
1207  template<typename... _Args>
1208  iterator
1209  emplace(const_iterator __position, _Args&&... __args)
1210  { return _M_emplace_aux(__position, std::forward<_Args>(__args)...); }
1211 
1212  /**
1213  * @brief Inserts given value into %vector before specified iterator.
1214  * @param __position A const_iterator into the %vector.
1215  * @param __x Data to be inserted.
1216  * @return An iterator that points to the inserted data.
1217  *
1218  * This function will insert a copy of the given value before
1219  * the specified location. Note that this kind of operation
1220  * could be expensive for a %vector and if it is frequently
1221  * used the user should consider using std::list.
1222  */
1223  iterator
1224  insert(const_iterator __position, const value_type& __x);
1225 #else
1226  /**
1227  * @brief Inserts given value into %vector before specified iterator.
1228  * @param __position An iterator into the %vector.
1229  * @param __x Data to be inserted.
1230  * @return An iterator that points to the inserted data.
1231  *
1232  * This function will insert a copy of the given value before
1233  * the specified location. Note that this kind of operation
1234  * could be expensive for a %vector and if it is frequently
1235  * used the user should consider using std::list.
1236  */
1237  iterator
1238  insert(iterator __position, const value_type& __x);
1239 #endif
1240 
1241 #if __cplusplus >= 201103L
1242  /**
1243  * @brief Inserts given rvalue into %vector before specified iterator.
1244  * @param __position A const_iterator into the %vector.
1245  * @param __x Data to be inserted.
1246  * @return An iterator that points to the inserted data.
1247  *
1248  * This function will insert a copy of the given rvalue before
1249  * the specified location. Note that this kind of operation
1250  * could be expensive for a %vector and if it is frequently
1251  * used the user should consider using std::list.
1252  */
1253  iterator
1254  insert(const_iterator __position, value_type&& __x)
1255  { return _M_insert_rval(__position, std::move(__x)); }
1256 
1257  /**
1258  * @brief Inserts an initializer_list into the %vector.
1259  * @param __position An iterator into the %vector.
1260  * @param __l An initializer_list.
1261  *
1262  * This function will insert copies of the data in the
1263  * initializer_list @a l into the %vector before the location
1264  * specified by @a position.
1265  *
1266  * Note that this kind of operation could be expensive for a
1267  * %vector and if it is frequently used the user should
1268  * consider using std::list.
1269  */
1270  iterator
1271  insert(const_iterator __position, initializer_list<value_type> __l)
1272  {
1273  auto __offset = __position - cbegin();
1274  _M_range_insert(begin() + __offset, __l.begin(), __l.end(),
1276  return begin() + __offset;
1277  }
1278 #endif
1279 
1280 #if __cplusplus >= 201103L
1281  /**
1282  * @brief Inserts a number of copies of given data into the %vector.
1283  * @param __position A const_iterator into the %vector.
1284  * @param __n Number of elements to be inserted.
1285  * @param __x Data to be inserted.
1286  * @return An iterator that points to the inserted data.
1287  *
1288  * This function will insert a specified number of copies of
1289  * the given data before the location specified by @a position.
1290  *
1291  * Note that this kind of operation could be expensive for a
1292  * %vector and if it is frequently used the user should
1293  * consider using std::list.
1294  */
1295  iterator
1296  insert(const_iterator __position, size_type __n, const value_type& __x)
1297  {
1298  difference_type __offset = __position - cbegin();
1299  _M_fill_insert(begin() + __offset, __n, __x);
1300  return begin() + __offset;
1301  }
1302 #else
1303  /**
1304  * @brief Inserts a number of copies of given data into the %vector.
1305  * @param __position An iterator into the %vector.
1306  * @param __n Number of elements to be inserted.
1307  * @param __x Data to be inserted.
1308  *
1309  * This function will insert a specified number of copies of
1310  * the given data before the location specified by @a position.
1311  *
1312  * Note that this kind of operation could be expensive for a
1313  * %vector and if it is frequently used the user should
1314  * consider using std::list.
1315  */
1316  void
1317  insert(iterator __position, size_type __n, const value_type& __x)
1318  { _M_fill_insert(__position, __n, __x); }
1319 #endif
1320 
1321 #if __cplusplus >= 201103L
1322  /**
1323  * @brief Inserts a range into the %vector.
1324  * @param __position A const_iterator into the %vector.
1325  * @param __first An input iterator.
1326  * @param __last An input iterator.
1327  * @return An iterator that points to the inserted data.
1328  *
1329  * This function will insert copies of the data in the range
1330  * [__first,__last) into the %vector before the location specified
1331  * by @a pos.
1332  *
1333  * Note that this kind of operation could be expensive for a
1334  * %vector and if it is frequently used the user should
1335  * consider using std::list.
1336  */
1337  template<typename _InputIterator,
1338  typename = std::_RequireInputIter<_InputIterator>>
1339  iterator
1340  insert(const_iterator __position, _InputIterator __first,
1341  _InputIterator __last)
1342  {
1343  difference_type __offset = __position - cbegin();
1344  _M_insert_dispatch(begin() + __offset,
1345  __first, __last, __false_type());
1346  return begin() + __offset;
1347  }
1348 #else
1349  /**
1350  * @brief Inserts a range into the %vector.
1351  * @param __position An iterator into the %vector.
1352  * @param __first An input iterator.
1353  * @param __last An input iterator.
1354  *
1355  * This function will insert copies of the data in the range
1356  * [__first,__last) into the %vector before the location specified
1357  * by @a pos.
1358  *
1359  * Note that this kind of operation could be expensive for a
1360  * %vector and if it is frequently used the user should
1361  * consider using std::list.
1362  */
1363  template<typename _InputIterator>
1364  void
1365  insert(iterator __position, _InputIterator __first,
1366  _InputIterator __last)
1367  {
1368  // Check whether it's an integral type. If so, it's not an iterator.
1369  typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1370  _M_insert_dispatch(__position, __first, __last, _Integral());
1371  }
1372 #endif
1373 
1374  /**
1375  * @brief Remove element at given position.
1376  * @param __position Iterator pointing to element to be erased.
1377  * @return An iterator pointing to the next element (or end()).
1378  *
1379  * This function will erase the element at the given position and thus
1380  * shorten the %vector by one.
1381  *
1382  * Note This operation could be expensive and if it is
1383  * frequently used the user should consider using std::list.
1384  * The user is also cautioned that this function only erases
1385  * the element, and that if the element is itself a pointer,
1386  * the pointed-to memory is not touched in any way. Managing
1387  * the pointer is the user's responsibility.
1388  */
1389  iterator
1390 #if __cplusplus >= 201103L
1391  erase(const_iterator __position)
1392  { return _M_erase(begin() + (__position - cbegin())); }
1393 #else
1394  erase(iterator __position)
1395  { return _M_erase(__position); }
1396 #endif
1397 
1398  /**
1399  * @brief Remove a range of elements.
1400  * @param __first Iterator pointing to the first element to be erased.
1401  * @param __last Iterator pointing to one past the last element to be
1402  * erased.
1403  * @return An iterator pointing to the element pointed to by @a __last
1404  * prior to erasing (or end()).
1405  *
1406  * This function will erase the elements in the range
1407  * [__first,__last) and shorten the %vector accordingly.
1408  *
1409  * Note This operation could be expensive and if it is
1410  * frequently used the user should consider using std::list.
1411  * The user is also cautioned that this function only erases
1412  * the elements, and that if the elements themselves are
1413  * pointers, the pointed-to memory is not touched in any way.
1414  * Managing the pointer is the user's responsibility.
1415  */
1416  iterator
1417 #if __cplusplus >= 201103L
1418  erase(const_iterator __first, const_iterator __last)
1419  {
1420  const auto __beg = begin();
1421  const auto __cbeg = cbegin();
1422  return _M_erase(__beg + (__first - __cbeg), __beg + (__last - __cbeg));
1423  }
1424 #else
1425  erase(iterator __first, iterator __last)
1426  { return _M_erase(__first, __last); }
1427 #endif
1428 
1429  /**
1430  * @brief Swaps data with another %vector.
1431  * @param __x A %vector of the same element and allocator types.
1432  *
1433  * This exchanges the elements between two vectors in constant time.
1434  * (Three pointers, so it should be quite fast.)
1435  * Note that the global std::swap() function is specialized such that
1436  * std::swap(v1,v2) will feed to this function.
1437  *
1438  * Whether the allocators are swapped depends on the allocator traits.
1439  */
1440  void
1441  swap(vector& __x) _GLIBCXX_NOEXCEPT
1442  {
1443 #if __cplusplus >= 201103L
1444  __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value
1445  || _M_get_Tp_allocator() == __x._M_get_Tp_allocator());
1446 #endif
1447  this->_M_impl._M_swap_data(__x._M_impl);
1448  _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1449  __x._M_get_Tp_allocator());
1450  }
1451 
1452  /**
1453  * Erases all the elements. Note that this function only erases the
1454  * elements, and that if the elements themselves are pointers, the
1455  * pointed-to memory is not touched in any way. Managing the pointer is
1456  * the user's responsibility.
1457  */
1458  void
1459  clear() _GLIBCXX_NOEXCEPT
1460  { _M_erase_at_end(this->_M_impl._M_start); }
1461 
1462  protected:
1463  /**
1464  * Memory expansion handler. Uses the member allocation function to
1465  * obtain @a n bytes of memory, and then copies [first,last) into it.
1466  */
1467  template<typename _ForwardIterator>
1468  pointer
1469  _M_allocate_and_copy(size_type __n,
1470  _ForwardIterator __first, _ForwardIterator __last)
1471  {
1472  pointer __result = this->_M_allocate(__n);
1473  __try
1474  {
1475  std::__uninitialized_copy_a(__first, __last, __result,
1476  _M_get_Tp_allocator());
1477  return __result;
1478  }
1479  __catch(...)
1480  {
1481  _M_deallocate(__result, __n);
1482  __throw_exception_again;
1483  }
1484  }
1485 
1486 
1487  // Internal constructor functions follow.
1488 
1489  // Called by the range constructor to implement [23.1.1]/9
1490 
1491 #if __cplusplus < 201103L
1492  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1493  // 438. Ambiguity in the "do the right thing" clause
1494  template<typename _Integer>
1495  void
1496  _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type)
1497  {
1498  this->_M_impl._M_start = _M_allocate(_S_check_init_len(
1499  static_cast<size_type>(__n), _M_get_Tp_allocator()));
1500  this->_M_impl._M_end_of_storage =
1501  this->_M_impl._M_start + static_cast<size_type>(__n);
1502  _M_fill_initialize(static_cast<size_type>(__n), __value);
1503  }
1504 
1505  // Called by the range constructor to implement [23.1.1]/9
1506  template<typename _InputIterator>
1507  void
1508  _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1509  __false_type)
1510  {
1511  _M_range_initialize(__first, __last,
1512  std::__iterator_category(__first));
1513  }
1514 #endif
1515 
1516  // Called by the second initialize_dispatch above
1517  template<typename _InputIterator>
1518  void
1519  _M_range_initialize(_InputIterator __first, _InputIterator __last,
1521  {
1522  __try {
1523  for (; __first != __last; ++__first)
1524 #if __cplusplus >= 201103L
1525  emplace_back(*__first);
1526 #else
1527  push_back(*__first);
1528 #endif
1529  } __catch(...) {
1530  clear();
1531  __throw_exception_again;
1532  }
1533  }
1534 
1535  // Called by the second initialize_dispatch above
1536  template<typename _ForwardIterator>
1537  void
1538  _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
1540  {
1541  const size_type __n = std::distance(__first, __last);
1542  this->_M_impl._M_start
1543  = this->_M_allocate(_S_check_init_len(__n, _M_get_Tp_allocator()));
1544  this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
1545  this->_M_impl._M_finish =
1546  std::__uninitialized_copy_a(__first, __last,
1547  this->_M_impl._M_start,
1548  _M_get_Tp_allocator());
1549  }
1550 
1551  // Called by the first initialize_dispatch above and by the
1552  // vector(n,value,a) constructor.
1553  void
1554  _M_fill_initialize(size_type __n, const value_type& __value)
1555  {
1556  this->_M_impl._M_finish =
1557  std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
1558  _M_get_Tp_allocator());
1559  }
1560 
1561 #if __cplusplus >= 201103L
1562  // Called by the vector(n) constructor.
1563  void
1564  _M_default_initialize(size_type __n)
1565  {
1566  this->_M_impl._M_finish =
1567  std::__uninitialized_default_n_a(this->_M_impl._M_start, __n,
1568  _M_get_Tp_allocator());
1569  }
1570 #endif
1571 
1572  // Internal assign functions follow. The *_aux functions do the actual
1573  // assignment work for the range versions.
1574 
1575  // Called by the range assign to implement [23.1.1]/9
1576 
1577  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1578  // 438. Ambiguity in the "do the right thing" clause
1579  template<typename _Integer>
1580  void
1581  _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1582  { _M_fill_assign(__n, __val); }
1583 
1584  // Called by the range assign to implement [23.1.1]/9
1585  template<typename _InputIterator>
1586  void
1587  _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1588  __false_type)
1589  { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
1590 
1591  // Called by the second assign_dispatch above
1592  template<typename _InputIterator>
1593  void
1594  _M_assign_aux(_InputIterator __first, _InputIterator __last,
1596 
1597  // Called by the second assign_dispatch above
1598  template<typename _ForwardIterator>
1599  void
1600  _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1602 
1603  // Called by assign(n,t), and the range assign when it turns out
1604  // to be the same thing.
1605  void
1606  _M_fill_assign(size_type __n, const value_type& __val);
1607 
1608  // Internal insert functions follow.
1609 
1610  // Called by the range insert to implement [23.1.1]/9
1611 
1612  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1613  // 438. Ambiguity in the "do the right thing" clause
1614  template<typename _Integer>
1615  void
1616  _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
1617  __true_type)
1618  { _M_fill_insert(__pos, __n, __val); }
1619 
1620  // Called by the range insert to implement [23.1.1]/9
1621  template<typename _InputIterator>
1622  void
1623  _M_insert_dispatch(iterator __pos, _InputIterator __first,
1624  _InputIterator __last, __false_type)
1625  {
1626  _M_range_insert(__pos, __first, __last,
1627  std::__iterator_category(__first));
1628  }
1629 
1630  // Called by the second insert_dispatch above
1631  template<typename _InputIterator>
1632  void
1633  _M_range_insert(iterator __pos, _InputIterator __first,
1634  _InputIterator __last, std::input_iterator_tag);
1635 
1636  // Called by the second insert_dispatch above
1637  template<typename _ForwardIterator>
1638  void
1639  _M_range_insert(iterator __pos, _ForwardIterator __first,
1640  _ForwardIterator __last, std::forward_iterator_tag);
1641 
1642  // Called by insert(p,n,x), and the range insert when it turns out to be
1643  // the same thing.
1644  void
1645  _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
1646 
1647 #if __cplusplus >= 201103L
1648  // Called by resize(n).
1649  void
1650  _M_default_append(size_type __n);
1651 
1652  bool
1653  _M_shrink_to_fit();
1654 #endif
1655 
1656 #if __cplusplus < 201103L
1657  // Called by insert(p,x)
1658  void
1659  _M_insert_aux(iterator __position, const value_type& __x);
1660 
1661  void
1662  _M_realloc_insert(iterator __position, const value_type& __x);
1663 #else
1664  // A value_type object constructed with _Alloc_traits::construct()
1665  // and destroyed with _Alloc_traits::destroy().
1666  struct _Temporary_value
1667  {
1668  template<typename... _Args>
1669  explicit
1670  _Temporary_value(vector* __vec, _Args&&... __args) : _M_this(__vec)
1671  {
1672  _Alloc_traits::construct(_M_this->_M_impl, _M_ptr(),
1673  std::forward<_Args>(__args)...);
1674  }
1675 
1676  ~_Temporary_value()
1677  { _Alloc_traits::destroy(_M_this->_M_impl, _M_ptr()); }
1678 
1679  value_type&
1680  _M_val() { return *_M_ptr(); }
1681 
1682  private:
1683  _Tp*
1684  _M_ptr() { return reinterpret_cast<_Tp*>(&__buf); }
1685 
1686  vector* _M_this;
1688  };
1689 
1690  // Called by insert(p,x) and other functions when insertion needs to
1691  // reallocate or move existing elements. _Arg is either _Tp& or _Tp.
1692  template<typename _Arg>
1693  void
1694  _M_insert_aux(iterator __position, _Arg&& __arg);
1695 
1696  template<typename... _Args>
1697  void
1698  _M_realloc_insert(iterator __position, _Args&&... __args);
1699 
1700  // Either move-construct at the end, or forward to _M_insert_aux.
1701  iterator
1702  _M_insert_rval(const_iterator __position, value_type&& __v);
1703 
1704  // Try to emplace at the end, otherwise forward to _M_insert_aux.
1705  template<typename... _Args>
1706  iterator
1707  _M_emplace_aux(const_iterator __position, _Args&&... __args);
1708 
1709  // Emplacing an rvalue of the correct type can use _M_insert_rval.
1710  iterator
1711  _M_emplace_aux(const_iterator __position, value_type&& __v)
1712  { return _M_insert_rval(__position, std::move(__v)); }
1713 #endif
1714 
1715  // Called by _M_fill_insert, _M_insert_aux etc.
1716  size_type
1717  _M_check_len(size_type __n, const char* __s) const
1718  {
1719  if (max_size() - size() < __n)
1720  __throw_length_error(__N(__s));
1721 
1722  const size_type __len = size() + (std::max)(size(), __n);
1723  return (__len < size() || __len > max_size()) ? max_size() : __len;
1724  }
1725 
1726  // Called by constructors to check initial size.
1727  static size_type
1728  _S_check_init_len(size_type __n, const allocator_type& __a)
1729  {
1730  if (__n > _S_max_size(_Tp_alloc_type(__a)))
1731  __throw_length_error(
1732  __N("cannot create std::vector larger than max_size()"));
1733  return __n;
1734  }
1735 
1736  static size_type
1737  _S_max_size(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
1738  {
1739  // std::distance(begin(), end()) cannot be greater than PTRDIFF_MAX,
1740  // and realistically we can't store more than PTRDIFF_MAX/sizeof(T)
1741  // (even if std::allocator_traits::max_size says we can).
1742  const size_t __diffmax
1743  = __gnu_cxx::__numeric_traits<ptrdiff_t>::__max / sizeof(_Tp);
1744  const size_t __allocmax = _Alloc_traits::max_size(__a);
1745  return (std::min)(__diffmax, __allocmax);
1746  }
1747 
1748  // Internal erase functions follow.
1749 
1750  // Called by erase(q1,q2), clear(), resize(), _M_fill_assign,
1751  // _M_assign_aux.
1752  void
1753  _M_erase_at_end(pointer __pos) _GLIBCXX_NOEXCEPT
1754  {
1755  if (size_type __n = this->_M_impl._M_finish - __pos)
1756  {
1757  std::_Destroy(__pos, this->_M_impl._M_finish,
1758  _M_get_Tp_allocator());
1759  this->_M_impl._M_finish = __pos;
1760  _GLIBCXX_ASAN_ANNOTATE_SHRINK(__n);
1761  }
1762  }
1763 
1764  iterator
1765  _M_erase(iterator __position);
1766 
1767  iterator
1768  _M_erase(iterator __first, iterator __last);
1769 
1770 #if __cplusplus >= 201103L
1771  private:
1772  // Constant-time move assignment when source object's memory can be
1773  // moved, either because the source's allocator will move too
1774  // or because the allocators are equal.
1775  void
1776  _M_move_assign(vector&& __x, true_type) noexcept
1777  {
1778  vector __tmp(get_allocator());
1779  this->_M_impl._M_swap_data(__x._M_impl);
1780  __tmp._M_impl._M_swap_data(__x._M_impl);
1781  std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
1782  }
1783 
1784  // Do move assignment when it might not be possible to move source
1785  // object's memory, resulting in a linear-time operation.
1786  void
1787  _M_move_assign(vector&& __x, false_type)
1788  {
1789  if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
1790  _M_move_assign(std::move(__x), true_type());
1791  else
1792  {
1793  // The rvalue's allocator cannot be moved and is not equal,
1794  // so we need to individually move each element.
1795  this->assign(std::__make_move_if_noexcept_iterator(__x.begin()),
1796  std::__make_move_if_noexcept_iterator(__x.end()));
1797  __x.clear();
1798  }
1799  }
1800 #endif
1801 
1802  template<typename _Up>
1803  _Up*
1804  _M_data_ptr(_Up* __ptr) const _GLIBCXX_NOEXCEPT
1805  { return __ptr; }
1806 
1807 #if __cplusplus >= 201103L
1808  template<typename _Ptr>
1810  _M_data_ptr(_Ptr __ptr) const
1811  { return empty() ? nullptr : std::__to_address(__ptr); }
1812 #else
1813  template<typename _Up>
1814  _Up*
1815  _M_data_ptr(_Up* __ptr) _GLIBCXX_NOEXCEPT
1816  { return __ptr; }
1817 
1818  template<typename _Ptr>
1819  value_type*
1820  _M_data_ptr(_Ptr __ptr)
1821  { return empty() ? (value_type*)0 : __ptr.operator->(); }
1822 
1823  template<typename _Ptr>
1824  const value_type*
1825  _M_data_ptr(_Ptr __ptr) const
1826  { return empty() ? (const value_type*)0 : __ptr.operator->(); }
1827 #endif
1828  };
1829 
1830 #if __cpp_deduction_guides >= 201606
1831  template<typename _InputIterator, typename _ValT
1832  = typename iterator_traits<_InputIterator>::value_type,
1833  typename _Allocator = allocator<_ValT>,
1834  typename = _RequireInputIter<_InputIterator>,
1835  typename = _RequireAllocator<_Allocator>>
1836  vector(_InputIterator, _InputIterator, _Allocator = _Allocator())
1838 #endif
1839 
1840  /**
1841  * @brief Vector equality comparison.
1842  * @param __x A %vector.
1843  * @param __y A %vector of the same type as @a __x.
1844  * @return True iff the size and elements of the vectors are equal.
1845  *
1846  * This is an equivalence relation. It is linear in the size of the
1847  * vectors. Vectors are considered equivalent if their sizes are equal,
1848  * and if corresponding elements compare equal.
1849  */
1850  template<typename _Tp, typename _Alloc>
1851  inline bool
1852  operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1853  { return (__x.size() == __y.size()
1854  && std::equal(__x.begin(), __x.end(), __y.begin())); }
1855 
1856  /**
1857  * @brief Vector ordering relation.
1858  * @param __x A %vector.
1859  * @param __y A %vector of the same type as @a __x.
1860  * @return True iff @a __x is lexicographically less than @a __y.
1861  *
1862  * This is a total ordering relation. It is linear in the size of the
1863  * vectors. The elements must be comparable with @c <.
1864  *
1865  * See std::lexicographical_compare() for how the determination is made.
1866  */
1867  template<typename _Tp, typename _Alloc>
1868  inline bool
1869  operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1870  { return std::lexicographical_compare(__x.begin(), __x.end(),
1871  __y.begin(), __y.end()); }
1872 
1873  /// Based on operator==
1874  template<typename _Tp, typename _Alloc>
1875  inline bool
1876  operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1877  { return !(__x == __y); }
1878 
1879  /// Based on operator<
1880  template<typename _Tp, typename _Alloc>
1881  inline bool
1882  operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1883  { return __y < __x; }
1884 
1885  /// Based on operator<
1886  template<typename _Tp, typename _Alloc>
1887  inline bool
1888  operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1889  { return !(__y < __x); }
1890 
1891  /// Based on operator<
1892  template<typename _Tp, typename _Alloc>
1893  inline bool
1894  operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1895  { return !(__x < __y); }
1896 
1897  /// See std::vector::swap().
1898  template<typename _Tp, typename _Alloc>
1899  inline void
1901  _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
1902  { __x.swap(__y); }
1903 
1904 _GLIBCXX_END_NAMESPACE_CONTAINER
1905 _GLIBCXX_END_NAMESPACE_VERSION
1906 } // namespace std
1907 
1908 #endif /* _STL_VECTOR_H */
const_reverse_iterator crbegin() const noexcept
Definition: stl_vector.h:863
const_reverse_iterator rbegin() const noexcept
Definition: stl_vector.h:817
iterator end() noexcept
Definition: stl_vector.h:790
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
reverse_iterator rend() noexcept
Definition: stl_vector.h:826
vector(initializer_list< value_type > __l, const allocator_type &__a=allocator_type())
Builds a vector from an initializer list.
Definition: stl_vector.h:586
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:772
vector(const vector &__x)
Vector copy constructor.
Definition: stl_vector.h:514
void assign(initializer_list< value_type > __l)
Assigns an initializer list to a vector.
Definition: stl_vector.h:755
vector(const vector &__x, const allocator_type &__a)
Copy constructor with alternative allocator.
Definition: stl_vector.h:536
reference back() noexcept
Definition: stl_vector.h:1104
const_iterator begin() const noexcept
Definition: stl_vector.h:781
const_reference back() const noexcept
Definition: stl_vector.h:1115
const_reference at(size_type __n) const
Provides access to the data contained in the vector.
Definition: stl_vector.h:1071
const_iterator end() const noexcept
Definition: stl_vector.h:799
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:898
reference operator[](size_type __n) noexcept
Subscript access to the data contained in the vector.
Definition: stl_vector.h:1004
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:884
void pop_back() noexcept
Removes last element.
Definition: stl_vector.h:1186
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:670
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:614
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:1031
_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:1053
void assign(size_type __n, const value_type &__val)
Assigns a given value to a vector.
Definition: stl_vector.h:710
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:1093
void push_back(const value_type &__x)
Add data to the end of the vector.
Definition: stl_vector.h:1148
iterator insert(const_iterator __position, value_type &&__x)
Inserts given rvalue into vector before specified iterator.
Definition: stl_vector.h:1254
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:1209
is_nothrow_default_constructible
Definition: type_traits:987
reference front() noexcept
Definition: stl_vector.h:1082
iterator insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
Inserts a range into the vector.
Definition: stl_vector.h:1340
vector(size_type __n, const allocator_type &__a=allocator_type())
Creates a vector with default constructed elements.
Definition: stl_vector.h:471
const_iterator cend() const noexcept
Definition: stl_vector.h:854
vector(const allocator_type &__a) noexcept
Creates a vector with no elements.
Definition: stl_vector.h:458
const_reference operator[](size_type __n) const noexcept
Subscript access to the data contained in the vector.
Definition: stl_vector.h:1022
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:483
size_type size() const noexcept
Definition: stl_vector.h:879
const_iterator cbegin() const noexcept
Definition: stl_vector.h:845
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:568
Uniform interface to C++98 and C++11 allocators.
iterator erase(const_iterator __position)
Remove element at given position.
Definition: stl_vector.h:1391
vector & operator=(initializer_list< value_type > __l)
Vector list assignment operator.
Definition: stl_vector.h:691
iterator insert(const_iterator __position, initializer_list< value_type > __l)
Inserts an initializer_list into the vector.
Definition: stl_vector.h:1271
void resize(size_type __new_size, const value_type &__x)
Resizes the vector to the specified number of elements.
Definition: stl_vector.h:918
void assign(_InputIterator __first, _InputIterator __last)
Assigns a range to a vector.
Definition: stl_vector.h:729
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:1296
void swap(vector &__x) noexcept
Swaps data with another vector.
Definition: stl_vector.h:1441
pointer _M_allocate_and_copy(size_type __n, _ForwardIterator __first, _ForwardIterator __last)
Definition: stl_vector.h:1469
~vector() noexcept
Definition: stl_vector.h:639
size_type capacity() const noexcept
Definition: stl_vector.h:959
const_reverse_iterator rend() const noexcept
Definition: stl_vector.h:835
const_reverse_iterator crend() const noexcept
Definition: stl_vector.h:872
void shrink_to_fit()
Definition: stl_vector.h:950
bool empty() const noexcept
Definition: stl_vector.h:968
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:1418
void clear() noexcept
Definition: stl_vector.h:1459
_Tp * data() noexcept
Definition: stl_vector.h:1129
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:808