LCOV - code coverage report
Current view: top level - usr/include/c++/6/bits - vector.tcc (source / functions) Hit Total Coverage
Test: coverage.info Lines: 82 120 68.3 %
Date: 2018-11-14 16:53:58 Functions: 25 66 37.9 %

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

Generated by: LCOV version 1.13