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