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