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