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