libstdc++
deque.tcc
Go to the documentation of this file.
00001 // Deque implementation (out of line) -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2018 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, ++__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(__n);
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         _M_reserve_map_at_back();
00488         *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
00489         __try
00490           {
00491 #if __cplusplus >= 201103L
00492             _Alloc_traits::construct(this->_M_impl,
00493                                      this->_M_impl._M_finish._M_cur,
00494                                      std::forward<_Args>(__args)...);
00495 #else
00496             this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t);
00497 #endif
00498             this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
00499                                                 + 1);
00500             this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
00501           }
00502         __catch(...)
00503           {
00504             _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
00505             __throw_exception_again;
00506           }
00507       }
00508 
00509   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
00510   template<typename _Tp, typename _Alloc>
00511 #if __cplusplus >= 201103L
00512     template<typename... _Args>
00513       void
00514       deque<_Tp, _Alloc>::
00515       _M_push_front_aux(_Args&&... __args)
00516 #else
00517       void
00518       deque<_Tp, _Alloc>::
00519       _M_push_front_aux(const value_type& __t)
00520 #endif
00521       {
00522         _M_reserve_map_at_front();
00523         *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
00524         __try
00525           {
00526             this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
00527                                                - 1);
00528             this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
00529 #if __cplusplus >= 201103L
00530             _Alloc_traits::construct(this->_M_impl,
00531                                      this->_M_impl._M_start._M_cur,
00532                                      std::forward<_Args>(__args)...);
00533 #else
00534             this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t);
00535 #endif
00536           }
00537         __catch(...)
00538           {
00539             ++this->_M_impl._M_start;
00540             _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
00541             __throw_exception_again;
00542           }
00543       }
00544 
00545   // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
00546   template <typename _Tp, typename _Alloc>
00547     void deque<_Tp, _Alloc>::
00548     _M_pop_back_aux()
00549     {
00550       _M_deallocate_node(this->_M_impl._M_finish._M_first);
00551       this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
00552       this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
00553       _Alloc_traits::destroy(_M_get_Tp_allocator(),
00554                              this->_M_impl._M_finish._M_cur);
00555     }
00556 
00557   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
00558   // Note that if the deque has at least one element (a precondition for this
00559   // member function), and if
00560   //   _M_impl._M_start._M_cur == _M_impl._M_start._M_last,
00561   // then the deque must have at least two nodes.
00562   template <typename _Tp, typename _Alloc>
00563     void deque<_Tp, _Alloc>::
00564     _M_pop_front_aux()
00565     {
00566       _Alloc_traits::destroy(_M_get_Tp_allocator(),
00567                              this->_M_impl._M_start._M_cur);
00568       _M_deallocate_node(this->_M_impl._M_start._M_first);
00569       this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
00570       this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
00571     }
00572 
00573   template <typename _Tp, typename _Alloc>
00574     template <typename _InputIterator>
00575       void
00576       deque<_Tp, _Alloc>::
00577       _M_range_insert_aux(iterator __pos,
00578                           _InputIterator __first, _InputIterator __last,
00579                           std::input_iterator_tag)
00580       { std::copy(__first, __last, std::inserter(*this, __pos)); }
00581 
00582   template <typename _Tp, typename _Alloc>
00583     template <typename _ForwardIterator>
00584       void
00585       deque<_Tp, _Alloc>::
00586       _M_range_insert_aux(iterator __pos,
00587                           _ForwardIterator __first, _ForwardIterator __last,
00588                           std::forward_iterator_tag)
00589       {
00590         const size_type __n = std::distance(__first, __last);
00591         if (__pos._M_cur == this->_M_impl._M_start._M_cur)
00592           {
00593             iterator __new_start = _M_reserve_elements_at_front(__n);
00594             __try
00595               {
00596                 std::__uninitialized_copy_a(__first, __last, __new_start,
00597                                             _M_get_Tp_allocator());
00598                 this->_M_impl._M_start = __new_start;
00599               }
00600             __catch(...)
00601               {
00602                 _M_destroy_nodes(__new_start._M_node,
00603                                  this->_M_impl._M_start._M_node);
00604                 __throw_exception_again;
00605               }
00606           }
00607         else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
00608           {
00609             iterator __new_finish = _M_reserve_elements_at_back(__n);
00610             __try
00611               {
00612                 std::__uninitialized_copy_a(__first, __last,
00613                                             this->_M_impl._M_finish,
00614                                             _M_get_Tp_allocator());
00615                 this->_M_impl._M_finish = __new_finish;
00616               }
00617             __catch(...)
00618               {
00619                 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00620                                  __new_finish._M_node + 1);
00621                 __throw_exception_again;
00622               }
00623           }
00624         else
00625           _M_insert_aux(__pos, __first, __last, __n);
00626       }
00627 
00628   template<typename _Tp, typename _Alloc>
00629 #if __cplusplus >= 201103L
00630     template<typename... _Args>
00631       typename deque<_Tp, _Alloc>::iterator
00632       deque<_Tp, _Alloc>::
00633       _M_insert_aux(iterator __pos, _Args&&... __args)
00634       {
00635         value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy
00636 #else
00637     typename deque<_Tp, _Alloc>::iterator
00638       deque<_Tp, _Alloc>::
00639       _M_insert_aux(iterator __pos, const value_type& __x)
00640       {
00641         value_type __x_copy = __x; // XXX copy
00642 #endif
00643         difference_type __index = __pos - this->_M_impl._M_start;
00644         if (static_cast<size_type>(__index) < size() / 2)
00645           {
00646             push_front(_GLIBCXX_MOVE(front()));
00647             iterator __front1 = this->_M_impl._M_start;
00648             ++__front1;
00649             iterator __front2 = __front1;
00650             ++__front2;
00651             __pos = this->_M_impl._M_start + __index;
00652             iterator __pos1 = __pos;
00653             ++__pos1;
00654             _GLIBCXX_MOVE3(__front2, __pos1, __front1);
00655           }
00656         else
00657           {
00658             push_back(_GLIBCXX_MOVE(back()));
00659             iterator __back1 = this->_M_impl._M_finish;
00660             --__back1;
00661             iterator __back2 = __back1;
00662             --__back2;
00663             __pos = this->_M_impl._M_start + __index;
00664             _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
00665           }
00666         *__pos = _GLIBCXX_MOVE(__x_copy);
00667         return __pos;
00668       }
00669 
00670   template <typename _Tp, typename _Alloc>
00671     void
00672     deque<_Tp, _Alloc>::
00673     _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
00674     {
00675       const difference_type __elems_before = __pos - this->_M_impl._M_start;
00676       const size_type __length = this->size();
00677       value_type __x_copy = __x;
00678       if (__elems_before < difference_type(__length / 2))
00679         {
00680           iterator __new_start = _M_reserve_elements_at_front(__n);
00681           iterator __old_start = this->_M_impl._M_start;
00682           __pos = this->_M_impl._M_start + __elems_before;
00683           __try
00684             {
00685               if (__elems_before >= difference_type(__n))
00686                 {
00687                   iterator __start_n = (this->_M_impl._M_start
00688                                         + difference_type(__n));
00689                   std::__uninitialized_move_a(this->_M_impl._M_start,
00690                                               __start_n, __new_start,
00691                                               _M_get_Tp_allocator());
00692                   this->_M_impl._M_start = __new_start;
00693                   _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
00694                   std::fill(__pos - difference_type(__n), __pos, __x_copy);
00695                 }
00696               else
00697                 {
00698                   std::__uninitialized_move_fill(this->_M_impl._M_start,
00699                                                  __pos, __new_start,
00700                                                  this->_M_impl._M_start,
00701                                                  __x_copy,
00702                                                  _M_get_Tp_allocator());
00703                   this->_M_impl._M_start = __new_start;
00704                   std::fill(__old_start, __pos, __x_copy);
00705                 }
00706             }
00707           __catch(...)
00708             {
00709               _M_destroy_nodes(__new_start._M_node,
00710                                this->_M_impl._M_start._M_node);
00711               __throw_exception_again;
00712             }
00713         }
00714       else
00715         {
00716           iterator __new_finish = _M_reserve_elements_at_back(__n);
00717           iterator __old_finish = this->_M_impl._M_finish;
00718           const difference_type __elems_after =
00719             difference_type(__length) - __elems_before;
00720           __pos = this->_M_impl._M_finish - __elems_after;
00721           __try
00722             {
00723               if (__elems_after > difference_type(__n))
00724                 {
00725                   iterator __finish_n = (this->_M_impl._M_finish
00726                                          - difference_type(__n));
00727                   std::__uninitialized_move_a(__finish_n,
00728                                               this->_M_impl._M_finish,
00729                                               this->_M_impl._M_finish,
00730                                               _M_get_Tp_allocator());
00731                   this->_M_impl._M_finish = __new_finish;
00732                   _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
00733                   std::fill(__pos, __pos + difference_type(__n), __x_copy);
00734                 }
00735               else
00736                 {
00737                   std::__uninitialized_fill_move(this->_M_impl._M_finish,
00738                                                  __pos + difference_type(__n),
00739                                                  __x_copy, __pos,
00740                                                  this->_M_impl._M_finish,
00741                                                  _M_get_Tp_allocator());
00742                   this->_M_impl._M_finish = __new_finish;
00743                   std::fill(__pos, __old_finish, __x_copy);
00744                 }
00745             }
00746           __catch(...)
00747             {
00748               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00749                                __new_finish._M_node + 1);
00750               __throw_exception_again;
00751             }
00752         }
00753     }
00754 
00755   template <typename _Tp, typename _Alloc>
00756     template <typename _ForwardIterator>
00757       void
00758       deque<_Tp, _Alloc>::
00759       _M_insert_aux(iterator __pos,
00760                     _ForwardIterator __first, _ForwardIterator __last,
00761                     size_type __n)
00762       {
00763         const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
00764         const size_type __length = size();
00765         if (static_cast<size_type>(__elemsbefore) < __length / 2)
00766           {
00767             iterator __new_start = _M_reserve_elements_at_front(__n);
00768             iterator __old_start = this->_M_impl._M_start;
00769             __pos = this->_M_impl._M_start + __elemsbefore;
00770             __try
00771               {
00772                 if (__elemsbefore >= difference_type(__n))
00773                   {
00774                     iterator __start_n = (this->_M_impl._M_start
00775                                           + difference_type(__n));
00776                     std::__uninitialized_move_a(this->_M_impl._M_start,
00777                                                 __start_n, __new_start,
00778                                                 _M_get_Tp_allocator());
00779                     this->_M_impl._M_start = __new_start;
00780                     _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
00781                     std::copy(__first, __last, __pos - difference_type(__n));
00782                   }
00783                 else
00784                   {
00785                     _ForwardIterator __mid = __first;
00786                     std::advance(__mid, difference_type(__n) - __elemsbefore);
00787                     std::__uninitialized_move_copy(this->_M_impl._M_start,
00788                                                    __pos, __first, __mid,
00789                                                    __new_start,
00790                                                    _M_get_Tp_allocator());
00791                     this->_M_impl._M_start = __new_start;
00792                     std::copy(__mid, __last, __old_start);
00793                   }
00794               }
00795             __catch(...)
00796               {
00797                 _M_destroy_nodes(__new_start._M_node,
00798                                  this->_M_impl._M_start._M_node);
00799                 __throw_exception_again;
00800               }
00801           }
00802         else
00803         {
00804           iterator __new_finish = _M_reserve_elements_at_back(__n);
00805           iterator __old_finish = this->_M_impl._M_finish;
00806           const difference_type __elemsafter =
00807             difference_type(__length) - __elemsbefore;
00808           __pos = this->_M_impl._M_finish - __elemsafter;
00809           __try
00810             {
00811               if (__elemsafter > difference_type(__n))
00812                 {
00813                   iterator __finish_n = (this->_M_impl._M_finish
00814                                          - difference_type(__n));
00815                   std::__uninitialized_move_a(__finish_n,
00816                                               this->_M_impl._M_finish,
00817                                               this->_M_impl._M_finish,
00818                                               _M_get_Tp_allocator());
00819                   this->_M_impl._M_finish = __new_finish;
00820                   _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
00821                   std::copy(__first, __last, __pos);
00822                 }
00823               else
00824                 {
00825                   _ForwardIterator __mid = __first;
00826                   std::advance(__mid, __elemsafter);
00827                   std::__uninitialized_copy_move(__mid, __last, __pos,
00828                                                  this->_M_impl._M_finish,
00829                                                  this->_M_impl._M_finish,
00830                                                  _M_get_Tp_allocator());
00831                   this->_M_impl._M_finish = __new_finish;
00832                   std::copy(__first, __mid, __pos);
00833                 }
00834             }
00835           __catch(...)
00836             {
00837               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00838                                __new_finish._M_node + 1);
00839               __throw_exception_again;
00840             }
00841         }
00842       }
00843 
00844    template<typename _Tp, typename _Alloc>
00845      void
00846      deque<_Tp, _Alloc>::
00847      _M_destroy_data_aux(iterator __first, iterator __last)
00848      {
00849        for (_Map_pointer __node = __first._M_node + 1;
00850             __node < __last._M_node; ++__node)
00851          std::_Destroy(*__node, *__node + _S_buffer_size(),
00852                        _M_get_Tp_allocator());
00853 
00854        if (__first._M_node != __last._M_node)
00855          {
00856            std::_Destroy(__first._M_cur, __first._M_last,
00857                          _M_get_Tp_allocator());
00858            std::_Destroy(__last._M_first, __last._M_cur,
00859                          _M_get_Tp_allocator());
00860          }
00861        else
00862          std::_Destroy(__first._M_cur, __last._M_cur,
00863                        _M_get_Tp_allocator());
00864      }
00865 
00866   template <typename _Tp, typename _Alloc>
00867     void
00868     deque<_Tp, _Alloc>::
00869     _M_new_elements_at_front(size_type __new_elems)
00870     {
00871       if (this->max_size() - this->size() < __new_elems)
00872         __throw_length_error(__N("deque::_M_new_elements_at_front"));
00873 
00874       const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
00875                                      / _S_buffer_size());
00876       _M_reserve_map_at_front(__new_nodes);
00877       size_type __i;
00878       __try
00879         {
00880           for (__i = 1; __i <= __new_nodes; ++__i)
00881             *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
00882         }
00883       __catch(...)
00884         {
00885           for (size_type __j = 1; __j < __i; ++__j)
00886             _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
00887           __throw_exception_again;
00888         }
00889     }
00890 
00891   template <typename _Tp, typename _Alloc>
00892     void
00893     deque<_Tp, _Alloc>::
00894     _M_new_elements_at_back(size_type __new_elems)
00895     {
00896       if (this->max_size() - this->size() < __new_elems)
00897         __throw_length_error(__N("deque::_M_new_elements_at_back"));
00898 
00899       const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
00900                                      / _S_buffer_size());
00901       _M_reserve_map_at_back(__new_nodes);
00902       size_type __i;
00903       __try
00904         {
00905           for (__i = 1; __i <= __new_nodes; ++__i)
00906             *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
00907         }
00908       __catch(...)
00909         {
00910           for (size_type __j = 1; __j < __i; ++__j)
00911             _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
00912           __throw_exception_again;
00913         }
00914     }
00915 
00916   template <typename _Tp, typename _Alloc>
00917     void
00918     deque<_Tp, _Alloc>::
00919     _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
00920     {
00921       const size_type __old_num_nodes
00922         = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
00923       const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
00924 
00925       _Map_pointer __new_nstart;
00926       if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
00927         {
00928           __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
00929                                          - __new_num_nodes) / 2
00930                          + (__add_at_front ? __nodes_to_add : 0);
00931           if (__new_nstart < this->_M_impl._M_start._M_node)
00932             std::copy(this->_M_impl._M_start._M_node,
00933                       this->_M_impl._M_finish._M_node + 1,
00934                       __new_nstart);
00935           else
00936             std::copy_backward(this->_M_impl._M_start._M_node,
00937                                this->_M_impl._M_finish._M_node + 1,
00938                                __new_nstart + __old_num_nodes);
00939         }
00940       else
00941         {
00942           size_type __new_map_size = this->_M_impl._M_map_size
00943                                      + std::max(this->_M_impl._M_map_size,
00944                                                 __nodes_to_add) + 2;
00945 
00946           _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
00947           __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
00948                          + (__add_at_front ? __nodes_to_add : 0);
00949           std::copy(this->_M_impl._M_start._M_node,
00950                     this->_M_impl._M_finish._M_node + 1,
00951                     __new_nstart);
00952           _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
00953 
00954           this->_M_impl._M_map = __new_map;
00955           this->_M_impl._M_map_size = __new_map_size;
00956         }
00957 
00958       this->_M_impl._M_start._M_set_node(__new_nstart);
00959       this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
00960     }
00961 
00962   // Overload for deque::iterators, exploiting the "segmented-iterator
00963   // optimization".
00964   template<typename _Tp>
00965     void
00966     fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
00967          const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
00968     {
00969       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
00970 
00971       for (typename _Self::_Map_pointer __node = __first._M_node + 1;
00972            __node < __last._M_node; ++__node)
00973         std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
00974 
00975       if (__first._M_node != __last._M_node)
00976         {
00977           std::fill(__first._M_cur, __first._M_last, __value);
00978           std::fill(__last._M_first, __last._M_cur, __value);
00979         }
00980       else
00981         std::fill(__first._M_cur, __last._M_cur, __value);
00982     }
00983 
00984   template<typename _Tp>
00985     _Deque_iterator<_Tp, _Tp&, _Tp*>
00986     copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
00987          _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
00988          _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
00989     {
00990       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
00991       typedef typename _Self::difference_type difference_type;
00992 
00993       difference_type __len = __last - __first;
00994       while (__len > 0)
00995         {
00996           const difference_type __clen
00997             = std::min(__len, std::min(__first._M_last - __first._M_cur,
00998                                        __result._M_last - __result._M_cur));
00999           std::copy(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
01000           __first += __clen;
01001           __result += __clen;
01002           __len -= __clen;
01003         }
01004       return __result;
01005     }
01006 
01007   template<typename _Tp>
01008     _Deque_iterator<_Tp, _Tp&, _Tp*>
01009     copy_backward(_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           difference_type __llen = __last._M_cur - __last._M_first;
01020           _Tp* __lend = __last._M_cur;
01021 
01022           difference_type __rlen = __result._M_cur - __result._M_first;
01023           _Tp* __rend = __result._M_cur;
01024 
01025           if (!__llen)
01026             {
01027               __llen = _Self::_S_buffer_size();
01028               __lend = *(__last._M_node - 1) + __llen;
01029             }
01030           if (!__rlen)
01031             {
01032               __rlen = _Self::_S_buffer_size();
01033               __rend = *(__result._M_node - 1) + __rlen;
01034             }
01035 
01036           const difference_type __clen = std::min(__len,
01037                                                   std::min(__llen, __rlen));
01038           std::copy_backward(__lend - __clen, __lend, __rend);
01039           __last -= __clen;
01040           __result -= __clen;
01041           __len -= __clen;
01042         }
01043       return __result;
01044     }
01045 
01046 #if __cplusplus >= 201103L
01047   template<typename _Tp>
01048     _Deque_iterator<_Tp, _Tp&, _Tp*>
01049     move(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
01050          _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
01051          _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
01052     {
01053       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
01054       typedef typename _Self::difference_type difference_type;
01055 
01056       difference_type __len = __last - __first;
01057       while (__len > 0)
01058         {
01059           const difference_type __clen
01060             = std::min(__len, std::min(__first._M_last - __first._M_cur,
01061                                        __result._M_last - __result._M_cur));
01062           std::move(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
01063           __first += __clen;
01064           __result += __clen;
01065           __len -= __clen;
01066         }
01067       return __result;
01068     }
01069 
01070   template<typename _Tp>
01071     _Deque_iterator<_Tp, _Tp&, _Tp*>
01072     move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
01073                   _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
01074                   _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
01075     {
01076       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
01077       typedef typename _Self::difference_type difference_type;
01078 
01079       difference_type __len = __last - __first;
01080       while (__len > 0)
01081         {
01082           difference_type __llen = __last._M_cur - __last._M_first;
01083           _Tp* __lend = __last._M_cur;
01084 
01085           difference_type __rlen = __result._M_cur - __result._M_first;
01086           _Tp* __rend = __result._M_cur;
01087 
01088           if (!__llen)
01089             {
01090               __llen = _Self::_S_buffer_size();
01091               __lend = *(__last._M_node - 1) + __llen;
01092             }
01093           if (!__rlen)
01094             {
01095               __rlen = _Self::_S_buffer_size();
01096               __rend = *(__result._M_node - 1) + __rlen;
01097             }
01098 
01099           const difference_type __clen = std::min(__len,
01100                                                   std::min(__llen, __rlen));
01101           std::move_backward(__lend - __clen, __lend, __rend);
01102           __last -= __clen;
01103           __result -= __clen;
01104           __len -= __clen;
01105         }
01106       return __result;
01107     }
01108 #endif
01109 
01110 _GLIBCXX_END_NAMESPACE_CONTAINER
01111 _GLIBCXX_END_NAMESPACE_VERSION
01112 } // namespace std
01113 
01114 #endif