# deque.tcc

Go to the documentation of this file.

    00001 // Deque implementation (out of line) -*- C++ -*-
    00002
    00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
    00004 // 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 2, 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 // You should have received a copy of the GNU General Public License along
    00018 // with this library; see the file COPYING.  If not, write to the Free
    00019 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
    00020 // USA.
    00021
    00022 // As a special exception, you may use this file as part of a free software
    00023 // library without restriction.  Specifically, if other files instantiate
    00024 // templates or use macros or inline functions from this file, or you compile
    00025 // this file and link it with other files to produce an executable, this
    00026 // file does not by itself cause the resulting executable to be covered by
    00027 // the GNU General Public License.  This exception does not however
    00028 // invalidate any other reasons why the executable file might be covered by
    00029 // the GNU General Public License.
    00030
    00031 /*
    00032  *
    00033  * Copyright (c) 1994
    00034  * Hewlett-Packard Company
    00035  *
    00036  * Permission to use, copy, modify, distribute and sell this software
    00037  * and its documentation for any purpose is hereby granted without fee,
    00038  * provided that the above copyright notice appear in all copies and
    00039  * that both that copyright notice and this permission notice appear
    00040  * in supporting documentation.  Hewlett-Packard Company makes no
    00041  * representations about the suitability of this software for any
    00042  * purpose.  It is provided "as is" without express or implied warranty.
    00043  *
    00044  *
    00045  * Copyright (c) 1997
    00046  * Silicon Graphics Computer Systems, Inc.
    00047  *
    00048  * Permission to use, copy, modify, distribute and sell this software
    00049  * and its documentation for any purpose is hereby granted without fee,
    00050  * provided that the above copyright notice appear in all copies and
    00051  * that both that copyright notice and this permission notice appear
    00052  * in supporting documentation.  Silicon Graphics makes no
    00053  * representations about the suitability of this software for any
    00054  * purpose.  It is provided "as is" without express or implied warranty.
    00055  */
    00056
    00057 /** @file deque.tcc
    00058  *  This is an internal header file, included by other library headers.
    00059  *  You should not attempt to use it directly.
    00060  */
    00061
    00062 #ifndef _DEQUE_TCC
    00063 #define _DEQUE_TCC 1
    00064
    00065 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
    00066
    00067   template <typename _Tp, typename _Alloc>
    00068     deque<_Tp, _Alloc>&
    00069     deque<_Tp, _Alloc>::
    00070     operator=(const deque& __x)
    00071     {
    00072       const size_type __len = size();
    00073       if (&__x != this)
    00074     {
    00075       if (__len >= __x.size())
    00076         _M_erase_at_end(std::copy(__x.begin(), __x.end(),
    00077                       this->_M_impl._M_start));
    00078       else
    00079         {
    00080           const_iterator __mid = __x.begin() + difference_type(__len);
    00081           std::copy(__x.begin(), __mid, this->_M_impl._M_start);
    00082           insert(this->_M_impl._M_finish, __mid, __x.end());
    00083         }
    00084     }
    00085       return *this;
    00086     }
    00087
    00088   template <typename _Tp, typename _Alloc>
    00089     typename deque<_Tp, _Alloc>::iterator
    00090     deque<_Tp, _Alloc>::
    00091     insert(iterator __position, const value_type& __x)
    00092     {
    00093       if (__position._M_cur == this->_M_impl._M_start._M_cur)
    00094     {
    00095       push_front(__x);
    00096       return this->_M_impl._M_start;
    00097     }
    00098       else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
    00099     {
    00100       push_back(__x);
    00101       iterator __tmp = this->_M_impl._M_finish;
    00102       --__tmp;
    00103       return __tmp;
    00104     }
    00105       else
    00106         return _M_insert_aux(__position, __x);
    00107     }
    00108
    00109   template <typename _Tp, typename _Alloc>
    00110     typename deque<_Tp, _Alloc>::iterator
    00111     deque<_Tp, _Alloc>::
    00112     erase(iterator __position)
    00113     {
    00114       iterator __next = __position;
    00115       ++__next;
    00116       const difference_type __index = __position - begin();
    00117       if (static_cast<size_type>(__index) < (size() >> 1))
    00118     {
    00119       if (__position != begin())
    00120         std::copy_backward(begin(), __position, __next);
    00121       pop_front();
    00122     }
    00123       else
    00124     {
    00125       if (__next != end())
    00126         std::copy(__next, end(), __position);
    00127       pop_back();
    00128     }
    00129       return begin() + __index;
    00130     }
    00131
    00132   template <typename _Tp, typename _Alloc>
    00133     typename deque<_Tp, _Alloc>::iterator
    00134     deque<_Tp, _Alloc>::
    00135     erase(iterator __first, iterator __last)
    00136     {
    00137       if (__first == begin() && __last == end())
    00138     {
    00139       clear();
    00140       return end();
    00141     }
    00142       else
    00143     {
    00144       const difference_type __n = __last - __first;
    00145       const difference_type __elems_before = __first - begin();
    00146       if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2)
    00147         {
    00148           if (__first != begin())
    00149         std::copy_backward(begin(), __first, __last);
    00150           _M_erase_at_begin(begin() + __n);
    00151         }
    00152       else
    00153         {
    00154           if (__last != end())
    00155         std::copy(__last, end(), __first);
    00156           _M_erase_at_end(end() - __n);
    00157         }
    00158       return begin() + __elems_before;
    00159     }
    00160     }
    00161
    00162   template <typename _Tp, class _Alloc>
    00163     template <typename _InputIterator>
    00164       void
    00165       deque<_Tp, _Alloc>::
    00166       _M_assign_aux(_InputIterator __first, _InputIterator __last,
    00167             std::input_iterator_tag)
    00168       {
    00169         iterator __cur = begin();
    00170         for (; __first != __last && __cur != end(); ++__cur, ++__first)
    00171           *__cur = *__first;
    00172         if (__first == __last)
    00173           _M_erase_at_end(__cur);
    00174         else
    00175           insert(end(), __first, __last);
    00176       }
    00177
    00178   template <typename _Tp, typename _Alloc>
    00179     void
    00180     deque<_Tp, _Alloc>::
    00181     _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
    00182     {
    00183       if (__pos._M_cur == this->_M_impl._M_start._M_cur)
    00184     {
    00185       iterator __new_start = _M_reserve_elements_at_front(__n);
    00186       try
    00187         {
    00188           std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
    00189                       __x, _M_get_Tp_allocator());
    00190           this->_M_impl._M_start = __new_start;
    00191         }
    00192       catch(...)
    00193         {
    00194           _M_destroy_nodes(__new_start._M_node,
    00195                    this->_M_impl._M_start._M_node);
    00196           __throw_exception_again;
    00197         }
    00198     }
    00199       else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
    00200     {
    00201       iterator __new_finish = _M_reserve_elements_at_back(__n);
    00202       try
    00203         {
    00204           std::__uninitialized_fill_a(this->_M_impl._M_finish,
    00205                       __new_finish, __x,
    00206                       _M_get_Tp_allocator());
    00207           this->_M_impl._M_finish = __new_finish;
    00208         }
    00209       catch(...)
    00210         {
    00211           _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
    00212                    __new_finish._M_node + 1);
    00213           __throw_exception_again;
    00214         }
    00215     }
    00216       else
    00217         _M_insert_aux(__pos, __n, __x);
    00218     }
    00219
    00220   template <typename _Tp, typename _Alloc>
    00221     void
    00222     deque<_Tp, _Alloc>::
    00223     _M_fill_initialize(const value_type& __value)
    00224     {
    00225       _Map_pointer __cur;
    00226       try
    00227         {
    00228           for (__cur = this->_M_impl._M_start._M_node;
    00229            __cur < this->_M_impl._M_finish._M_node;
    00230            ++__cur)
    00231             std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
    00232                     __value, _M_get_Tp_allocator());
    00233           std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
    00234                       this->_M_impl._M_finish._M_cur,
    00235                       __value, _M_get_Tp_allocator());
    00236         }
    00237       catch(...)
    00238         {
    00239           std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
    00240             _M_get_Tp_allocator());
    00241           __throw_exception_again;
    00242         }
    00243     }
    00244
    00245   template <typename _Tp, typename _Alloc>
    00246     template <typename _InputIterator>
    00247       void
    00248       deque<_Tp, _Alloc>::
    00249       _M_range_initialize(_InputIterator __first, _InputIterator __last,
    00250                           std::input_iterator_tag)
    00251       {
    00252         this->_M_initialize_map(0);
    00253         try
    00254           {
    00255             for (; __first != __last; ++__first)
    00256               push_back(*__first);
    00257           }
    00258         catch(...)
    00259           {
    00260             clear();
    00261             __throw_exception_again;
    00262           }
    00263       }
    00264
    00265   template <typename _Tp, typename _Alloc>
    00266     template <typename _ForwardIterator>
    00267       void
    00268       deque<_Tp, _Alloc>::
    00269       _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
    00270                           std::forward_iterator_tag)
    00271       {
    00272         const size_type __n = std::distance(__first, __last);
    00273         this->_M_initialize_map(__n);
    00274
    00275         _Map_pointer __cur_node;
    00276         try
    00277           {
    00278             for (__cur_node = this->_M_impl._M_start._M_node;
    00279                  __cur_node < this->_M_impl._M_finish._M_node;
    00280                  ++__cur_node)
    00281           {
    00282         _ForwardIterator __mid = __first;
    00283         std::advance(__mid, _S_buffer_size());
    00284         std::__uninitialized_copy_a(__first, __mid, *__cur_node,
    00285                         _M_get_Tp_allocator());
    00286         __first = __mid;
    00287           }
    00288             std::__uninitialized_copy_a(__first, __last,
    00289                     this->_M_impl._M_finish._M_first,
    00290                     _M_get_Tp_allocator());
    00291           }
    00292         catch(...)
    00293           {
    00294             std::_Destroy(this->_M_impl._M_start,
    00295               iterator(*__cur_node, __cur_node),
    00296               _M_get_Tp_allocator());
    00297             __throw_exception_again;
    00298           }
    00299       }
    00300
    00301   // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
    00302   template <typename _Tp, typename _Alloc>
    00303     void
    00304     deque<_Tp, _Alloc>::
    00305     _M_push_back_aux(const value_type& __t)
    00306     {
    00307       value_type __t_copy = __t;
    00308       _M_reserve_map_at_back();
    00309       *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
    00310       try
    00311         {
    00312           this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t_copy);
    00313           this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
    00314                           + 1);
    00315           this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
    00316         }
    00317       catch(...)
    00318         {
    00319           _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
    00320           __throw_exception_again;
    00321         }
    00322     }
    00323
    00324   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
    00325   template <typename _Tp, typename _Alloc>
    00326     void
    00327     deque<_Tp, _Alloc>::
    00328     _M_push_front_aux(const value_type& __t)
    00329     {
    00330       value_type __t_copy = __t;
    00331       _M_reserve_map_at_front();
    00332       *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
    00333       try
    00334         {
    00335           this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
    00336                          - 1);
    00337           this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
    00338           this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t_copy);
    00339         }
    00340       catch(...)
    00341         {
    00342           ++this->_M_impl._M_start;
    00343           _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
    00344           __throw_exception_again;
    00345         }
    00346     }
    00347
    00348   // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
    00349   template <typename _Tp, typename _Alloc>
    00350     void deque<_Tp, _Alloc>::
    00351     _M_pop_back_aux()
    00352     {
    00353       _M_deallocate_node(this->_M_impl._M_finish._M_first);
    00354       this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
    00355       this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
    00356       this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
    00357     }
    00358
    00359   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
    00360   // Note that if the deque has at least one element (a precondition for this
    00361   // member function), and if
    00362   //   _M_impl._M_start._M_cur == _M_impl._M_start._M_last,
    00363   // then the deque must have at least two nodes.
    00364   template <typename _Tp, typename _Alloc>
    00365     void deque<_Tp, _Alloc>::
    00366     _M_pop_front_aux()
    00367     {
    00368       this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
    00369       _M_deallocate_node(this->_M_impl._M_start._M_first);
    00370       this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
    00371       this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
    00372     }
    00373
    00374   template <typename _Tp, typename _Alloc>
    00375     template <typename _InputIterator>
    00376       void
    00377       deque<_Tp, _Alloc>::
    00378       _M_range_insert_aux(iterator __pos,
    00379                           _InputIterator __first, _InputIterator __last,
    00380                           std::input_iterator_tag)
    00381       { std::copy(__first, __last, std::inserter(*this, __pos)); }
    00382
    00383   template <typename _Tp, typename _Alloc>
    00384     template <typename _ForwardIterator>
    00385       void
    00386       deque<_Tp, _Alloc>::
    00387       _M_range_insert_aux(iterator __pos,
    00388                           _ForwardIterator __first, _ForwardIterator __last,
    00389                           std::forward_iterator_tag)
    00390       {
    00391         const size_type __n = std::distance(__first, __last);
    00392         if (__pos._M_cur == this->_M_impl._M_start._M_cur)
    00393       {
    00394         iterator __new_start = _M_reserve_elements_at_front(__n);
    00395         try
    00396           {
    00397         std::__uninitialized_copy_a(__first, __last, __new_start,
    00398                         _M_get_Tp_allocator());
    00399         this->_M_impl._M_start = __new_start;
    00400           }
    00401         catch(...)
    00402           {
    00403         _M_destroy_nodes(__new_start._M_node,
    00404                  this->_M_impl._M_start._M_node);
    00405         __throw_exception_again;
    00406           }
    00407       }
    00408         else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
    00409       {
    00410         iterator __new_finish = _M_reserve_elements_at_back(__n);
    00411         try
    00412           {
    00413         std::__uninitialized_copy_a(__first, __last,
    00414                         this->_M_impl._M_finish,
    00415                         _M_get_Tp_allocator());
    00416         this->_M_impl._M_finish = __new_finish;
    00417           }
    00418         catch(...)
    00419           {
    00420         _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
    00421                  __new_finish._M_node + 1);
    00422         __throw_exception_again;
    00423           }
    00424       }
    00425         else
    00426           _M_insert_aux(__pos, __first, __last, __n);
    00427       }
    00428
    00429   template <typename _Tp, typename _Alloc>
    00430     typename deque<_Tp, _Alloc>::iterator
    00431     deque<_Tp, _Alloc>::
    00432     _M_insert_aux(iterator __pos, const value_type& __x)
    00433     {
    00434       difference_type __index = __pos - this->_M_impl._M_start;
    00435       value_type __x_copy = __x; // XXX copy
    00436       if (static_cast<size_type>(__index) < size() / 2)
    00437     {
    00438       push_front(front());
    00439       iterator __front1 = this->_M_impl._M_start;
    00440       ++__front1;
    00441       iterator __front2 = __front1;
    00442       ++__front2;
    00443       __pos = this->_M_impl._M_start + __index;
    00444       iterator __pos1 = __pos;
    00445       ++__pos1;
    00446       std::copy(__front2, __pos1, __front1);
    00447     }
    00448       else
    00449     {
    00450       push_back(back());
    00451       iterator __back1 = this->_M_impl._M_finish;
    00452       --__back1;
    00453       iterator __back2 = __back1;
    00454       --__back2;
    00455       __pos = this->_M_impl._M_start + __index;
    00456       std::copy_backward(__pos, __back2, __back1);
    00457     }
    00458       *__pos = __x_copy;
    00459       return __pos;
    00460     }
    00461
    00462   template <typename _Tp, typename _Alloc>
    00463     void
    00464     deque<_Tp, _Alloc>::
    00465     _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
    00466     {
    00467       const difference_type __elems_before = __pos - this->_M_impl._M_start;
    00468       const size_type __length = this->size();
    00469       value_type __x_copy = __x;
    00470       if (__elems_before < difference_type(__length / 2))
    00471     {
    00472       iterator __new_start = _M_reserve_elements_at_front(__n);
    00473       iterator __old_start = this->_M_impl._M_start;
    00474       __pos = this->_M_impl._M_start + __elems_before;
    00475       try
    00476         {
    00477           if (__elems_before >= difference_type(__n))
    00478         {
    00479           iterator __start_n = (this->_M_impl._M_start
    00480                     + difference_type(__n));
    00481           std::__uninitialized_copy_a(this->_M_impl._M_start,
    00482                           __start_n, __new_start,
    00483                           _M_get_Tp_allocator());
    00484           this->_M_impl._M_start = __new_start;
    00485           std::copy(__start_n, __pos, __old_start);
    00486           std::fill(__pos - difference_type(__n), __pos, __x_copy);
    00487         }
    00488           else
    00489         {
    00490           std::__uninitialized_copy_fill(this->_M_impl._M_start,
    00491                          __pos, __new_start,
    00492                          this->_M_impl._M_start,
    00493                          __x_copy,
    00494                          _M_get_Tp_allocator());
    00495           this->_M_impl._M_start = __new_start;
    00496           std::fill(__old_start, __pos, __x_copy);
    00497         }
    00498         }
    00499       catch(...)
    00500         {
    00501           _M_destroy_nodes(__new_start._M_node,
    00502                    this->_M_impl._M_start._M_node);
    00503           __throw_exception_again;
    00504         }
    00505     }
    00506       else
    00507     {
    00508       iterator __new_finish = _M_reserve_elements_at_back(__n);
    00509       iterator __old_finish = this->_M_impl._M_finish;
    00510       const difference_type __elems_after =
    00511         difference_type(__length) - __elems_before;
    00512       __pos = this->_M_impl._M_finish - __elems_after;
    00513       try
    00514         {
    00515           if (__elems_after > difference_type(__n))
    00516         {
    00517           iterator __finish_n = (this->_M_impl._M_finish
    00518                      - difference_type(__n));
    00519           std::__uninitialized_copy_a(__finish_n,
    00520                           this->_M_impl._M_finish,
    00521                           this->_M_impl._M_finish,
    00522                           _M_get_Tp_allocator());
    00523           this->_M_impl._M_finish = __new_finish;
    00524           std::copy_backward(__pos, __finish_n, __old_finish);
    00525           std::fill(__pos, __pos + difference_type(__n), __x_copy);
    00526         }
    00527           else
    00528         {
    00529           std::__uninitialized_fill_copy(this->_M_impl._M_finish,
    00530                          __pos + difference_type(__n),
    00531                          __x_copy, __pos,
    00532                          this->_M_impl._M_finish,
    00533                          _M_get_Tp_allocator());
    00534           this->_M_impl._M_finish = __new_finish;
    00535           std::fill(__pos, __old_finish, __x_copy);
    00536         }
    00537         }
    00538       catch(...)
    00539         {
    00540           _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
    00541                    __new_finish._M_node + 1);
    00542           __throw_exception_again;
    00543         }
    00544     }
    00545     }
    00546
    00547   template <typename _Tp, typename _Alloc>
    00548     template <typename _ForwardIterator>
    00549       void
    00550       deque<_Tp, _Alloc>::
    00551       _M_insert_aux(iterator __pos,
    00552                     _ForwardIterator __first, _ForwardIterator __last,
    00553                     size_type __n)
    00554       {
    00555         const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
    00556         const size_type __length = size();
    00557         if (static_cast<size_type>(__elemsbefore) < __length / 2)
    00558       {
    00559         iterator __new_start = _M_reserve_elements_at_front(__n);
    00560         iterator __old_start = this->_M_impl._M_start;
    00561         __pos = this->_M_impl._M_start + __elemsbefore;
    00562         try
    00563           {
    00564         if (__elemsbefore >= difference_type(__n))
    00565           {
    00566             iterator __start_n = (this->_M_impl._M_start
    00567                       + difference_type(__n));
    00568             std::__uninitialized_copy_a(this->_M_impl._M_start,
    00569                         __start_n, __new_start,
    00570                         _M_get_Tp_allocator());
    00571             this->_M_impl._M_start = __new_start;
    00572             std::copy(__start_n, __pos, __old_start);
    00573             std::copy(__first, __last, __pos - difference_type(__n));
    00574           }
    00575         else
    00576           {
    00577             _ForwardIterator __mid = __first;
    00578             std::advance(__mid, difference_type(__n) - __elemsbefore);
    00579             std::__uninitialized_copy_copy(this->_M_impl._M_start,
    00580                            __pos, __first, __mid,
    00581                            __new_start,
    00582                            _M_get_Tp_allocator());
    00583             this->_M_impl._M_start = __new_start;
    00584             std::copy(__mid, __last, __old_start);
    00585           }
    00586           }
    00587         catch(...)
    00588           {
    00589         _M_destroy_nodes(__new_start._M_node,
    00590                  this->_M_impl._M_start._M_node);
    00591         __throw_exception_again;
    00592           }
    00593       }
    00594         else
    00595         {
    00596           iterator __new_finish = _M_reserve_elements_at_back(__n);
    00597           iterator __old_finish = this->_M_impl._M_finish;
    00598           const difference_type __elemsafter =
    00599             difference_type(__length) - __elemsbefore;
    00600           __pos = this->_M_impl._M_finish - __elemsafter;
    00601           try
    00602             {
    00603               if (__elemsafter > difference_type(__n))
    00604         {
    00605           iterator __finish_n = (this->_M_impl._M_finish
    00606                      - difference_type(__n));
    00607           std::__uninitialized_copy_a(__finish_n,
    00608                           this->_M_impl._M_finish,
    00609                           this->_M_impl._M_finish,
    00610                           _M_get_Tp_allocator());
    00611           this->_M_impl._M_finish = __new_finish;
    00612           std::copy_backward(__pos, __finish_n, __old_finish);
    00613           std::copy(__first, __last, __pos);
    00614         }
    00615               else
    00616         {
    00617           _ForwardIterator __mid = __first;
    00618           std::advance(__mid, __elemsafter);
    00619           std::__uninitialized_copy_copy(__mid, __last, __pos,
    00620                          this->_M_impl._M_finish,
    00621                          this->_M_impl._M_finish,
    00622                          _M_get_Tp_allocator());
    00623           this->_M_impl._M_finish = __new_finish;
    00624           std::copy(__first, __mid, __pos);
    00625         }
    00626             }
    00627           catch(...)
    00628             {
    00629               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
    00630                    __new_finish._M_node + 1);
    00631               __throw_exception_again;
    00632             }
    00633         }
    00634       }
    00635
    00636    template<typename _Tp, typename _Alloc>
    00637      void
    00638      deque<_Tp, _Alloc>::
    00639      _M_destroy_data_aux(iterator __first, iterator __last)
    00640      {
    00641        for (_Map_pointer __node = __first._M_node + 1;
    00642         __node < __last._M_node; ++__node)
    00643      std::_Destroy(*__node, *__node + _S_buffer_size(),
    00644                _M_get_Tp_allocator());
    00645
    00646        if (__first._M_node != __last._M_node)
    00647      {
    00648        std::_Destroy(__first._M_cur, __first._M_last,
    00649              _M_get_Tp_allocator());
    00650        std::_Destroy(__last._M_first, __last._M_cur,
    00651              _M_get_Tp_allocator());
    00652      }
    00653        else
    00654      std::_Destroy(__first._M_cur, __last._M_cur,
    00655                _M_get_Tp_allocator());
    00656      }
    00657
    00658   template <typename _Tp, typename _Alloc>
    00659     void
    00660     deque<_Tp, _Alloc>::
    00661     _M_new_elements_at_front(size_type __new_elems)
    00662     {
    00663       if (this->max_size() - this->size() < __new_elems)
    00664     __throw_length_error(__N("deque::_M_new_elements_at_front"));
    00665
    00666       const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
    00667                      / _S_buffer_size());
    00668       _M_reserve_map_at_front(__new_nodes);
    00669       size_type __i;
    00670       try
    00671         {
    00672           for (__i = 1; __i <= __new_nodes; ++__i)
    00673             *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
    00674         }
    00675       catch(...)
    00676         {
    00677           for (size_type __j = 1; __j < __i; ++__j)
    00678             _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
    00679           __throw_exception_again;
    00680         }
    00681     }
    00682
    00683   template <typename _Tp, typename _Alloc>
    00684     void
    00685     deque<_Tp, _Alloc>::
    00686     _M_new_elements_at_back(size_type __new_elems)
    00687     {
    00688       if (this->max_size() - this->size() < __new_elems)
    00689     __throw_length_error(__N("deque::_M_new_elements_at_back"));
    00690
    00691       const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
    00692                      / _S_buffer_size());
    00693       _M_reserve_map_at_back(__new_nodes);
    00694       size_type __i;
    00695       try
    00696         {
    00697           for (__i = 1; __i <= __new_nodes; ++__i)
    00698             *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
    00699         }
    00700       catch(...)
    00701         {
    00702           for (size_type __j = 1; __j < __i; ++__j)
    00703             _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
    00704           __throw_exception_again;
    00705         }
    00706     }
    00707
    00708   template <typename _Tp, typename _Alloc>
    00709     void
    00710     deque<_Tp, _Alloc>::
    00711     _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
    00712     {
    00713       const size_type __old_num_nodes
    00714     = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
    00715       const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
    00716
    00717       _Map_pointer __new_nstart;
    00718       if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
    00719     {
    00720       __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
    00721                      - __new_num_nodes) / 2
    00722                      + (__add_at_front ? __nodes_to_add : 0);
    00723       if (__new_nstart < this->_M_impl._M_start._M_node)
    00724         std::copy(this->_M_impl._M_start._M_node,
    00725               this->_M_impl._M_finish._M_node + 1,
    00726               __new_nstart);
    00727       else
    00728         std::copy_backward(this->_M_impl._M_start._M_node,
    00729                    this->_M_impl._M_finish._M_node + 1,
    00730                    __new_nstart + __old_num_nodes);
    00731     }
    00732       else
    00733     {
    00734       size_type __new_map_size = this->_M_impl._M_map_size
    00735                                  + std::max(this->_M_impl._M_map_size,
    00736                         __nodes_to_add) + 2;
    00737
    00738       _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
    00739       __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
    00740                      + (__add_at_front ? __nodes_to_add : 0);
    00741       std::copy(this->_M_impl._M_start._M_node,
    00742             this->_M_impl._M_finish._M_node + 1,
    00743             __new_nstart);
    00744       _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
    00745
    00746       this->_M_impl._M_map = __new_map;
    00747       this->_M_impl._M_map_size = __new_map_size;
    00748     }
    00749
    00750       this->_M_impl._M_start._M_set_node(__new_nstart);
    00751       this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
    00752     }
    00753
    00754   // Overload for deque::iterators, exploiting the "segmented-iterator
    00755   // optimization".  NB: leave const_iterators alone!
    00756   template<typename _Tp>
    00757     void
    00758     fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
    00759      const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
    00760     {
    00761       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
    00762
    00763       for (typename _Self::_Map_pointer __node = __first._M_node + 1;
    00764            __node < __last._M_node; ++__node)
    00765     std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
    00766
    00767       if (__first._M_node != __last._M_node)
    00768     {
    00769       std::fill(__first._M_cur, __first._M_last, __value);
    00770       std::fill(__last._M_first, __last._M_cur, __value);
    00771     }
    00772       else
    00773     std::fill(__first._M_cur, __last._M_cur, __value);
    00774     }
    00775
    00776 _GLIBCXX_END_NESTED_NAMESPACE
    00777
    00778 #endif