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

Generated on Thu Jul 23 21:16:04 2009 for libstdc++ by  doxygen 1.5.8