libstdc++
vector.tcc
Go to the documentation of this file.
00001 // Vector implementation (out of line) -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2017 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /*
00026  *
00027  * Copyright (c) 1994
00028  * Hewlett-Packard Company
00029  *
00030  * Permission to use, copy, modify, distribute and sell this software
00031  * and its documentation for any purpose is hereby granted without fee,
00032  * provided that the above copyright notice appear in all copies and
00033  * that both that copyright notice and this permission notice appear
00034  * in supporting documentation.  Hewlett-Packard Company makes no
00035  * representations about the suitability of this software for any
00036  * purpose.  It is provided "as is" without express or implied warranty.
00037  *
00038  *
00039  * Copyright (c) 1996
00040  * Silicon Graphics Computer Systems, Inc.
00041  *
00042  * Permission to use, copy, modify, distribute and sell this software
00043  * and its documentation for any purpose is hereby granted without fee,
00044  * provided that the above copyright notice appear in all copies and
00045  * that both that copyright notice and this permission notice appear
00046  * in supporting documentation.  Silicon Graphics makes no
00047  * representations about the suitability of this  software for any
00048  * purpose.  It is provided "as is" without express or implied warranty.
00049  */
00050 
00051 /** @file bits/vector.tcc
00052  *  This is an internal header file, included by other library headers.
00053  *  Do not attempt to use it directly. @headername{vector}
00054  */
00055 
00056 #ifndef _VECTOR_TCC
00057 #define _VECTOR_TCC 1
00058 
00059 namespace std _GLIBCXX_VISIBILITY(default)
00060 {
00061 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00062 
00063   template<typename _Tp, typename _Alloc>
00064     void
00065     vector<_Tp, _Alloc>::
00066     reserve(size_type __n)
00067     {
00068       if (__n > this->max_size())
00069         __throw_length_error(__N("vector::reserve"));
00070       if (this->capacity() < __n)
00071         {
00072           const size_type __old_size = size();
00073           pointer __tmp = _M_allocate_and_copy(__n,
00074             _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_start),
00075             _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_finish));
00076           std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00077                         _M_get_Tp_allocator());
00078           _M_deallocate(this->_M_impl._M_start,
00079                         this->_M_impl._M_end_of_storage
00080                         - this->_M_impl._M_start);
00081           this->_M_impl._M_start = __tmp;
00082           this->_M_impl._M_finish = __tmp + __old_size;
00083           this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
00084         }
00085     }
00086 
00087 #if __cplusplus >= 201103L
00088   template<typename _Tp, typename _Alloc>
00089     template<typename... _Args>
00090 #if __cplusplus > 201402L
00091       typename vector<_Tp, _Alloc>::reference
00092 #else
00093       void
00094 #endif
00095       vector<_Tp, _Alloc>::
00096       emplace_back(_Args&&... __args)
00097       {
00098         if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
00099           {
00100             _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
00101                                      std::forward<_Args>(__args)...);
00102             ++this->_M_impl._M_finish;
00103           }
00104         else
00105           _M_realloc_insert(end(), std::forward<_Args>(__args)...);
00106 #if __cplusplus > 201402L
00107         return back();
00108 #endif
00109       }
00110 #endif
00111 
00112   template<typename _Tp, typename _Alloc>
00113     typename vector<_Tp, _Alloc>::iterator
00114     vector<_Tp, _Alloc>::
00115 #if __cplusplus >= 201103L
00116     insert(const_iterator __position, const value_type& __x)
00117 #else
00118     insert(iterator __position, const value_type& __x)
00119 #endif
00120     {
00121       const size_type __n = __position - begin();
00122       if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
00123         if (__position == end())
00124           {
00125             _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
00126                                      __x);
00127             ++this->_M_impl._M_finish;
00128           }
00129         else
00130           {
00131 #if __cplusplus >= 201103L
00132             const auto __pos = begin() + (__position - cbegin());
00133             // __x could be an existing element of this vector, so make a
00134             // copy of it before _M_insert_aux moves elements around.
00135             _Temporary_value __x_copy(this, __x);
00136             _M_insert_aux(__pos, std::move(__x_copy._M_val()));
00137 #else
00138             _M_insert_aux(__position, __x);
00139 #endif
00140           }
00141       else
00142 #if __cplusplus >= 201103L
00143         _M_realloc_insert(begin() + (__position - cbegin()), __x);
00144 #else
00145         _M_realloc_insert(__position, __x);
00146 #endif
00147 
00148       return iterator(this->_M_impl._M_start + __n);
00149     }
00150 
00151   template<typename _Tp, typename _Alloc>
00152     typename vector<_Tp, _Alloc>::iterator
00153     vector<_Tp, _Alloc>::
00154     _M_erase(iterator __position)
00155     {
00156       if (__position + 1 != end())
00157         _GLIBCXX_MOVE3(__position + 1, end(), __position);
00158       --this->_M_impl._M_finish;
00159       _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
00160       return __position;
00161     }
00162 
00163   template<typename _Tp, typename _Alloc>
00164     typename vector<_Tp, _Alloc>::iterator
00165     vector<_Tp, _Alloc>::
00166     _M_erase(iterator __first, iterator __last)
00167     {
00168       if (__first != __last)
00169         {
00170           if (__last != end())
00171             _GLIBCXX_MOVE3(__last, end(), __first);
00172           _M_erase_at_end(__first.base() + (end() - __last));
00173         }
00174       return __first;
00175     }
00176 
00177   template<typename _Tp, typename _Alloc>
00178     vector<_Tp, _Alloc>&
00179     vector<_Tp, _Alloc>::
00180     operator=(const vector<_Tp, _Alloc>& __x)
00181     {
00182       if (&__x != this)
00183         {
00184 #if __cplusplus >= 201103L
00185           if (_Alloc_traits::_S_propagate_on_copy_assign())
00186             {
00187               if (!_Alloc_traits::_S_always_equal()
00188                   && _M_get_Tp_allocator() != __x._M_get_Tp_allocator())
00189                 {
00190                   // replacement allocator cannot free existing storage
00191                   this->clear();
00192                   _M_deallocate(this->_M_impl._M_start,
00193                                 this->_M_impl._M_end_of_storage
00194                                 - this->_M_impl._M_start);
00195                   this->_M_impl._M_start = nullptr;
00196                   this->_M_impl._M_finish = nullptr;
00197                   this->_M_impl._M_end_of_storage = nullptr;
00198                 }
00199               std::__alloc_on_copy(_M_get_Tp_allocator(),
00200                                    __x._M_get_Tp_allocator());
00201             }
00202 #endif
00203           const size_type __xlen = __x.size();
00204           if (__xlen > capacity())
00205             {
00206               pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(),
00207                                                    __x.end());
00208               std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00209                             _M_get_Tp_allocator());
00210               _M_deallocate(this->_M_impl._M_start,
00211                             this->_M_impl._M_end_of_storage
00212                             - this->_M_impl._M_start);
00213               this->_M_impl._M_start = __tmp;
00214               this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen;
00215             }
00216           else if (size() >= __xlen)
00217             {
00218               std::_Destroy(std::copy(__x.begin(), __x.end(), begin()),
00219                             end(), _M_get_Tp_allocator());
00220             }
00221           else
00222             {
00223               std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(),
00224                         this->_M_impl._M_start);
00225               std::__uninitialized_copy_a(__x._M_impl._M_start + size(),
00226                                           __x._M_impl._M_finish,
00227                                           this->_M_impl._M_finish,
00228                                           _M_get_Tp_allocator());
00229             }
00230           this->_M_impl._M_finish = this->_M_impl._M_start + __xlen;
00231         }
00232       return *this;
00233     }
00234 
00235   template<typename _Tp, typename _Alloc>
00236     void
00237     vector<_Tp, _Alloc>::
00238     _M_fill_assign(size_t __n, const value_type& __val)
00239     {
00240       if (__n > capacity())
00241         {
00242           vector __tmp(__n, __val, _M_get_Tp_allocator());
00243           __tmp._M_impl._M_swap_data(this->_M_impl);
00244         }
00245       else if (__n > size())
00246         {
00247           std::fill(begin(), end(), __val);
00248           this->_M_impl._M_finish =
00249             std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
00250                                           __n - size(), __val,
00251                                           _M_get_Tp_allocator());
00252         }
00253       else
00254         _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val));
00255     }
00256 
00257   template<typename _Tp, typename _Alloc>
00258     template<typename _InputIterator>
00259       void
00260       vector<_Tp, _Alloc>::
00261       _M_assign_aux(_InputIterator __first, _InputIterator __last,
00262                     std::input_iterator_tag)
00263       {
00264         pointer __cur(this->_M_impl._M_start);
00265         for (; __first != __last && __cur != this->_M_impl._M_finish;
00266              ++__cur, ++__first)
00267           *__cur = *__first;
00268         if (__first == __last)
00269           _M_erase_at_end(__cur);
00270         else
00271           _M_range_insert(end(), __first, __last,
00272                           std::__iterator_category(__first));
00273       }
00274 
00275   template<typename _Tp, typename _Alloc>
00276     template<typename _ForwardIterator>
00277       void
00278       vector<_Tp, _Alloc>::
00279       _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
00280                     std::forward_iterator_tag)
00281       {
00282         const size_type __len = std::distance(__first, __last);
00283 
00284         if (__len > capacity())
00285           {
00286             pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
00287             std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00288                           _M_get_Tp_allocator());
00289             _M_deallocate(this->_M_impl._M_start,
00290                           this->_M_impl._M_end_of_storage
00291                           - this->_M_impl._M_start);
00292             this->_M_impl._M_start = __tmp;
00293             this->_M_impl._M_finish = this->_M_impl._M_start + __len;
00294             this->_M_impl._M_end_of_storage = this->_M_impl._M_finish;
00295           }
00296         else if (size() >= __len)
00297           _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start));
00298         else
00299           {
00300             _ForwardIterator __mid = __first;
00301             std::advance(__mid, size());
00302             std::copy(__first, __mid, this->_M_impl._M_start);
00303             this->_M_impl._M_finish =
00304               std::__uninitialized_copy_a(__mid, __last,
00305                                           this->_M_impl._M_finish,
00306                                           _M_get_Tp_allocator());
00307           }
00308       }
00309 
00310 #if __cplusplus >= 201103L
00311   template<typename _Tp, typename _Alloc>
00312     auto
00313     vector<_Tp, _Alloc>::
00314     _M_insert_rval(const_iterator __position, value_type&& __v) -> iterator
00315     {
00316       const auto __n = __position - cbegin();
00317       if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
00318         if (__position == cend())
00319           {
00320             _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
00321                                      std::move(__v));
00322             ++this->_M_impl._M_finish;
00323           }
00324         else
00325           _M_insert_aux(begin() + __n, std::move(__v));
00326       else
00327         _M_realloc_insert(begin() + __n, std::move(__v));
00328 
00329       return iterator(this->_M_impl._M_start + __n);
00330     }
00331 
00332   template<typename _Tp, typename _Alloc>
00333     template<typename... _Args>
00334       auto
00335       vector<_Tp, _Alloc>::
00336       _M_emplace_aux(const_iterator __position, _Args&&... __args)
00337       -> iterator
00338       {
00339         const auto __n = __position - cbegin();
00340         if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
00341           if (__position == cend())
00342             {
00343               _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
00344                                        std::forward<_Args>(__args)...);
00345               ++this->_M_impl._M_finish;
00346             }
00347           else
00348             {
00349               // We need to construct a temporary because something in __args...
00350               // could alias one of the elements of the container and so we
00351               // need to use it before _M_insert_aux moves elements around.
00352               _Temporary_value __tmp(this, std::forward<_Args>(__args)...);
00353               _M_insert_aux(begin() + __n, std::move(__tmp._M_val()));
00354             }
00355         else
00356           _M_realloc_insert(begin() + __n, std::forward<_Args>(__args)...);
00357 
00358         return iterator(this->_M_impl._M_start + __n);
00359       }
00360 
00361   template<typename _Tp, typename _Alloc>
00362     template<typename _Arg>
00363       void
00364       vector<_Tp, _Alloc>::
00365       _M_insert_aux(iterator __position, _Arg&& __arg)
00366 #else
00367   template<typename _Tp, typename _Alloc>
00368     void
00369     vector<_Tp, _Alloc>::
00370     _M_insert_aux(iterator __position, const _Tp& __x)
00371 #endif
00372     {
00373       _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
00374                                _GLIBCXX_MOVE(*(this->_M_impl._M_finish
00375                                                - 1)));
00376       ++this->_M_impl._M_finish;
00377 #if __cplusplus < 201103L
00378       _Tp __x_copy = __x;
00379 #endif
00380       _GLIBCXX_MOVE_BACKWARD3(__position.base(),
00381                               this->_M_impl._M_finish - 2,
00382                               this->_M_impl._M_finish - 1);
00383 #if __cplusplus < 201103L
00384       *__position = __x_copy;
00385 #else
00386       *__position = std::forward<_Arg>(__arg);
00387 #endif
00388     }
00389 
00390 #if __cplusplus >= 201103L
00391   template<typename _Tp, typename _Alloc>
00392     template<typename... _Args>
00393       void
00394       vector<_Tp, _Alloc>::
00395       _M_realloc_insert(iterator __position, _Args&&... __args)
00396 #else
00397   template<typename _Tp, typename _Alloc>
00398     void
00399     vector<_Tp, _Alloc>::
00400     _M_realloc_insert(iterator __position, const _Tp& __x)
00401 #endif
00402     {
00403       const size_type __len =
00404         _M_check_len(size_type(1), "vector::_M_realloc_insert");
00405       const size_type __elems_before = __position - begin();
00406       pointer __new_start(this->_M_allocate(__len));
00407       pointer __new_finish(__new_start);
00408       __try
00409         {
00410           // The order of the three operations is dictated by the C++11
00411           // case, where the moves could alter a new element belonging
00412           // to the existing vector.  This is an issue only for callers
00413           // taking the element by lvalue ref (see last bullet of C++11
00414           // [res.on.arguments]).
00415           _Alloc_traits::construct(this->_M_impl,
00416                                    __new_start + __elems_before,
00417 #if __cplusplus >= 201103L
00418                                    std::forward<_Args>(__args)...);
00419 #else
00420                                    __x);
00421 #endif
00422           __new_finish = pointer();
00423 
00424           __new_finish
00425             = std::__uninitialized_move_if_noexcept_a
00426             (this->_M_impl._M_start, __position.base(),
00427              __new_start, _M_get_Tp_allocator());
00428 
00429           ++__new_finish;
00430 
00431           __new_finish
00432             = std::__uninitialized_move_if_noexcept_a
00433             (__position.base(), this->_M_impl._M_finish,
00434              __new_finish, _M_get_Tp_allocator());
00435         }
00436       __catch(...)
00437         {
00438           if (!__new_finish)
00439             _Alloc_traits::destroy(this->_M_impl,
00440                                    __new_start + __elems_before);
00441           else
00442             std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
00443           _M_deallocate(__new_start, __len);
00444           __throw_exception_again;
00445         }
00446       std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00447                     _M_get_Tp_allocator());
00448       _M_deallocate(this->_M_impl._M_start,
00449                     this->_M_impl._M_end_of_storage
00450                     - this->_M_impl._M_start);
00451       this->_M_impl._M_start = __new_start;
00452       this->_M_impl._M_finish = __new_finish;
00453       this->_M_impl._M_end_of_storage = __new_start + __len;
00454     }
00455 
00456   template<typename _Tp, typename _Alloc>
00457     void
00458     vector<_Tp, _Alloc>::
00459     _M_fill_insert(iterator __position, size_type __n, const value_type& __x)
00460     {
00461       if (__n != 0)
00462         {
00463           if (size_type(this->_M_impl._M_end_of_storage
00464                         - this->_M_impl._M_finish) >= __n)
00465             {
00466 #if __cplusplus < 201103L
00467               value_type __x_copy = __x;
00468 #else
00469               _Temporary_value __tmp(this, __x);
00470               value_type& __x_copy = __tmp._M_val();
00471 #endif
00472               const size_type __elems_after = end() - __position;
00473               pointer __old_finish(this->_M_impl._M_finish);
00474               if (__elems_after > __n)
00475                 {
00476                   std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
00477                                               this->_M_impl._M_finish,
00478                                               this->_M_impl._M_finish,
00479                                               _M_get_Tp_allocator());
00480                   this->_M_impl._M_finish += __n;
00481                   _GLIBCXX_MOVE_BACKWARD3(__position.base(),
00482                                           __old_finish - __n, __old_finish);
00483                   std::fill(__position.base(), __position.base() + __n,
00484                             __x_copy);
00485                 }
00486               else
00487                 {
00488                   this->_M_impl._M_finish =
00489                     std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
00490                                                   __n - __elems_after,
00491                                                   __x_copy,
00492                                                   _M_get_Tp_allocator());
00493                   std::__uninitialized_move_a(__position.base(), __old_finish,
00494                                               this->_M_impl._M_finish,
00495                                               _M_get_Tp_allocator());
00496                   this->_M_impl._M_finish += __elems_after;
00497                   std::fill(__position.base(), __old_finish, __x_copy);
00498                 }
00499             }
00500           else
00501             {
00502               const size_type __len =
00503                 _M_check_len(__n, "vector::_M_fill_insert");
00504               const size_type __elems_before = __position - begin();
00505               pointer __new_start(this->_M_allocate(__len));
00506               pointer __new_finish(__new_start);
00507               __try
00508                 {
00509                   // See _M_realloc_insert above.
00510                   std::__uninitialized_fill_n_a(__new_start + __elems_before,
00511                                                 __n, __x,
00512                                                 _M_get_Tp_allocator());
00513                   __new_finish = pointer();
00514 
00515                   __new_finish
00516                     = std::__uninitialized_move_if_noexcept_a
00517                     (this->_M_impl._M_start, __position.base(),
00518                      __new_start, _M_get_Tp_allocator());
00519 
00520                   __new_finish += __n;
00521 
00522                   __new_finish
00523                     = std::__uninitialized_move_if_noexcept_a
00524                     (__position.base(), this->_M_impl._M_finish,
00525                      __new_finish, _M_get_Tp_allocator());
00526                 }
00527               __catch(...)
00528                 {
00529                   if (!__new_finish)
00530                     std::_Destroy(__new_start + __elems_before,
00531                                   __new_start + __elems_before + __n,
00532                                   _M_get_Tp_allocator());
00533                   else
00534                     std::_Destroy(__new_start, __new_finish,
00535                                   _M_get_Tp_allocator());
00536                   _M_deallocate(__new_start, __len);
00537                   __throw_exception_again;
00538                 }
00539               std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00540                             _M_get_Tp_allocator());
00541               _M_deallocate(this->_M_impl._M_start,
00542                             this->_M_impl._M_end_of_storage
00543                             - this->_M_impl._M_start);
00544               this->_M_impl._M_start = __new_start;
00545               this->_M_impl._M_finish = __new_finish;
00546               this->_M_impl._M_end_of_storage = __new_start + __len;
00547             }
00548         }
00549     }
00550 
00551 #if __cplusplus >= 201103L
00552   template<typename _Tp, typename _Alloc>
00553     void
00554     vector<_Tp, _Alloc>::
00555     _M_default_append(size_type __n)
00556     {
00557       if (__n != 0)
00558         {
00559           if (size_type(this->_M_impl._M_end_of_storage
00560                         - this->_M_impl._M_finish) >= __n)
00561             {
00562               this->_M_impl._M_finish =
00563                 std::__uninitialized_default_n_a(this->_M_impl._M_finish,
00564                                                  __n, _M_get_Tp_allocator());
00565             }
00566           else
00567             {
00568               const size_type __len =
00569                 _M_check_len(__n, "vector::_M_default_append");
00570               const size_type __old_size = this->size();
00571               pointer __new_start(this->_M_allocate(__len));
00572               pointer __new_finish(__new_start);
00573               __try
00574                 {
00575                   __new_finish
00576                     = std::__uninitialized_move_if_noexcept_a
00577                     (this->_M_impl._M_start, this->_M_impl._M_finish,
00578                      __new_start, _M_get_Tp_allocator());
00579                   __new_finish =
00580                     std::__uninitialized_default_n_a(__new_finish, __n,
00581                                                      _M_get_Tp_allocator());
00582                 }
00583               __catch(...)
00584                 {
00585                   std::_Destroy(__new_start, __new_finish,
00586                                 _M_get_Tp_allocator());
00587                   _M_deallocate(__new_start, __len);
00588                   __throw_exception_again;
00589                 }
00590               std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00591                             _M_get_Tp_allocator());
00592               _M_deallocate(this->_M_impl._M_start,
00593                             this->_M_impl._M_end_of_storage
00594                             - this->_M_impl._M_start);
00595               this->_M_impl._M_start = __new_start;
00596               this->_M_impl._M_finish = __new_finish;
00597               this->_M_impl._M_end_of_storage = __new_start + __len;
00598             }
00599         }
00600     }
00601 
00602   template<typename _Tp, typename _Alloc>
00603     bool
00604     vector<_Tp, _Alloc>::
00605     _M_shrink_to_fit()
00606     {
00607       if (capacity() == size())
00608         return false;
00609       return std::__shrink_to_fit_aux<vector>::_S_do_it(*this);
00610     }
00611 #endif
00612 
00613   template<typename _Tp, typename _Alloc>
00614     template<typename _InputIterator>
00615       void
00616       vector<_Tp, _Alloc>::
00617       _M_range_insert(iterator __pos, _InputIterator __first,
00618                       _InputIterator __last, std::input_iterator_tag)
00619       {
00620         for (; __first != __last; ++__first)
00621           {
00622             __pos = insert(__pos, *__first);
00623             ++__pos;
00624           }
00625       }
00626 
00627   template<typename _Tp, typename _Alloc>
00628     template<typename _ForwardIterator>
00629       void
00630       vector<_Tp, _Alloc>::
00631       _M_range_insert(iterator __position, _ForwardIterator __first,
00632                       _ForwardIterator __last, std::forward_iterator_tag)
00633       {
00634         if (__first != __last)
00635           {
00636             const size_type __n = std::distance(__first, __last);
00637             if (size_type(this->_M_impl._M_end_of_storage
00638                           - this->_M_impl._M_finish) >= __n)
00639               {
00640                 const size_type __elems_after = end() - __position;
00641                 pointer __old_finish(this->_M_impl._M_finish);
00642                 if (__elems_after > __n)
00643                   {
00644                     std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
00645                                                 this->_M_impl._M_finish,
00646                                                 this->_M_impl._M_finish,
00647                                                 _M_get_Tp_allocator());
00648                     this->_M_impl._M_finish += __n;
00649                     _GLIBCXX_MOVE_BACKWARD3(__position.base(),
00650                                             __old_finish - __n, __old_finish);
00651                     std::copy(__first, __last, __position);
00652                   }
00653                 else
00654                   {
00655                     _ForwardIterator __mid = __first;
00656                     std::advance(__mid, __elems_after);
00657                     std::__uninitialized_copy_a(__mid, __last,
00658                                                 this->_M_impl._M_finish,
00659                                                 _M_get_Tp_allocator());
00660                     this->_M_impl._M_finish += __n - __elems_after;
00661                     std::__uninitialized_move_a(__position.base(),
00662                                                 __old_finish,
00663                                                 this->_M_impl._M_finish,
00664                                                 _M_get_Tp_allocator());
00665                     this->_M_impl._M_finish += __elems_after;
00666                     std::copy(__first, __mid, __position);
00667                   }
00668               }
00669             else
00670               {
00671                 const size_type __len =
00672                   _M_check_len(__n, "vector::_M_range_insert");
00673                 pointer __new_start(this->_M_allocate(__len));
00674                 pointer __new_finish(__new_start);
00675                 __try
00676                   {
00677                     __new_finish
00678                       = std::__uninitialized_move_if_noexcept_a
00679                       (this->_M_impl._M_start, __position.base(),
00680                        __new_start, _M_get_Tp_allocator());
00681                     __new_finish
00682                       = std::__uninitialized_copy_a(__first, __last,
00683                                                     __new_finish,
00684                                                     _M_get_Tp_allocator());
00685                     __new_finish
00686                       = std::__uninitialized_move_if_noexcept_a
00687                       (__position.base(), this->_M_impl._M_finish,
00688                        __new_finish, _M_get_Tp_allocator());
00689                   }
00690                 __catch(...)
00691                   {
00692                     std::_Destroy(__new_start, __new_finish,
00693                                   _M_get_Tp_allocator());
00694                     _M_deallocate(__new_start, __len);
00695                     __throw_exception_again;
00696                   }
00697                 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00698                               _M_get_Tp_allocator());
00699                 _M_deallocate(this->_M_impl._M_start,
00700                               this->_M_impl._M_end_of_storage
00701                               - this->_M_impl._M_start);
00702                 this->_M_impl._M_start = __new_start;
00703                 this->_M_impl._M_finish = __new_finish;
00704                 this->_M_impl._M_end_of_storage = __new_start + __len;
00705               }
00706           }
00707       }
00708 
00709 
00710   // vector<bool>
00711   template<typename _Alloc>
00712     void
00713     vector<bool, _Alloc>::
00714     _M_reallocate(size_type __n)
00715     {
00716       _Bit_pointer __q = this->_M_allocate(__n);
00717       iterator __start(std::__addressof(*__q), 0);
00718       iterator __finish(_M_copy_aligned(begin(), end(), __start));
00719       this->_M_deallocate();
00720       this->_M_impl._M_start = __start;
00721       this->_M_impl._M_finish = __finish;
00722       this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
00723     }
00724 
00725   template<typename _Alloc>
00726     void
00727     vector<bool, _Alloc>::
00728     _M_fill_insert(iterator __position, size_type __n, bool __x)
00729     {
00730       if (__n == 0)
00731         return;
00732       if (capacity() - size() >= __n)
00733         {
00734           std::copy_backward(__position, end(),
00735                              this->_M_impl._M_finish + difference_type(__n));
00736           std::fill(__position, __position + difference_type(__n), __x);
00737           this->_M_impl._M_finish += difference_type(__n);
00738         }
00739       else
00740         {
00741           const size_type __len = 
00742             _M_check_len(__n, "vector<bool>::_M_fill_insert");
00743           _Bit_pointer __q = this->_M_allocate(__len);
00744           iterator __start(std::__addressof(*__q), 0);
00745           iterator __i = _M_copy_aligned(begin(), __position, __start);
00746           std::fill(__i, __i + difference_type(__n), __x);
00747           iterator __finish = std::copy(__position, end(),
00748                                         __i + difference_type(__n));
00749           this->_M_deallocate();
00750           this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
00751           this->_M_impl._M_start = __start;
00752           this->_M_impl._M_finish = __finish;
00753         }
00754     }
00755 
00756   template<typename _Alloc>
00757     template<typename _ForwardIterator>
00758       void
00759       vector<bool, _Alloc>::
00760       _M_insert_range(iterator __position, _ForwardIterator __first, 
00761                       _ForwardIterator __last, std::forward_iterator_tag)
00762       {
00763         if (__first != __last)
00764           {
00765             size_type __n = std::distance(__first, __last);
00766             if (capacity() - size() >= __n)
00767               {
00768                 std::copy_backward(__position, end(),
00769                                    this->_M_impl._M_finish
00770                                    + difference_type(__n));
00771                 std::copy(__first, __last, __position);
00772                 this->_M_impl._M_finish += difference_type(__n);
00773               }
00774             else
00775               {
00776                 const size_type __len =
00777                   _M_check_len(__n, "vector<bool>::_M_insert_range");
00778                 _Bit_pointer __q = this->_M_allocate(__len);
00779                 iterator __start(std::__addressof(*__q), 0);
00780                 iterator __i = _M_copy_aligned(begin(), __position, __start);
00781                 __i = std::copy(__first, __last, __i);
00782                 iterator __finish = std::copy(__position, end(), __i);
00783                 this->_M_deallocate();
00784                 this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
00785                 this->_M_impl._M_start = __start;
00786                 this->_M_impl._M_finish = __finish;
00787               }
00788           }
00789       }
00790 
00791   template<typename _Alloc>
00792     void
00793     vector<bool, _Alloc>::
00794     _M_insert_aux(iterator __position, bool __x)
00795     {
00796       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
00797         {
00798           std::copy_backward(__position, this->_M_impl._M_finish, 
00799                              this->_M_impl._M_finish + 1);
00800           *__position = __x;
00801           ++this->_M_impl._M_finish;
00802         }
00803       else
00804         {
00805           const size_type __len =
00806             _M_check_len(size_type(1), "vector<bool>::_M_insert_aux");
00807           _Bit_pointer __q = this->_M_allocate(__len);
00808           iterator __start(std::__addressof(*__q), 0);
00809           iterator __i = _M_copy_aligned(begin(), __position, __start);
00810           *__i++ = __x;
00811           iterator __finish = std::copy(__position, end(), __i);
00812           this->_M_deallocate();
00813           this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
00814           this->_M_impl._M_start = __start;
00815           this->_M_impl._M_finish = __finish;
00816         }
00817     }
00818 
00819   template<typename _Alloc>
00820     typename vector<bool, _Alloc>::iterator
00821     vector<bool, _Alloc>::
00822     _M_erase(iterator __position)
00823     {
00824       if (__position + 1 != end())
00825         std::copy(__position + 1, end(), __position);
00826       --this->_M_impl._M_finish;
00827       return __position;
00828     }
00829 
00830   template<typename _Alloc>
00831     typename vector<bool, _Alloc>::iterator
00832     vector<bool, _Alloc>::
00833     _M_erase(iterator __first, iterator __last)
00834     {
00835       if (__first != __last)
00836         _M_erase_at_end(std::copy(__last, end(), __first));
00837       return __first;
00838     }
00839 
00840 #if __cplusplus >= 201103L
00841   template<typename _Alloc>
00842     bool
00843     vector<bool, _Alloc>::
00844     _M_shrink_to_fit()
00845     {
00846       if (capacity() - size() < int(_S_word_bit))
00847         return false;
00848       __try
00849         {
00850           _M_reallocate(size());
00851           return true;
00852         }
00853       __catch(...)
00854         { return false; }
00855     }
00856 #endif
00857 
00858 _GLIBCXX_END_NAMESPACE_CONTAINER
00859 } // namespace std
00860 
00861 #if __cplusplus >= 201103L
00862 
00863 namespace std _GLIBCXX_VISIBILITY(default)
00864 {
00865 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00866 
00867   template<typename _Alloc>
00868     size_t
00869     hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>::
00870     operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const noexcept
00871     {
00872       size_t __hash = 0;
00873       using _GLIBCXX_STD_C::_S_word_bit;
00874       using _GLIBCXX_STD_C::_Bit_type;
00875 
00876       const size_t __words = __b.size() / _S_word_bit;
00877       if (__words)
00878         {
00879           const size_t __clength = __words * sizeof(_Bit_type);
00880           __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength);
00881         }
00882 
00883       const size_t __extrabits = __b.size() % _S_word_bit;
00884       if (__extrabits)
00885         {
00886           _Bit_type __hiword = *__b._M_impl._M_finish._M_p;
00887           __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits);
00888 
00889           const size_t __clength
00890             = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__;
00891           if (__words)
00892             __hash = std::_Hash_impl::hash(&__hiword, __clength, __hash);
00893           else
00894             __hash = std::_Hash_impl::hash(&__hiword, __clength);
00895         }
00896 
00897       return __hash;
00898     }
00899 
00900 _GLIBCXX_END_NAMESPACE_VERSION
00901 } // namespace std
00902 
00903 #endif // C++11
00904 
00905 #endif /* _VECTOR_TCC */