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