LCOV - code coverage report
Current view: top level - usr/include/c++/4.9/bits - stl_vector.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 110 144 76.4 %
Date: 2016-11-29 15:07:43 Functions: 208 604 34.4 %

          Line data    Source code
       1             : // Vector implementation -*- C++ -*-
       2             : 
       3             : // Copyright (C) 2001-2014 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             : 
      59             : #include <bits/stl_iterator_base_funcs.h>
      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             :     {
      74             :       typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
      75             :         rebind<_Tp>::other _Tp_alloc_type;
      76             :       typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer
      77             :         pointer;
      78             : 
      79         210 :       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         128 :         _Vector_impl()
      87         128 :         : _Tp_alloc_type(), _M_start(0), _M_finish(0), _M_end_of_storage(0)
      88         128 :         { }
      89             : 
      90          50 :         _Vector_impl(_Tp_alloc_type const& __a) _GLIBCXX_NOEXCEPT
      91          50 :         : _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
      92          50 :         { }
      93             : 
      94             : #if __cplusplus >= 201103L
      95          32 :         _Vector_impl(_Tp_alloc_type&& __a) noexcept
      96          32 :         : _Tp_alloc_type(std::move(__a)),
      97          32 :           _M_start(0), _M_finish(0), _M_end_of_storage(0)
      98          32 :         { }
      99             : #endif
     100             : 
     101          36 :         void _M_swap_data(_Vector_impl& __x) _GLIBCXX_NOEXCEPT
     102             :         {
     103          36 :           std::swap(_M_start, __x._M_start);
     104          36 :           std::swap(_M_finish, __x._M_finish);
     105          36 :           std::swap(_M_end_of_storage, __x._M_end_of_storage);
     106          36 :         }
     107             :       };
     108             :       
     109             :     public:
     110             :       typedef _Alloc allocator_type;
     111             : 
     112             :       _Tp_alloc_type&
     113         517 :       _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
     114         517 :       { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
     115             : 
     116             :       const _Tp_alloc_type&
     117         233 :       _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
     118         233 :       { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
     119             : 
     120             :       allocator_type
     121           2 :       get_allocator() const _GLIBCXX_NOEXCEPT
     122           2 :       { return allocator_type(_M_get_Tp_allocator()); }
     123             : 
     124         128 :       _Vector_base()
     125         128 :       : _M_impl() { }
     126             : 
     127           2 :       _Vector_base(const allocator_type& __a) _GLIBCXX_NOEXCEPT
     128           2 :       : _M_impl(__a) { }
     129             : 
     130             :       _Vector_base(size_t __n)
     131             :       : _M_impl()
     132             :       { _M_create_storage(__n); }
     133             : 
     134          48 :       _Vector_base(size_t __n, const allocator_type& __a)
     135          48 :       : _M_impl(__a)
     136          48 :       { _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          32 :       _Vector_base(_Vector_base&& __x) noexcept
     143          32 :       : _M_impl(std::move(__x._M_get_Tp_allocator()))
     144          32 :       { 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         210 :       ~_Vector_base() _GLIBCXX_NOEXCEPT
     160         210 :       { _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage
     161         420 :                       - this->_M_impl._M_start); }
     162             : 
     163             :     public:
     164             :       _Vector_impl _M_impl;
     165             : 
     166             :       pointer
     167         157 :       _M_allocate(size_t __n)
     168             :       {
     169             :         typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
     170         157 :         return __n != 0 ? _Tr::allocate(_M_impl, __n) : 0;
     171             :       }
     172             : 
     173             :       void
     174         319 :       _M_deallocate(pointer __p, size_t __n)
     175             :       {
     176             :         typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
     177         319 :         if (__p)
     178         157 :           _Tr::deallocate(_M_impl, __p, __n);
     179         319 :       }
     180             : 
     181             :     private:
     182             :       void
     183          48 :       _M_create_storage(size_t __n)
     184             :       {
     185          48 :         this->_M_impl._M_start = this->_M_allocate(__n);
     186          48 :         this->_M_impl._M_finish = this->_M_impl._M_start;
     187          48 :         this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
     188          48 :       }
     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             :       
     221             :       typedef _Vector_base<_Tp, _Alloc>                    _Base;
     222             :       typedef typename _Base::_Tp_alloc_type             _Tp_alloc_type;
     223             :       typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type>  _Alloc_traits;
     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;
     234             :       typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
     235             :       typedef std::reverse_iterator<iterator>              reverse_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             :        */
     253         128 :       vector()
     254             : #if __cplusplus >= 201103L
     255             :       noexcept(is_nothrow_default_constructible<_Alloc>::value)
     256             : #endif
     257         128 :       : _Base() { }
     258             : 
     259             :       /**
     260             :        *  @brief  Creates a %vector with no elements.
     261             :        *  @param  __a  An allocator object.
     262             :        */
     263             :       explicit
     264           2 :       vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT
     265           2 :       : _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          48 :       vector(const vector& __x)
     319             :       : _Base(__x.size(),
     320          48 :         _Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()))
     321          48 :       { this->_M_impl._M_finish =
     322             :           std::__uninitialized_copy_a(__x.begin(), __x.end(),
     323             :                                       this->_M_impl._M_start,
     324          48 :                                       _M_get_Tp_allocator());
     325          48 :       }
     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          32 :       vector(vector&& __x) noexcept
     336          32 :       : _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             :        */
     373             :       vector(initializer_list<value_type> __l,
     374             :              const allocator_type& __a = allocator_type())
     375             :       : _Base(__a)
     376             :       {
     377             :         _M_range_initialize(__l.begin(), __l.end(),
     378             :                             random_access_iterator_tag());
     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         210 :       ~vector() _GLIBCXX_NOEXCEPT
     424         210 :       { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
     425         420 :                       _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           2 :       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
     449             :       {
     450             :         constexpr bool __move_storage =
     451             :           _Alloc_traits::_S_propagate_on_move_assign()
     452           2 :           || _Alloc_traits::_S_always_equal();
     453           2 :         _M_move_assign(std::move(__x),
     454           2 :                        integral_constant<bool, __move_storage>());
     455           2 :         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&
     470             :       operator=(initializer_list<value_type> __l)
     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
     533             :       assign(initializer_list<value_type> __l)
     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          66 :       begin() _GLIBCXX_NOEXCEPT
     548          66 :       { 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          98 :       begin() const _GLIBCXX_NOEXCEPT
     557          98 :       { 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          87 :       end() _GLIBCXX_NOEXCEPT
     566          87 :       { 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         100 :       end() const _GLIBCXX_NOEXCEPT
     575         100 :       { 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           0 :       cbegin() const noexcept
     621           0 :       { 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         571 :       size() const _GLIBCXX_NOEXCEPT
     655         571 :       { 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         183 :       max_size() const _GLIBCXX_NOEXCEPT
     660         183 :       { 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           0 :       resize(size_type __new_size)
     674             :       {
     675           0 :         if (__new_size > size())
     676           0 :           _M_default_append(__new_size - size());
     677           0 :         else if (__new_size < size())
     678           0 :           _M_erase_at_end(this->_M_impl._M_start + __new_size);
     679           0 :       }
     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
     725             :       shrink_to_fit()
     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          33 :       capacity() const _GLIBCXX_NOEXCEPT
     735             :       { return size_type(this->_M_impl._M_end_of_storage
     736          33 :                          - 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           9 :       empty() const _GLIBCXX_NOEXCEPT
     744           9 :       { 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          58 :       operator[](size_type __n) _GLIBCXX_NOEXCEPT
     780          58 :       { 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           5 :       front() _GLIBCXX_NOEXCEPT
     852           5 :       { 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           0 :       back() _GLIBCXX_NOEXCEPT
     868           0 :       { 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          23 :       push_back(const value_type& __x)
     914             :       {
     915          23 :         if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
     916             :           {
     917           0 :             _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
     918           0 :                                      __x);
     919           0 :             ++this->_M_impl._M_finish;
     920             :           }
     921             :         else
     922             : #if __cplusplus >= 201103L
     923          23 :           _M_emplace_back_aux(__x);
     924             : #else
     925             :           _M_insert_aux(end(), __x);
     926             : #endif
     927          23 :       }
     928             : 
     929             : #if __cplusplus >= 201103L
     930             :       void
     931          85 :       push_back(value_type&& __x)
     932          85 :       { 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          14 :       pop_back() _GLIBCXX_NOEXCEPT
     950             :       {
     951          14 :         --this->_M_impl._M_finish;
     952          14 :         _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
     953          14 :       }
     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           0 :       erase(const_iterator __position)
    1147           0 :       { 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           0 :       erase(const_iterator __first, const_iterator __last)
    1174             :       {
    1175           0 :         const auto __beg = begin();
    1176           0 :         const auto __cbeg = cbegin();
    1177           0 :         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           0 :       swap(vector& __x)
    1195             : #if __cplusplus >= 201103L
    1196             :       noexcept(_Alloc_traits::_S_nothrow_swap())
    1197             : #endif
    1198             :       {
    1199           0 :         this->_M_impl._M_swap_data(__x._M_impl);
    1200           0 :         _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
    1201           0 :                                   __x._M_get_Tp_allocator());
    1202           0 :       }
    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           0 :       clear() _GLIBCXX_NOEXCEPT
    1212           0 :       { _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          28 :         _M_allocate_and_copy(size_type __n,
    1222             :                              _ForwardIterator __first, _ForwardIterator __last)
    1223             :         {
    1224          28 :           pointer __result = this->_M_allocate(__n);
    1225             :           __try
    1226             :             {
    1227          28 :               std::__uninitialized_copy_a(__first, __last, __result,
    1228          28 :                                           _M_get_Tp_allocator());
    1229          28 :               return __result;
    1230             :             }
    1231           0 :           __catch(...)
    1232             :             {
    1233           0 :               _M_deallocate(__result, __n);
    1234           0 :               __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             :         std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value, 
    1301             :                                       _M_get_Tp_allocator());
    1302             :         this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
    1303             :       }
    1304             : 
    1305             : #if __cplusplus >= 201103L
    1306             :       // Called by the vector(n) constructor.
    1307             :       void
    1308             :       _M_default_initialize(size_type __n)
    1309             :       {
    1310             :         std::__uninitialized_default_n_a(this->_M_impl._M_start, __n, 
    1311             :                                          _M_get_Tp_allocator());
    1312             :         this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
    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,
    1343             :                       std::input_iterator_tag);
    1344             : 
    1345             :       // Called by the second assign_dispatch above
    1346             :       template<typename _ForwardIterator>
    1347             :         void
    1348             :         _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
    1349             :                       std::forward_iterator_tag);
    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          81 :       _M_check_len(size_type __n, const char* __s) const
    1423             :       {
    1424          81 :         if (max_size() - size() < __n)
    1425           0 :           __throw_length_error(__N(__s));
    1426             : 
    1427          81 :         const size_type __len = size() + std::max(size(), __n);
    1428          81 :         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           0 :       _M_erase_at_end(pointer __pos) _GLIBCXX_NOEXCEPT
    1437             :       {
    1438           0 :         std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator());
    1439           0 :         this->_M_impl._M_finish = __pos;
    1440           0 :       }
    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           2 :       _M_move_assign(vector&& __x, std::true_type) noexcept
    1455             :       {
    1456           2 :         vector __tmp(get_allocator());
    1457           2 :         this->_M_impl._M_swap_data(__tmp._M_impl);
    1458           2 :         this->_M_impl._M_swap_data(__x._M_impl);
    1459           2 :         std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
    1460           2 :       }
    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>
    1487             :         typename std::pointer_traits<_Ptr>::element_type*
    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
    1559             :     swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
    1560             :     { __x.swap(__y); }
    1561             : 
    1562             : _GLIBCXX_END_NAMESPACE_CONTAINER
    1563             : } // namespace std
    1564             : 
    1565             : #endif /* _STL_VECTOR_H */

Generated by: LCOV version 1.11