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