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_ITERATOR(this->_M_impl._M_start),
00076          _GLIBCXX_MAKE_MOVE_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         this->_M_impl.construct(this->_M_impl._M_finish,
00098                     std::forward<_Args>(__args)...);
00099         ++this->_M_impl._M_finish;
00100       }
00101     else
00102       _M_insert_aux(end(), 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       this->_M_impl.construct(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       this->_M_impl.destroy(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 (__last != end())
00151     _GLIBCXX_MOVE3(__last, end(), __first);
00152       _M_erase_at_end(__first.base() + (end() - __last));
00153       return __first;
00154     }
00155 
00156   template<typename _Tp, typename _Alloc>
00157     vector<_Tp, _Alloc>&
00158     vector<_Tp, _Alloc>::
00159     operator=(const vector<_Tp, _Alloc>& __x)
00160     {
00161       if (&__x != this)
00162     {
00163       const size_type __xlen = __x.size();
00164       if (__xlen > capacity())
00165         {
00166           pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(),
00167                            __x.end());
00168           std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00169                 _M_get_Tp_allocator());
00170           _M_deallocate(this->_M_impl._M_start,
00171                 this->_M_impl._M_end_of_storage
00172                 - this->_M_impl._M_start);
00173           this->_M_impl._M_start = __tmp;
00174           this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen;
00175         }
00176       else if (size() >= __xlen)
00177         {
00178           std::_Destroy(std::copy(__x.begin(), __x.end(), begin()),
00179                 end(), _M_get_Tp_allocator());
00180         }
00181       else
00182         {
00183           std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(),
00184             this->_M_impl._M_start);
00185           std::__uninitialized_copy_a(__x._M_impl._M_start + size(),
00186                       __x._M_impl._M_finish,
00187                       this->_M_impl._M_finish,
00188                       _M_get_Tp_allocator());
00189         }
00190       this->_M_impl._M_finish = this->_M_impl._M_start + __xlen;
00191     }
00192       return *this;
00193     }
00194 
00195   template<typename _Tp, typename _Alloc>
00196     void
00197     vector<_Tp, _Alloc>::
00198     _M_fill_assign(size_t __n, const value_type& __val)
00199     {
00200       if (__n > capacity())
00201     {
00202       vector __tmp(__n, __val, _M_get_Tp_allocator());
00203       __tmp.swap(*this);
00204     }
00205       else if (__n > size())
00206     {
00207       std::fill(begin(), end(), __val);
00208       std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
00209                     __n - size(), __val,
00210                     _M_get_Tp_allocator());
00211       this->_M_impl._M_finish += __n - size();
00212     }
00213       else
00214         _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val));
00215     }
00216 
00217   template<typename _Tp, typename _Alloc>
00218     template<typename _InputIterator>
00219       void
00220       vector<_Tp, _Alloc>::
00221       _M_assign_aux(_InputIterator __first, _InputIterator __last,
00222             std::input_iterator_tag)
00223       {
00224     pointer __cur(this->_M_impl._M_start);
00225     for (; __first != __last && __cur != this->_M_impl._M_finish;
00226          ++__cur, ++__first)
00227       *__cur = *__first;
00228     if (__first == __last)
00229       _M_erase_at_end(__cur);
00230     else
00231       insert(end(), __first, __last);
00232       }
00233 
00234   template<typename _Tp, typename _Alloc>
00235     template<typename _ForwardIterator>
00236       void
00237       vector<_Tp, _Alloc>::
00238       _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
00239             std::forward_iterator_tag)
00240       {
00241     const size_type __len = std::distance(__first, __last);
00242 
00243     if (__len > capacity())
00244       {
00245         pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
00246         std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00247               _M_get_Tp_allocator());
00248         _M_deallocate(this->_M_impl._M_start,
00249               this->_M_impl._M_end_of_storage
00250               - this->_M_impl._M_start);
00251         this->_M_impl._M_start = __tmp;
00252         this->_M_impl._M_finish = this->_M_impl._M_start + __len;
00253         this->_M_impl._M_end_of_storage = this->_M_impl._M_finish;
00254       }
00255     else if (size() >= __len)
00256       _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start));
00257     else
00258       {
00259         _ForwardIterator __mid = __first;
00260         std::advance(__mid, size());
00261         std::copy(__first, __mid, this->_M_impl._M_start);
00262         this->_M_impl._M_finish =
00263           std::__uninitialized_copy_a(__mid, __last,
00264                       this->_M_impl._M_finish,
00265                       _M_get_Tp_allocator());
00266       }
00267       }
00268 
00269 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00270   template<typename _Tp, typename _Alloc>
00271     template<typename... _Args>
00272       typename vector<_Tp, _Alloc>::iterator
00273       vector<_Tp, _Alloc>::
00274       emplace(iterator __position, _Args&&... __args)
00275       {
00276     const size_type __n = __position - begin();
00277     if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
00278         && __position == end())
00279       {
00280         this->_M_impl.construct(this->_M_impl._M_finish,
00281                     std::forward<_Args>(__args)...);
00282         ++this->_M_impl._M_finish;
00283       }
00284     else
00285       _M_insert_aux(__position, std::forward<_Args>(__args)...);
00286     return iterator(this->_M_impl._M_start + __n);
00287       }
00288 
00289   template<typename _Tp, typename _Alloc>
00290     template<typename... _Args>
00291       void
00292       vector<_Tp, _Alloc>::
00293       _M_insert_aux(iterator __position, _Args&&... __args)
00294 #else
00295   template<typename _Tp, typename _Alloc>
00296     void
00297     vector<_Tp, _Alloc>::
00298     _M_insert_aux(iterator __position, const _Tp& __x)
00299 #endif
00300     {
00301       if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
00302     {
00303       this->_M_impl.construct(this->_M_impl._M_finish,
00304                   _GLIBCXX_MOVE(*(this->_M_impl._M_finish
00305                           - 1)));
00306       ++this->_M_impl._M_finish;
00307 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00308       _Tp __x_copy = __x;
00309 #endif
00310       _GLIBCXX_MOVE_BACKWARD3(__position.base(),
00311                   this->_M_impl._M_finish - 2,
00312                   this->_M_impl._M_finish - 1);
00313 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00314       *__position = __x_copy;
00315 #else
00316       *__position = _Tp(std::forward<_Args>(__args)...);
00317 #endif
00318     }
00319       else
00320     {
00321       const size_type __len =
00322         _M_check_len(size_type(1), "vector::_M_insert_aux");
00323       const size_type __elems_before = __position - begin();
00324       pointer __new_start(this->_M_allocate(__len));
00325       pointer __new_finish(__new_start);
00326       __try
00327         {
00328           // The order of the three operations is dictated by the C++0x
00329           // case, where the moves could alter a new element belonging
00330           // to the existing vector.  This is an issue only for callers
00331           // taking the element by const lvalue ref (see 23.1/13).
00332           this->_M_impl.construct(__new_start + __elems_before,
00333 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00334                       std::forward<_Args>(__args)...);
00335 #else
00336                                   __x);
00337 #endif
00338           __new_finish = 0;
00339 
00340           __new_finish =
00341         std::__uninitialized_move_a(this->_M_impl._M_start,
00342                         __position.base(), __new_start,
00343                         _M_get_Tp_allocator());
00344           ++__new_finish;
00345 
00346           __new_finish =
00347         std::__uninitialized_move_a(__position.base(),
00348                         this->_M_impl._M_finish,
00349                         __new_finish,
00350                         _M_get_Tp_allocator());
00351         }
00352           __catch(...)
00353         {
00354           if (!__new_finish)
00355         this->_M_impl.destroy(__new_start + __elems_before);
00356           else
00357         std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
00358           _M_deallocate(__new_start, __len);
00359           __throw_exception_again;
00360         }
00361       std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00362             _M_get_Tp_allocator());
00363       _M_deallocate(this->_M_impl._M_start,
00364             this->_M_impl._M_end_of_storage
00365             - this->_M_impl._M_start);
00366       this->_M_impl._M_start = __new_start;
00367       this->_M_impl._M_finish = __new_finish;
00368       this->_M_impl._M_end_of_storage = __new_start + __len;
00369     }
00370     }
00371 
00372   template<typename _Tp, typename _Alloc>
00373     void
00374     vector<_Tp, _Alloc>::
00375     _M_fill_insert(iterator __position, size_type __n, const value_type& __x)
00376     {
00377       if (__n != 0)
00378     {
00379       if (size_type(this->_M_impl._M_end_of_storage
00380             - this->_M_impl._M_finish) >= __n)
00381         {
00382           value_type __x_copy = __x;
00383           const size_type __elems_after = end() - __position;
00384           pointer __old_finish(this->_M_impl._M_finish);
00385           if (__elems_after > __n)
00386         {
00387           std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
00388                           this->_M_impl._M_finish,
00389                           this->_M_impl._M_finish,
00390                           _M_get_Tp_allocator());
00391           this->_M_impl._M_finish += __n;
00392           _GLIBCXX_MOVE_BACKWARD3(__position.base(),
00393                       __old_finish - __n, __old_finish);
00394           std::fill(__position.base(), __position.base() + __n,
00395                 __x_copy);
00396         }
00397           else
00398         {
00399           std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
00400                         __n - __elems_after,
00401                         __x_copy,
00402                         _M_get_Tp_allocator());
00403           this->_M_impl._M_finish += __n - __elems_after;
00404           std::__uninitialized_move_a(__position.base(), __old_finish,
00405                           this->_M_impl._M_finish,
00406                           _M_get_Tp_allocator());
00407           this->_M_impl._M_finish += __elems_after;
00408           std::fill(__position.base(), __old_finish, __x_copy);
00409         }
00410         }
00411       else
00412         {
00413           const size_type __len =
00414         _M_check_len(__n, "vector::_M_fill_insert");
00415           const size_type __elems_before = __position - begin();
00416           pointer __new_start(this->_M_allocate(__len));
00417           pointer __new_finish(__new_start);
00418           __try
00419         {
00420           // See _M_insert_aux above.
00421           std::__uninitialized_fill_n_a(__new_start + __elems_before,
00422                         __n, __x,
00423                         _M_get_Tp_allocator());
00424           __new_finish = 0;
00425 
00426           __new_finish =
00427             std::__uninitialized_move_a(this->_M_impl._M_start,
00428                         __position.base(),
00429                         __new_start,
00430                         _M_get_Tp_allocator());
00431           __new_finish += __n;
00432 
00433           __new_finish =
00434             std::__uninitialized_move_a(__position.base(),
00435                         this->_M_impl._M_finish,
00436                         __new_finish,
00437                         _M_get_Tp_allocator());
00438         }
00439           __catch(...)
00440         {
00441           if (!__new_finish)
00442             std::_Destroy(__new_start + __elems_before,
00443                   __new_start + __elems_before + __n,
00444                   _M_get_Tp_allocator());
00445           else
00446             std::_Destroy(__new_start, __new_finish,
00447                   _M_get_Tp_allocator());
00448           _M_deallocate(__new_start, __len);
00449           __throw_exception_again;
00450         }
00451           std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00452                 _M_get_Tp_allocator());
00453           _M_deallocate(this->_M_impl._M_start,
00454                 this->_M_impl._M_end_of_storage
00455                 - this->_M_impl._M_start);
00456           this->_M_impl._M_start = __new_start;
00457           this->_M_impl._M_finish = __new_finish;
00458           this->_M_impl._M_end_of_storage = __new_start + __len;
00459         }
00460     }
00461     }
00462 
00463 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00464   template<typename _Tp, typename _Alloc>
00465     void
00466     vector<_Tp, _Alloc>::
00467     _M_default_append(size_type __n)
00468     {
00469       if (__n != 0)
00470     {
00471       if (size_type(this->_M_impl._M_end_of_storage
00472             - this->_M_impl._M_finish) >= __n)
00473         {
00474           std::__uninitialized_default_n_a(this->_M_impl._M_finish,
00475                            __n, _M_get_Tp_allocator());
00476           this->_M_impl._M_finish += __n;
00477         }
00478       else
00479         {
00480           const size_type __len =
00481         _M_check_len(__n, "vector::_M_default_append");
00482           const size_type __old_size = this->size();
00483           pointer __new_start(this->_M_allocate(__len));
00484           pointer __new_finish(__new_start);
00485           __try
00486         {
00487           __new_finish =
00488             std::__uninitialized_move_a(this->_M_impl._M_start,
00489                         this->_M_impl._M_finish,
00490                         __new_start,
00491                         _M_get_Tp_allocator());
00492           std::__uninitialized_default_n_a(__new_finish, __n,
00493                            _M_get_Tp_allocator());
00494           __new_finish += __n;
00495         }
00496           __catch(...)
00497         {
00498           std::_Destroy(__new_start, __new_finish,
00499                 _M_get_Tp_allocator());
00500           _M_deallocate(__new_start, __len);
00501           __throw_exception_again;
00502         }
00503           std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00504                 _M_get_Tp_allocator());
00505           _M_deallocate(this->_M_impl._M_start,
00506                 this->_M_impl._M_end_of_storage
00507                 - this->_M_impl._M_start);
00508           this->_M_impl._M_start = __new_start;
00509           this->_M_impl._M_finish = __new_finish;
00510           this->_M_impl._M_end_of_storage = __new_start + __len;
00511         }
00512     }
00513     }
00514 #endif
00515 
00516   template<typename _Tp, typename _Alloc>
00517     template<typename _InputIterator>
00518       void
00519       vector<_Tp, _Alloc>::
00520       _M_range_insert(iterator __pos, _InputIterator __first,
00521               _InputIterator __last, std::input_iterator_tag)
00522       {
00523     for (; __first != __last; ++__first)
00524       {
00525         __pos = insert(__pos, *__first);
00526         ++__pos;
00527       }
00528       }
00529 
00530   template<typename _Tp, typename _Alloc>
00531     template<typename _ForwardIterator>
00532       void
00533       vector<_Tp, _Alloc>::
00534       _M_range_insert(iterator __position, _ForwardIterator __first,
00535               _ForwardIterator __last, std::forward_iterator_tag)
00536       {
00537     if (__first != __last)
00538       {
00539         const size_type __n = std::distance(__first, __last);
00540         if (size_type(this->_M_impl._M_end_of_storage
00541               - this->_M_impl._M_finish) >= __n)
00542           {
00543         const size_type __elems_after = end() - __position;
00544         pointer __old_finish(this->_M_impl._M_finish);
00545         if (__elems_after > __n)
00546           {
00547             std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
00548                         this->_M_impl._M_finish,
00549                         this->_M_impl._M_finish,
00550                         _M_get_Tp_allocator());
00551             this->_M_impl._M_finish += __n;
00552             _GLIBCXX_MOVE_BACKWARD3(__position.base(),
00553                         __old_finish - __n, __old_finish);
00554             std::copy(__first, __last, __position);
00555           }
00556         else
00557           {
00558             _ForwardIterator __mid = __first;
00559             std::advance(__mid, __elems_after);
00560             std::__uninitialized_copy_a(__mid, __last,
00561                         this->_M_impl._M_finish,
00562                         _M_get_Tp_allocator());
00563             this->_M_impl._M_finish += __n - __elems_after;
00564             std::__uninitialized_move_a(__position.base(),
00565                         __old_finish,
00566                         this->_M_impl._M_finish,
00567                         _M_get_Tp_allocator());
00568             this->_M_impl._M_finish += __elems_after;
00569             std::copy(__first, __mid, __position);
00570           }
00571           }
00572         else
00573           {
00574         const size_type __len =
00575           _M_check_len(__n, "vector::_M_range_insert");
00576         pointer __new_start(this->_M_allocate(__len));
00577         pointer __new_finish(__new_start);
00578         __try
00579           {
00580             __new_finish =
00581               std::__uninitialized_move_a(this->_M_impl._M_start,
00582                           __position.base(),
00583                           __new_start,
00584                           _M_get_Tp_allocator());
00585             __new_finish =
00586               std::__uninitialized_copy_a(__first, __last,
00587                           __new_finish,
00588                           _M_get_Tp_allocator());
00589             __new_finish =
00590               std::__uninitialized_move_a(__position.base(),
00591                           this->_M_impl._M_finish,
00592                           __new_finish,
00593                           _M_get_Tp_allocator());
00594           }
00595         __catch(...)
00596           {
00597             std::_Destroy(__new_start, __new_finish,
00598                   _M_get_Tp_allocator());
00599             _M_deallocate(__new_start, __len);
00600             __throw_exception_again;
00601           }
00602         std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00603                   _M_get_Tp_allocator());
00604         _M_deallocate(this->_M_impl._M_start,
00605                   this->_M_impl._M_end_of_storage
00606                   - this->_M_impl._M_start);
00607         this->_M_impl._M_start = __new_start;
00608         this->_M_impl._M_finish = __new_finish;
00609         this->_M_impl._M_end_of_storage = __new_start + __len;
00610           }
00611       }
00612       }
00613 
00614 
00615   // vector<bool>
00616 
00617   template<typename _Alloc>
00618     void
00619     vector<bool, _Alloc>::
00620     reserve(size_type __n)
00621     {
00622       if (__n > this->max_size())
00623     __throw_length_error(__N("vector::reserve"));
00624       if (this->capacity() < __n)
00625     {
00626       _Bit_type* __q = this->_M_allocate(__n);
00627       this->_M_impl._M_finish = _M_copy_aligned(begin(), end(),
00628                             iterator(__q, 0));
00629       this->_M_deallocate();
00630       this->_M_impl._M_start = iterator(__q, 0);
00631       this->_M_impl._M_end_of_storage = (__q + (__n + int(_S_word_bit) - 1)
00632                          / int(_S_word_bit));
00633     }
00634     }
00635 
00636   template<typename _Alloc>
00637     void
00638     vector<bool, _Alloc>::
00639     _M_fill_insert(iterator __position, size_type __n, bool __x)
00640     {
00641       if (__n == 0)
00642     return;
00643       if (capacity() - size() >= __n)
00644     {
00645       std::copy_backward(__position, end(),
00646                  this->_M_impl._M_finish + difference_type(__n));
00647       std::fill(__position, __position + difference_type(__n), __x);
00648       this->_M_impl._M_finish += difference_type(__n);
00649     }
00650       else
00651     {
00652       const size_type __len = 
00653         _M_check_len(__n, "vector<bool>::_M_fill_insert");
00654       _Bit_type * __q = this->_M_allocate(__len);
00655       iterator __i = _M_copy_aligned(begin(), __position,
00656                      iterator(__q, 0));
00657       std::fill(__i, __i + difference_type(__n), __x);
00658       this->_M_impl._M_finish = std::copy(__position, end(),
00659                           __i + difference_type(__n));
00660       this->_M_deallocate();
00661       this->_M_impl._M_end_of_storage = (__q + ((__len
00662                              + int(_S_word_bit) - 1)
00663                             / int(_S_word_bit)));
00664       this->_M_impl._M_start = iterator(__q, 0);
00665     }
00666     }
00667 
00668   template<typename _Alloc>
00669     template<typename _ForwardIterator>
00670       void
00671       vector<bool, _Alloc>::
00672       _M_insert_range(iterator __position, _ForwardIterator __first, 
00673               _ForwardIterator __last, std::forward_iterator_tag)
00674       {
00675     if (__first != __last)
00676       {
00677         size_type __n = std::distance(__first, __last);
00678         if (capacity() - size() >= __n)
00679           {
00680         std::copy_backward(__position, end(),
00681                    this->_M_impl._M_finish
00682                    + difference_type(__n));
00683         std::copy(__first, __last, __position);
00684         this->_M_impl._M_finish += difference_type(__n);
00685           }
00686         else
00687           {
00688         const size_type __len =
00689           _M_check_len(__n, "vector<bool>::_M_insert_range");
00690         _Bit_type * __q = this->_M_allocate(__len);
00691         iterator __i = _M_copy_aligned(begin(), __position,
00692                            iterator(__q, 0));
00693         __i = std::copy(__first, __last, __i);
00694         this->_M_impl._M_finish = std::copy(__position, end(), __i);
00695         this->_M_deallocate();
00696         this->_M_impl._M_end_of_storage = (__q
00697                            + ((__len
00698                                + int(_S_word_bit) - 1)
00699                               / int(_S_word_bit)));
00700         this->_M_impl._M_start = iterator(__q, 0);
00701           }
00702       }
00703       }
00704 
00705   template<typename _Alloc>
00706     void
00707     vector<bool, _Alloc>::
00708     _M_insert_aux(iterator __position, bool __x)
00709     {
00710       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
00711     {
00712       std::copy_backward(__position, this->_M_impl._M_finish, 
00713                  this->_M_impl._M_finish + 1);
00714       *__position = __x;
00715       ++this->_M_impl._M_finish;
00716     }
00717       else
00718     {
00719       const size_type __len =
00720         _M_check_len(size_type(1), "vector<bool>::_M_insert_aux");
00721       _Bit_type * __q = this->_M_allocate(__len);
00722       iterator __i = _M_copy_aligned(begin(), __position,
00723                      iterator(__q, 0));
00724       *__i++ = __x;
00725       this->_M_impl._M_finish = std::copy(__position, end(), __i);
00726       this->_M_deallocate();
00727       this->_M_impl._M_end_of_storage = (__q + ((__len
00728                              + int(_S_word_bit) - 1)
00729                             / int(_S_word_bit)));
00730       this->_M_impl._M_start = iterator(__q, 0);
00731     }
00732     }
00733 
00734 _GLIBCXX_END_NAMESPACE_CONTAINER
00735 } // namespace std
00736 
00737 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00738 
00739 namespace std _GLIBCXX_VISIBILITY(default)
00740 {
00741 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00742 
00743   template<typename _Alloc>
00744     size_t
00745     hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>::
00746     operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const
00747     {
00748       size_t __hash = 0;
00749       using _GLIBCXX_STD_C::_S_word_bit;
00750       using _GLIBCXX_STD_C::_Bit_type;
00751 
00752       const size_t __words = __b.size() / _S_word_bit;
00753       if (__words)
00754     {
00755       const size_t __clength = __words * sizeof(_Bit_type);
00756       __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength);
00757     }
00758 
00759       const size_t __extrabits = __b.size() % _S_word_bit;
00760       if (__extrabits)
00761     {
00762       _Bit_type __hiword = *__b._M_impl._M_finish._M_p;
00763       __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits);
00764 
00765       const size_t __clength
00766         = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__;
00767       if (__words)
00768         __hash = std::_Hash_impl::hash(&__hiword, __clength, __hash);
00769       else
00770         __hash = std::_Hash_impl::hash(&__hiword, __clength);
00771     }
00772 
00773       return __hash;
00774     }
00775 
00776 _GLIBCXX_END_NAMESPACE_VERSION
00777 } // namespace std
00778 
00779 #endif // __GXX_EXPERIMENTAL_CXX0X__
00780 
00781 #endif /* _VECTOR_TCC */