stl_deque.h

Go to the documentation of this file.
00001 // deque implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002 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 2, 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 // You should have received a copy of the GNU General Public License along
00017 // with this library; see the file COPYING.  If not, write to the Free
00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
00019 // USA.
00020 
00021 // As a special exception, you may use this file as part of a free software
00022 // library without restriction.  Specifically, if other files instantiate
00023 // templates or use macros or inline functions from this file, or you compile
00024 // this file and link it with other files to produce an executable, this
00025 // file does not by itself cause the resulting executable to be covered by
00026 // the GNU General Public License.  This exception does not however
00027 // invalidate any other reasons why the executable file might be covered by
00028 // the GNU General Public License.
00029 
00030 /*
00031  *
00032  * Copyright (c) 1994
00033  * Hewlett-Packard Company
00034  *
00035  * Permission to use, copy, modify, distribute and sell this software
00036  * and its documentation for any purpose is hereby granted without fee,
00037  * provided that the above copyright notice appear in all copies and
00038  * that both that copyright notice and this permission notice appear
00039  * in supporting documentation.  Hewlett-Packard Company makes no
00040  * representations about the suitability of this software for any
00041  * purpose.  It is provided "as is" without express or implied warranty.
00042  *
00043  *
00044  * Copyright (c) 1997
00045  * Silicon Graphics Computer Systems, Inc.
00046  *
00047  * Permission to use, copy, modify, distribute and sell this software
00048  * and its documentation for any purpose is hereby granted without fee,
00049  * provided that the above copyright notice appear in all copies and
00050  * that both that copyright notice and this permission notice appear
00051  * in supporting documentation.  Silicon Graphics makes no
00052  * representations about the suitability of this software for any
00053  * purpose.  It is provided "as is" without express or implied warranty.
00054  */
00055 
00061 #include <bits/concept_check.h>
00062 #include <bits/stl_iterator_base_types.h>
00063 #include <bits/stl_iterator_base_funcs.h>
00064 
00065 #ifndef __GLIBCPP_INTERNAL_DEQUE_H
00066 #define __GLIBCPP_INTERNAL_DEQUE_H
00067 
00068 
00069 // Since this entire file is within namespace std, there's no reason to
00070 // waste two spaces along the left column.  Thus the leading indentation is
00071 // slightly violated from here on.
00072 namespace std
00073 { 
00074 
00085 inline size_t 
00086 __deque_buf_size(size_t __size) 
00087 { return __size < 512 ? size_t(512 / __size) : size_t(1); }
00088 
00089 
00091 
00101 template <class _Tp, class _Ref, class _Ptr>
00102 struct _Deque_iterator
00103 {
00104   typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
00105   typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
00106   static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
00107 
00108   typedef random_access_iterator_tag iterator_category;
00109   typedef _Tp                        value_type;
00110   typedef _Ptr                       pointer;
00111   typedef _Ref                       reference;
00112   typedef size_t                     size_type;
00113   typedef ptrdiff_t                  difference_type;
00114   typedef _Tp**                      _Map_pointer;
00115   typedef _Deque_iterator            _Self;
00116 
00117   _Tp* _M_cur;
00118   _Tp* _M_first;
00119   _Tp* _M_last;
00120   _Map_pointer _M_node;
00121 
00122   _Deque_iterator(_Tp* __x, _Map_pointer __y) 
00123     : _M_cur(__x), _M_first(*__y),
00124       _M_last(*__y + _S_buffer_size()), _M_node(__y) {}
00125   _Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
00126   _Deque_iterator(const iterator& __x)
00127     : _M_cur(__x._M_cur), _M_first(__x._M_first), 
00128       _M_last(__x._M_last), _M_node(__x._M_node) {}
00129 
00130   reference operator*() const { return *_M_cur; }
00131   pointer operator->() const { return _M_cur; }
00132 
00133   _Self& operator++() {
00134     ++_M_cur;
00135     if (_M_cur == _M_last) {
00136       _M_set_node(_M_node + 1);
00137       _M_cur = _M_first;
00138     }
00139     return *this; 
00140   }
00141   _Self operator++(int)  {
00142     _Self __tmp = *this;
00143     ++*this;
00144     return __tmp;
00145   }
00146 
00147   _Self& operator--() {
00148     if (_M_cur == _M_first) {
00149       _M_set_node(_M_node - 1);
00150       _M_cur = _M_last;
00151     }
00152     --_M_cur;
00153     return *this;
00154   }
00155   _Self operator--(int) {
00156     _Self __tmp = *this;
00157     --*this;
00158     return __tmp;
00159   }
00160 
00161   _Self& operator+=(difference_type __n)
00162   {
00163     difference_type __offset = __n + (_M_cur - _M_first);
00164     if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
00165       _M_cur += __n;
00166     else {
00167       difference_type __node_offset =
00168         __offset > 0 ? __offset / difference_type(_S_buffer_size())
00169                    : -difference_type((-__offset - 1) / _S_buffer_size()) - 1;
00170       _M_set_node(_M_node + __node_offset);
00171       _M_cur = _M_first + 
00172         (__offset - __node_offset * difference_type(_S_buffer_size()));
00173     }
00174     return *this;
00175   }
00176 
00177   _Self operator+(difference_type __n) const
00178   {
00179     _Self __tmp = *this;
00180     return __tmp += __n;
00181   }
00182 
00183   _Self& operator-=(difference_type __n) { return *this += -__n; }
00184  
00185   _Self operator-(difference_type __n) const {
00186     _Self __tmp = *this;
00187     return __tmp -= __n;
00188   }
00189 
00190   reference operator[](difference_type __n) const { return *(*this + __n); }
00191 
00198   void _M_set_node(_Map_pointer __new_node) {
00199     _M_node = __new_node;
00200     _M_first = *__new_node;
00201     _M_last = _M_first + difference_type(_S_buffer_size());
00202   }
00203 };
00204 
00205 // Note: we also provide overloads whose operands are of the same type in
00206 // order to avoid ambiguos overload resolution when std::rel_ops operators
00207 // are in scope (for additional details, see libstdc++/3628)
00208 template <class _Tp, class _Ref, class _Ptr>
00209 inline bool
00210 operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00211        const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00212 {
00213   return __x._M_cur == __y._M_cur;
00214 }
00215 
00216 template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
00217 inline bool
00218 operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00219        const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00220 {
00221   return __x._M_cur == __y._M_cur;
00222 }
00223 
00224 template <class _Tp, class _Ref, class _Ptr>
00225 inline bool
00226 operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00227        const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00228 {
00229   return !(__x == __y);
00230 }
00231 
00232 template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
00233 inline bool
00234 operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00235        const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00236 {
00237   return !(__x == __y);
00238 }
00239 
00240 template <class _Tp, class _Ref, class _Ptr>
00241 inline bool
00242 operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00243        const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00244 {
00245   return (__x._M_node == __y._M_node) ? 
00246     (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
00247 }
00248 
00249 template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
00250 inline bool
00251 operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00252        const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00253 {
00254   return (__x._M_node == __y._M_node) ? 
00255     (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
00256 }
00257 
00258 template <class _Tp, class _Ref, class _Ptr>
00259 inline bool
00260 operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00261        const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00262 {
00263   return __y < __x;
00264 }
00265 
00266 template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
00267 inline bool
00268 operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00269        const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00270 {
00271   return __y < __x;
00272 }
00273 
00274 template <class _Tp, class _Ref, class _Ptr>
00275 inline bool
00276 operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00277        const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00278 {
00279   return !(__y < __x);
00280 }
00281 
00282 template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
00283 inline bool
00284 operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00285        const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00286 {
00287   return !(__y < __x);
00288 }
00289 
00290 template <class _Tp, class _Ref, class _Ptr>
00291 inline bool
00292 operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00293        const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00294 {
00295   return !(__x < __y);
00296 }
00297 
00298 template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
00299 inline bool
00300 operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00301        const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00302 {
00303   return !(__x < __y);
00304 }
00305 
00306 // _GLIBCPP_RESOLVE_LIB_DEFECTS
00307 // According to the resolution of DR179 not only the various comparison
00308 // operators but also operator- must accept mixed iterator/const_iterator
00309 // parameters.
00310 template <typename _Tp, typename _RefL, typename _PtrL,
00311                         typename _RefR, typename _PtrR>
00312 inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
00313 operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00314       const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00315 {
00316   return _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
00317     (_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size()) *
00318     (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first) +
00319     (__y._M_last - __y._M_cur);
00320 }
00321 
00322 template <class _Tp, class _Ref, class _Ptr>
00323 inline _Deque_iterator<_Tp, _Ref, _Ptr>
00324 operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
00325 {
00326   return __x + __n;
00327 }
00328 
00329 
00331 
00341 template <class _Tp, class _Alloc, bool __is_static>
00342 class _Deque_alloc_base
00343 {
00344 public:
00345   typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
00346   allocator_type get_allocator() const { return _M_node_allocator; }
00347 
00348   _Deque_alloc_base(const allocator_type& __a)
00349     : _M_node_allocator(__a), _M_map_allocator(__a),
00350       _M_map(0), _M_map_size(0)
00351   {}
00352   
00353 protected:
00354   typedef typename _Alloc_traits<_Tp*, _Alloc>::allocator_type
00355           _Map_allocator_type;
00356 
00357   allocator_type      _M_node_allocator;
00358   _Map_allocator_type _M_map_allocator;
00359 
00360   _Tp* _M_allocate_node() {
00361     return _M_node_allocator.allocate(__deque_buf_size(sizeof(_Tp)));
00362   }
00363   void _M_deallocate_node(_Tp* __p) {
00364     _M_node_allocator.deallocate(__p, __deque_buf_size(sizeof(_Tp)));
00365   }
00366   _Tp** _M_allocate_map(size_t __n) 
00367     { return _M_map_allocator.allocate(__n); }
00368   void _M_deallocate_map(_Tp** __p, size_t __n) 
00369     { _M_map_allocator.deallocate(__p, __n); }
00370 
00371   _Tp** _M_map;
00372   size_t _M_map_size;
00373 };
00374 
00376 template <class _Tp, class _Alloc>
00377 class _Deque_alloc_base<_Tp, _Alloc, true>
00378 {
00379 public:
00380   typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
00381   allocator_type get_allocator() const { return allocator_type(); }
00382 
00383   _Deque_alloc_base(const allocator_type&) : _M_map(0), _M_map_size(0) {}
00384   
00385 protected:
00386   typedef typename _Alloc_traits<_Tp, _Alloc>::_Alloc_type _Node_alloc_type;
00387   typedef typename _Alloc_traits<_Tp*, _Alloc>::_Alloc_type _Map_alloc_type;
00388 
00389   _Tp* _M_allocate_node() {
00390     return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp)));
00391   }
00392   void _M_deallocate_node(_Tp* __p) {
00393     _Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp)));
00394   }
00395   _Tp** _M_allocate_map(size_t __n) 
00396     { return _Map_alloc_type::allocate(__n); }
00397   void _M_deallocate_map(_Tp** __p, size_t __n) 
00398     { _Map_alloc_type::deallocate(__p, __n); }
00399 
00400   _Tp** _M_map;
00401   size_t _M_map_size;
00402 };
00403 
00404 
00415 template <class _Tp, class _Alloc>
00416 class _Deque_base
00417   : public _Deque_alloc_base<_Tp,_Alloc,
00418                               _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
00419 {
00420 public:
00421   typedef _Deque_alloc_base<_Tp,_Alloc,
00422                              _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
00423           _Base;
00424   typedef typename _Base::allocator_type             allocator_type;
00425   typedef _Deque_iterator<_Tp,_Tp&,_Tp*>             iterator;
00426   typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
00427 
00428   _Deque_base(const allocator_type& __a, size_t __num_elements)
00429     : _Base(__a), _M_start(), _M_finish()
00430     { _M_initialize_map(__num_elements); }
00431   _Deque_base(const allocator_type& __a) 
00432     : _Base(__a), _M_start(), _M_finish() {}
00433   ~_Deque_base();    
00434 
00435 protected:
00436   void _M_initialize_map(size_t);
00437   void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
00438   void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
00439   enum { _S_initial_map_size = 8 };
00440 
00441 protected:
00442   iterator _M_start;
00443   iterator _M_finish;
00444 };
00445 
00446 
00447 template <class _Tp, class _Alloc>
00448 _Deque_base<_Tp,_Alloc>::~_Deque_base()
00449 {
00450   if (_M_map) {
00451     _M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1);
00452     _M_deallocate_map(_M_map, _M_map_size);
00453   }
00454 }
00455 
00465 template <class _Tp, class _Alloc>
00466 void
00467 _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
00468 {
00469   size_t __num_nodes = 
00470     __num_elements / __deque_buf_size(sizeof(_Tp)) + 1;
00471 
00472   _M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2);
00473   _M_map = _M_allocate_map(_M_map_size);
00474 
00475   _Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2;
00476   _Tp** __nfinish = __nstart + __num_nodes;
00477     
00478   try 
00479     { _M_create_nodes(__nstart, __nfinish); }
00480   catch(...)
00481     {
00482       _M_deallocate_map(_M_map, _M_map_size);
00483       _M_map = 0;
00484       _M_map_size = 0;
00485       __throw_exception_again;
00486     }
00487   
00488   _M_start._M_set_node(__nstart);
00489   _M_finish._M_set_node(__nfinish - 1);
00490   _M_start._M_cur = _M_start._M_first;
00491   _M_finish._M_cur = _M_finish._M_first +
00492                __num_elements % __deque_buf_size(sizeof(_Tp));
00493 }
00494 
00495 template <class _Tp, class _Alloc>
00496 void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
00497 {
00498   _Tp** __cur;
00499   try {
00500     for (__cur = __nstart; __cur < __nfinish; ++__cur)
00501       *__cur = _M_allocate_node();
00502   }
00503   catch(...)
00504     { 
00505       _M_destroy_nodes(__nstart, __cur);
00506       __throw_exception_again; 
00507     }
00508 }
00509 
00510 template <class _Tp, class _Alloc>
00511 void
00512 _Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish)
00513 {
00514   for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
00515     _M_deallocate_node(*__n);
00516 }
00517 
00518 
00599 template <class _Tp, class _Alloc = allocator<_Tp> >
00600 class deque : protected _Deque_base<_Tp, _Alloc>
00601 {
00602   // concept requirements
00603   __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
00604 
00605   typedef _Deque_base<_Tp, _Alloc> _Base;
00606 
00607 public:
00608   typedef _Tp                                value_type;
00609   typedef value_type*                        pointer;
00610   typedef const value_type*                  const_pointer;
00611   typedef value_type&                        reference;
00612   typedef const value_type&                  const_reference;
00613   typedef size_t                             size_type;
00614   typedef ptrdiff_t                          difference_type;
00615 
00616   typedef typename _Base::allocator_type allocator_type;
00617   allocator_type get_allocator() const { return _Base::get_allocator(); }
00618 
00619   typedef typename _Base::iterator           iterator;
00620   typedef typename _Base::const_iterator     const_iterator;
00621   typedef reverse_iterator<const_iterator>   const_reverse_iterator;
00622   typedef reverse_iterator<iterator>         reverse_iterator;
00623 
00624 protected:
00625   typedef pointer* _Map_pointer;
00626   static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
00627 
00628   // Functions controlling memory layout, and nothing else.
00629   using _Base::_M_initialize_map;
00630   using _Base::_M_create_nodes;
00631   using _Base::_M_destroy_nodes;
00632   using _Base::_M_allocate_node;
00633   using _Base::_M_deallocate_node;
00634   using _Base::_M_allocate_map;
00635   using _Base::_M_deallocate_map;
00636 
00643   using _Base::_M_map;
00644   using _Base::_M_map_size;
00645   using _Base::_M_start;
00646   using _Base::_M_finish;
00647 
00648 public:                         // Basic accessors
00649   iterator begin() { return _M_start; }
00650   iterator end() { return _M_finish; }
00651   const_iterator begin() const { return _M_start; }
00652   const_iterator end() const { return _M_finish; }
00653 
00654   reverse_iterator rbegin() { return reverse_iterator(_M_finish); }
00655   reverse_iterator rend() { return reverse_iterator(_M_start); }
00656   const_reverse_iterator rbegin() const 
00657     { return const_reverse_iterator(_M_finish); }
00658   const_reverse_iterator rend() const 
00659     { return const_reverse_iterator(_M_start); }
00660 
00661   reference operator[](size_type __n)
00662     { return _M_start[difference_type(__n)]; }
00663   const_reference operator[](size_type __n) const 
00664     { return _M_start[difference_type(__n)]; }
00665 
00666   void _M_range_check(size_type __n) const {
00667     if (__n >= this->size())
00668       __throw_out_of_range("deque");
00669   }
00670 
00671   reference at(size_type __n)
00672     { _M_range_check(__n); return (*this)[__n]; }
00673   const_reference at(size_type __n) const
00674     { _M_range_check(__n); return (*this)[__n]; }
00675 
00676   reference front() { return *_M_start; }
00677   reference back() {
00678     iterator __tmp = _M_finish;
00679     --__tmp;
00680     return *__tmp;
00681   }
00682   const_reference front() const { return *_M_start; }
00683   const_reference back() const {
00684     const_iterator __tmp = _M_finish;
00685     --__tmp;
00686     return *__tmp;
00687   }
00688 
00689   size_type size() const { return _M_finish - _M_start; }
00690   size_type max_size() const { return size_type(-1); }
00691   bool empty() const { return _M_finish == _M_start; }
00692 
00693 public:                         // Constructor, destructor.
00694   explicit deque(const allocator_type& __a = allocator_type()) 
00695     : _Base(__a, 0) {}
00696   deque(const deque& __x) : _Base(__x.get_allocator(), __x.size()) 
00697     { uninitialized_copy(__x.begin(), __x.end(), _M_start); }
00698   deque(size_type __n, const value_type& __value,
00699         const allocator_type& __a = allocator_type()) : _Base(__a, __n)
00700     { _M_fill_initialize(__value); }
00701 
00702   explicit
00703   deque(size_type __n)
00704   : _Base(allocator_type(), __n)
00705   { _M_fill_initialize(value_type()); }
00706 
00707   // Check whether it's an integral type.  If so, it's not an iterator.
00708   template<class _InputIterator>
00709     deque(_InputIterator __first, _InputIterator __last,
00710           const allocator_type& __a = allocator_type())
00711     : _Base(__a)
00712     {
00713       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00714       _M_initialize_dispatch(__first, __last, _Integral());
00715     }
00716 
00717   template<class _Integer>
00718     void
00719     _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
00720     {
00721       _M_initialize_map(__n);
00722       _M_fill_initialize(__x);
00723     }
00724 
00725   template<class _InputIter>
00726     void
00727     _M_initialize_dispatch(_InputIter __first, _InputIter __last, __false_type)
00728     {
00729       typedef typename iterator_traits<_InputIter>::iterator_category _IterCategory;
00730       _M_range_initialize(__first, __last, _IterCategory());
00731     }
00732 
00733   ~deque()
00734   { _Destroy(_M_start, _M_finish); }
00735 
00736   deque& operator= (const deque& __x) {
00737     const size_type __len = size();
00738     if (&__x != this) {
00739       if (__len >= __x.size())
00740         erase(copy(__x.begin(), __x.end(), _M_start), _M_finish);
00741       else {
00742         const_iterator __mid = __x.begin() + difference_type(__len);
00743         copy(__x.begin(), __mid, _M_start);
00744         insert(_M_finish, __mid, __x.end());
00745       }
00746     }
00747     return *this;
00748   }        
00749 
00750   void swap(deque& __x) {
00751     std::swap(_M_start, __x._M_start);
00752     std::swap(_M_finish, __x._M_finish);
00753     std::swap(_M_map, __x._M_map);
00754     std::swap(_M_map_size, __x._M_map_size);
00755   }
00756 
00757 public: 
00758   // assign(), a generalized assignment member function.  Two
00759   // versions: one that takes a count, and one that takes a range.
00760   // The range version is a member template, so we dispatch on whether
00761   // or not the type is an integer.
00762 
00763   void _M_fill_assign(size_type __n, const _Tp& __val) {
00764     if (__n > size()) {
00765       fill(begin(), end(), __val);
00766       insert(end(), __n - size(), __val);
00767     }
00768     else {
00769       erase(begin() + __n, end());
00770       fill(begin(), end(), __val);
00771     }
00772   }
00773 
00774   void
00775   assign(size_type __n, const _Tp& __val)
00776   { _M_fill_assign(__n, __val); }
00777 
00778   template<class _InputIterator>
00779     void
00780     assign(_InputIterator __first, _InputIterator __last)
00781     {
00782       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00783       _M_assign_dispatch(__first, __last, _Integral());
00784     }
00785 
00786 private:                        // helper functions for assign() 
00787 
00788   template<class _Integer>
00789     void
00790     _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
00791     { _M_fill_assign(static_cast<size_type>(__n), static_cast<_Tp>(__val)); }
00792 
00793   template<class _InputIterator>
00794     void
00795     _M_assign_dispatch(_InputIterator __first, _InputIterator __last, __false_type)
00796     {
00797       typedef typename iterator_traits<_InputIterator>::iterator_category _IterCategory;
00798       _M_assign_aux(__first, __last, _IterCategory());
00799     }
00800 
00801   template <class _InputIterator>
00802   void _M_assign_aux(_InputIterator __first, _InputIterator __last,
00803                      input_iterator_tag);
00804 
00805   template <class _ForwardIterator>
00806   void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
00807                      forward_iterator_tag) {
00808     size_type __len = distance(__first, __last);
00809     if (__len > size()) {
00810       _ForwardIterator __mid = __first;
00811       advance(__mid, size());
00812       copy(__first, __mid, begin());
00813       insert(end(), __mid, __last);
00814     }
00815     else
00816       erase(copy(__first, __last, begin()), end());
00817   }
00818 
00819 public:                         // push_* and pop_*
00820   
00821   void
00822   push_back(const value_type& __t)
00823   {
00824     if (_M_finish._M_cur != _M_finish._M_last - 1) {
00825       _Construct(_M_finish._M_cur, __t);
00826       ++_M_finish._M_cur;
00827     }
00828     else
00829       _M_push_back_aux(__t);
00830   }
00831 
00832   void
00833   push_back()
00834   {
00835     if (_M_finish._M_cur != _M_finish._M_last - 1) {
00836       _Construct(_M_finish._M_cur);
00837       ++_M_finish._M_cur;
00838     }
00839     else
00840       _M_push_back_aux();
00841   }
00842 
00843   void
00844   push_front(const value_type& __t) 
00845   {
00846     if (_M_start._M_cur != _M_start._M_first) {
00847       _Construct(_M_start._M_cur - 1, __t);
00848       --_M_start._M_cur;
00849     }
00850     else
00851       _M_push_front_aux(__t);
00852   }
00853 
00854   void
00855   push_front()
00856   {
00857     if (_M_start._M_cur != _M_start._M_first) {
00858       _Construct(_M_start._M_cur - 1);
00859       --_M_start._M_cur;
00860     }
00861     else
00862       _M_push_front_aux();
00863   }
00864 
00865 
00866   void
00867   pop_back()
00868   {
00869     if (_M_finish._M_cur != _M_finish._M_first) {
00870       --_M_finish._M_cur;
00871       _Destroy(_M_finish._M_cur);
00872     }
00873     else
00874       _M_pop_back_aux();
00875   }
00876 
00877   void
00878   pop_front()
00879   {
00880     if (_M_start._M_cur != _M_start._M_last - 1) {
00881       _Destroy(_M_start._M_cur);
00882       ++_M_start._M_cur;
00883     }
00884     else 
00885       _M_pop_front_aux();
00886   }
00887 
00888 public:                         // Insert
00889 
00890   iterator
00891   insert(iterator position, const value_type& __x)
00892   {
00893     if (position._M_cur == _M_start._M_cur) {
00894       push_front(__x);
00895       return _M_start;
00896     }
00897     else if (position._M_cur == _M_finish._M_cur) {
00898       push_back(__x);
00899       iterator __tmp = _M_finish;
00900       --__tmp;
00901       return __tmp;
00902     }
00903     else {
00904       return _M_insert_aux(position, __x);
00905     }
00906   }
00907 
00908   iterator
00909   insert(iterator __position)
00910   { return insert(__position, value_type()); }
00911 
00912   void
00913   insert(iterator __pos, size_type __n, const value_type& __x)
00914   { _M_fill_insert(__pos, __n, __x); }
00915 
00916   void
00917   _M_fill_insert(iterator __pos, size_type __n, const value_type& __x); 
00918 
00919   // Check whether it's an integral type.  If so, it's not an iterator.
00920   template<class _InputIterator>
00921     void
00922     insert(iterator __pos, _InputIterator __first, _InputIterator __last)
00923     {
00924       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00925       _M_insert_dispatch(__pos, __first, __last, _Integral());
00926     }
00927 
00928   template<class _Integer>
00929     void
00930     _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, __true_type)
00931     { _M_fill_insert(__pos, static_cast<size_type>(__n), static_cast<value_type>(__x)); }
00932 
00933   template<class _InputIterator>
00934     void
00935     _M_insert_dispatch(iterator __pos,
00936                        _InputIterator __first, _InputIterator __last,
00937                        __false_type)
00938     {
00939       typedef typename iterator_traits<_InputIterator>::iterator_category _IterCategory;
00940       insert(__pos, __first, __last, _IterCategory());
00941     }
00942 
00943   void resize(size_type __new_size, const value_type& __x) {
00944     const size_type __len = size();
00945     if (__new_size < __len) 
00946       erase(_M_start + __new_size, _M_finish);
00947     else
00948       insert(_M_finish, __new_size - __len, __x);
00949   }
00950 
00951   void resize(size_type new_size) { resize(new_size, value_type()); }
00952 
00953 public:                         // Erase
00954   iterator erase(iterator __pos) {
00955     iterator __next = __pos;
00956     ++__next;
00957     size_type __index = __pos - _M_start;
00958     if (__index < (size() >> 1)) {
00959       copy_backward(_M_start, __pos, __next);
00960       pop_front();
00961     }
00962     else {
00963       copy(__next, _M_finish, __pos);
00964       pop_back();
00965     }
00966     return _M_start + __index;
00967   }
00968 
00969   iterator erase(iterator __first, iterator __last);
00970   void clear(); 
00971 
00972 protected:                        // Internal construction/destruction
00973 
00974   void _M_fill_initialize(const value_type& __value);
00975 
00976   template <class _InputIterator>
00977   void _M_range_initialize(_InputIterator __first, _InputIterator __last,
00978                         input_iterator_tag);
00979 
00980   template <class _ForwardIterator>
00981   void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
00982                         forward_iterator_tag);
00983 
00984 protected:                        // Internal push_* and pop_*
00985 
00986   void _M_push_back_aux(const value_type&);
00987   void _M_push_back_aux();
00988   void _M_push_front_aux(const value_type&);
00989   void _M_push_front_aux();
00990   void _M_pop_back_aux();
00991   void _M_pop_front_aux();
00992 
00993 protected:                        // Internal insert functions
00994 
00995   template <class _InputIterator>
00996   void insert(iterator __pos, _InputIterator __first, _InputIterator __last,
00997               input_iterator_tag);
00998 
00999   template <class _ForwardIterator>
01000   void insert(iterator __pos,
01001               _ForwardIterator __first, _ForwardIterator __last,
01002               forward_iterator_tag);
01003 
01004   iterator _M_insert_aux(iterator __pos, const value_type& __x);
01005   iterator _M_insert_aux(iterator __pos);
01006   void _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
01007 
01008   template <class _ForwardIterator>
01009   void _M_insert_aux(iterator __pos, 
01010                      _ForwardIterator __first, _ForwardIterator __last,
01011                      size_type __n);
01012 
01013   iterator _M_reserve_elements_at_front(size_type __n) {
01014     size_type __vacancies = _M_start._M_cur - _M_start._M_first;
01015     if (__n > __vacancies) 
01016       _M_new_elements_at_front(__n - __vacancies);
01017     return _M_start - difference_type(__n);
01018   }
01019 
01020   iterator _M_reserve_elements_at_back(size_type __n) {
01021     size_type __vacancies = (_M_finish._M_last - _M_finish._M_cur) - 1;
01022     if (__n > __vacancies)
01023       _M_new_elements_at_back(__n - __vacancies);
01024     return _M_finish + difference_type(__n);
01025   }
01026 
01027   void _M_new_elements_at_front(size_type __new_elements);
01028   void _M_new_elements_at_back(size_type __new_elements);
01029 
01030 protected:                      // Allocation of _M_map and nodes
01031 
01032   // Makes sure the _M_map has space for new nodes.  Does not actually
01033   //  add the nodes.  Can invalidate _M_map pointers.  (And consequently, 
01034   //  deque iterators.)
01035 
01036   void _M_reserve_map_at_back (size_type __nodes_to_add = 1) {
01037     if (__nodes_to_add + 1 > _M_map_size - (_M_finish._M_node - _M_map))
01038       _M_reallocate_map(__nodes_to_add, false);
01039   }
01040 
01041   void _M_reserve_map_at_front (size_type __nodes_to_add = 1) {
01042     if (__nodes_to_add > size_type(_M_start._M_node - _M_map))
01043       _M_reallocate_map(__nodes_to_add, true);
01044   }
01045 
01046   void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
01047 };
01048 
01049 // Non-inline member functions
01050 
01051 template <class _Tp, class _Alloc>
01052 template <class _InputIter>
01053 void deque<_Tp, _Alloc>
01054   ::_M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag)
01055 {
01056   iterator __cur = begin();
01057   for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
01058     *__cur = *__first;
01059   if (__first == __last)
01060     erase(__cur, end());
01061   else
01062     insert(end(), __first, __last);
01063 }
01064 
01065 template <class _Tp, class _Alloc>
01066 void deque<_Tp, _Alloc>::_M_fill_insert(iterator __pos,
01067                                         size_type __n, const value_type& __x)
01068 {
01069   if (__pos._M_cur == _M_start._M_cur) {
01070     iterator __new_start = _M_reserve_elements_at_front(__n);
01071     try {
01072       uninitialized_fill(__new_start, _M_start, __x);
01073       _M_start = __new_start;
01074     }
01075     catch(...)
01076       {
01077     _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
01078     __throw_exception_again;
01079       }
01080   }
01081   else if (__pos._M_cur == _M_finish._M_cur) {
01082     iterator __new_finish = _M_reserve_elements_at_back(__n);
01083     try {
01084       uninitialized_fill(_M_finish, __new_finish, __x);
01085       _M_finish = __new_finish;
01086     }
01087     catch(...)
01088       {
01089     _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);    
01090     __throw_exception_again;
01091       }
01092   }
01093   else 
01094     _M_insert_aux(__pos, __n, __x);
01095 }
01096 
01097 template <class _Tp, class _Alloc>
01098 typename deque<_Tp,_Alloc>::iterator 
01099 deque<_Tp,_Alloc>::erase(iterator __first, iterator __last)
01100 {
01101   if (__first == _M_start && __last == _M_finish) {
01102     clear();
01103     return _M_finish;
01104   }
01105   else {
01106     difference_type __n = __last - __first;
01107     difference_type __elems_before = __first - _M_start;
01108     if (static_cast<size_type>(__elems_before) < (size() - __n) / 2) {
01109       copy_backward(_M_start, __first, __last);
01110       iterator __new_start = _M_start + __n;
01111       _Destroy(_M_start, __new_start);
01112       _M_destroy_nodes(_M_start._M_node, __new_start._M_node);
01113       _M_start = __new_start;
01114     }
01115     else {
01116       copy(__last, _M_finish, __first);
01117       iterator __new_finish = _M_finish - __n;
01118       _Destroy(__new_finish, _M_finish);
01119       _M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1);
01120       _M_finish = __new_finish;
01121     }
01122     return _M_start + __elems_before;
01123   }
01124 }
01125 
01126 template <class _Tp, class _Alloc> 
01127 void deque<_Tp,_Alloc>::clear()
01128 {
01129   for (_Map_pointer __node = _M_start._M_node + 1;
01130        __node < _M_finish._M_node;
01131        ++__node) {
01132     _Destroy(*__node, *__node + _S_buffer_size());
01133     _M_deallocate_node(*__node);
01134   }
01135 
01136   if (_M_start._M_node != _M_finish._M_node) {
01137     _Destroy(_M_start._M_cur, _M_start._M_last);
01138     _Destroy(_M_finish._M_first, _M_finish._M_cur);
01139     _M_deallocate_node(_M_finish._M_first);
01140   }
01141   else
01142     _Destroy(_M_start._M_cur, _M_finish._M_cur);
01143 
01144   _M_finish = _M_start;
01145 }
01146 
01159 template <class _Tp, class _Alloc>
01160 void deque<_Tp,_Alloc>::_M_fill_initialize(const value_type& __value)
01161 {
01162   _Map_pointer __cur;
01163   try {
01164     for (__cur = _M_start._M_node; __cur < _M_finish._M_node; ++__cur)
01165       uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value);
01166     uninitialized_fill(_M_finish._M_first, _M_finish._M_cur, __value);
01167   }
01168   catch(...)
01169     {
01170       _Destroy(_M_start, iterator(*__cur, __cur));
01171       __throw_exception_again;
01172     }
01173 }
01174 
01187 template <class _Tp, class _Alloc> template <class _InputIterator>
01188 void deque<_Tp,_Alloc>::_M_range_initialize(_InputIterator __first,
01189                                             _InputIterator __last,
01190                                             input_iterator_tag)
01191 {
01192   _M_initialize_map(0);
01193   try {
01194     for ( ; __first != __last; ++__first)
01195       push_back(*__first);
01196   }
01197   catch(...)
01198     {
01199       clear();
01200       __throw_exception_again;
01201     }
01202 }
01203 
01204 template <class _Tp, class _Alloc> template <class _ForwardIterator>
01205 void deque<_Tp,_Alloc>::_M_range_initialize(_ForwardIterator __first,
01206                                             _ForwardIterator __last,
01207                                             forward_iterator_tag)
01208 {
01209   size_type __n = distance(__first, __last);
01210   _M_initialize_map(__n);
01211 
01212   _Map_pointer __cur_node;
01213   try {
01214     for (__cur_node = _M_start._M_node; 
01215          __cur_node < _M_finish._M_node; 
01216          ++__cur_node) {
01217       _ForwardIterator __mid = __first;
01218       advance(__mid, _S_buffer_size());
01219       uninitialized_copy(__first, __mid, *__cur_node);
01220       __first = __mid;
01221     }
01222     uninitialized_copy(__first, __last, _M_finish._M_first);
01223   }
01224   catch(...)
01225     {
01226       _Destroy(_M_start, iterator(*__cur_node, __cur_node));
01227       __throw_exception_again;
01228     }
01229 }
01232 // Called only if _M_finish._M_cur == _M_finish._M_last - 1.
01233 template <class _Tp, class _Alloc>
01234 void
01235 deque<_Tp,_Alloc>::_M_push_back_aux(const value_type& __t)
01236 {
01237   value_type __t_copy = __t;
01238   _M_reserve_map_at_back();
01239   *(_M_finish._M_node + 1) = _M_allocate_node();
01240   try {
01241     _Construct(_M_finish._M_cur, __t_copy);
01242     _M_finish._M_set_node(_M_finish._M_node + 1);
01243     _M_finish._M_cur = _M_finish._M_first;
01244   }
01245   catch(...)
01246     {
01247       _M_deallocate_node(*(_M_finish._M_node + 1));
01248       __throw_exception_again;
01249     }
01250 }
01251 
01252 // Called only if _M_finish._M_cur == _M_finish._M_last - 1.
01253 template <class _Tp, class _Alloc>
01254 void
01255 deque<_Tp,_Alloc>::_M_push_back_aux()
01256 {
01257   _M_reserve_map_at_back();
01258   *(_M_finish._M_node + 1) = _M_allocate_node();
01259   try {
01260     _Construct(_M_finish._M_cur);
01261     _M_finish._M_set_node(_M_finish._M_node + 1);
01262     _M_finish._M_cur = _M_finish._M_first;
01263   }
01264   catch(...)
01265     {
01266       _M_deallocate_node(*(_M_finish._M_node + 1));
01267       __throw_exception_again;
01268     }
01269 }
01270 
01271 // Called only if _M_start._M_cur == _M_start._M_first.
01272 template <class _Tp, class _Alloc>
01273 void
01274 deque<_Tp,_Alloc>::_M_push_front_aux(const value_type& __t)
01275 {
01276   value_type __t_copy = __t;
01277   _M_reserve_map_at_front();
01278   *(_M_start._M_node - 1) = _M_allocate_node();
01279   try {
01280     _M_start._M_set_node(_M_start._M_node - 1);
01281     _M_start._M_cur = _M_start._M_last - 1;
01282     _Construct(_M_start._M_cur, __t_copy);
01283   }
01284   catch(...)
01285     {
01286       ++_M_start;
01287       _M_deallocate_node(*(_M_start._M_node - 1));
01288       __throw_exception_again;
01289     }
01290 } 
01291 
01292 // Called only if _M_start._M_cur == _M_start._M_first.
01293 template <class _Tp, class _Alloc>
01294 void
01295 deque<_Tp,_Alloc>::_M_push_front_aux()
01296 {
01297   _M_reserve_map_at_front();
01298   *(_M_start._M_node - 1) = _M_allocate_node();
01299   try {
01300     _M_start._M_set_node(_M_start._M_node - 1);
01301     _M_start._M_cur = _M_start._M_last - 1;
01302     _Construct(_M_start._M_cur);
01303   }
01304   catch(...)
01305     {
01306       ++_M_start;
01307       _M_deallocate_node(*(_M_start._M_node - 1));
01308       __throw_exception_again;
01309     }
01310 } 
01311 
01312 // Called only if _M_finish._M_cur == _M_finish._M_first.
01313 template <class _Tp, class _Alloc>
01314 void deque<_Tp,_Alloc>::_M_pop_back_aux()
01315 {
01316   _M_deallocate_node(_M_finish._M_first);
01317   _M_finish._M_set_node(_M_finish._M_node - 1);
01318   _M_finish._M_cur = _M_finish._M_last - 1;
01319   _Destroy(_M_finish._M_cur);
01320 }
01321 
01322 // Called only if _M_start._M_cur == _M_start._M_last - 1.  Note that 
01323 // if the deque has at least one element (a precondition for this member 
01324 // function), and if _M_start._M_cur == _M_start._M_last, then the deque 
01325 // must have at least two nodes.
01326 template <class _Tp, class _Alloc>
01327 void deque<_Tp,_Alloc>::_M_pop_front_aux()
01328 {
01329   _Destroy(_M_start._M_cur);
01330   _M_deallocate_node(_M_start._M_first);
01331   _M_start._M_set_node(_M_start._M_node + 1);
01332   _M_start._M_cur = _M_start._M_first;
01333 }      
01334 
01335 template <class _Tp, class _Alloc> template <class _InputIterator>
01336 void deque<_Tp,_Alloc>::insert(iterator __pos,
01337                                _InputIterator __first, _InputIterator __last,
01338                                input_iterator_tag)
01339 {
01340   copy(__first, __last, inserter(*this, __pos));
01341 }
01342 
01343 template <class _Tp, class _Alloc> template <class _ForwardIterator>
01344 void
01345 deque<_Tp,_Alloc>::insert(iterator __pos,
01346                           _ForwardIterator __first, _ForwardIterator __last,
01347                           forward_iterator_tag) {
01348   size_type __n = distance(__first, __last);
01349   if (__pos._M_cur == _M_start._M_cur) {
01350     iterator __new_start = _M_reserve_elements_at_front(__n);
01351     try {
01352       uninitialized_copy(__first, __last, __new_start);
01353       _M_start = __new_start;
01354     }
01355     catch(...)
01356       {
01357     _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
01358     __throw_exception_again;
01359       }
01360   }
01361   else if (__pos._M_cur == _M_finish._M_cur) {
01362     iterator __new_finish = _M_reserve_elements_at_back(__n);
01363     try {
01364       uninitialized_copy(__first, __last, _M_finish);
01365       _M_finish = __new_finish;
01366     }
01367     catch(...)
01368       {
01369     _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
01370     __throw_exception_again;
01371       }
01372   }
01373   else
01374     _M_insert_aux(__pos, __first, __last, __n);
01375 }
01376 
01377 template <class _Tp, class _Alloc>
01378 typename deque<_Tp, _Alloc>::iterator
01379 deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, const value_type& __x)
01380 {
01381   difference_type __index = __pos - _M_start;
01382   value_type __x_copy = __x;
01383   if (static_cast<size_type>(__index) < size() / 2) {
01384     push_front(front());
01385     iterator __front1 = _M_start;
01386     ++__front1;
01387     iterator __front2 = __front1;
01388     ++__front2;
01389     __pos = _M_start + __index;
01390     iterator __pos1 = __pos;
01391     ++__pos1;
01392     copy(__front2, __pos1, __front1);
01393   }
01394   else {
01395     push_back(back());
01396     iterator __back1 = _M_finish;
01397     --__back1;
01398     iterator __back2 = __back1;
01399     --__back2;
01400     __pos = _M_start + __index;
01401     copy_backward(__pos, __back2, __back1);
01402   }
01403   *__pos = __x_copy;
01404   return __pos;
01405 }
01406 
01407 template <class _Tp, class _Alloc>
01408 typename deque<_Tp,_Alloc>::iterator 
01409 deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos)
01410 {
01411   difference_type __index = __pos - _M_start;
01412   if (static_cast<size_type>(__index) < size() / 2) {
01413     push_front(front());
01414     iterator __front1 = _M_start;
01415     ++__front1;
01416     iterator __front2 = __front1;
01417     ++__front2;
01418     __pos = _M_start + __index;
01419     iterator __pos1 = __pos;
01420     ++__pos1;
01421     copy(__front2, __pos1, __front1);
01422   }
01423   else {
01424     push_back(back());
01425     iterator __back1 = _M_finish;
01426     --__back1;
01427     iterator __back2 = __back1;
01428     --__back2;
01429     __pos = _M_start + __index;
01430     copy_backward(__pos, __back2, __back1);
01431   }
01432   *__pos = value_type();
01433   return __pos;
01434 }
01435 
01436 template <class _Tp, class _Alloc>
01437 void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
01438                                       size_type __n,
01439                                       const value_type& __x)
01440 {
01441   const difference_type __elems_before = __pos - _M_start;
01442   size_type __length = this->size();
01443   value_type __x_copy = __x;
01444   if (__elems_before < difference_type(__length / 2)) {
01445     iterator __new_start = _M_reserve_elements_at_front(__n);
01446     iterator __old_start = _M_start;
01447     __pos = _M_start + __elems_before;
01448     try {
01449       if (__elems_before >= difference_type(__n)) {
01450         iterator __start_n = _M_start + difference_type(__n);
01451         uninitialized_copy(_M_start, __start_n, __new_start);
01452         _M_start = __new_start;
01453         copy(__start_n, __pos, __old_start);
01454         fill(__pos - difference_type(__n), __pos, __x_copy);
01455       }
01456       else {
01457         __uninitialized_copy_fill(_M_start, __pos, __new_start, 
01458                                   _M_start, __x_copy);
01459         _M_start = __new_start;
01460         fill(__old_start, __pos, __x_copy);
01461       }
01462     }
01463     catch(...)
01464       { 
01465     _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
01466     __throw_exception_again;
01467       }
01468   }
01469   else {
01470     iterator __new_finish = _M_reserve_elements_at_back(__n);
01471     iterator __old_finish = _M_finish;
01472     const difference_type __elems_after = 
01473       difference_type(__length) - __elems_before;
01474     __pos = _M_finish - __elems_after;
01475     try {
01476       if (__elems_after > difference_type(__n)) {
01477         iterator __finish_n = _M_finish - difference_type(__n);
01478         uninitialized_copy(__finish_n, _M_finish, _M_finish);
01479         _M_finish = __new_finish;
01480         copy_backward(__pos, __finish_n, __old_finish);
01481         fill(__pos, __pos + difference_type(__n), __x_copy);
01482       }
01483       else {
01484         __uninitialized_fill_copy(_M_finish, __pos + difference_type(__n),
01485                                   __x_copy, __pos, _M_finish);
01486         _M_finish = __new_finish;
01487         fill(__pos, __old_finish, __x_copy);
01488       }
01489     }
01490     catch(...)
01491       { 
01492     _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
01493     __throw_exception_again;
01494       }
01495   }
01496 }
01497 
01498 template <class _Tp, class _Alloc> template <class _ForwardIterator>
01499 void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
01500                                       _ForwardIterator __first,
01501                                       _ForwardIterator __last,
01502                                       size_type __n)
01503 {
01504   const difference_type __elemsbefore = __pos - _M_start;
01505   size_type __length = size();
01506   if (static_cast<size_type>(__elemsbefore) < __length / 2) {
01507     iterator __new_start = _M_reserve_elements_at_front(__n);
01508     iterator __old_start = _M_start;
01509     __pos = _M_start + __elemsbefore;
01510     try {
01511       if (__elemsbefore >= difference_type(__n)) {
01512         iterator __start_n = _M_start + difference_type(__n); 
01513         uninitialized_copy(_M_start, __start_n, __new_start);
01514         _M_start = __new_start;
01515         copy(__start_n, __pos, __old_start);
01516         copy(__first, __last, __pos - difference_type(__n));
01517       }
01518       else {
01519         _ForwardIterator __mid = __first;
01520         advance(__mid, difference_type(__n) - __elemsbefore);
01521         __uninitialized_copy_copy(_M_start, __pos, __first, __mid,
01522                                   __new_start);
01523         _M_start = __new_start;
01524         copy(__mid, __last, __old_start);
01525       }
01526     }
01527     catch(...)
01528       {
01529     _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
01530     __throw_exception_again;
01531       }
01532   }
01533   else {
01534     iterator __new_finish = _M_reserve_elements_at_back(__n);
01535     iterator __old_finish = _M_finish;
01536     const difference_type __elemsafter = 
01537       difference_type(__length) - __elemsbefore;
01538     __pos = _M_finish - __elemsafter;
01539     try {
01540       if (__elemsafter > difference_type(__n)) {
01541         iterator __finish_n = _M_finish - difference_type(__n);
01542         uninitialized_copy(__finish_n, _M_finish, _M_finish);
01543         _M_finish = __new_finish;
01544         copy_backward(__pos, __finish_n, __old_finish);
01545         copy(__first, __last, __pos);
01546       }
01547       else {
01548         _ForwardIterator __mid = __first;
01549         advance(__mid, __elemsafter);
01550         __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);
01551         _M_finish = __new_finish;
01552         copy(__first, __mid, __pos);
01553       }
01554     }
01555     catch(...)
01556       {
01557     _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
01558     __throw_exception_again;
01559       }
01560   }
01561 }
01562 
01563 template <class _Tp, class _Alloc>
01564 void deque<_Tp,_Alloc>::_M_new_elements_at_front(size_type __new_elems)
01565 {
01566   size_type __new_nodes
01567       = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
01568   _M_reserve_map_at_front(__new_nodes);
01569   size_type __i;
01570   try {
01571     for (__i = 1; __i <= __new_nodes; ++__i)
01572       *(_M_start._M_node - __i) = _M_allocate_node();
01573   }
01574   catch(...) {
01575     for (size_type __j = 1; __j < __i; ++__j)
01576       _M_deallocate_node(*(_M_start._M_node - __j));      
01577     __throw_exception_again;
01578   }
01579 }
01580 
01581 template <class _Tp, class _Alloc>
01582 void deque<_Tp,_Alloc>::_M_new_elements_at_back(size_type __new_elems)
01583 {
01584   size_type __new_nodes
01585       = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
01586   _M_reserve_map_at_back(__new_nodes);
01587   size_type __i;
01588   try {
01589     for (__i = 1; __i <= __new_nodes; ++__i)
01590       *(_M_finish._M_node + __i) = _M_allocate_node();
01591   }
01592   catch(...) {
01593     for (size_type __j = 1; __j < __i; ++__j)
01594       _M_deallocate_node(*(_M_finish._M_node + __j));      
01595     __throw_exception_again;
01596   }
01597 }
01598 
01599 template <class _Tp, class _Alloc>
01600 void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add,
01601                                           bool __add_at_front)
01602 {
01603   size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1;
01604   size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
01605 
01606   _Map_pointer __new_nstart;
01607   if (_M_map_size > 2 * __new_num_nodes) {
01608     __new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2 
01609                      + (__add_at_front ? __nodes_to_add : 0);
01610     if (__new_nstart < _M_start._M_node)
01611       copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
01612     else
01613       copy_backward(_M_start._M_node, _M_finish._M_node + 1, 
01614                     __new_nstart + __old_num_nodes);
01615   }
01616   else {
01617     size_type __new_map_size = 
01618       _M_map_size + max(_M_map_size, __nodes_to_add) + 2;
01619 
01620     _Map_pointer __new_map = _M_allocate_map(__new_map_size);
01621     __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
01622                          + (__add_at_front ? __nodes_to_add : 0);
01623     copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
01624     _M_deallocate_map(_M_map, _M_map_size);
01625 
01626     _M_map = __new_map;
01627     _M_map_size = __new_map_size;
01628   }
01629 
01630   _M_start._M_set_node(__new_nstart);
01631   _M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
01632 }
01633 
01634 
01635 // Nonmember functions.
01636 
01637 template <class _Tp, class _Alloc>
01638 inline bool operator==(const deque<_Tp, _Alloc>& __x,
01639                        const deque<_Tp, _Alloc>& __y) {
01640   return __x.size() == __y.size() &&
01641          equal(__x.begin(), __x.end(), __y.begin());
01642 }
01643 
01644 template <class _Tp, class _Alloc>
01645 inline bool operator<(const deque<_Tp, _Alloc>& __x,
01646                       const deque<_Tp, _Alloc>& __y) {
01647   return lexicographical_compare(__x.begin(), __x.end(), 
01648                                  __y.begin(), __y.end());
01649 }
01650 
01651 template <class _Tp, class _Alloc>
01652 inline bool operator!=(const deque<_Tp, _Alloc>& __x,
01653                        const deque<_Tp, _Alloc>& __y) {
01654   return !(__x == __y);
01655 }
01656 
01657 template <class _Tp, class _Alloc>
01658 inline bool operator>(const deque<_Tp, _Alloc>& __x,
01659                       const deque<_Tp, _Alloc>& __y) {
01660   return __y < __x;
01661 }
01662 
01663 template <class _Tp, class _Alloc>
01664 inline bool operator<=(const deque<_Tp, _Alloc>& __x,
01665                        const deque<_Tp, _Alloc>& __y) {
01666   return !(__y < __x);
01667 }
01668 template <class _Tp, class _Alloc>
01669 inline bool operator>=(const deque<_Tp, _Alloc>& __x,
01670                        const deque<_Tp, _Alloc>& __y) {
01671   return !(__x < __y);
01672 }
01673 
01674 template <class _Tp, class _Alloc>
01675 inline void swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y) {
01676   __x.swap(__y);
01677 }
01678 
01679 } // namespace std 
01680   
01681 #endif /* __GLIBCPP_INTERNAL_DEQUE_H */
01682 

Generated on Tue Dec 23 12:34:06 2003 for libstdc++-v3 Source by doxygen 1.3.4