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