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