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 == __last)
00222     return __first;
00223       else if (__first == begin() && __last == end())
00224     {
00225       clear();
00226       return end();
00227     }
00228       else
00229     {
00230       const difference_type __n = __last - __first;
00231       const difference_type __elems_before = __first - begin();
00232       if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2)
00233         {
00234           if (__first != begin())
00235         _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last);
00236           _M_erase_at_begin(begin() + __n);
00237         }
00238       else
00239         {
00240           if (__last != end())
00241         _GLIBCXX_MOVE3(__last, end(), __first);
00242           _M_erase_at_end(end() - __n);
00243         }
00244       return begin() + __elems_before;
00245     }
00246     }
00247 
00248   template <typename _Tp, class _Alloc>
00249     template <typename _InputIterator>
00250       void
00251       deque<_Tp, _Alloc>::
00252       _M_assign_aux(_InputIterator __first, _InputIterator __last,
00253             std::input_iterator_tag)
00254       {
00255         iterator __cur = begin();
00256         for (; __first != __last && __cur != end(); ++__cur, ++__first)
00257           *__cur = *__first;
00258         if (__first == __last)
00259           _M_erase_at_end(__cur);
00260         else
00261           insert(end(), __first, __last);
00262       }
00263 
00264   template <typename _Tp, typename _Alloc>
00265     void
00266     deque<_Tp, _Alloc>::
00267     _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
00268     {
00269       if (__pos._M_cur == this->_M_impl._M_start._M_cur)
00270     {
00271       iterator __new_start = _M_reserve_elements_at_front(__n);
00272       __try
00273         {
00274           std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
00275                       __x, _M_get_Tp_allocator());
00276           this->_M_impl._M_start = __new_start;
00277         }
00278       __catch(...)
00279         {
00280           _M_destroy_nodes(__new_start._M_node,
00281                    this->_M_impl._M_start._M_node);
00282           __throw_exception_again;
00283         }
00284     }
00285       else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
00286     {
00287       iterator __new_finish = _M_reserve_elements_at_back(__n);
00288       __try
00289         {
00290           std::__uninitialized_fill_a(this->_M_impl._M_finish,
00291                       __new_finish, __x,
00292                       _M_get_Tp_allocator());
00293           this->_M_impl._M_finish = __new_finish;
00294         }
00295       __catch(...)
00296         {
00297           _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00298                    __new_finish._M_node + 1);
00299           __throw_exception_again;
00300         }
00301     }
00302       else
00303         _M_insert_aux(__pos, __n, __x);
00304     }
00305 
00306 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00307   template <typename _Tp, typename _Alloc>
00308     void
00309     deque<_Tp, _Alloc>::
00310     _M_default_append(size_type __n)
00311     {
00312       if (__n)
00313     {
00314       iterator __new_finish = _M_reserve_elements_at_back(__n);
00315       __try
00316         {
00317           std::__uninitialized_default_a(this->_M_impl._M_finish,
00318                          __new_finish,
00319                          _M_get_Tp_allocator());
00320           this->_M_impl._M_finish = __new_finish;
00321         }
00322       __catch(...)
00323         {
00324           _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00325                    __new_finish._M_node + 1);
00326           __throw_exception_again;
00327         }
00328     }
00329     }
00330 
00331   template <typename _Tp, typename _Alloc>
00332     bool
00333     deque<_Tp, _Alloc>::
00334     _M_shrink_to_fit()
00335     {
00336       const difference_type __front_capacity
00337     = (this->_M_impl._M_start._M_cur - this->_M_impl._M_start._M_first);
00338       if (__front_capacity == 0)
00339     return false;
00340 
00341       const difference_type __back_capacity
00342     = (this->_M_impl._M_finish._M_last - this->_M_impl._M_finish._M_cur);
00343       if (__front_capacity + __back_capacity < _S_buffer_size())
00344     return false;
00345 
00346       return std::__shrink_to_fit_aux<deque>::_S_do_it(*this);
00347     }
00348 #endif
00349 
00350   template <typename _Tp, typename _Alloc>
00351     void
00352     deque<_Tp, _Alloc>::
00353     _M_fill_initialize(const value_type& __value)
00354     {
00355       _Map_pointer __cur;
00356       __try
00357         {
00358           for (__cur = this->_M_impl._M_start._M_node;
00359            __cur < this->_M_impl._M_finish._M_node;
00360            ++__cur)
00361             std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
00362                     __value, _M_get_Tp_allocator());
00363           std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
00364                       this->_M_impl._M_finish._M_cur,
00365                       __value, _M_get_Tp_allocator());
00366         }
00367       __catch(...)
00368         {
00369           std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
00370             _M_get_Tp_allocator());
00371           __throw_exception_again;
00372         }
00373     }
00374 
00375   template <typename _Tp, typename _Alloc>
00376     template <typename _InputIterator>
00377       void
00378       deque<_Tp, _Alloc>::
00379       _M_range_initialize(_InputIterator __first, _InputIterator __last,
00380                           std::input_iterator_tag)
00381       {
00382         this->_M_initialize_map(0);
00383         __try
00384           {
00385             for (; __first != __last; ++__first)
00386               push_back(*__first);
00387           }
00388         __catch(...)
00389           {
00390             clear();
00391             __throw_exception_again;
00392           }
00393       }
00394 
00395   template <typename _Tp, typename _Alloc>
00396     template <typename _ForwardIterator>
00397       void
00398       deque<_Tp, _Alloc>::
00399       _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
00400                           std::forward_iterator_tag)
00401       {
00402         const size_type __n = std::distance(__first, __last);
00403         this->_M_initialize_map(__n);
00404 
00405         _Map_pointer __cur_node;
00406         __try
00407           {
00408             for (__cur_node = this->_M_impl._M_start._M_node;
00409                  __cur_node < this->_M_impl._M_finish._M_node;
00410                  ++__cur_node)
00411           {
00412         _ForwardIterator __mid = __first;
00413         std::advance(__mid, _S_buffer_size());
00414         std::__uninitialized_copy_a(__first, __mid, *__cur_node,
00415                         _M_get_Tp_allocator());
00416         __first = __mid;
00417           }
00418             std::__uninitialized_copy_a(__first, __last,
00419                     this->_M_impl._M_finish._M_first,
00420                     _M_get_Tp_allocator());
00421           }
00422         __catch(...)
00423           {
00424             std::_Destroy(this->_M_impl._M_start,
00425               iterator(*__cur_node, __cur_node),
00426               _M_get_Tp_allocator());
00427             __throw_exception_again;
00428           }
00429       }
00430 
00431   // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
00432   template<typename _Tp, typename _Alloc>
00433 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00434     template<typename... _Args>
00435       void
00436       deque<_Tp, _Alloc>::
00437       _M_push_back_aux(_Args&&... __args)
00438 #else
00439       void
00440       deque<_Tp, _Alloc>::
00441       _M_push_back_aux(const value_type& __t)
00442 #endif
00443       {
00444     _M_reserve_map_at_back();
00445     *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
00446     __try
00447       {
00448 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00449         this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
00450                     std::forward<_Args>(__args)...);
00451 #else
00452         this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t);
00453 #endif
00454         this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
00455                         + 1);
00456         this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
00457       }
00458     __catch(...)
00459       {
00460         _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
00461         __throw_exception_again;
00462       }
00463       }
00464 
00465   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
00466   template<typename _Tp, typename _Alloc>
00467 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00468     template<typename... _Args>
00469       void
00470       deque<_Tp, _Alloc>::
00471       _M_push_front_aux(_Args&&... __args)
00472 #else
00473       void
00474       deque<_Tp, _Alloc>::
00475       _M_push_front_aux(const value_type& __t)
00476 #endif
00477       {
00478     _M_reserve_map_at_front();
00479     *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
00480     __try
00481       {
00482         this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
00483                            - 1);
00484         this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
00485 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00486         this->_M_impl.construct(this->_M_impl._M_start._M_cur,
00487                     std::forward<_Args>(__args)...);
00488 #else
00489         this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t);
00490 #endif
00491       }
00492     __catch(...)
00493       {
00494         ++this->_M_impl._M_start;
00495         _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
00496         __throw_exception_again;
00497       }
00498       }
00499 
00500   // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
00501   template <typename _Tp, typename _Alloc>
00502     void deque<_Tp, _Alloc>::
00503     _M_pop_back_aux()
00504     {
00505       _M_deallocate_node(this->_M_impl._M_finish._M_first);
00506       this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
00507       this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
00508       this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
00509     }
00510 
00511   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
00512   // Note that if the deque has at least one element (a precondition for this
00513   // member function), and if
00514   //   _M_impl._M_start._M_cur == _M_impl._M_start._M_last,
00515   // then the deque must have at least two nodes.
00516   template <typename _Tp, typename _Alloc>
00517     void deque<_Tp, _Alloc>::
00518     _M_pop_front_aux()
00519     {
00520       this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
00521       _M_deallocate_node(this->_M_impl._M_start._M_first);
00522       this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
00523       this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
00524     }
00525 
00526   template <typename _Tp, typename _Alloc>
00527     template <typename _InputIterator>
00528       void
00529       deque<_Tp, _Alloc>::
00530       _M_range_insert_aux(iterator __pos,
00531                           _InputIterator __first, _InputIterator __last,
00532                           std::input_iterator_tag)
00533       { std::copy(__first, __last, std::inserter(*this, __pos)); }
00534 
00535   template <typename _Tp, typename _Alloc>
00536     template <typename _ForwardIterator>
00537       void
00538       deque<_Tp, _Alloc>::
00539       _M_range_insert_aux(iterator __pos,
00540                           _ForwardIterator __first, _ForwardIterator __last,
00541                           std::forward_iterator_tag)
00542       {
00543         const size_type __n = std::distance(__first, __last);
00544         if (__pos._M_cur == this->_M_impl._M_start._M_cur)
00545       {
00546         iterator __new_start = _M_reserve_elements_at_front(__n);
00547         __try
00548           {
00549         std::__uninitialized_copy_a(__first, __last, __new_start,
00550                         _M_get_Tp_allocator());
00551         this->_M_impl._M_start = __new_start;
00552           }
00553         __catch(...)
00554           {
00555         _M_destroy_nodes(__new_start._M_node,
00556                  this->_M_impl._M_start._M_node);
00557         __throw_exception_again;
00558           }
00559       }
00560         else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
00561       {
00562         iterator __new_finish = _M_reserve_elements_at_back(__n);
00563         __try
00564           {
00565         std::__uninitialized_copy_a(__first, __last,
00566                         this->_M_impl._M_finish,
00567                         _M_get_Tp_allocator());
00568         this->_M_impl._M_finish = __new_finish;
00569           }
00570         __catch(...)
00571           {
00572         _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00573                  __new_finish._M_node + 1);
00574         __throw_exception_again;
00575           }
00576       }
00577         else
00578           _M_insert_aux(__pos, __first, __last, __n);
00579       }
00580 
00581   template<typename _Tp, typename _Alloc>
00582 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00583     template<typename... _Args>
00584       typename deque<_Tp, _Alloc>::iterator
00585       deque<_Tp, _Alloc>::
00586       _M_insert_aux(iterator __pos, _Args&&... __args)
00587       {
00588     value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy
00589 #else
00590     typename deque<_Tp, _Alloc>::iterator
00591       deque<_Tp, _Alloc>::
00592       _M_insert_aux(iterator __pos, const value_type& __x)
00593       {
00594     value_type __x_copy = __x; // XXX copy
00595 #endif
00596     difference_type __index = __pos - this->_M_impl._M_start;
00597     if (static_cast<size_type>(__index) < size() / 2)
00598       {
00599         push_front(_GLIBCXX_MOVE(front()));
00600         iterator __front1 = this->_M_impl._M_start;
00601         ++__front1;
00602         iterator __front2 = __front1;
00603         ++__front2;
00604         __pos = this->_M_impl._M_start + __index;
00605         iterator __pos1 = __pos;
00606         ++__pos1;
00607         _GLIBCXX_MOVE3(__front2, __pos1, __front1);
00608       }
00609     else
00610       {
00611         push_back(_GLIBCXX_MOVE(back()));
00612         iterator __back1 = this->_M_impl._M_finish;
00613         --__back1;
00614         iterator __back2 = __back1;
00615         --__back2;
00616         __pos = this->_M_impl._M_start + __index;
00617         _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
00618       }
00619     *__pos = _GLIBCXX_MOVE(__x_copy);
00620     return __pos;
00621       }
00622 
00623   template <typename _Tp, typename _Alloc>
00624     void
00625     deque<_Tp, _Alloc>::
00626     _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
00627     {
00628       const difference_type __elems_before = __pos - this->_M_impl._M_start;
00629       const size_type __length = this->size();
00630       value_type __x_copy = __x;
00631       if (__elems_before < difference_type(__length / 2))
00632     {
00633       iterator __new_start = _M_reserve_elements_at_front(__n);
00634       iterator __old_start = this->_M_impl._M_start;
00635       __pos = this->_M_impl._M_start + __elems_before;
00636       __try
00637         {
00638           if (__elems_before >= difference_type(__n))
00639         {
00640           iterator __start_n = (this->_M_impl._M_start
00641                     + difference_type(__n));
00642           std::__uninitialized_move_a(this->_M_impl._M_start,
00643                           __start_n, __new_start,
00644                           _M_get_Tp_allocator());
00645           this->_M_impl._M_start = __new_start;
00646           _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
00647           std::fill(__pos - difference_type(__n), __pos, __x_copy);
00648         }
00649           else
00650         {
00651           std::__uninitialized_move_fill(this->_M_impl._M_start,
00652                          __pos, __new_start,
00653                          this->_M_impl._M_start,
00654                          __x_copy,
00655                          _M_get_Tp_allocator());
00656           this->_M_impl._M_start = __new_start;
00657           std::fill(__old_start, __pos, __x_copy);
00658         }
00659         }
00660       __catch(...)
00661         {
00662           _M_destroy_nodes(__new_start._M_node,
00663                    this->_M_impl._M_start._M_node);
00664           __throw_exception_again;
00665         }
00666     }
00667       else
00668     {
00669       iterator __new_finish = _M_reserve_elements_at_back(__n);
00670       iterator __old_finish = this->_M_impl._M_finish;
00671       const difference_type __elems_after =
00672         difference_type(__length) - __elems_before;
00673       __pos = this->_M_impl._M_finish - __elems_after;
00674       __try
00675         {
00676           if (__elems_after > difference_type(__n))
00677         {
00678           iterator __finish_n = (this->_M_impl._M_finish
00679                      - difference_type(__n));
00680           std::__uninitialized_move_a(__finish_n,
00681                           this->_M_impl._M_finish,
00682                           this->_M_impl._M_finish,
00683                           _M_get_Tp_allocator());
00684           this->_M_impl._M_finish = __new_finish;
00685           _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
00686           std::fill(__pos, __pos + difference_type(__n), __x_copy);
00687         }
00688           else
00689         {
00690           std::__uninitialized_fill_move(this->_M_impl._M_finish,
00691                          __pos + difference_type(__n),
00692                          __x_copy, __pos,
00693                          this->_M_impl._M_finish,
00694                          _M_get_Tp_allocator());
00695           this->_M_impl._M_finish = __new_finish;
00696           std::fill(__pos, __old_finish, __x_copy);
00697         }
00698         }
00699       __catch(...)
00700         {
00701           _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00702                    __new_finish._M_node + 1);
00703           __throw_exception_again;
00704         }
00705     }
00706     }
00707 
00708   template <typename _Tp, typename _Alloc>
00709     template <typename _ForwardIterator>
00710       void
00711       deque<_Tp, _Alloc>::
00712       _M_insert_aux(iterator __pos,
00713                     _ForwardIterator __first, _ForwardIterator __last,
00714                     size_type __n)
00715       {
00716         const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
00717         const size_type __length = size();
00718         if (static_cast<size_type>(__elemsbefore) < __length / 2)
00719       {
00720         iterator __new_start = _M_reserve_elements_at_front(__n);
00721         iterator __old_start = this->_M_impl._M_start;
00722         __pos = this->_M_impl._M_start + __elemsbefore;
00723         __try
00724           {
00725         if (__elemsbefore >= difference_type(__n))
00726           {
00727             iterator __start_n = (this->_M_impl._M_start
00728                       + difference_type(__n));
00729             std::__uninitialized_move_a(this->_M_impl._M_start,
00730                         __start_n, __new_start,
00731                         _M_get_Tp_allocator());
00732             this->_M_impl._M_start = __new_start;
00733             _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
00734             std::copy(__first, __last, __pos - difference_type(__n));
00735           }
00736         else
00737           {
00738             _ForwardIterator __mid = __first;
00739             std::advance(__mid, difference_type(__n) - __elemsbefore);
00740             std::__uninitialized_move_copy(this->_M_impl._M_start,
00741                            __pos, __first, __mid,
00742                            __new_start,
00743                            _M_get_Tp_allocator());
00744             this->_M_impl._M_start = __new_start;
00745             std::copy(__mid, __last, __old_start);
00746           }
00747           }
00748         __catch(...)
00749           {
00750         _M_destroy_nodes(__new_start._M_node,
00751                  this->_M_impl._M_start._M_node);
00752         __throw_exception_again;
00753           }
00754       }
00755         else
00756         {
00757           iterator __new_finish = _M_reserve_elements_at_back(__n);
00758           iterator __old_finish = this->_M_impl._M_finish;
00759           const difference_type __elemsafter =
00760             difference_type(__length) - __elemsbefore;
00761           __pos = this->_M_impl._M_finish - __elemsafter;
00762           __try
00763             {
00764               if (__elemsafter > difference_type(__n))
00765         {
00766           iterator __finish_n = (this->_M_impl._M_finish
00767                      - difference_type(__n));
00768           std::__uninitialized_move_a(__finish_n,
00769                           this->_M_impl._M_finish,
00770                           this->_M_impl._M_finish,
00771                           _M_get_Tp_allocator());
00772           this->_M_impl._M_finish = __new_finish;
00773           _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
00774           std::copy(__first, __last, __pos);
00775         }
00776               else
00777         {
00778           _ForwardIterator __mid = __first;
00779           std::advance(__mid, __elemsafter);
00780           std::__uninitialized_copy_move(__mid, __last, __pos,
00781                          this->_M_impl._M_finish,
00782                          this->_M_impl._M_finish,
00783                          _M_get_Tp_allocator());
00784           this->_M_impl._M_finish = __new_finish;
00785           std::copy(__first, __mid, __pos);
00786         }
00787             }
00788           __catch(...)
00789             {
00790               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00791                    __new_finish._M_node + 1);
00792               __throw_exception_again;
00793             }
00794         }
00795       }
00796 
00797    template<typename _Tp, typename _Alloc>
00798      void
00799      deque<_Tp, _Alloc>::
00800      _M_destroy_data_aux(iterator __first, iterator __last)
00801      {
00802        for (_Map_pointer __node = __first._M_node + 1;
00803         __node < __last._M_node; ++__node)
00804      std::_Destroy(*__node, *__node + _S_buffer_size(),
00805                _M_get_Tp_allocator());
00806 
00807        if (__first._M_node != __last._M_node)
00808      {
00809        std::_Destroy(__first._M_cur, __first._M_last,
00810              _M_get_Tp_allocator());
00811        std::_Destroy(__last._M_first, __last._M_cur,
00812              _M_get_Tp_allocator());
00813      }
00814        else
00815      std::_Destroy(__first._M_cur, __last._M_cur,
00816                _M_get_Tp_allocator());
00817      }
00818 
00819   template <typename _Tp, typename _Alloc>
00820     void
00821     deque<_Tp, _Alloc>::
00822     _M_new_elements_at_front(size_type __new_elems)
00823     {
00824       if (this->max_size() - this->size() < __new_elems)
00825     __throw_length_error(__N("deque::_M_new_elements_at_front"));
00826 
00827       const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
00828                      / _S_buffer_size());
00829       _M_reserve_map_at_front(__new_nodes);
00830       size_type __i;
00831       __try
00832         {
00833           for (__i = 1; __i <= __new_nodes; ++__i)
00834             *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
00835         }
00836       __catch(...)
00837         {
00838           for (size_type __j = 1; __j < __i; ++__j)
00839             _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
00840           __throw_exception_again;
00841         }
00842     }
00843 
00844   template <typename _Tp, typename _Alloc>
00845     void
00846     deque<_Tp, _Alloc>::
00847     _M_new_elements_at_back(size_type __new_elems)
00848     {
00849       if (this->max_size() - this->size() < __new_elems)
00850     __throw_length_error(__N("deque::_M_new_elements_at_back"));
00851 
00852       const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
00853                      / _S_buffer_size());
00854       _M_reserve_map_at_back(__new_nodes);
00855       size_type __i;
00856       __try
00857         {
00858           for (__i = 1; __i <= __new_nodes; ++__i)
00859             *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
00860         }
00861       __catch(...)
00862         {
00863           for (size_type __j = 1; __j < __i; ++__j)
00864             _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
00865           __throw_exception_again;
00866         }
00867     }
00868 
00869   template <typename _Tp, typename _Alloc>
00870     void
00871     deque<_Tp, _Alloc>::
00872     _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
00873     {
00874       const size_type __old_num_nodes
00875     = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
00876       const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
00877 
00878       _Map_pointer __new_nstart;
00879       if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
00880     {
00881       __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
00882                      - __new_num_nodes) / 2
00883                      + (__add_at_front ? __nodes_to_add : 0);
00884       if (__new_nstart < this->_M_impl._M_start._M_node)
00885         std::copy(this->_M_impl._M_start._M_node,
00886               this->_M_impl._M_finish._M_node + 1,
00887               __new_nstart);
00888       else
00889         std::copy_backward(this->_M_impl._M_start._M_node,
00890                    this->_M_impl._M_finish._M_node + 1,
00891                    __new_nstart + __old_num_nodes);
00892     }
00893       else
00894     {
00895       size_type __new_map_size = this->_M_impl._M_map_size
00896                                  + std::max(this->_M_impl._M_map_size,
00897                         __nodes_to_add) + 2;
00898 
00899       _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
00900       __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
00901                      + (__add_at_front ? __nodes_to_add : 0);
00902       std::copy(this->_M_impl._M_start._M_node,
00903             this->_M_impl._M_finish._M_node + 1,
00904             __new_nstart);
00905       _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
00906 
00907       this->_M_impl._M_map = __new_map;
00908       this->_M_impl._M_map_size = __new_map_size;
00909     }
00910 
00911       this->_M_impl._M_start._M_set_node(__new_nstart);
00912       this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
00913     }
00914 
00915   // Overload for deque::iterators, exploiting the "segmented-iterator
00916   // optimization".
00917   template<typename _Tp>
00918     void
00919     fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
00920      const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
00921     {
00922       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
00923 
00924       for (typename _Self::_Map_pointer __node = __first._M_node + 1;
00925            __node < __last._M_node; ++__node)
00926     std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
00927 
00928       if (__first._M_node != __last._M_node)
00929     {
00930       std::fill(__first._M_cur, __first._M_last, __value);
00931       std::fill(__last._M_first, __last._M_cur, __value);
00932     }
00933       else
00934     std::fill(__first._M_cur, __last._M_cur, __value);
00935     }
00936 
00937   template<typename _Tp>
00938     _Deque_iterator<_Tp, _Tp&, _Tp*>
00939     copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
00940      _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
00941      _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
00942     {
00943       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
00944       typedef typename _Self::difference_type difference_type;
00945 
00946       difference_type __len = __last - __first;
00947       while (__len > 0)
00948     {
00949       const difference_type __clen
00950         = std::min(__len, std::min(__first._M_last - __first._M_cur,
00951                        __result._M_last - __result._M_cur));
00952       std::copy(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
00953       __first += __clen;
00954       __result += __clen;
00955       __len -= __clen;
00956     }
00957       return __result;
00958     }
00959 
00960   template<typename _Tp>
00961     _Deque_iterator<_Tp, _Tp&, _Tp*>
00962     copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
00963           _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
00964           _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
00965     {
00966       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
00967       typedef typename _Self::difference_type difference_type;
00968 
00969       difference_type __len = __last - __first;
00970       while (__len > 0)
00971     {
00972       difference_type __llen = __last._M_cur - __last._M_first;
00973       _Tp* __lend = __last._M_cur;
00974 
00975       difference_type __rlen = __result._M_cur - __result._M_first;
00976       _Tp* __rend = __result._M_cur;
00977 
00978       if (!__llen)
00979         {
00980           __llen = _Self::_S_buffer_size();
00981           __lend = *(__last._M_node - 1) + __llen;
00982         }
00983       if (!__rlen)
00984         {
00985           __rlen = _Self::_S_buffer_size();
00986           __rend = *(__result._M_node - 1) + __rlen;
00987         }
00988 
00989       const difference_type __clen = std::min(__len,
00990                           std::min(__llen, __rlen));
00991       std::copy_backward(__lend - __clen, __lend, __rend);
00992       __last -= __clen;
00993       __result -= __clen;
00994       __len -= __clen;
00995     }
00996       return __result;
00997     }
00998 
00999 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01000   template<typename _Tp>
01001     _Deque_iterator<_Tp, _Tp&, _Tp*>
01002     move(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
01003      _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
01004      _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
01005     {
01006       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
01007       typedef typename _Self::difference_type difference_type;
01008 
01009       difference_type __len = __last - __first;
01010       while (__len > 0)
01011     {
01012       const difference_type __clen
01013         = std::min(__len, std::min(__first._M_last - __first._M_cur,
01014                        __result._M_last - __result._M_cur));
01015       std::move(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
01016       __first += __clen;
01017       __result += __clen;
01018       __len -= __clen;
01019     }
01020       return __result;
01021     }
01022 
01023   template<typename _Tp>
01024     _Deque_iterator<_Tp, _Tp&, _Tp*>
01025     move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
01026           _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
01027           _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
01028     {
01029       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
01030       typedef typename _Self::difference_type difference_type;
01031 
01032       difference_type __len = __last - __first;
01033       while (__len > 0)
01034     {
01035       difference_type __llen = __last._M_cur - __last._M_first;
01036       _Tp* __lend = __last._M_cur;
01037 
01038       difference_type __rlen = __result._M_cur - __result._M_first;
01039       _Tp* __rend = __result._M_cur;
01040 
01041       if (!__llen)
01042         {
01043           __llen = _Self::_S_buffer_size();
01044           __lend = *(__last._M_node - 1) + __llen;
01045         }
01046       if (!__rlen)
01047         {
01048           __rlen = _Self::_S_buffer_size();
01049           __rend = *(__result._M_node - 1) + __rlen;
01050         }
01051 
01052       const difference_type __clen = std::min(__len,
01053                           std::min(__llen, __rlen));
01054       std::move_backward(__lend - __clen, __lend, __rend);
01055       __last -= __clen;
01056       __result -= __clen;
01057       __len -= __clen;
01058     }
01059       return __result;
01060     }
01061 #endif
01062 
01063 _GLIBCXX_END_NAMESPACE_CONTAINER
01064 } // namespace std
01065 
01066 #endif