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