libstdc++

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, 2008,
00004 // 2009, 2010, 2011
00005 // Free Software Foundation, Inc.
00006 //
00007 // This file is part of the GNU ISO C++ Library.  This library is free
00008 // software; you can redistribute it and/or modify it under the
00009 // terms of the GNU General Public License as published by the
00010 // Free Software Foundation; either version 3, or (at your option)
00011 // any later version.
00012 
00013 // This library is distributed in the hope that it will be useful,
00014 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00015 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00016 // GNU General Public License for more details.
00017 
00018 // Under Section 7 of GPL version 3, you are granted additional
00019 // permissions described in the GCC Runtime Library Exception, version
00020 // 3.1, as published by the Free Software Foundation.
00021 
00022 // You should have received a copy of the GNU General Public License and
00023 // a copy of the GCC Runtime Library Exception along with this program;
00024 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00025 // <http://www.gnu.org/licenses/>.
00026 
00027 /*
00028  *
00029  * Copyright (c) 1994
00030  * Hewlett-Packard Company
00031  *
00032  * Permission to use, copy, modify, distribute and sell this software
00033  * and its documentation for any purpose is hereby granted without fee,
00034  * provided that the above copyright notice appear in all copies and
00035  * that both that copyright notice and this permission notice appear
00036  * in supporting documentation.  Hewlett-Packard Company makes no
00037  * representations about the suitability of this software for any
00038  * purpose.  It is provided "as is" without express or implied warranty.
00039  *
00040  *
00041  * Copyright (c) 1997
00042  * Silicon Graphics Computer Systems, Inc.
00043  *
00044  * Permission to use, copy, modify, distribute and sell this software
00045  * and its documentation for any purpose is hereby granted without fee,
00046  * provided that the above copyright notice appear in all copies and
00047  * that both that copyright notice and this permission notice appear
00048  * in supporting documentation.  Silicon Graphics makes no
00049  * representations about the suitability of this software for any
00050  * purpose.  It is provided "as is" without express or implied warranty.
00051  */
00052 
00053 /** @file bits/deque.tcc
00054  *  This is an internal header file, included by other library headers.
00055  *  Do not attempt to use it directly. @headername{deque}
00056  */
00057 
00058 #ifndef _DEQUE_TCC
00059 #define _DEQUE_TCC 1
00060 
00061 namespace std _GLIBCXX_VISIBILITY(default)
00062 {
00063 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00064 
00065 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00066   template <typename _Tp, typename _Alloc>
00067     void
00068     deque<_Tp, _Alloc>::
00069     _M_default_initialize()
00070     {
00071       _Map_pointer __cur;
00072       __try
00073         {
00074           for (__cur = this->_M_impl._M_start._M_node;
00075            __cur < this->_M_impl._M_finish._M_node;
00076            ++__cur)
00077             std::__uninitialized_default_a(*__cur, *__cur + _S_buffer_size(),
00078                        _M_get_Tp_allocator());
00079           std::__uninitialized_default_a(this->_M_impl._M_finish._M_first,
00080                      this->_M_impl._M_finish._M_cur,
00081                      _M_get_Tp_allocator());
00082         }
00083       __catch(...)
00084         {
00085           std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
00086             _M_get_Tp_allocator());
00087           __throw_exception_again;
00088         }
00089     }
00090 #endif
00091 
00092   template <typename _Tp, typename _Alloc>
00093     deque<_Tp, _Alloc>&
00094     deque<_Tp, _Alloc>::
00095     operator=(const deque& __x)
00096     {
00097       const size_type __len = size();
00098       if (&__x != this)
00099     {
00100       if (__len >= __x.size())
00101         _M_erase_at_end(std::copy(__x.begin(), __x.end(),
00102                       this->_M_impl._M_start));
00103       else
00104         {
00105           const_iterator __mid = __x.begin() + difference_type(__len);
00106           std::copy(__x.begin(), __mid, this->_M_impl._M_start);
00107           insert(this->_M_impl._M_finish, __mid, __x.end());
00108         }
00109     }
00110       return *this;
00111     }
00112 
00113 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00114   template<typename _Tp, typename _Alloc>
00115     template<typename... _Args>
00116       void
00117       deque<_Tp, _Alloc>::
00118       emplace_front(_Args&&... __args)
00119       {
00120     if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
00121       {
00122         this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1,
00123                     std::forward<_Args>(__args)...);
00124         --this->_M_impl._M_start._M_cur;
00125       }
00126     else
00127       _M_push_front_aux(std::forward<_Args>(__args)...);
00128       }
00129 
00130   template<typename _Tp, typename _Alloc>
00131     template<typename... _Args>
00132       void
00133       deque<_Tp, _Alloc>::
00134       emplace_back(_Args&&... __args)
00135       {
00136     if (this->_M_impl._M_finish._M_cur
00137         != this->_M_impl._M_finish._M_last - 1)
00138       {
00139         this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
00140                     std::forward<_Args>(__args)...);
00141         ++this->_M_impl._M_finish._M_cur;
00142       }
00143     else
00144       _M_push_back_aux(std::forward<_Args>(__args)...);
00145       }
00146 #endif
00147 
00148   template <typename _Tp, typename _Alloc>
00149     typename deque<_Tp, _Alloc>::iterator
00150     deque<_Tp, _Alloc>::
00151     insert(iterator __position, const value_type& __x)
00152     {
00153       if (__position._M_cur == this->_M_impl._M_start._M_cur)
00154     {
00155       push_front(__x);
00156       return this->_M_impl._M_start;
00157     }
00158       else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
00159     {
00160       push_back(__x);
00161       iterator __tmp = this->_M_impl._M_finish;
00162       --__tmp;
00163       return __tmp;
00164     }
00165       else
00166         return _M_insert_aux(__position, __x);
00167     }
00168 
00169 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00170   template<typename _Tp, typename _Alloc>
00171     template<typename... _Args>
00172       typename deque<_Tp, _Alloc>::iterator
00173       deque<_Tp, _Alloc>::
00174       emplace(iterator __position, _Args&&... __args)
00175       {
00176     if (__position._M_cur == this->_M_impl._M_start._M_cur)
00177       {
00178         push_front(std::forward<_Args>(__args)...);
00179         return this->_M_impl._M_start;
00180       }
00181     else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
00182       {
00183         push_back(std::forward<_Args>(__args)...);
00184         iterator __tmp = this->_M_impl._M_finish;
00185         --__tmp;
00186         return __tmp;
00187       }
00188     else
00189       return _M_insert_aux(__position, std::forward<_Args>(__args)...);
00190       }
00191 #endif
00192 
00193   template <typename _Tp, typename _Alloc>
00194     typename deque<_Tp, _Alloc>::iterator
00195     deque<_Tp, _Alloc>::
00196     erase(iterator __position)
00197     {
00198       iterator __next = __position;
00199       ++__next;
00200       const difference_type __index = __position - begin();
00201       if (static_cast<size_type>(__index) < (size() >> 1))
00202     {
00203       if (__position != begin())
00204         _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next);
00205       pop_front();
00206     }
00207       else
00208     {
00209       if (__next != end())
00210         _GLIBCXX_MOVE3(__next, end(), __position);
00211       pop_back();
00212     }
00213       return begin() + __index;
00214     }
00215 
00216   template <typename _Tp, typename _Alloc>
00217     typename deque<_Tp, _Alloc>::iterator
00218     deque<_Tp, _Alloc>::
00219     erase(iterator __first, iterator __last)
00220     {
00221       if (__first == begin() && __last == end())
00222     {
00223       clear();
00224       return end();
00225     }
00226       else
00227     {
00228       const difference_type __n = __last - __first;
00229       const difference_type __elems_before = __first - begin();
00230       if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2)
00231         {
00232           if (__first != begin())
00233         _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last);
00234           _M_erase_at_begin(begin() + __n);
00235         }
00236       else
00237         {
00238           if (__last != end())
00239         _GLIBCXX_MOVE3(__last, end(), __first);
00240           _M_erase_at_end(end() - __n);
00241         }
00242       return begin() + __elems_before;
00243     }
00244     }
00245 
00246   template <typename _Tp, class _Alloc>
00247     template <typename _InputIterator>
00248       void
00249       deque<_Tp, _Alloc>::
00250       _M_assign_aux(_InputIterator __first, _InputIterator __last,
00251             std::input_iterator_tag)
00252       {
00253         iterator __cur = begin();
00254         for (; __first != __last && __cur != end(); ++__cur, ++__first)
00255           *__cur = *__first;
00256         if (__first == __last)
00257           _M_erase_at_end(__cur);
00258         else
00259           insert(end(), __first, __last);
00260       }
00261 
00262   template <typename _Tp, typename _Alloc>
00263     void
00264     deque<_Tp, _Alloc>::
00265     _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
00266     {
00267       if (__pos._M_cur == this->_M_impl._M_start._M_cur)
00268     {
00269       iterator __new_start = _M_reserve_elements_at_front(__n);
00270       __try
00271         {
00272           std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
00273                       __x, _M_get_Tp_allocator());
00274           this->_M_impl._M_start = __new_start;
00275         }
00276       __catch(...)
00277         {
00278           _M_destroy_nodes(__new_start._M_node,
00279                    this->_M_impl._M_start._M_node);
00280           __throw_exception_again;
00281         }
00282     }
00283       else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
00284     {
00285       iterator __new_finish = _M_reserve_elements_at_back(__n);
00286       __try
00287         {
00288           std::__uninitialized_fill_a(this->_M_impl._M_finish,
00289                       __new_finish, __x,
00290                       _M_get_Tp_allocator());
00291           this->_M_impl._M_finish = __new_finish;
00292         }
00293       __catch(...)
00294         {
00295           _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00296                    __new_finish._M_node + 1);
00297           __throw_exception_again;
00298         }
00299     }
00300       else
00301         _M_insert_aux(__pos, __n, __x);
00302     }
00303 
00304 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00305   template <typename _Tp, typename _Alloc>
00306     void
00307     deque<_Tp, _Alloc>::
00308     _M_default_append(size_type __n)
00309     {
00310       if (__n)
00311     {
00312       iterator __new_finish = _M_reserve_elements_at_back(__n);
00313       __try
00314         {
00315           std::__uninitialized_default_a(this->_M_impl._M_finish,
00316                          __new_finish,
00317                          _M_get_Tp_allocator());
00318           this->_M_impl._M_finish = __new_finish;
00319         }
00320       __catch(...)
00321         {
00322           _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00323                    __new_finish._M_node + 1);
00324           __throw_exception_again;
00325         }
00326     }
00327     }
00328 #endif
00329 
00330   template <typename _Tp, typename _Alloc>
00331     void
00332     deque<_Tp, _Alloc>::
00333     _M_fill_initialize(const value_type& __value)
00334     {
00335       _Map_pointer __cur;
00336       __try
00337         {
00338           for (__cur = this->_M_impl._M_start._M_node;
00339            __cur < this->_M_impl._M_finish._M_node;
00340            ++__cur)
00341             std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
00342                     __value, _M_get_Tp_allocator());
00343           std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
00344                       this->_M_impl._M_finish._M_cur,
00345                       __value, _M_get_Tp_allocator());
00346         }
00347       __catch(...)
00348         {
00349           std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
00350             _M_get_Tp_allocator());
00351           __throw_exception_again;
00352         }
00353     }
00354 
00355   template <typename _Tp, typename _Alloc>
00356     template <typename _InputIterator>
00357       void
00358       deque<_Tp, _Alloc>::
00359       _M_range_initialize(_InputIterator __first, _InputIterator __last,
00360                           std::input_iterator_tag)
00361       {
00362         this->_M_initialize_map(0);
00363         __try
00364           {
00365             for (; __first != __last; ++__first)
00366               push_back(*__first);
00367           }
00368         __catch(...)
00369           {
00370             clear();
00371             __throw_exception_again;
00372           }
00373       }
00374 
00375   template <typename _Tp, typename _Alloc>
00376     template <typename _ForwardIterator>
00377       void
00378       deque<_Tp, _Alloc>::
00379       _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
00380                           std::forward_iterator_tag)
00381       {
00382         const size_type __n = std::distance(__first, __last);
00383         this->_M_initialize_map(__n);
00384 
00385         _Map_pointer __cur_node;
00386         __try
00387           {
00388             for (__cur_node = this->_M_impl._M_start._M_node;
00389                  __cur_node < this->_M_impl._M_finish._M_node;
00390                  ++__cur_node)
00391           {
00392         _ForwardIterator __mid = __first;
00393         std::advance(__mid, _S_buffer_size());
00394         std::__uninitialized_copy_a(__first, __mid, *__cur_node,
00395                         _M_get_Tp_allocator());
00396         __first = __mid;
00397           }
00398             std::__uninitialized_copy_a(__first, __last,
00399                     this->_M_impl._M_finish._M_first,
00400                     _M_get_Tp_allocator());
00401           }
00402         __catch(...)
00403           {
00404             std::_Destroy(this->_M_impl._M_start,
00405               iterator(*__cur_node, __cur_node),
00406               _M_get_Tp_allocator());
00407             __throw_exception_again;
00408           }
00409       }
00410 
00411   // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
00412   template<typename _Tp, typename _Alloc>
00413 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00414     template<typename... _Args>
00415       void
00416       deque<_Tp, _Alloc>::
00417       _M_push_back_aux(_Args&&... __args)
00418 #else
00419       void
00420       deque<_Tp, _Alloc>::
00421       _M_push_back_aux(const value_type& __t)
00422 #endif
00423       {
00424     _M_reserve_map_at_back();
00425     *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
00426     __try
00427       {
00428 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00429         this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
00430                     std::forward<_Args>(__args)...);
00431 #else
00432         this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t);
00433 #endif
00434         this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
00435                         + 1);
00436         this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
00437       }
00438     __catch(...)
00439       {
00440         _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
00441         __throw_exception_again;
00442       }
00443       }
00444 
00445   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
00446   template<typename _Tp, typename _Alloc>
00447 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00448     template<typename... _Args>
00449       void
00450       deque<_Tp, _Alloc>::
00451       _M_push_front_aux(_Args&&... __args)
00452 #else
00453       void
00454       deque<_Tp, _Alloc>::
00455       _M_push_front_aux(const value_type& __t)
00456 #endif
00457       {
00458     _M_reserve_map_at_front();
00459     *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
00460     __try
00461       {
00462         this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
00463                            - 1);
00464         this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
00465 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00466         this->_M_impl.construct(this->_M_impl._M_start._M_cur,
00467                     std::forward<_Args>(__args)...);
00468 #else
00469         this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t);
00470 #endif
00471       }
00472     __catch(...)
00473       {
00474         ++this->_M_impl._M_start;
00475         _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
00476         __throw_exception_again;
00477       }
00478       }
00479 
00480   // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
00481   template <typename _Tp, typename _Alloc>
00482     void deque<_Tp, _Alloc>::
00483     _M_pop_back_aux()
00484     {
00485       _M_deallocate_node(this->_M_impl._M_finish._M_first);
00486       this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
00487       this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
00488       this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
00489     }
00490 
00491   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
00492   // Note that if the deque has at least one element (a precondition for this
00493   // member function), and if
00494   //   _M_impl._M_start._M_cur == _M_impl._M_start._M_last,
00495   // then the deque must have at least two nodes.
00496   template <typename _Tp, typename _Alloc>
00497     void deque<_Tp, _Alloc>::
00498     _M_pop_front_aux()
00499     {
00500       this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
00501       _M_deallocate_node(this->_M_impl._M_start._M_first);
00502       this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
00503       this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
00504     }
00505 
00506   template <typename _Tp, typename _Alloc>
00507     template <typename _InputIterator>
00508       void
00509       deque<_Tp, _Alloc>::
00510       _M_range_insert_aux(iterator __pos,
00511                           _InputIterator __first, _InputIterator __last,
00512                           std::input_iterator_tag)
00513       { std::copy(__first, __last, std::inserter(*this, __pos)); }
00514 
00515   template <typename _Tp, typename _Alloc>
00516     template <typename _ForwardIterator>
00517       void
00518       deque<_Tp, _Alloc>::
00519       _M_range_insert_aux(iterator __pos,
00520                           _ForwardIterator __first, _ForwardIterator __last,
00521                           std::forward_iterator_tag)
00522       {
00523         const size_type __n = std::distance(__first, __last);
00524         if (__pos._M_cur == this->_M_impl._M_start._M_cur)
00525       {
00526         iterator __new_start = _M_reserve_elements_at_front(__n);
00527         __try
00528           {
00529         std::__uninitialized_copy_a(__first, __last, __new_start,
00530                         _M_get_Tp_allocator());
00531         this->_M_impl._M_start = __new_start;
00532           }
00533         __catch(...)
00534           {
00535         _M_destroy_nodes(__new_start._M_node,
00536                  this->_M_impl._M_start._M_node);
00537         __throw_exception_again;
00538           }
00539       }
00540         else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
00541       {
00542         iterator __new_finish = _M_reserve_elements_at_back(__n);
00543         __try
00544           {
00545         std::__uninitialized_copy_a(__first, __last,
00546                         this->_M_impl._M_finish,
00547                         _M_get_Tp_allocator());
00548         this->_M_impl._M_finish = __new_finish;
00549           }
00550         __catch(...)
00551           {
00552         _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00553                  __new_finish._M_node + 1);
00554         __throw_exception_again;
00555           }
00556       }
00557         else
00558           _M_insert_aux(__pos, __first, __last, __n);
00559       }
00560 
00561   template<typename _Tp, typename _Alloc>
00562 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00563     template<typename... _Args>
00564       typename deque<_Tp, _Alloc>::iterator
00565       deque<_Tp, _Alloc>::
00566       _M_insert_aux(iterator __pos, _Args&&... __args)
00567       {
00568     value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy
00569 #else
00570     typename deque<_Tp, _Alloc>::iterator
00571       deque<_Tp, _Alloc>::
00572       _M_insert_aux(iterator __pos, const value_type& __x)
00573       {
00574     value_type __x_copy = __x; // XXX copy
00575 #endif
00576     difference_type __index = __pos - this->_M_impl._M_start;
00577     if (static_cast<size_type>(__index) < size() / 2)
00578       {
00579         push_front(_GLIBCXX_MOVE(front()));
00580         iterator __front1 = this->_M_impl._M_start;
00581         ++__front1;
00582         iterator __front2 = __front1;
00583         ++__front2;
00584         __pos = this->_M_impl._M_start + __index;
00585         iterator __pos1 = __pos;
00586         ++__pos1;
00587         _GLIBCXX_MOVE3(__front2, __pos1, __front1);
00588       }
00589     else
00590       {
00591         push_back(_GLIBCXX_MOVE(back()));
00592         iterator __back1 = this->_M_impl._M_finish;
00593         --__back1;
00594         iterator __back2 = __back1;
00595         --__back2;
00596         __pos = this->_M_impl._M_start + __index;
00597         _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
00598       }
00599     *__pos = _GLIBCXX_MOVE(__x_copy);
00600     return __pos;
00601       }
00602 
00603   template <typename _Tp, typename _Alloc>
00604     void
00605     deque<_Tp, _Alloc>::
00606     _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
00607     {
00608       const difference_type __elems_before = __pos - this->_M_impl._M_start;
00609       const size_type __length = this->size();
00610       value_type __x_copy = __x;
00611       if (__elems_before < difference_type(__length / 2))
00612     {
00613       iterator __new_start = _M_reserve_elements_at_front(__n);
00614       iterator __old_start = this->_M_impl._M_start;
00615       __pos = this->_M_impl._M_start + __elems_before;
00616       __try
00617         {
00618           if (__elems_before >= difference_type(__n))
00619         {
00620           iterator __start_n = (this->_M_impl._M_start
00621                     + difference_type(__n));
00622           std::__uninitialized_move_a(this->_M_impl._M_start,
00623                           __start_n, __new_start,
00624                           _M_get_Tp_allocator());
00625           this->_M_impl._M_start = __new_start;
00626           _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
00627           std::fill(__pos - difference_type(__n), __pos, __x_copy);
00628         }
00629           else
00630         {
00631           std::__uninitialized_move_fill(this->_M_impl._M_start,
00632                          __pos, __new_start,
00633                          this->_M_impl._M_start,
00634                          __x_copy,
00635                          _M_get_Tp_allocator());
00636           this->_M_impl._M_start = __new_start;
00637           std::fill(__old_start, __pos, __x_copy);
00638         }
00639         }
00640       __catch(...)
00641         {
00642           _M_destroy_nodes(__new_start._M_node,
00643                    this->_M_impl._M_start._M_node);
00644           __throw_exception_again;
00645         }
00646     }
00647       else
00648     {
00649       iterator __new_finish = _M_reserve_elements_at_back(__n);
00650       iterator __old_finish = this->_M_impl._M_finish;
00651       const difference_type __elems_after =
00652         difference_type(__length) - __elems_before;
00653       __pos = this->_M_impl._M_finish - __elems_after;
00654       __try
00655         {
00656           if (__elems_after > difference_type(__n))
00657         {
00658           iterator __finish_n = (this->_M_impl._M_finish
00659                      - difference_type(__n));
00660           std::__uninitialized_move_a(__finish_n,
00661                           this->_M_impl._M_finish,
00662                           this->_M_impl._M_finish,
00663                           _M_get_Tp_allocator());
00664           this->_M_impl._M_finish = __new_finish;
00665           _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
00666           std::fill(__pos, __pos + difference_type(__n), __x_copy);
00667         }
00668           else
00669         {
00670           std::__uninitialized_fill_move(this->_M_impl._M_finish,
00671                          __pos + difference_type(__n),
00672                          __x_copy, __pos,
00673                          this->_M_impl._M_finish,
00674                          _M_get_Tp_allocator());
00675           this->_M_impl._M_finish = __new_finish;
00676           std::fill(__pos, __old_finish, __x_copy);
00677         }
00678         }
00679       __catch(...)
00680         {
00681           _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00682                    __new_finish._M_node + 1);
00683           __throw_exception_again;
00684         }
00685     }
00686     }
00687 
00688   template <typename _Tp, typename _Alloc>
00689     template <typename _ForwardIterator>
00690       void
00691       deque<_Tp, _Alloc>::
00692       _M_insert_aux(iterator __pos,
00693                     _ForwardIterator __first, _ForwardIterator __last,
00694                     size_type __n)
00695       {
00696         const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
00697         const size_type __length = size();
00698         if (static_cast<size_type>(__elemsbefore) < __length / 2)
00699       {
00700         iterator __new_start = _M_reserve_elements_at_front(__n);
00701         iterator __old_start = this->_M_impl._M_start;
00702         __pos = this->_M_impl._M_start + __elemsbefore;
00703         __try
00704           {
00705         if (__elemsbefore >= difference_type(__n))
00706           {
00707             iterator __start_n = (this->_M_impl._M_start
00708                       + difference_type(__n));
00709             std::__uninitialized_move_a(this->_M_impl._M_start,
00710                         __start_n, __new_start,
00711                         _M_get_Tp_allocator());
00712             this->_M_impl._M_start = __new_start;
00713             _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
00714             std::copy(__first, __last, __pos - difference_type(__n));
00715           }
00716         else
00717           {
00718             _ForwardIterator __mid = __first;
00719             std::advance(__mid, difference_type(__n) - __elemsbefore);
00720             std::__uninitialized_move_copy(this->_M_impl._M_start,
00721                            __pos, __first, __mid,
00722                            __new_start,
00723                            _M_get_Tp_allocator());
00724             this->_M_impl._M_start = __new_start;
00725             std::copy(__mid, __last, __old_start);
00726           }
00727           }
00728         __catch(...)
00729           {
00730         _M_destroy_nodes(__new_start._M_node,
00731                  this->_M_impl._M_start._M_node);
00732         __throw_exception_again;
00733           }
00734       }
00735         else
00736         {
00737           iterator __new_finish = _M_reserve_elements_at_back(__n);
00738           iterator __old_finish = this->_M_impl._M_finish;
00739           const difference_type __elemsafter =
00740             difference_type(__length) - __elemsbefore;
00741           __pos = this->_M_impl._M_finish - __elemsafter;
00742           __try
00743             {
00744               if (__elemsafter > difference_type(__n))
00745         {
00746           iterator __finish_n = (this->_M_impl._M_finish
00747                      - difference_type(__n));
00748           std::__uninitialized_move_a(__finish_n,
00749                           this->_M_impl._M_finish,
00750                           this->_M_impl._M_finish,
00751                           _M_get_Tp_allocator());
00752           this->_M_impl._M_finish = __new_finish;
00753           _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
00754           std::copy(__first, __last, __pos);
00755         }
00756               else
00757         {
00758           _ForwardIterator __mid = __first;
00759           std::advance(__mid, __elemsafter);
00760           std::__uninitialized_copy_move(__mid, __last, __pos,
00761                          this->_M_impl._M_finish,
00762                          this->_M_impl._M_finish,
00763                          _M_get_Tp_allocator());
00764           this->_M_impl._M_finish = __new_finish;
00765           std::copy(__first, __mid, __pos);
00766         }
00767             }
00768           __catch(...)
00769             {
00770               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00771                    __new_finish._M_node + 1);
00772               __throw_exception_again;
00773             }
00774         }
00775       }
00776 
00777    template<typename _Tp, typename _Alloc>
00778      void
00779      deque<_Tp, _Alloc>::
00780      _M_destroy_data_aux(iterator __first, iterator __last)
00781      {
00782        for (_Map_pointer __node = __first._M_node + 1;
00783         __node < __last._M_node; ++__node)
00784      std::_Destroy(*__node, *__node + _S_buffer_size(),
00785                _M_get_Tp_allocator());
00786 
00787        if (__first._M_node != __last._M_node)
00788      {
00789        std::_Destroy(__first._M_cur, __first._M_last,
00790              _M_get_Tp_allocator());
00791        std::_Destroy(__last._M_first, __last._M_cur,
00792              _M_get_Tp_allocator());
00793      }
00794        else
00795      std::_Destroy(__first._M_cur, __last._M_cur,
00796                _M_get_Tp_allocator());
00797      }
00798 
00799   template <typename _Tp, typename _Alloc>
00800     void
00801     deque<_Tp, _Alloc>::
00802     _M_new_elements_at_front(size_type __new_elems)
00803     {
00804       if (this->max_size() - this->size() < __new_elems)
00805     __throw_length_error(__N("deque::_M_new_elements_at_front"));
00806 
00807       const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
00808                      / _S_buffer_size());
00809       _M_reserve_map_at_front(__new_nodes);
00810       size_type __i;
00811       __try
00812         {
00813           for (__i = 1; __i <= __new_nodes; ++__i)
00814             *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
00815         }
00816       __catch(...)
00817         {
00818           for (size_type __j = 1; __j < __i; ++__j)
00819             _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
00820           __throw_exception_again;
00821         }
00822     }
00823 
00824   template <typename _Tp, typename _Alloc>
00825     void
00826     deque<_Tp, _Alloc>::
00827     _M_new_elements_at_back(size_type __new_elems)
00828     {
00829       if (this->max_size() - this->size() < __new_elems)
00830     __throw_length_error(__N("deque::_M_new_elements_at_back"));
00831 
00832       const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
00833                      / _S_buffer_size());
00834       _M_reserve_map_at_back(__new_nodes);
00835       size_type __i;
00836       __try
00837         {
00838           for (__i = 1; __i <= __new_nodes; ++__i)
00839             *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
00840         }
00841       __catch(...)
00842         {
00843           for (size_type __j = 1; __j < __i; ++__j)
00844             _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
00845           __throw_exception_again;
00846         }
00847     }
00848 
00849   template <typename _Tp, typename _Alloc>
00850     void
00851     deque<_Tp, _Alloc>::
00852     _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
00853     {
00854       const size_type __old_num_nodes
00855     = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
00856       const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
00857 
00858       _Map_pointer __new_nstart;
00859       if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
00860     {
00861       __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
00862                      - __new_num_nodes) / 2
00863                      + (__add_at_front ? __nodes_to_add : 0);
00864       if (__new_nstart < this->_M_impl._M_start._M_node)
00865         std::copy(this->_M_impl._M_start._M_node,
00866               this->_M_impl._M_finish._M_node + 1,
00867               __new_nstart);
00868       else
00869         std::copy_backward(this->_M_impl._M_start._M_node,
00870                    this->_M_impl._M_finish._M_node + 1,
00871                    __new_nstart + __old_num_nodes);
00872     }
00873       else
00874     {
00875       size_type __new_map_size = this->_M_impl._M_map_size
00876                                  + std::max(this->_M_impl._M_map_size,
00877                         __nodes_to_add) + 2;
00878 
00879       _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
00880       __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
00881                      + (__add_at_front ? __nodes_to_add : 0);
00882       std::copy(this->_M_impl._M_start._M_node,
00883             this->_M_impl._M_finish._M_node + 1,
00884             __new_nstart);
00885       _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
00886 
00887       this->_M_impl._M_map = __new_map;
00888       this->_M_impl._M_map_size = __new_map_size;
00889     }
00890 
00891       this->_M_impl._M_start._M_set_node(__new_nstart);
00892       this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
00893     }
00894 
00895   // Overload for deque::iterators, exploiting the "segmented-iterator
00896   // optimization".
00897   template<typename _Tp>
00898     void
00899     fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
00900      const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
00901     {
00902       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
00903 
00904       for (typename _Self::_Map_pointer __node = __first._M_node + 1;
00905            __node < __last._M_node; ++__node)
00906     std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
00907 
00908       if (__first._M_node != __last._M_node)
00909     {
00910       std::fill(__first._M_cur, __first._M_last, __value);
00911       std::fill(__last._M_first, __last._M_cur, __value);
00912     }
00913       else
00914     std::fill(__first._M_cur, __last._M_cur, __value);
00915     }
00916 
00917   template<typename _Tp>
00918     _Deque_iterator<_Tp, _Tp&, _Tp*>
00919     copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
00920      _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
00921      _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
00922     {
00923       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
00924       typedef typename _Self::difference_type difference_type;
00925 
00926       difference_type __len = __last - __first;
00927       while (__len > 0)
00928     {
00929       const difference_type __clen
00930         = std::min(__len, std::min(__first._M_last - __first._M_cur,
00931                        __result._M_last - __result._M_cur));
00932       std::copy(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
00933       __first += __clen;
00934       __result += __clen;
00935       __len -= __clen;
00936     }
00937       return __result;
00938     }
00939 
00940   template<typename _Tp>
00941     _Deque_iterator<_Tp, _Tp&, _Tp*>
00942     copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
00943           _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
00944           _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
00945     {
00946       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
00947       typedef typename _Self::difference_type difference_type;
00948 
00949       difference_type __len = __last - __first;
00950       while (__len > 0)
00951     {
00952       difference_type __llen = __last._M_cur - __last._M_first;
00953       _Tp* __lend = __last._M_cur;
00954 
00955       difference_type __rlen = __result._M_cur - __result._M_first;
00956       _Tp* __rend = __result._M_cur;
00957 
00958       if (!__llen)
00959         {
00960           __llen = _Self::_S_buffer_size();
00961           __lend = *(__last._M_node - 1) + __llen;
00962         }
00963       if (!__rlen)
00964         {
00965           __rlen = _Self::_S_buffer_size();
00966           __rend = *(__result._M_node - 1) + __rlen;
00967         }
00968 
00969       const difference_type __clen = std::min(__len,
00970                           std::min(__llen, __rlen));
00971       std::copy_backward(__lend - __clen, __lend, __rend);
00972       __last -= __clen;
00973       __result -= __clen;
00974       __len -= __clen;
00975     }
00976       return __result;
00977     }
00978 
00979 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00980   template<typename _Tp>
00981     _Deque_iterator<_Tp, _Tp&, _Tp*>
00982     move(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
00983      _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
00984      _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
00985     {
00986       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
00987       typedef typename _Self::difference_type difference_type;
00988 
00989       difference_type __len = __last - __first;
00990       while (__len > 0)
00991     {
00992       const difference_type __clen
00993         = std::min(__len, std::min(__first._M_last - __first._M_cur,
00994                        __result._M_last - __result._M_cur));
00995       std::move(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
00996       __first += __clen;
00997       __result += __clen;
00998       __len -= __clen;
00999     }
01000       return __result;
01001     }
01002 
01003   template<typename _Tp>
01004     _Deque_iterator<_Tp, _Tp&, _Tp*>
01005     move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
01006           _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
01007           _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
01008     {
01009       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
01010       typedef typename _Self::difference_type difference_type;
01011 
01012       difference_type __len = __last - __first;
01013       while (__len > 0)
01014     {
01015       difference_type __llen = __last._M_cur - __last._M_first;
01016       _Tp* __lend = __last._M_cur;
01017 
01018       difference_type __rlen = __result._M_cur - __result._M_first;
01019       _Tp* __rend = __result._M_cur;
01020 
01021       if (!__llen)
01022         {
01023           __llen = _Self::_S_buffer_size();
01024           __lend = *(__last._M_node - 1) + __llen;
01025         }
01026       if (!__rlen)
01027         {
01028           __rlen = _Self::_S_buffer_size();
01029           __rend = *(__result._M_node - 1) + __rlen;
01030         }
01031 
01032       const difference_type __clen = std::min(__len,
01033                           std::min(__llen, __rlen));
01034       std::move_backward(__lend - __clen, __lend, __rend);
01035       __last -= __clen;
01036       __result -= __clen;
01037       __len -= __clen;
01038     }
01039       return __result;
01040     }
01041 #endif
01042 
01043 _GLIBCXX_END_NAMESPACE_CONTAINER
01044 } // namespace std
01045 
01046 #endif