# deque.tcc

Go to the documentation of this file.

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