LCOV - code coverage report
Current view: top level - usr/include/c++/7/bits - vector.tcc (source / functions) Hit Total Coverage
Test: coverage.info Lines: 44 52 84.6 %
Date: 2020-10-15 20:26:03 Functions: 13 18 72.2 %

          Line data    Source code
       1             : // Vector implementation (out of line) -*- C++ -*-
       2             : 
       3             : // Copyright (C) 2001-2017 Free Software Foundation, Inc.
       4             : //
       5             : // This file is part of the GNU ISO C++ Library.  This library is free
       6             : // software; you can redistribute it and/or modify it under the
       7             : // terms of the GNU General Public License as published by the
       8             : // Free Software Foundation; either version 3, or (at your option)
       9             : // any later version.
      10             : 
      11             : // This library is distributed in the hope that it will be useful,
      12             : // but WITHOUT ANY WARRANTY; without even the implied warranty of
      13             : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      14             : // GNU General Public License for more details.
      15             : 
      16             : // Under Section 7 of GPL version 3, you are granted additional
      17             : // permissions described in the GCC Runtime Library Exception, version
      18             : // 3.1, as published by the Free Software Foundation.
      19             : 
      20             : // You should have received a copy of the GNU General Public License and
      21             : // a copy of the GCC Runtime Library Exception along with this program;
      22             : // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
      23             : // <http://www.gnu.org/licenses/>.
      24             : 
      25             : /*
      26             :  *
      27             :  * Copyright (c) 1994
      28             :  * Hewlett-Packard Company
      29             :  *
      30             :  * Permission to use, copy, modify, distribute and sell this software
      31             :  * and its documentation for any purpose is hereby granted without fee,
      32             :  * provided that the above copyright notice appear in all copies and
      33             :  * that both that copyright notice and this permission notice appear
      34             :  * in supporting documentation.  Hewlett-Packard Company makes no
      35             :  * representations about the suitability of this software for any
      36             :  * purpose.  It is provided "as is" without express or implied warranty.
      37             :  *
      38             :  *
      39             :  * Copyright (c) 1996
      40             :  * Silicon Graphics Computer Systems, Inc.
      41             :  *
      42             :  * Permission to use, copy, modify, distribute and sell this software
      43             :  * and its documentation for any purpose is hereby granted without fee,
      44             :  * provided that the above copyright notice appear in all copies and
      45             :  * that both that copyright notice and this permission notice appear
      46             :  * in supporting documentation.  Silicon Graphics makes no
      47             :  * representations about the suitability of this  software for any
      48             :  * purpose.  It is provided "as is" without express or implied warranty.
      49             :  */
      50             : 
      51             : /** @file bits/vector.tcc
      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 _VECTOR_TCC
      57             : #define _VECTOR_TCC 1
      58             : 
      59             : namespace std _GLIBCXX_VISIBILITY(default)
      60             : {
      61             : _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
      62             : 
      63             :   template<typename _Tp, typename _Alloc>
      64             :     void
      65          60 :     vector<_Tp, _Alloc>::
      66             :     reserve(size_type __n)
      67             :     {
      68          60 :       if (__n > this->max_size())
      69           0 :         __throw_length_error(__N("vector::reserve"));
      70          60 :       if (this->capacity() < __n)
      71             :         {
      72          60 :           const size_type __old_size = size();
      73          60 :           pointer __tmp = _M_allocate_and_copy(__n,
      74             :             _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_start),
      75             :             _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_finish));
      76          60 :           std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
      77          60 :                         _M_get_Tp_allocator());
      78         120 :           _M_deallocate(this->_M_impl._M_start,
      79          60 :                         this->_M_impl._M_end_of_storage
      80          60 :                         - this->_M_impl._M_start);
      81          60 :           this->_M_impl._M_start = __tmp;
      82          60 :           this->_M_impl._M_finish = __tmp + __old_size;
      83          60 :           this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
      84             :         }
      85          60 :     }
      86             : 
      87             : #if __cplusplus >= 201103L
      88             :   template<typename _Tp, typename _Alloc>
      89             :     template<typename... _Args>
      90             : #if __cplusplus > 201402L
      91             :       typename vector<_Tp, _Alloc>::reference
      92             : #else
      93             :       void
      94             : #endif
      95      178183 :       vector<_Tp, _Alloc>::
      96             :       emplace_back(_Args&&... __args)
      97             :       {
      98      178183 :         if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
      99             :           {
     100      178098 :             _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
     101             :                                      std::forward<_Args>(__args)...);
     102      178098 :             ++this->_M_impl._M_finish;
     103             :           }
     104             :         else
     105          85 :           _M_realloc_insert(end(), std::forward<_Args>(__args)...);
     106             : #if __cplusplus > 201402L
     107             :         return back();
     108             : #endif
     109      178183 :       }
     110             : #endif
     111             : 
     112             :   template<typename _Tp, typename _Alloc>
     113             :     typename vector<_Tp, _Alloc>::iterator
     114             :     vector<_Tp, _Alloc>::
     115             : #if __cplusplus >= 201103L
     116             :     insert(const_iterator __position, const value_type& __x)
     117             : #else
     118             :     insert(iterator __position, const value_type& __x)
     119             : #endif
     120             :     {
     121             :       const size_type __n = __position - begin();
     122             :       if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
     123             :         if (__position == end())
     124             :           {
     125             :             _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
     126             :                                      __x);
     127             :             ++this->_M_impl._M_finish;
     128             :           }
     129             :         else
     130             :           {
     131             : #if __cplusplus >= 201103L
     132             :             const auto __pos = begin() + (__position - cbegin());
     133             :             // __x could be an existing element of this vector, so make a
     134             :             // copy of it before _M_insert_aux moves elements around.
     135             :             _Temporary_value __x_copy(this, __x);
     136             :             _M_insert_aux(__pos, std::move(__x_copy._M_val()));
     137             : #else
     138             :             _M_insert_aux(__position, __x);
     139             : #endif
     140             :           }
     141             :       else
     142             : #if __cplusplus >= 201103L
     143             :         _M_realloc_insert(begin() + (__position - cbegin()), __x);
     144             : #else
     145             :         _M_realloc_insert(__position, __x);
     146             : #endif
     147             : 
     148             :       return iterator(this->_M_impl._M_start + __n);
     149             :     }
     150             : 
     151             :   template<typename _Tp, typename _Alloc>
     152             :     typename vector<_Tp, _Alloc>::iterator
     153             :     vector<_Tp, _Alloc>::
     154             :     _M_erase(iterator __position)
     155             :     {
     156             :       if (__position + 1 != end())
     157             :         _GLIBCXX_MOVE3(__position + 1, end(), __position);
     158             :       --this->_M_impl._M_finish;
     159             :       _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
     160             :       return __position;
     161             :     }
     162             : 
     163             :   template<typename _Tp, typename _Alloc>
     164             :     typename vector<_Tp, _Alloc>::iterator
     165             :     vector<_Tp, _Alloc>::
     166             :     _M_erase(iterator __first, iterator __last)
     167             :     {
     168             :       if (__first != __last)
     169             :         {
     170             :           if (__last != end())
     171             :             _GLIBCXX_MOVE3(__last, end(), __first);
     172             :           _M_erase_at_end(__first.base() + (end() - __last));
     173             :         }
     174             :       return __first;
     175             :     }
     176             : 
     177             :   template<typename _Tp, typename _Alloc>
     178             :     vector<_Tp, _Alloc>&
     179             :     vector<_Tp, _Alloc>::
     180             :     operator=(const vector<_Tp, _Alloc>& __x)
     181             :     {
     182             :       if (&__x != this)
     183             :         {
     184             : #if __cplusplus >= 201103L
     185             :           if (_Alloc_traits::_S_propagate_on_copy_assign())
     186             :             {
     187             :               if (!_Alloc_traits::_S_always_equal()
     188             :                   && _M_get_Tp_allocator() != __x._M_get_Tp_allocator())
     189             :                 {
     190             :                   // replacement allocator cannot free existing storage
     191             :                   this->clear();
     192             :                   _M_deallocate(this->_M_impl._M_start,
     193             :                                 this->_M_impl._M_end_of_storage
     194             :                                 - this->_M_impl._M_start);
     195             :                   this->_M_impl._M_start = nullptr;
     196             :                   this->_M_impl._M_finish = nullptr;
     197             :                   this->_M_impl._M_end_of_storage = nullptr;
     198             :                 }
     199             :               std::__alloc_on_copy(_M_get_Tp_allocator(),
     200             :                                    __x._M_get_Tp_allocator());
     201             :             }
     202             : #endif
     203             :           const size_type __xlen = __x.size();
     204             :           if (__xlen > capacity())
     205             :             {
     206             :               pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(),
     207             :                                                    __x.end());
     208             :               std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
     209             :                             _M_get_Tp_allocator());
     210             :               _M_deallocate(this->_M_impl._M_start,
     211             :                             this->_M_impl._M_end_of_storage
     212             :                             - this->_M_impl._M_start);
     213             :               this->_M_impl._M_start = __tmp;
     214             :               this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen;
     215             :             }
     216             :           else if (size() >= __xlen)
     217             :             {
     218             :               std::_Destroy(std::copy(__x.begin(), __x.end(), begin()),
     219             :                             end(), _M_get_Tp_allocator());
     220             :             }
     221             :           else
     222             :             {
     223             :               std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(),
     224             :                         this->_M_impl._M_start);
     225             :               std::__uninitialized_copy_a(__x._M_impl._M_start + size(),
     226             :                                           __x._M_impl._M_finish,
     227             :                                           this->_M_impl._M_finish,
     228             :                                           _M_get_Tp_allocator());
     229             :             }
     230             :           this->_M_impl._M_finish = this->_M_impl._M_start + __xlen;
     231             :         }
     232             :       return *this;
     233             :     }
     234             : 
     235             :   template<typename _Tp, typename _Alloc>
     236             :     void
     237             :     vector<_Tp, _Alloc>::
     238             :     _M_fill_assign(size_t __n, const value_type& __val)
     239             :     {
     240             :       if (__n > capacity())
     241             :         {
     242             :           vector __tmp(__n, __val, _M_get_Tp_allocator());
     243             :           __tmp._M_impl._M_swap_data(this->_M_impl);
     244             :         }
     245             :       else if (__n > size())
     246             :         {
     247             :           std::fill(begin(), end(), __val);
     248             :           this->_M_impl._M_finish =
     249             :             std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
     250             :                                           __n - size(), __val,
     251             :                                           _M_get_Tp_allocator());
     252             :         }
     253             :       else
     254             :         _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val));
     255             :     }
     256             : 
     257             :   template<typename _Tp, typename _Alloc>
     258             :     template<typename _InputIterator>
     259             :       void
     260             :       vector<_Tp, _Alloc>::
     261             :       _M_assign_aux(_InputIterator __first, _InputIterator __last,
     262             :                     std::input_iterator_tag)
     263             :       {
     264             :         pointer __cur(this->_M_impl._M_start);
     265             :         for (; __first != __last && __cur != this->_M_impl._M_finish;
     266             :              ++__cur, ++__first)
     267             :           *__cur = *__first;
     268             :         if (__first == __last)
     269             :           _M_erase_at_end(__cur);
     270             :         else
     271             :           _M_range_insert(end(), __first, __last,
     272             :                           std::__iterator_category(__first));
     273             :       }
     274             : 
     275             :   template<typename _Tp, typename _Alloc>
     276             :     template<typename _ForwardIterator>
     277             :       void
     278             :       vector<_Tp, _Alloc>::
     279             :       _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
     280             :                     std::forward_iterator_tag)
     281             :       {
     282             :         const size_type __len = std::distance(__first, __last);
     283             : 
     284             :         if (__len > capacity())
     285             :           {
     286             :             pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
     287             :             std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
     288             :                           _M_get_Tp_allocator());
     289             :             _M_deallocate(this->_M_impl._M_start,
     290             :                           this->_M_impl._M_end_of_storage
     291             :                           - this->_M_impl._M_start);
     292             :             this->_M_impl._M_start = __tmp;
     293             :             this->_M_impl._M_finish = this->_M_impl._M_start + __len;
     294             :             this->_M_impl._M_end_of_storage = this->_M_impl._M_finish;
     295             :           }
     296             :         else if (size() >= __len)
     297             :           _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start));
     298             :         else
     299             :           {
     300             :             _ForwardIterator __mid = __first;
     301             :             std::advance(__mid, size());
     302             :             std::copy(__first, __mid, this->_M_impl._M_start);
     303             :             this->_M_impl._M_finish =
     304             :               std::__uninitialized_copy_a(__mid, __last,
     305             :                                           this->_M_impl._M_finish,
     306             :                                           _M_get_Tp_allocator());
     307             :           }
     308             :       }
     309             : 
     310             : #if __cplusplus >= 201103L
     311             :   template<typename _Tp, typename _Alloc>
     312             :     auto
     313             :     vector<_Tp, _Alloc>::
     314             :     _M_insert_rval(const_iterator __position, value_type&& __v) -> iterator
     315             :     {
     316             :       const auto __n = __position - cbegin();
     317             :       if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
     318             :         if (__position == cend())
     319             :           {
     320             :             _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
     321             :                                      std::move(__v));
     322             :             ++this->_M_impl._M_finish;
     323             :           }
     324             :         else
     325             :           _M_insert_aux(begin() + __n, std::move(__v));
     326             :       else
     327             :         _M_realloc_insert(begin() + __n, std::move(__v));
     328             : 
     329             :       return iterator(this->_M_impl._M_start + __n);
     330             :     }
     331             : 
     332             :   template<typename _Tp, typename _Alloc>
     333             :     template<typename... _Args>
     334             :       auto
     335             :       vector<_Tp, _Alloc>::
     336             :       _M_emplace_aux(const_iterator __position, _Args&&... __args)
     337             :       -> iterator
     338             :       {
     339             :         const auto __n = __position - cbegin();
     340             :         if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
     341             :           if (__position == cend())
     342             :             {
     343             :               _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
     344             :                                        std::forward<_Args>(__args)...);
     345             :               ++this->_M_impl._M_finish;
     346             :             }
     347             :           else
     348             :             {
     349             :               // We need to construct a temporary because something in __args...
     350             :               // could alias one of the elements of the container and so we
     351             :               // need to use it before _M_insert_aux moves elements around.
     352             :               _Temporary_value __tmp(this, std::forward<_Args>(__args)...);
     353             :               _M_insert_aux(begin() + __n, std::move(__tmp._M_val()));
     354             :             }
     355             :         else
     356             :           _M_realloc_insert(begin() + __n, std::forward<_Args>(__args)...);
     357             : 
     358             :         return iterator(this->_M_impl._M_start + __n);
     359             :       }
     360             : 
     361             :   template<typename _Tp, typename _Alloc>
     362             :     template<typename _Arg>
     363             :       void
     364             :       vector<_Tp, _Alloc>::
     365             :       _M_insert_aux(iterator __position, _Arg&& __arg)
     366             : #else
     367             :   template<typename _Tp, typename _Alloc>
     368             :     void
     369             :     vector<_Tp, _Alloc>::
     370             :     _M_insert_aux(iterator __position, const _Tp& __x)
     371             : #endif
     372             :     {
     373             :       _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
     374             :                                _GLIBCXX_MOVE(*(this->_M_impl._M_finish
     375             :                                                - 1)));
     376             :       ++this->_M_impl._M_finish;
     377             : #if __cplusplus < 201103L
     378             :       _Tp __x_copy = __x;
     379             : #endif
     380             :       _GLIBCXX_MOVE_BACKWARD3(__position.base(),
     381             :                               this->_M_impl._M_finish - 2,
     382             :                               this->_M_impl._M_finish - 1);
     383             : #if __cplusplus < 201103L
     384             :       *__position = __x_copy;
     385             : #else
     386             :       *__position = std::forward<_Arg>(__arg);
     387             : #endif
     388             :     }
     389             : 
     390             : #if __cplusplus >= 201103L
     391             :   template<typename _Tp, typename _Alloc>
     392             :     template<typename... _Args>
     393             :       void
     394         291 :       vector<_Tp, _Alloc>::
     395             :       _M_realloc_insert(iterator __position, _Args&&... __args)
     396             : #else
     397             :   template<typename _Tp, typename _Alloc>
     398             :     void
     399             :     vector<_Tp, _Alloc>::
     400             :     _M_realloc_insert(iterator __position, const _Tp& __x)
     401             : #endif
     402             :     {
     403         291 :       const size_type __len =
     404             :         _M_check_len(size_type(1), "vector::_M_realloc_insert");
     405         291 :       const size_type __elems_before = __position - begin();
     406         291 :       pointer __new_start(this->_M_allocate(__len));
     407         291 :       pointer __new_finish(__new_start);
     408             :       __try
     409             :         {
     410             :           // The order of the three operations is dictated by the C++11
     411             :           // case, where the moves could alter a new element belonging
     412             :           // to the existing vector.  This is an issue only for callers
     413             :           // taking the element by lvalue ref (see last bullet of C++11
     414             :           // [res.on.arguments]).
     415         582 :           _Alloc_traits::construct(this->_M_impl,
     416         291 :                                    __new_start + __elems_before,
     417             : #if __cplusplus >= 201103L
     418             :                                    std::forward<_Args>(__args)...);
     419             : #else
     420             :                                    __x);
     421             : #endif
     422         291 :           __new_finish = pointer();
     423             : 
     424         291 :           __new_finish
     425             :             = std::__uninitialized_move_if_noexcept_a
     426         291 :             (this->_M_impl._M_start, __position.base(),
     427         291 :              __new_start, _M_get_Tp_allocator());
     428             : 
     429         291 :           ++__new_finish;
     430             : 
     431         291 :           __new_finish
     432             :             = std::__uninitialized_move_if_noexcept_a
     433         291 :             (__position.base(), this->_M_impl._M_finish,
     434         291 :              __new_finish, _M_get_Tp_allocator());
     435             :         }
     436           0 :       __catch(...)
     437             :         {
     438           0 :           if (!__new_finish)
     439           0 :             _Alloc_traits::destroy(this->_M_impl,
     440           0 :                                    __new_start + __elems_before);
     441             :           else
     442           0 :             std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
     443           0 :           _M_deallocate(__new_start, __len);
     444           0 :           __throw_exception_again;
     445             :         }
     446         291 :       std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
     447         291 :                     _M_get_Tp_allocator());
     448         582 :       _M_deallocate(this->_M_impl._M_start,
     449         291 :                     this->_M_impl._M_end_of_storage
     450         291 :                     - this->_M_impl._M_start);
     451         291 :       this->_M_impl._M_start = __new_start;
     452         291 :       this->_M_impl._M_finish = __new_finish;
     453         291 :       this->_M_impl._M_end_of_storage = __new_start + __len;
     454         291 :     }
     455             : 
     456             :   template<typename _Tp, typename _Alloc>
     457             :     void
     458             :     vector<_Tp, _Alloc>::
     459             :     _M_fill_insert(iterator __position, size_type __n, const value_type& __x)
     460             :     {
     461             :       if (__n != 0)
     462             :         {
     463             :           if (size_type(this->_M_impl._M_end_of_storage
     464             :                         - this->_M_impl._M_finish) >= __n)
     465             :             {
     466             : #if __cplusplus < 201103L
     467             :               value_type __x_copy = __x;
     468             : #else
     469             :               _Temporary_value __tmp(this, __x);
     470             :               value_type& __x_copy = __tmp._M_val();
     471             : #endif
     472             :               const size_type __elems_after = end() - __position;
     473             :               pointer __old_finish(this->_M_impl._M_finish);
     474             :               if (__elems_after > __n)
     475             :                 {
     476             :                   std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
     477             :                                               this->_M_impl._M_finish,
     478             :                                               this->_M_impl._M_finish,
     479             :                                               _M_get_Tp_allocator());
     480             :                   this->_M_impl._M_finish += __n;
     481             :                   _GLIBCXX_MOVE_BACKWARD3(__position.base(),
     482             :                                           __old_finish - __n, __old_finish);
     483             :                   std::fill(__position.base(), __position.base() + __n,
     484             :                             __x_copy);
     485             :                 }
     486             :               else
     487             :                 {
     488             :                   this->_M_impl._M_finish =
     489             :                     std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
     490             :                                                   __n - __elems_after,
     491             :                                                   __x_copy,
     492             :                                                   _M_get_Tp_allocator());
     493             :                   std::__uninitialized_move_a(__position.base(), __old_finish,
     494             :                                               this->_M_impl._M_finish,
     495             :                                               _M_get_Tp_allocator());
     496             :                   this->_M_impl._M_finish += __elems_after;
     497             :                   std::fill(__position.base(), __old_finish, __x_copy);
     498             :                 }
     499             :             }
     500             :           else
     501             :             {
     502             :               const size_type __len =
     503             :                 _M_check_len(__n, "vector::_M_fill_insert");
     504             :               const size_type __elems_before = __position - begin();
     505             :               pointer __new_start(this->_M_allocate(__len));
     506             :               pointer __new_finish(__new_start);
     507             :               __try
     508             :                 {
     509             :                   // See _M_realloc_insert above.
     510             :                   std::__uninitialized_fill_n_a(__new_start + __elems_before,
     511             :                                                 __n, __x,
     512             :                                                 _M_get_Tp_allocator());
     513             :                   __new_finish = pointer();
     514             : 
     515             :                   __new_finish
     516             :                     = std::__uninitialized_move_if_noexcept_a
     517             :                     (this->_M_impl._M_start, __position.base(),
     518             :                      __new_start, _M_get_Tp_allocator());
     519             : 
     520             :                   __new_finish += __n;
     521             : 
     522             :                   __new_finish
     523             :                     = std::__uninitialized_move_if_noexcept_a
     524             :                     (__position.base(), this->_M_impl._M_finish,
     525             :                      __new_finish, _M_get_Tp_allocator());
     526             :                 }
     527             :               __catch(...)
     528             :                 {
     529             :                   if (!__new_finish)
     530             :                     std::_Destroy(__new_start + __elems_before,
     531             :                                   __new_start + __elems_before + __n,
     532             :                                   _M_get_Tp_allocator());
     533             :                   else
     534             :                     std::_Destroy(__new_start, __new_finish,
     535             :                                   _M_get_Tp_allocator());
     536             :                   _M_deallocate(__new_start, __len);
     537             :                   __throw_exception_again;
     538             :                 }
     539             :               std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
     540             :                             _M_get_Tp_allocator());
     541             :               _M_deallocate(this->_M_impl._M_start,
     542             :                             this->_M_impl._M_end_of_storage
     543             :                             - this->_M_impl._M_start);
     544             :               this->_M_impl._M_start = __new_start;
     545             :               this->_M_impl._M_finish = __new_finish;
     546             :               this->_M_impl._M_end_of_storage = __new_start + __len;
     547             :             }
     548             :         }
     549             :     }
     550             : 
     551             : #if __cplusplus >= 201103L
     552             :   template<typename _Tp, typename _Alloc>
     553             :     void
     554             :     vector<_Tp, _Alloc>::
     555             :     _M_default_append(size_type __n)
     556             :     {
     557             :       if (__n != 0)
     558             :         {
     559             :           if (size_type(this->_M_impl._M_end_of_storage
     560             :                         - this->_M_impl._M_finish) >= __n)
     561             :             {
     562             :               this->_M_impl._M_finish =
     563             :                 std::__uninitialized_default_n_a(this->_M_impl._M_finish,
     564             :                                                  __n, _M_get_Tp_allocator());
     565             :             }
     566             :           else
     567             :             {
     568             :               const size_type __len =
     569             :                 _M_check_len(__n, "vector::_M_default_append");
     570             :               const size_type __size = this->size();
     571             :               pointer __new_start(this->_M_allocate(__len));
     572             :               pointer __destroy_from = pointer();
     573             :               __try
     574             :                 {
     575             :                   std::__uninitialized_default_n_a(__new_start + __size,
     576             :                                                    __n, _M_get_Tp_allocator());
     577             :                   __destroy_from = __new_start + __size;
     578             :                   std::__uninitialized_move_if_noexcept_a(
     579             :                       this->_M_impl._M_start, this->_M_impl._M_finish,
     580             :                       __new_start, _M_get_Tp_allocator());
     581             :                 }
     582             :               __catch(...)
     583             :                 {
     584             :                   if (__destroy_from)
     585             :                     std::_Destroy(__destroy_from, __destroy_from + __n,
     586             :                                   _M_get_Tp_allocator());
     587             :                   _M_deallocate(__new_start, __len);
     588             :                   __throw_exception_again;
     589             :                 }
     590             :               std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
     591             :                             _M_get_Tp_allocator());
     592             :               _M_deallocate(this->_M_impl._M_start,
     593             :                             this->_M_impl._M_end_of_storage
     594             :                             - this->_M_impl._M_start);
     595             :               this->_M_impl._M_start = __new_start;
     596             :               this->_M_impl._M_finish = __new_start + __size + __n;
     597             :               this->_M_impl._M_end_of_storage = __new_start + __len;
     598             :             }
     599             :         }
     600             :     }
     601             : 
     602             :   template<typename _Tp, typename _Alloc>
     603             :     bool
     604             :     vector<_Tp, _Alloc>::
     605             :     _M_shrink_to_fit()
     606             :     {
     607             :       if (capacity() == size())
     608             :         return false;
     609             :       return std::__shrink_to_fit_aux<vector>::_S_do_it(*this);
     610             :     }
     611             : #endif
     612             : 
     613             :   template<typename _Tp, typename _Alloc>
     614             :     template<typename _InputIterator>
     615             :       void
     616             :       vector<_Tp, _Alloc>::
     617             :       _M_range_insert(iterator __pos, _InputIterator __first,
     618             :                       _InputIterator __last, std::input_iterator_tag)
     619             :       {
     620             :         for (; __first != __last; ++__first)
     621             :           {
     622             :             __pos = insert(__pos, *__first);
     623             :             ++__pos;
     624             :           }
     625             :       }
     626             : 
     627             :   template<typename _Tp, typename _Alloc>
     628             :     template<typename _ForwardIterator>
     629             :       void
     630             :       vector<_Tp, _Alloc>::
     631             :       _M_range_insert(iterator __position, _ForwardIterator __first,
     632             :                       _ForwardIterator __last, std::forward_iterator_tag)
     633             :       {
     634             :         if (__first != __last)
     635             :           {
     636             :             const size_type __n = std::distance(__first, __last);
     637             :             if (size_type(this->_M_impl._M_end_of_storage
     638             :                           - this->_M_impl._M_finish) >= __n)
     639             :               {
     640             :                 const size_type __elems_after = end() - __position;
     641             :                 pointer __old_finish(this->_M_impl._M_finish);
     642             :                 if (__elems_after > __n)
     643             :                   {
     644             :                     std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
     645             :                                                 this->_M_impl._M_finish,
     646             :                                                 this->_M_impl._M_finish,
     647             :                                                 _M_get_Tp_allocator());
     648             :                     this->_M_impl._M_finish += __n;
     649             :                     _GLIBCXX_MOVE_BACKWARD3(__position.base(),
     650             :                                             __old_finish - __n, __old_finish);
     651             :                     std::copy(__first, __last, __position);
     652             :                   }
     653             :                 else
     654             :                   {
     655             :                     _ForwardIterator __mid = __first;
     656             :                     std::advance(__mid, __elems_after);
     657             :                     std::__uninitialized_copy_a(__mid, __last,
     658             :                                                 this->_M_impl._M_finish,
     659             :                                                 _M_get_Tp_allocator());
     660             :                     this->_M_impl._M_finish += __n - __elems_after;
     661             :                     std::__uninitialized_move_a(__position.base(),
     662             :                                                 __old_finish,
     663             :                                                 this->_M_impl._M_finish,
     664             :                                                 _M_get_Tp_allocator());
     665             :                     this->_M_impl._M_finish += __elems_after;
     666             :                     std::copy(__first, __mid, __position);
     667             :                   }
     668             :               }
     669             :             else
     670             :               {
     671             :                 const size_type __len =
     672             :                   _M_check_len(__n, "vector::_M_range_insert");
     673             :                 pointer __new_start(this->_M_allocate(__len));
     674             :                 pointer __new_finish(__new_start);
     675             :                 __try
     676             :                   {
     677             :                     __new_finish
     678             :                       = std::__uninitialized_move_if_noexcept_a
     679             :                       (this->_M_impl._M_start, __position.base(),
     680             :                        __new_start, _M_get_Tp_allocator());
     681             :                     __new_finish
     682             :                       = std::__uninitialized_copy_a(__first, __last,
     683             :                                                     __new_finish,
     684             :                                                     _M_get_Tp_allocator());
     685             :                     __new_finish
     686             :                       = std::__uninitialized_move_if_noexcept_a
     687             :                       (__position.base(), this->_M_impl._M_finish,
     688             :                        __new_finish, _M_get_Tp_allocator());
     689             :                   }
     690             :                 __catch(...)
     691             :                   {
     692             :                     std::_Destroy(__new_start, __new_finish,
     693             :                                   _M_get_Tp_allocator());
     694             :                     _M_deallocate(__new_start, __len);
     695             :                     __throw_exception_again;
     696             :                   }
     697             :                 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
     698             :                               _M_get_Tp_allocator());
     699             :                 _M_deallocate(this->_M_impl._M_start,
     700             :                               this->_M_impl._M_end_of_storage
     701             :                               - this->_M_impl._M_start);
     702             :                 this->_M_impl._M_start = __new_start;
     703             :                 this->_M_impl._M_finish = __new_finish;
     704             :                 this->_M_impl._M_end_of_storage = __new_start + __len;
     705             :               }
     706             :           }
     707             :       }
     708             : 
     709             : 
     710             :   // vector<bool>
     711             :   template<typename _Alloc>
     712             :     void
     713             :     vector<bool, _Alloc>::
     714             :     _M_reallocate(size_type __n)
     715             :     {
     716             :       _Bit_pointer __q = this->_M_allocate(__n);
     717             :       iterator __start(std::__addressof(*__q), 0);
     718             :       iterator __finish(_M_copy_aligned(begin(), end(), __start));
     719             :       this->_M_deallocate();
     720             :       this->_M_impl._M_start = __start;
     721             :       this->_M_impl._M_finish = __finish;
     722             :       this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
     723             :     }
     724             : 
     725             :   template<typename _Alloc>
     726             :     void
     727             :     vector<bool, _Alloc>::
     728             :     _M_fill_insert(iterator __position, size_type __n, bool __x)
     729             :     {
     730             :       if (__n == 0)
     731             :         return;
     732             :       if (capacity() - size() >= __n)
     733             :         {
     734             :           std::copy_backward(__position, end(),
     735             :                              this->_M_impl._M_finish + difference_type(__n));
     736             :           std::fill(__position, __position + difference_type(__n), __x);
     737             :           this->_M_impl._M_finish += difference_type(__n);
     738             :         }
     739             :       else
     740             :         {
     741             :           const size_type __len = 
     742             :             _M_check_len(__n, "vector<bool>::_M_fill_insert");
     743             :           _Bit_pointer __q = this->_M_allocate(__len);
     744             :           iterator __start(std::__addressof(*__q), 0);
     745             :           iterator __i = _M_copy_aligned(begin(), __position, __start);
     746             :           std::fill(__i, __i + difference_type(__n), __x);
     747             :           iterator __finish = std::copy(__position, end(),
     748             :                                         __i + difference_type(__n));
     749             :           this->_M_deallocate();
     750             :           this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
     751             :           this->_M_impl._M_start = __start;
     752             :           this->_M_impl._M_finish = __finish;
     753             :         }
     754             :     }
     755             : 
     756             :   template<typename _Alloc>
     757             :     template<typename _ForwardIterator>
     758             :       void
     759             :       vector<bool, _Alloc>::
     760             :       _M_insert_range(iterator __position, _ForwardIterator __first, 
     761             :                       _ForwardIterator __last, std::forward_iterator_tag)
     762             :       {
     763             :         if (__first != __last)
     764             :           {
     765             :             size_type __n = std::distance(__first, __last);
     766             :             if (capacity() - size() >= __n)
     767             :               {
     768             :                 std::copy_backward(__position, end(),
     769             :                                    this->_M_impl._M_finish
     770             :                                    + difference_type(__n));
     771             :                 std::copy(__first, __last, __position);
     772             :                 this->_M_impl._M_finish += difference_type(__n);
     773             :               }
     774             :             else
     775             :               {
     776             :                 const size_type __len =
     777             :                   _M_check_len(__n, "vector<bool>::_M_insert_range");
     778             :                 _Bit_pointer __q = this->_M_allocate(__len);
     779             :                 iterator __start(std::__addressof(*__q), 0);
     780             :                 iterator __i = _M_copy_aligned(begin(), __position, __start);
     781             :                 __i = std::copy(__first, __last, __i);
     782             :                 iterator __finish = std::copy(__position, end(), __i);
     783             :                 this->_M_deallocate();
     784             :                 this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
     785             :                 this->_M_impl._M_start = __start;
     786             :                 this->_M_impl._M_finish = __finish;
     787             :               }
     788             :           }
     789             :       }
     790             : 
     791             :   template<typename _Alloc>
     792             :     void
     793             :     vector<bool, _Alloc>::
     794             :     _M_insert_aux(iterator __position, bool __x)
     795             :     {
     796             :       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
     797             :         {
     798             :           std::copy_backward(__position, this->_M_impl._M_finish, 
     799             :                              this->_M_impl._M_finish + 1);
     800             :           *__position = __x;
     801             :           ++this->_M_impl._M_finish;
     802             :         }
     803             :       else
     804             :         {
     805             :           const size_type __len =
     806             :             _M_check_len(size_type(1), "vector<bool>::_M_insert_aux");
     807             :           _Bit_pointer __q = this->_M_allocate(__len);
     808             :           iterator __start(std::__addressof(*__q), 0);
     809             :           iterator __i = _M_copy_aligned(begin(), __position, __start);
     810             :           *__i++ = __x;
     811             :           iterator __finish = std::copy(__position, end(), __i);
     812             :           this->_M_deallocate();
     813             :           this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
     814             :           this->_M_impl._M_start = __start;
     815             :           this->_M_impl._M_finish = __finish;
     816             :         }
     817             :     }
     818             : 
     819             :   template<typename _Alloc>
     820             :     typename vector<bool, _Alloc>::iterator
     821             :     vector<bool, _Alloc>::
     822             :     _M_erase(iterator __position)
     823             :     {
     824             :       if (__position + 1 != end())
     825             :         std::copy(__position + 1, end(), __position);
     826             :       --this->_M_impl._M_finish;
     827             :       return __position;
     828             :     }
     829             : 
     830             :   template<typename _Alloc>
     831             :     typename vector<bool, _Alloc>::iterator
     832             :     vector<bool, _Alloc>::
     833             :     _M_erase(iterator __first, iterator __last)
     834             :     {
     835             :       if (__first != __last)
     836             :         _M_erase_at_end(std::copy(__last, end(), __first));
     837             :       return __first;
     838             :     }
     839             : 
     840             : #if __cplusplus >= 201103L
     841             :   template<typename _Alloc>
     842             :     bool
     843             :     vector<bool, _Alloc>::
     844             :     _M_shrink_to_fit()
     845             :     {
     846             :       if (capacity() - size() < int(_S_word_bit))
     847             :         return false;
     848             :       __try
     849             :         {
     850             :           _M_reallocate(size());
     851             :           return true;
     852             :         }
     853             :       __catch(...)
     854             :         { return false; }
     855             :     }
     856             : #endif
     857             : 
     858             : _GLIBCXX_END_NAMESPACE_CONTAINER
     859             : } // namespace std
     860             : 
     861             : #if __cplusplus >= 201103L
     862             : 
     863             : namespace std _GLIBCXX_VISIBILITY(default)
     864             : {
     865             : _GLIBCXX_BEGIN_NAMESPACE_VERSION
     866             : 
     867             :   template<typename _Alloc>
     868             :     size_t
     869             :     hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>::
     870             :     operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const noexcept
     871             :     {
     872             :       size_t __hash = 0;
     873             :       using _GLIBCXX_STD_C::_S_word_bit;
     874             :       using _GLIBCXX_STD_C::_Bit_type;
     875             : 
     876             :       const size_t __words = __b.size() / _S_word_bit;
     877             :       if (__words)
     878             :         {
     879             :           const size_t __clength = __words * sizeof(_Bit_type);
     880             :           __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength);
     881             :         }
     882             : 
     883             :       const size_t __extrabits = __b.size() % _S_word_bit;
     884             :       if (__extrabits)
     885             :         {
     886             :           _Bit_type __hiword = *__b._M_impl._M_finish._M_p;
     887             :           __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits);
     888             : 
     889             :           const size_t __clength
     890             :             = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__;
     891             :           if (__words)
     892             :             __hash = std::_Hash_impl::hash(&__hiword, __clength, __hash);
     893             :           else
     894             :             __hash = std::_Hash_impl::hash(&__hiword, __clength);
     895             :         }
     896             : 
     897             :       return __hash;
     898             :     }
     899             : 
     900             : _GLIBCXX_END_NAMESPACE_VERSION
     901             : } // namespace std
     902             : 
     903             : #endif // C++11
     904             : 
     905             : #endif /* _VECTOR_TCC */

Generated by: LCOV version 1.13