libstdc++
stl_deque.h
Go to the documentation of this file.
00001 // Deque implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
00004 // 2011 Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the
00008 // terms of the GNU General Public License as published by the
00009 // Free Software Foundation; either version 3, or (at your option)
00010 // any later version.
00011 
00012 // This library is distributed in the hope that it will be useful,
00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 // GNU General Public License for more details.
00016 
00017 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 /*
00027  *
00028  * Copyright (c) 1994
00029  * Hewlett-Packard Company
00030  *
00031  * Permission to use, copy, modify, distribute and sell this software
00032  * and its documentation for any purpose is hereby granted without fee,
00033  * provided that the above copyright notice appear in all copies and
00034  * that both that copyright notice and this permission notice appear
00035  * in supporting documentation.  Hewlett-Packard Company makes no
00036  * representations about the suitability of this software for any
00037  * purpose.  It is provided "as is" without express or implied warranty.
00038  *
00039  *
00040  * Copyright (c) 1997
00041  * Silicon Graphics Computer Systems, Inc.
00042  *
00043  * Permission to use, copy, modify, distribute and sell this software
00044  * and its documentation for any purpose is hereby granted without fee,
00045  * provided that the above copyright notice appear in all copies and
00046  * that both that copyright notice and this permission notice appear
00047  * in supporting documentation.  Silicon Graphics makes no
00048  * representations about the suitability of this software for any
00049  * purpose.  It is provided "as is" without express or implied warranty.
00050  */
00051 
00052 /** @file bits/stl_deque.h
00053  *  This is an internal header file, included by other library headers.
00054  *  Do not attempt to use it directly. @headername{deque}
00055  */
00056 
00057 #ifndef _STL_DEQUE_H
00058 #define _STL_DEQUE_H 1
00059 
00060 #include <bits/concept_check.h>
00061 #include <bits/stl_iterator_base_types.h>
00062 #include <bits/stl_iterator_base_funcs.h>
00063 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00064 #include <initializer_list>
00065 #endif
00066 
00067 namespace std _GLIBCXX_VISIBILITY(default)
00068 {
00069 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00070 
00071   /**
00072    *  @brief This function controls the size of memory nodes.
00073    *  @param  __size  The size of an element.
00074    *  @return   The number (not byte size) of elements per node.
00075    *
00076    *  This function started off as a compiler kludge from SGI, but
00077    *  seems to be a useful wrapper around a repeated constant
00078    *  expression.  The @b 512 is tunable (and no other code needs to
00079    *  change), but no investigation has been done since inheriting the
00080    *  SGI code.  Touch _GLIBCXX_DEQUE_BUF_SIZE only if you know what
00081    *  you are doing, however: changing it breaks the binary
00082    *  compatibility!!
00083   */
00084 
00085 #ifndef _GLIBCXX_DEQUE_BUF_SIZE
00086 #define _GLIBCXX_DEQUE_BUF_SIZE 512
00087 #endif
00088 
00089   inline size_t
00090   __deque_buf_size(size_t __size)
00091   { return (__size < _GLIBCXX_DEQUE_BUF_SIZE
00092         ? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) : size_t(1)); }
00093 
00094 
00095   /**
00096    *  @brief A deque::iterator.
00097    *
00098    *  Quite a bit of intelligence here.  Much of the functionality of
00099    *  deque is actually passed off to this class.  A deque holds two
00100    *  of these internally, marking its valid range.  Access to
00101    *  elements is done as offsets of either of those two, relying on
00102    *  operator overloading in this class.
00103    *
00104    *  All the functions are op overloads except for _M_set_node.
00105   */
00106   template<typename _Tp, typename _Ref, typename _Ptr>
00107     struct _Deque_iterator
00108     {
00109       typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
00110       typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
00111 
00112       static size_t _S_buffer_size()
00113       { return __deque_buf_size(sizeof(_Tp)); }
00114 
00115       typedef std::random_access_iterator_tag iterator_category;
00116       typedef _Tp                             value_type;
00117       typedef _Ptr                            pointer;
00118       typedef _Ref                            reference;
00119       typedef size_t                          size_type;
00120       typedef ptrdiff_t                       difference_type;
00121       typedef _Tp**                           _Map_pointer;
00122       typedef _Deque_iterator                 _Self;
00123 
00124       _Tp* _M_cur;
00125       _Tp* _M_first;
00126       _Tp* _M_last;
00127       _Map_pointer _M_node;
00128 
00129       _Deque_iterator(_Tp* __x, _Map_pointer __y)
00130       : _M_cur(__x), _M_first(*__y),
00131         _M_last(*__y + _S_buffer_size()), _M_node(__y) { }
00132 
00133       _Deque_iterator()
00134       : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) { }
00135 
00136       _Deque_iterator(const iterator& __x)
00137       : _M_cur(__x._M_cur), _M_first(__x._M_first),
00138         _M_last(__x._M_last), _M_node(__x._M_node) { }
00139 
00140       reference
00141       operator*() const
00142       { return *_M_cur; }
00143 
00144       pointer
00145       operator->() const
00146       { return _M_cur; }
00147 
00148       _Self&
00149       operator++()
00150       {
00151     ++_M_cur;
00152     if (_M_cur == _M_last)
00153       {
00154         _M_set_node(_M_node + 1);
00155         _M_cur = _M_first;
00156       }
00157     return *this;
00158       }
00159 
00160       _Self
00161       operator++(int)
00162       {
00163     _Self __tmp = *this;
00164     ++*this;
00165     return __tmp;
00166       }
00167 
00168       _Self&
00169       operator--()
00170       {
00171     if (_M_cur == _M_first)
00172       {
00173         _M_set_node(_M_node - 1);
00174         _M_cur = _M_last;
00175       }
00176     --_M_cur;
00177     return *this;
00178       }
00179 
00180       _Self
00181       operator--(int)
00182       {
00183     _Self __tmp = *this;
00184     --*this;
00185     return __tmp;
00186       }
00187 
00188       _Self&
00189       operator+=(difference_type __n)
00190       {
00191     const difference_type __offset = __n + (_M_cur - _M_first);
00192     if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
00193       _M_cur += __n;
00194     else
00195       {
00196         const difference_type __node_offset =
00197           __offset > 0 ? __offset / difference_type(_S_buffer_size())
00198                        : -difference_type((-__offset - 1)
00199                           / _S_buffer_size()) - 1;
00200         _M_set_node(_M_node + __node_offset);
00201         _M_cur = _M_first + (__offset - __node_offset
00202                  * difference_type(_S_buffer_size()));
00203       }
00204     return *this;
00205       }
00206 
00207       _Self
00208       operator+(difference_type __n) const
00209       {
00210     _Self __tmp = *this;
00211     return __tmp += __n;
00212       }
00213 
00214       _Self&
00215       operator-=(difference_type __n)
00216       { return *this += -__n; }
00217 
00218       _Self
00219       operator-(difference_type __n) const
00220       {
00221     _Self __tmp = *this;
00222     return __tmp -= __n;
00223       }
00224 
00225       reference
00226       operator[](difference_type __n) const
00227       { return *(*this + __n); }
00228 
00229       /** 
00230        *  Prepares to traverse new_node.  Sets everything except
00231        *  _M_cur, which should therefore be set by the caller
00232        *  immediately afterwards, based on _M_first and _M_last.
00233        */
00234       void
00235       _M_set_node(_Map_pointer __new_node)
00236       {
00237     _M_node = __new_node;
00238     _M_first = *__new_node;
00239     _M_last = _M_first + difference_type(_S_buffer_size());
00240       }
00241     };
00242 
00243   // Note: we also provide overloads whose operands are of the same type in
00244   // order to avoid ambiguous overload resolution when std::rel_ops operators
00245   // are in scope (for additional details, see libstdc++/3628)
00246   template<typename _Tp, typename _Ref, typename _Ptr>
00247     inline bool
00248     operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00249            const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00250     { return __x._M_cur == __y._M_cur; }
00251 
00252   template<typename _Tp, typename _RefL, typename _PtrL,
00253        typename _RefR, typename _PtrR>
00254     inline bool
00255     operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00256            const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00257     { return __x._M_cur == __y._M_cur; }
00258 
00259   template<typename _Tp, typename _Ref, typename _Ptr>
00260     inline bool
00261     operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00262            const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00263     { return !(__x == __y); }
00264 
00265   template<typename _Tp, typename _RefL, typename _PtrL,
00266        typename _RefR, typename _PtrR>
00267     inline bool
00268     operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00269            const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00270     { return !(__x == __y); }
00271 
00272   template<typename _Tp, typename _Ref, typename _Ptr>
00273     inline bool
00274     operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00275           const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00276     { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
00277                                           : (__x._M_node < __y._M_node); }
00278 
00279   template<typename _Tp, typename _RefL, typename _PtrL,
00280        typename _RefR, typename _PtrR>
00281     inline bool
00282     operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00283           const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00284     { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
00285                                       : (__x._M_node < __y._M_node); }
00286 
00287   template<typename _Tp, typename _Ref, typename _Ptr>
00288     inline bool
00289     operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00290           const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00291     { return __y < __x; }
00292 
00293   template<typename _Tp, typename _RefL, typename _PtrL,
00294        typename _RefR, typename _PtrR>
00295     inline bool
00296     operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00297           const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00298     { return __y < __x; }
00299 
00300   template<typename _Tp, typename _Ref, typename _Ptr>
00301     inline bool
00302     operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00303            const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00304     { return !(__y < __x); }
00305 
00306   template<typename _Tp, typename _RefL, typename _PtrL,
00307        typename _RefR, typename _PtrR>
00308     inline bool
00309     operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00310            const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00311     { return !(__y < __x); }
00312 
00313   template<typename _Tp, typename _Ref, typename _Ptr>
00314     inline bool
00315     operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00316            const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00317     { return !(__x < __y); }
00318 
00319   template<typename _Tp, typename _RefL, typename _PtrL,
00320        typename _RefR, typename _PtrR>
00321     inline bool
00322     operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00323            const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00324     { return !(__x < __y); }
00325 
00326   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00327   // According to the resolution of DR179 not only the various comparison
00328   // operators but also operator- must accept mixed iterator/const_iterator
00329   // parameters.
00330   template<typename _Tp, typename _Ref, typename _Ptr>
00331     inline typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type
00332     operator-(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00333           const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00334     {
00335       return typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type
00336     (_Deque_iterator<_Tp, _Ref, _Ptr>::_S_buffer_size())
00337     * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
00338     + (__y._M_last - __y._M_cur);
00339     }
00340 
00341   template<typename _Tp, typename _RefL, typename _PtrL,
00342        typename _RefR, typename _PtrR>
00343     inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
00344     operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00345           const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00346     {
00347       return typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
00348     (_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size())
00349     * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
00350     + (__y._M_last - __y._M_cur);
00351     }
00352 
00353   template<typename _Tp, typename _Ref, typename _Ptr>
00354     inline _Deque_iterator<_Tp, _Ref, _Ptr>
00355     operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
00356     { return __x + __n; }
00357 
00358   template<typename _Tp>
00359     void
00360     fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>&,
00361      const _Deque_iterator<_Tp, _Tp&, _Tp*>&, const _Tp&);
00362 
00363   template<typename _Tp>
00364     _Deque_iterator<_Tp, _Tp&, _Tp*>
00365     copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
00366      _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
00367      _Deque_iterator<_Tp, _Tp&, _Tp*>);
00368 
00369   template<typename _Tp>
00370     inline _Deque_iterator<_Tp, _Tp&, _Tp*>
00371     copy(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
00372      _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
00373      _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
00374     { return std::copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
00375                _Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),
00376                __result); }
00377 
00378   template<typename _Tp>
00379     _Deque_iterator<_Tp, _Tp&, _Tp*>
00380     copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
00381           _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
00382           _Deque_iterator<_Tp, _Tp&, _Tp*>);
00383 
00384   template<typename _Tp>
00385     inline _Deque_iterator<_Tp, _Tp&, _Tp*>
00386     copy_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
00387           _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
00388           _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
00389     { return std::copy_backward(_Deque_iterator<_Tp,
00390                 const _Tp&, const _Tp*>(__first),
00391                 _Deque_iterator<_Tp,
00392                 const _Tp&, const _Tp*>(__last),
00393                 __result); }
00394 
00395 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00396   template<typename _Tp>
00397     _Deque_iterator<_Tp, _Tp&, _Tp*>
00398     move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
00399      _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
00400      _Deque_iterator<_Tp, _Tp&, _Tp*>);
00401 
00402   template<typename _Tp>
00403     inline _Deque_iterator<_Tp, _Tp&, _Tp*>
00404     move(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
00405      _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
00406      _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
00407     { return std::move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
00408                _Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),
00409                __result); }
00410 
00411   template<typename _Tp>
00412     _Deque_iterator<_Tp, _Tp&, _Tp*>
00413     move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
00414           _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
00415           _Deque_iterator<_Tp, _Tp&, _Tp*>);
00416 
00417   template<typename _Tp>
00418     inline _Deque_iterator<_Tp, _Tp&, _Tp*>
00419     move_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
00420           _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
00421           _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
00422     { return std::move_backward(_Deque_iterator<_Tp,
00423                 const _Tp&, const _Tp*>(__first),
00424                 _Deque_iterator<_Tp,
00425                 const _Tp&, const _Tp*>(__last),
00426                 __result); }
00427 #endif
00428 
00429   /**
00430    *  Deque base class.  This class provides the unified face for %deque's
00431    *  allocation.  This class's constructor and destructor allocate and
00432    *  deallocate (but do not initialize) storage.  This makes %exception
00433    *  safety easier.
00434    *
00435    *  Nothing in this class ever constructs or destroys an actual Tp element.
00436    *  (Deque handles that itself.)  Only/All memory management is performed
00437    *  here.
00438   */
00439   template<typename _Tp, typename _Alloc>
00440     class _Deque_base
00441     {
00442     public:
00443       typedef _Alloc                  allocator_type;
00444 
00445       allocator_type
00446       get_allocator() const _GLIBCXX_NOEXCEPT
00447       { return allocator_type(_M_get_Tp_allocator()); }
00448 
00449       typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
00450       typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
00451 
00452       _Deque_base()
00453       : _M_impl()
00454       { _M_initialize_map(0); }
00455 
00456       _Deque_base(size_t __num_elements)
00457       : _M_impl()
00458       { _M_initialize_map(__num_elements); }
00459 
00460       _Deque_base(const allocator_type& __a, size_t __num_elements)
00461       : _M_impl(__a)
00462       { _M_initialize_map(__num_elements); }
00463 
00464       _Deque_base(const allocator_type& __a)
00465       : _M_impl(__a)
00466       { }
00467 
00468 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00469       _Deque_base(_Deque_base&& __x)
00470       : _M_impl(std::move(__x._M_get_Tp_allocator()))
00471       {
00472     _M_initialize_map(0);
00473     if (__x._M_impl._M_map)
00474       {
00475         std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
00476         std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
00477         std::swap(this->_M_impl._M_map, __x._M_impl._M_map);
00478         std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size);
00479       }
00480       }
00481 #endif
00482 
00483       ~_Deque_base();
00484 
00485     protected:
00486       //This struct encapsulates the implementation of the std::deque
00487       //standard container and at the same time makes use of the EBO
00488       //for empty allocators.
00489       typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type;
00490 
00491       typedef typename _Alloc::template rebind<_Tp>::other  _Tp_alloc_type;
00492 
00493       struct _Deque_impl
00494       : public _Tp_alloc_type
00495       {
00496     _Tp** _M_map;
00497     size_t _M_map_size;
00498     iterator _M_start;
00499     iterator _M_finish;
00500 
00501     _Deque_impl()
00502     : _Tp_alloc_type(), _M_map(0), _M_map_size(0),
00503       _M_start(), _M_finish()
00504     { }
00505 
00506     _Deque_impl(const _Tp_alloc_type& __a)
00507     : _Tp_alloc_type(__a), _M_map(0), _M_map_size(0),
00508       _M_start(), _M_finish()
00509     { }
00510 
00511 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00512     _Deque_impl(_Tp_alloc_type&& __a)
00513     : _Tp_alloc_type(std::move(__a)), _M_map(0), _M_map_size(0),
00514       _M_start(), _M_finish()
00515     { }
00516 #endif
00517       };
00518 
00519       _Tp_alloc_type&
00520       _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
00521       { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
00522 
00523       const _Tp_alloc_type&
00524       _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
00525       { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
00526 
00527       _Map_alloc_type
00528       _M_get_map_allocator() const _GLIBCXX_NOEXCEPT
00529       { return _Map_alloc_type(_M_get_Tp_allocator()); }
00530 
00531       _Tp*
00532       _M_allocate_node()
00533       { 
00534     return _M_impl._Tp_alloc_type::allocate(__deque_buf_size(sizeof(_Tp)));
00535       }
00536 
00537       void
00538       _M_deallocate_node(_Tp* __p)
00539       {
00540     _M_impl._Tp_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp)));
00541       }
00542 
00543       _Tp**
00544       _M_allocate_map(size_t __n)
00545       { return _M_get_map_allocator().allocate(__n); }
00546 
00547       void
00548       _M_deallocate_map(_Tp** __p, size_t __n)
00549       { _M_get_map_allocator().deallocate(__p, __n); }
00550 
00551     protected:
00552       void _M_initialize_map(size_t);
00553       void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
00554       void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
00555       enum { _S_initial_map_size = 8 };
00556 
00557       _Deque_impl _M_impl;
00558     };
00559 
00560   template<typename _Tp, typename _Alloc>
00561     _Deque_base<_Tp, _Alloc>::
00562     ~_Deque_base()
00563     {
00564       if (this->_M_impl._M_map)
00565     {
00566       _M_destroy_nodes(this->_M_impl._M_start._M_node,
00567                this->_M_impl._M_finish._M_node + 1);
00568       _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
00569     }
00570     }
00571 
00572   /**
00573    *  @brief Layout storage.
00574    *  @param  __num_elements  The count of T's for which to allocate space
00575    *                        at first.
00576    *  @return   Nothing.
00577    *
00578    *  The initial underlying memory layout is a bit complicated...
00579   */
00580   template<typename _Tp, typename _Alloc>
00581     void
00582     _Deque_base<_Tp, _Alloc>::
00583     _M_initialize_map(size_t __num_elements)
00584     {
00585       const size_t __num_nodes = (__num_elements/ __deque_buf_size(sizeof(_Tp))
00586                   + 1);
00587 
00588       this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,
00589                        size_t(__num_nodes + 2));
00590       this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
00591 
00592       // For "small" maps (needing less than _M_map_size nodes), allocation
00593       // starts in the middle elements and grows outwards.  So nstart may be
00594       // the beginning of _M_map, but for small maps it may be as far in as
00595       // _M_map+3.
00596 
00597       _Tp** __nstart = (this->_M_impl._M_map
00598             + (this->_M_impl._M_map_size - __num_nodes) / 2);
00599       _Tp** __nfinish = __nstart + __num_nodes;
00600 
00601       __try
00602     { _M_create_nodes(__nstart, __nfinish); }
00603       __catch(...)
00604     {
00605       _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
00606       this->_M_impl._M_map = 0;
00607       this->_M_impl._M_map_size = 0;
00608       __throw_exception_again;
00609     }
00610 
00611       this->_M_impl._M_start._M_set_node(__nstart);
00612       this->_M_impl._M_finish._M_set_node(__nfinish - 1);
00613       this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
00614       this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
00615                     + __num_elements
00616                     % __deque_buf_size(sizeof(_Tp)));
00617     }
00618 
00619   template<typename _Tp, typename _Alloc>
00620     void
00621     _Deque_base<_Tp, _Alloc>::
00622     _M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
00623     {
00624       _Tp** __cur;
00625       __try
00626     {
00627       for (__cur = __nstart; __cur < __nfinish; ++__cur)
00628         *__cur = this->_M_allocate_node();
00629     }
00630       __catch(...)
00631     {
00632       _M_destroy_nodes(__nstart, __cur);
00633       __throw_exception_again;
00634     }
00635     }
00636 
00637   template<typename _Tp, typename _Alloc>
00638     void
00639     _Deque_base<_Tp, _Alloc>::
00640     _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish)
00641     {
00642       for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
00643     _M_deallocate_node(*__n);
00644     }
00645 
00646   /**
00647    *  @brief  A standard container using fixed-size memory allocation and
00648    *  constant-time manipulation of elements at either end.
00649    *
00650    *  @ingroup sequences
00651    *
00652    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
00653    *  <a href="tables.html#66">reversible container</a>, and a
00654    *  <a href="tables.html#67">sequence</a>, including the
00655    *  <a href="tables.html#68">optional sequence requirements</a>.
00656    *
00657    *  In previous HP/SGI versions of deque, there was an extra template
00658    *  parameter so users could control the node size.  This extension turned
00659    *  out to violate the C++ standard (it can be detected using template
00660    *  template parameters), and it was removed.
00661    *
00662    *  Here's how a deque<Tp> manages memory.  Each deque has 4 members:
00663    *
00664    *  - Tp**        _M_map
00665    *  - size_t      _M_map_size
00666    *  - iterator    _M_start, _M_finish
00667    *
00668    *  map_size is at least 8.  %map is an array of map_size
00669    *  pointers-to-@a nodes.  (The name %map has nothing to do with the
00670    *  std::map class, and @b nodes should not be confused with
00671    *  std::list's usage of @a node.)
00672    *
00673    *  A @a node has no specific type name as such, but it is referred
00674    *  to as @a node in this file.  It is a simple array-of-Tp.  If Tp
00675    *  is very large, there will be one Tp element per node (i.e., an
00676    *  @a array of one).  For non-huge Tp's, node size is inversely
00677    *  related to Tp size: the larger the Tp, the fewer Tp's will fit
00678    *  in a node.  The goal here is to keep the total size of a node
00679    *  relatively small and constant over different Tp's, to improve
00680    *  allocator efficiency.
00681    *
00682    *  Not every pointer in the %map array will point to a node.  If
00683    *  the initial number of elements in the deque is small, the
00684    *  /middle/ %map pointers will be valid, and the ones at the edges
00685    *  will be unused.  This same situation will arise as the %map
00686    *  grows: available %map pointers, if any, will be on the ends.  As
00687    *  new nodes are created, only a subset of the %map's pointers need
00688    *  to be copied @a outward.
00689    *
00690    *  Class invariants:
00691    * - For any nonsingular iterator i:
00692    *    - i.node points to a member of the %map array.  (Yes, you read that
00693    *      correctly:  i.node does not actually point to a node.)  The member of
00694    *      the %map array is what actually points to the node.
00695    *    - i.first == *(i.node)    (This points to the node (first Tp element).)
00696    *    - i.last  == i.first + node_size
00697    *    - i.cur is a pointer in the range [i.first, i.last).  NOTE:
00698    *      the implication of this is that i.cur is always a dereferenceable
00699    *      pointer, even if i is a past-the-end iterator.
00700    * - Start and Finish are always nonsingular iterators.  NOTE: this
00701    * means that an empty deque must have one node, a deque with <N
00702    * elements (where N is the node buffer size) must have one node, a
00703    * deque with N through (2N-1) elements must have two nodes, etc.
00704    * - For every node other than start.node and finish.node, every
00705    * element in the node is an initialized object.  If start.node ==
00706    * finish.node, then [start.cur, finish.cur) are initialized
00707    * objects, and the elements outside that range are uninitialized
00708    * storage.  Otherwise, [start.cur, start.last) and [finish.first,
00709    * finish.cur) are initialized objects, and [start.first, start.cur)
00710    * and [finish.cur, finish.last) are uninitialized storage.
00711    * - [%map, %map + map_size) is a valid, non-empty range.
00712    * - [start.node, finish.node] is a valid range contained within
00713    *   [%map, %map + map_size).
00714    * - A pointer in the range [%map, %map + map_size) points to an allocated
00715    *   node if and only if the pointer is in the range
00716    *   [start.node, finish.node].
00717    *
00718    *  Here's the magic:  nothing in deque is @b aware of the discontiguous
00719    *  storage!
00720    *
00721    *  The memory setup and layout occurs in the parent, _Base, and the iterator
00722    *  class is entirely responsible for @a leaping from one node to the next.
00723    *  All the implementation routines for deque itself work only through the
00724    *  start and finish iterators.  This keeps the routines simple and sane,
00725    *  and we can use other standard algorithms as well.
00726   */
00727   template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
00728     class deque : protected _Deque_base<_Tp, _Alloc>
00729     {
00730       // concept requirements
00731       typedef typename _Alloc::value_type        _Alloc_value_type;
00732       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00733       __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
00734 
00735       typedef _Deque_base<_Tp, _Alloc>           _Base;
00736       typedef typename _Base::_Tp_alloc_type     _Tp_alloc_type;
00737 
00738     public:
00739       typedef _Tp                                        value_type;
00740       typedef typename _Tp_alloc_type::pointer           pointer;
00741       typedef typename _Tp_alloc_type::const_pointer     const_pointer;
00742       typedef typename _Tp_alloc_type::reference         reference;
00743       typedef typename _Tp_alloc_type::const_reference   const_reference;
00744       typedef typename _Base::iterator                   iterator;
00745       typedef typename _Base::const_iterator             const_iterator;
00746       typedef std::reverse_iterator<const_iterator>      const_reverse_iterator;
00747       typedef std::reverse_iterator<iterator>            reverse_iterator;
00748       typedef size_t                             size_type;
00749       typedef ptrdiff_t                          difference_type;
00750       typedef _Alloc                             allocator_type;
00751 
00752     protected:
00753       typedef pointer*                           _Map_pointer;
00754 
00755       static size_t _S_buffer_size()
00756       { return __deque_buf_size(sizeof(_Tp)); }
00757 
00758       // Functions controlling memory layout, and nothing else.
00759       using _Base::_M_initialize_map;
00760       using _Base::_M_create_nodes;
00761       using _Base::_M_destroy_nodes;
00762       using _Base::_M_allocate_node;
00763       using _Base::_M_deallocate_node;
00764       using _Base::_M_allocate_map;
00765       using _Base::_M_deallocate_map;
00766       using _Base::_M_get_Tp_allocator;
00767 
00768       /** 
00769        *  A total of four data members accumulated down the hierarchy.
00770        *  May be accessed via _M_impl.*
00771        */
00772       using _Base::_M_impl;
00773 
00774     public:
00775       // [23.2.1.1] construct/copy/destroy
00776       // (assign() and get_allocator() are also listed in this section)
00777       /**
00778        *  @brief  Default constructor creates no elements.
00779        */
00780       deque()
00781       : _Base() { }
00782 
00783       /**
00784        *  @brief  Creates a %deque with no elements.
00785        *  @param  __a  An allocator object.
00786        */
00787       explicit
00788       deque(const allocator_type& __a)
00789       : _Base(__a, 0) { }
00790 
00791 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00792       /**
00793        *  @brief  Creates a %deque with default constructed elements.
00794        *  @param  __n  The number of elements to initially create.
00795        *
00796        *  This constructor fills the %deque with @a n default
00797        *  constructed elements.
00798        */
00799       explicit
00800       deque(size_type __n)
00801       : _Base(__n)
00802       { _M_default_initialize(); }
00803 
00804       /**
00805        *  @brief  Creates a %deque with copies of an exemplar element.
00806        *  @param  __n  The number of elements to initially create.
00807        *  @param  __value  An element to copy.
00808        *  @param  __a  An allocator.
00809        *
00810        *  This constructor fills the %deque with @a __n copies of @a __value.
00811        */
00812       deque(size_type __n, const value_type& __value,
00813         const allocator_type& __a = allocator_type())
00814       : _Base(__a, __n)
00815       { _M_fill_initialize(__value); }
00816 #else
00817       /**
00818        *  @brief  Creates a %deque with copies of an exemplar element.
00819        *  @param  __n  The number of elements to initially create.
00820        *  @param  __value  An element to copy.
00821        *  @param  __a  An allocator.
00822        *
00823        *  This constructor fills the %deque with @a __n copies of @a __value.
00824        */
00825       explicit
00826       deque(size_type __n, const value_type& __value = value_type(),
00827         const allocator_type& __a = allocator_type())
00828       : _Base(__a, __n)
00829       { _M_fill_initialize(__value); }
00830 #endif
00831 
00832       /**
00833        *  @brief  %Deque copy constructor.
00834        *  @param  __x  A %deque of identical element and allocator types.
00835        *
00836        *  The newly-created %deque uses a copy of the allocation object used
00837        *  by @a __x.
00838        */
00839       deque(const deque& __x)
00840       : _Base(__x._M_get_Tp_allocator(), __x.size())
00841       { std::__uninitialized_copy_a(__x.begin(), __x.end(), 
00842                     this->_M_impl._M_start,
00843                     _M_get_Tp_allocator()); }
00844 
00845 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00846       /**
00847        *  @brief  %Deque move constructor.
00848        *  @param  __x  A %deque of identical element and allocator types.
00849        *
00850        *  The newly-created %deque contains the exact contents of @a __x.
00851        *  The contents of @a __x are a valid, but unspecified %deque.
00852        */
00853       deque(deque&& __x)
00854       : _Base(std::move(__x)) { }
00855 
00856       /**
00857        *  @brief  Builds a %deque from an initializer list.
00858        *  @param  __l  An initializer_list.
00859        *  @param  __a  An allocator object.
00860        *
00861        *  Create a %deque consisting of copies of the elements in the
00862        *  initializer_list @a __l.
00863        *
00864        *  This will call the element type's copy constructor N times
00865        *  (where N is __l.size()) and do no memory reallocation.
00866        */
00867       deque(initializer_list<value_type> __l,
00868         const allocator_type& __a = allocator_type())
00869       : _Base(__a)
00870       {
00871     _M_range_initialize(__l.begin(), __l.end(),
00872                 random_access_iterator_tag());
00873       }
00874 #endif
00875 
00876       /**
00877        *  @brief  Builds a %deque from a range.
00878        *  @param  __first  An input iterator.
00879        *  @param  __last  An input iterator.
00880        *  @param  __a  An allocator object.
00881        *
00882        *  Create a %deque consisting of copies of the elements from [__first,
00883        *  __last).
00884        *
00885        *  If the iterators are forward, bidirectional, or random-access, then
00886        *  this will call the elements' copy constructor N times (where N is
00887        *  distance(__first,__last)) and do no memory reallocation.  But if only
00888        *  input iterators are used, then this will do at most 2N calls to the
00889        *  copy constructor, and logN memory reallocations.
00890        */
00891       template<typename _InputIterator>
00892         deque(_InputIterator __first, _InputIterator __last,
00893           const allocator_type& __a = allocator_type())
00894     : _Base(__a)
00895         {
00896       // Check whether it's an integral type.  If so, it's not an iterator.
00897       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00898       _M_initialize_dispatch(__first, __last, _Integral());
00899     }
00900 
00901       /**
00902        *  The dtor only erases the elements, and note that if the elements
00903        *  themselves are pointers, the pointed-to memory is not touched in any
00904        *  way.  Managing the pointer is the user's responsibility.
00905        */
00906       ~deque() _GLIBCXX_NOEXCEPT
00907       { _M_destroy_data(begin(), end(), _M_get_Tp_allocator()); }
00908 
00909       /**
00910        *  @brief  %Deque assignment operator.
00911        *  @param  __x  A %deque of identical element and allocator types.
00912        *
00913        *  All the elements of @a x are copied, but unlike the copy constructor,
00914        *  the allocator object is not copied.
00915        */
00916       deque&
00917       operator=(const deque& __x);
00918 
00919 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00920       /**
00921        *  @brief  %Deque move assignment operator.
00922        *  @param  __x  A %deque of identical element and allocator types.
00923        *
00924        *  The contents of @a __x are moved into this deque (without copying).
00925        *  @a __x is a valid, but unspecified %deque.
00926        */
00927       deque&
00928       operator=(deque&& __x)
00929       {
00930     // NB: DR 1204.
00931     // NB: DR 675.
00932     this->clear();
00933     this->swap(__x);
00934     return *this;
00935       }
00936 
00937       /**
00938        *  @brief  Assigns an initializer list to a %deque.
00939        *  @param  __l  An initializer_list.
00940        *
00941        *  This function fills a %deque with copies of the elements in the
00942        *  initializer_list @a __l.
00943        *
00944        *  Note that the assignment completely changes the %deque and that the
00945        *  resulting %deque's size is the same as the number of elements
00946        *  assigned.  Old data may be lost.
00947        */
00948       deque&
00949       operator=(initializer_list<value_type> __l)
00950       {
00951     this->assign(__l.begin(), __l.end());
00952     return *this;
00953       }
00954 #endif
00955 
00956       /**
00957        *  @brief  Assigns a given value to a %deque.
00958        *  @param  __n  Number of elements to be assigned.
00959        *  @param  __val  Value to be assigned.
00960        *
00961        *  This function fills a %deque with @a n copies of the given
00962        *  value.  Note that the assignment completely changes the
00963        *  %deque and that the resulting %deque's size is the same as
00964        *  the number of elements assigned.  Old data may be lost.
00965        */
00966       void
00967       assign(size_type __n, const value_type& __val)
00968       { _M_fill_assign(__n, __val); }
00969 
00970       /**
00971        *  @brief  Assigns a range to a %deque.
00972        *  @param  __first  An input iterator.
00973        *  @param  __last   An input iterator.
00974        *
00975        *  This function fills a %deque with copies of the elements in the
00976        *  range [__first,__last).
00977        *
00978        *  Note that the assignment completely changes the %deque and that the
00979        *  resulting %deque's size is the same as the number of elements
00980        *  assigned.  Old data may be lost.
00981        */
00982       template<typename _InputIterator>
00983         void
00984         assign(_InputIterator __first, _InputIterator __last)
00985         {
00986       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00987       _M_assign_dispatch(__first, __last, _Integral());
00988     }
00989 
00990 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00991       /**
00992        *  @brief  Assigns an initializer list to a %deque.
00993        *  @param  __l  An initializer_list.
00994        *
00995        *  This function fills a %deque with copies of the elements in the
00996        *  initializer_list @a __l.
00997        *
00998        *  Note that the assignment completely changes the %deque and that the
00999        *  resulting %deque's size is the same as the number of elements
01000        *  assigned.  Old data may be lost.
01001        */
01002       void
01003       assign(initializer_list<value_type> __l)
01004       { this->assign(__l.begin(), __l.end()); }
01005 #endif
01006 
01007       /// Get a copy of the memory allocation object.
01008       allocator_type
01009       get_allocator() const _GLIBCXX_NOEXCEPT
01010       { return _Base::get_allocator(); }
01011 
01012       // iterators
01013       /**
01014        *  Returns a read/write iterator that points to the first element in the
01015        *  %deque.  Iteration is done in ordinary element order.
01016        */
01017       iterator
01018       begin() _GLIBCXX_NOEXCEPT
01019       { return this->_M_impl._M_start; }
01020 
01021       /**
01022        *  Returns a read-only (constant) iterator that points to the first
01023        *  element in the %deque.  Iteration is done in ordinary element order.
01024        */
01025       const_iterator
01026       begin() const _GLIBCXX_NOEXCEPT
01027       { return this->_M_impl._M_start; }
01028 
01029       /**
01030        *  Returns a read/write iterator that points one past the last
01031        *  element in the %deque.  Iteration is done in ordinary
01032        *  element order.
01033        */
01034       iterator
01035       end() _GLIBCXX_NOEXCEPT
01036       { return this->_M_impl._M_finish; }
01037 
01038       /**
01039        *  Returns a read-only (constant) iterator that points one past
01040        *  the last element in the %deque.  Iteration is done in
01041        *  ordinary element order.
01042        */
01043       const_iterator
01044       end() const _GLIBCXX_NOEXCEPT
01045       { return this->_M_impl._M_finish; }
01046 
01047       /**
01048        *  Returns a read/write reverse iterator that points to the
01049        *  last element in the %deque.  Iteration is done in reverse
01050        *  element order.
01051        */
01052       reverse_iterator
01053       rbegin() _GLIBCXX_NOEXCEPT
01054       { return reverse_iterator(this->_M_impl._M_finish); }
01055 
01056       /**
01057        *  Returns a read-only (constant) reverse iterator that points
01058        *  to the last element in the %deque.  Iteration is done in
01059        *  reverse element order.
01060        */
01061       const_reverse_iterator
01062       rbegin() const _GLIBCXX_NOEXCEPT
01063       { return const_reverse_iterator(this->_M_impl._M_finish); }
01064 
01065       /**
01066        *  Returns a read/write reverse iterator that points to one
01067        *  before the first element in the %deque.  Iteration is done
01068        *  in reverse element order.
01069        */
01070       reverse_iterator
01071       rend() _GLIBCXX_NOEXCEPT
01072       { return reverse_iterator(this->_M_impl._M_start); }
01073 
01074       /**
01075        *  Returns a read-only (constant) reverse iterator that points
01076        *  to one before the first element in the %deque.  Iteration is
01077        *  done in reverse element order.
01078        */
01079       const_reverse_iterator
01080       rend() const _GLIBCXX_NOEXCEPT
01081       { return const_reverse_iterator(this->_M_impl._M_start); }
01082 
01083 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01084       /**
01085        *  Returns a read-only (constant) iterator that points to the first
01086        *  element in the %deque.  Iteration is done in ordinary element order.
01087        */
01088       const_iterator
01089       cbegin() const noexcept
01090       { return this->_M_impl._M_start; }
01091 
01092       /**
01093        *  Returns a read-only (constant) iterator that points one past
01094        *  the last element in the %deque.  Iteration is done in
01095        *  ordinary element order.
01096        */
01097       const_iterator
01098       cend() const noexcept
01099       { return this->_M_impl._M_finish; }
01100 
01101       /**
01102        *  Returns a read-only (constant) reverse iterator that points
01103        *  to the last element in the %deque.  Iteration is done in
01104        *  reverse element order.
01105        */
01106       const_reverse_iterator
01107       crbegin() const noexcept
01108       { return const_reverse_iterator(this->_M_impl._M_finish); }
01109 
01110       /**
01111        *  Returns a read-only (constant) reverse iterator that points
01112        *  to one before the first element in the %deque.  Iteration is
01113        *  done in reverse element order.
01114        */
01115       const_reverse_iterator
01116       crend() const noexcept
01117       { return const_reverse_iterator(this->_M_impl._M_start); }
01118 #endif
01119 
01120       // [23.2.1.2] capacity
01121       /**  Returns the number of elements in the %deque.  */
01122       size_type
01123       size() const _GLIBCXX_NOEXCEPT
01124       { return this->_M_impl._M_finish - this->_M_impl._M_start; }
01125 
01126       /**  Returns the size() of the largest possible %deque.  */
01127       size_type
01128       max_size() const _GLIBCXX_NOEXCEPT
01129       { return _M_get_Tp_allocator().max_size(); }
01130 
01131 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01132       /**
01133        *  @brief  Resizes the %deque to the specified number of elements.
01134        *  @param  __new_size  Number of elements the %deque should contain.
01135        *
01136        *  This function will %resize the %deque to the specified
01137        *  number of elements.  If the number is smaller than the
01138        *  %deque's current size the %deque is truncated, otherwise
01139        *  default constructed elements are appended.
01140        */
01141       void
01142       resize(size_type __new_size)
01143       {
01144     const size_type __len = size();
01145     if (__new_size > __len)
01146       _M_default_append(__new_size - __len);
01147     else if (__new_size < __len)
01148       _M_erase_at_end(this->_M_impl._M_start
01149               + difference_type(__new_size));
01150       }
01151 
01152       /**
01153        *  @brief  Resizes the %deque to the specified number of elements.
01154        *  @param  __new_size  Number of elements the %deque should contain.
01155        *  @param  __x  Data with which new elements should be populated.
01156        *
01157        *  This function will %resize the %deque to the specified
01158        *  number of elements.  If the number is smaller than the
01159        *  %deque's current size the %deque is truncated, otherwise the
01160        *  %deque is extended and new elements are populated with given
01161        *  data.
01162        */
01163       void
01164       resize(size_type __new_size, const value_type& __x)
01165       {
01166     const size_type __len = size();
01167     if (__new_size > __len)
01168       insert(this->_M_impl._M_finish, __new_size - __len, __x);
01169     else if (__new_size < __len)
01170       _M_erase_at_end(this->_M_impl._M_start
01171               + difference_type(__new_size));
01172       }
01173 #else
01174       /**
01175        *  @brief  Resizes the %deque to the specified number of elements.
01176        *  @param  __new_size  Number of elements the %deque should contain.
01177        *  @param  __x  Data with which new elements should be populated.
01178        *
01179        *  This function will %resize the %deque to the specified
01180        *  number of elements.  If the number is smaller than the
01181        *  %deque's current size the %deque is truncated, otherwise the
01182        *  %deque is extended and new elements are populated with given
01183        *  data.
01184        */
01185       void
01186       resize(size_type __new_size, value_type __x = value_type())
01187       {
01188     const size_type __len = size();
01189     if (__new_size > __len)
01190       insert(this->_M_impl._M_finish, __new_size - __len, __x);
01191     else if (__new_size < __len)
01192       _M_erase_at_end(this->_M_impl._M_start
01193               + difference_type(__new_size));
01194       }
01195 #endif
01196 
01197 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01198       /**  A non-binding request to reduce memory use.  */
01199       void
01200       shrink_to_fit()
01201       { _M_shrink_to_fit(); }
01202 #endif
01203 
01204       /**
01205        *  Returns true if the %deque is empty.  (Thus begin() would
01206        *  equal end().)
01207        */
01208       bool
01209       empty() const _GLIBCXX_NOEXCEPT
01210       { return this->_M_impl._M_finish == this->_M_impl._M_start; }
01211 
01212       // element access
01213       /**
01214        *  @brief Subscript access to the data contained in the %deque.
01215        *  @param __n The index of the element for which data should be
01216        *  accessed.
01217        *  @return  Read/write reference to data.
01218        *
01219        *  This operator allows for easy, array-style, data access.
01220        *  Note that data access with this operator is unchecked and
01221        *  out_of_range lookups are not defined. (For checked lookups
01222        *  see at().)
01223        */
01224       reference
01225       operator[](size_type __n)
01226       { return this->_M_impl._M_start[difference_type(__n)]; }
01227 
01228       /**
01229        *  @brief Subscript access to the data contained in the %deque.
01230        *  @param __n The index of the element for which data should be
01231        *  accessed.
01232        *  @return  Read-only (constant) reference to data.
01233        *
01234        *  This operator allows for easy, array-style, data access.
01235        *  Note that data access with this operator is unchecked and
01236        *  out_of_range lookups are not defined. (For checked lookups
01237        *  see at().)
01238        */
01239       const_reference
01240       operator[](size_type __n) const
01241       { return this->_M_impl._M_start[difference_type(__n)]; }
01242 
01243     protected:
01244       /// Safety check used only from at().
01245       void
01246       _M_range_check(size_type __n) const
01247       {
01248     if (__n >= this->size())
01249       __throw_out_of_range(__N("deque::_M_range_check"));
01250       }
01251 
01252     public:
01253       /**
01254        *  @brief  Provides access to the data contained in the %deque.
01255        *  @param __n The index of the element for which data should be
01256        *  accessed.
01257        *  @return  Read/write reference to data.
01258        *  @throw  std::out_of_range  If @a __n is an invalid index.
01259        *
01260        *  This function provides for safer data access.  The parameter
01261        *  is first checked that it is in the range of the deque.  The
01262        *  function throws out_of_range if the check fails.
01263        */
01264       reference
01265       at(size_type __n)
01266       {
01267     _M_range_check(__n);
01268     return (*this)[__n];
01269       }
01270 
01271       /**
01272        *  @brief  Provides access to the data contained in the %deque.
01273        *  @param __n The index of the element for which data should be
01274        *  accessed.
01275        *  @return  Read-only (constant) reference to data.
01276        *  @throw  std::out_of_range  If @a __n is an invalid index.
01277        *
01278        *  This function provides for safer data access.  The parameter is first
01279        *  checked that it is in the range of the deque.  The function throws
01280        *  out_of_range if the check fails.
01281        */
01282       const_reference
01283       at(size_type __n) const
01284       {
01285     _M_range_check(__n);
01286     return (*this)[__n];
01287       }
01288 
01289       /**
01290        *  Returns a read/write reference to the data at the first
01291        *  element of the %deque.
01292        */
01293       reference
01294       front()
01295       { return *begin(); }
01296 
01297       /**
01298        *  Returns a read-only (constant) reference to the data at the first
01299        *  element of the %deque.
01300        */
01301       const_reference
01302       front() const
01303       { return *begin(); }
01304 
01305       /**
01306        *  Returns a read/write reference to the data at the last element of the
01307        *  %deque.
01308        */
01309       reference
01310       back()
01311       {
01312     iterator __tmp = end();
01313     --__tmp;
01314     return *__tmp;
01315       }
01316 
01317       /**
01318        *  Returns a read-only (constant) reference to the data at the last
01319        *  element of the %deque.
01320        */
01321       const_reference
01322       back() const
01323       {
01324     const_iterator __tmp = end();
01325     --__tmp;
01326     return *__tmp;
01327       }
01328 
01329       // [23.2.1.2] modifiers
01330       /**
01331        *  @brief  Add data to the front of the %deque.
01332        *  @param  __x  Data to be added.
01333        *
01334        *  This is a typical stack operation.  The function creates an
01335        *  element at the front of the %deque and assigns the given
01336        *  data to it.  Due to the nature of a %deque this operation
01337        *  can be done in constant time.
01338        */
01339       void
01340       push_front(const value_type& __x)
01341       {
01342     if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
01343       {
01344         this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1, __x);
01345         --this->_M_impl._M_start._M_cur;
01346       }
01347     else
01348       _M_push_front_aux(__x);
01349       }
01350 
01351 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01352       void
01353       push_front(value_type&& __x)
01354       { emplace_front(std::move(__x)); }
01355 
01356       template<typename... _Args>
01357         void
01358         emplace_front(_Args&&... __args);
01359 #endif
01360 
01361       /**
01362        *  @brief  Add data to the end of the %deque.
01363        *  @param  __x  Data to be added.
01364        *
01365        *  This is a typical stack operation.  The function creates an
01366        *  element at the end of the %deque and assigns the given data
01367        *  to it.  Due to the nature of a %deque this operation can be
01368        *  done in constant time.
01369        */
01370       void
01371       push_back(const value_type& __x)
01372       {
01373     if (this->_M_impl._M_finish._M_cur
01374         != this->_M_impl._M_finish._M_last - 1)
01375       {
01376         this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __x);
01377         ++this->_M_impl._M_finish._M_cur;
01378       }
01379     else
01380       _M_push_back_aux(__x);
01381       }
01382 
01383 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01384       void
01385       push_back(value_type&& __x)
01386       { emplace_back(std::move(__x)); }
01387 
01388       template<typename... _Args>
01389         void
01390         emplace_back(_Args&&... __args);
01391 #endif
01392 
01393       /**
01394        *  @brief  Removes first element.
01395        *
01396        *  This is a typical stack operation.  It shrinks the %deque by one.
01397        *
01398        *  Note that no data is returned, and if the first element's data is
01399        *  needed, it should be retrieved before pop_front() is called.
01400        */
01401       void
01402       pop_front()
01403       {
01404     if (this->_M_impl._M_start._M_cur
01405         != this->_M_impl._M_start._M_last - 1)
01406       {
01407         this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
01408         ++this->_M_impl._M_start._M_cur;
01409       }
01410     else
01411       _M_pop_front_aux();
01412       }
01413 
01414       /**
01415        *  @brief  Removes last element.
01416        *
01417        *  This is a typical stack operation.  It shrinks the %deque by one.
01418        *
01419        *  Note that no data is returned, and if the last element's data is
01420        *  needed, it should be retrieved before pop_back() is called.
01421        */
01422       void
01423       pop_back()
01424       {
01425     if (this->_M_impl._M_finish._M_cur
01426         != this->_M_impl._M_finish._M_first)
01427       {
01428         --this->_M_impl._M_finish._M_cur;
01429         this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
01430       }
01431     else
01432       _M_pop_back_aux();
01433       }
01434 
01435 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01436       /**
01437        *  @brief  Inserts an object in %deque before specified iterator.
01438        *  @param  __position  An iterator into the %deque.
01439        *  @param  __args  Arguments.
01440        *  @return  An iterator that points to the inserted data.
01441        *
01442        *  This function will insert an object of type T constructed
01443        *  with T(std::forward<Args>(args)...) before the specified location.
01444        */
01445       template<typename... _Args>
01446         iterator
01447         emplace(iterator __position, _Args&&... __args);
01448 #endif
01449 
01450       /**
01451        *  @brief  Inserts given value into %deque before specified iterator.
01452        *  @param  __position  An iterator into the %deque.
01453        *  @param  __x  Data to be inserted.
01454        *  @return  An iterator that points to the inserted data.
01455        *
01456        *  This function will insert a copy of the given value before the
01457        *  specified location.
01458        */
01459       iterator
01460       insert(iterator __position, const value_type& __x);
01461 
01462 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01463       /**
01464        *  @brief  Inserts given rvalue into %deque before specified iterator.
01465        *  @param  __position  An iterator into the %deque.
01466        *  @param  __x  Data to be inserted.
01467        *  @return  An iterator that points to the inserted data.
01468        *
01469        *  This function will insert a copy of the given rvalue before the
01470        *  specified location.
01471        */
01472       iterator
01473       insert(iterator __position, value_type&& __x)
01474       { return emplace(__position, std::move(__x)); }
01475 
01476       /**
01477        *  @brief  Inserts an initializer list into the %deque.
01478        *  @param  __p  An iterator into the %deque.
01479        *  @param  __l  An initializer_list.
01480        *
01481        *  This function will insert copies of the data in the
01482        *  initializer_list @a __l into the %deque before the location
01483        *  specified by @a __p.  This is known as <em>list insert</em>.
01484        */
01485       void
01486       insert(iterator __p, initializer_list<value_type> __l)
01487       { this->insert(__p, __l.begin(), __l.end()); }
01488 #endif
01489 
01490       /**
01491        *  @brief  Inserts a number of copies of given data into the %deque.
01492        *  @param  __position  An iterator into the %deque.
01493        *  @param  __n  Number of elements to be inserted.
01494        *  @param  __x  Data to be inserted.
01495        *
01496        *  This function will insert a specified number of copies of the given
01497        *  data before the location specified by @a __position.
01498        */
01499       void
01500       insert(iterator __position, size_type __n, const value_type& __x)
01501       { _M_fill_insert(__position, __n, __x); }
01502 
01503       /**
01504        *  @brief  Inserts a range into the %deque.
01505        *  @param  __position  An iterator into the %deque.
01506        *  @param  __first  An input iterator.
01507        *  @param  __last   An input iterator.
01508        *
01509        *  This function will insert copies of the data in the range
01510        *  [__first,__last) into the %deque before the location specified
01511        *  by @a __position.  This is known as <em>range insert</em>.
01512        */
01513       template<typename _InputIterator>
01514         void
01515         insert(iterator __position, _InputIterator __first,
01516            _InputIterator __last)
01517         {
01518       // Check whether it's an integral type.  If so, it's not an iterator.
01519       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
01520       _M_insert_dispatch(__position, __first, __last, _Integral());
01521     }
01522 
01523       /**
01524        *  @brief  Remove element at given position.
01525        *  @param  __position  Iterator pointing to element to be erased.
01526        *  @return  An iterator pointing to the next element (or end()).
01527        *
01528        *  This function will erase the element at the given position and thus
01529        *  shorten the %deque by one.
01530        *
01531        *  The user is cautioned that
01532        *  this function only erases the element, and that if the element is
01533        *  itself a pointer, the pointed-to memory is not touched in any way.
01534        *  Managing the pointer is the user's responsibility.
01535        */
01536       iterator
01537       erase(iterator __position);
01538 
01539       /**
01540        *  @brief  Remove a range of elements.
01541        *  @param  __first  Iterator pointing to the first element to be erased.
01542        *  @param  __last  Iterator pointing to one past the last element to be
01543        *                erased.
01544        *  @return  An iterator pointing to the element pointed to by @a last
01545        *           prior to erasing (or end()).
01546        *
01547        *  This function will erase the elements in the range
01548        *  [__first,__last) and shorten the %deque accordingly.
01549        *
01550        *  The user is cautioned that
01551        *  this function only erases the elements, and that if the elements
01552        *  themselves are pointers, the pointed-to memory is not touched in any
01553        *  way.  Managing the pointer is the user's responsibility.
01554        */
01555       iterator
01556       erase(iterator __first, iterator __last);
01557 
01558       /**
01559        *  @brief  Swaps data with another %deque.
01560        *  @param  __x  A %deque of the same element and allocator types.
01561        *
01562        *  This exchanges the elements between two deques in constant time.
01563        *  (Four pointers, so it should be quite fast.)
01564        *  Note that the global std::swap() function is specialized such that
01565        *  std::swap(d1,d2) will feed to this function.
01566        */
01567       void
01568       swap(deque& __x)
01569       {
01570     std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
01571     std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
01572     std::swap(this->_M_impl._M_map, __x._M_impl._M_map);
01573     std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size);
01574 
01575     // _GLIBCXX_RESOLVE_LIB_DEFECTS
01576     // 431. Swapping containers with unequal allocators.
01577     std::__alloc_swap<_Tp_alloc_type>::_S_do_it(_M_get_Tp_allocator(),
01578                             __x._M_get_Tp_allocator());
01579       }
01580 
01581       /**
01582        *  Erases all the elements.  Note that this function only erases the
01583        *  elements, and that if the elements themselves are pointers, the
01584        *  pointed-to memory is not touched in any way.  Managing the pointer is
01585        *  the user's responsibility.
01586        */
01587       void
01588       clear() _GLIBCXX_NOEXCEPT
01589       { _M_erase_at_end(begin()); }
01590 
01591     protected:
01592       // Internal constructor functions follow.
01593 
01594       // called by the range constructor to implement [23.1.1]/9
01595 
01596       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01597       // 438. Ambiguity in the "do the right thing" clause
01598       template<typename _Integer>
01599         void
01600         _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
01601         {
01602       _M_initialize_map(static_cast<size_type>(__n));
01603       _M_fill_initialize(__x);
01604     }
01605 
01606       // called by the range constructor to implement [23.1.1]/9
01607       template<typename _InputIterator>
01608         void
01609         _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
01610                    __false_type)
01611         {
01612       typedef typename std::iterator_traits<_InputIterator>::
01613         iterator_category _IterCategory;
01614       _M_range_initialize(__first, __last, _IterCategory());
01615     }
01616 
01617       // called by the second initialize_dispatch above
01618       //@{
01619       /**
01620        *  @brief Fills the deque with whatever is in [first,last).
01621        *  @param  __first  An input iterator.
01622        *  @param  __last  An input iterator.
01623        *  @return   Nothing.
01624        *
01625        *  If the iterators are actually forward iterators (or better), then the
01626        *  memory layout can be done all at once.  Else we move forward using
01627        *  push_back on each value from the iterator.
01628        */
01629       template<typename _InputIterator>
01630         void
01631         _M_range_initialize(_InputIterator __first, _InputIterator __last,
01632                 std::input_iterator_tag);
01633 
01634       // called by the second initialize_dispatch above
01635       template<typename _ForwardIterator>
01636         void
01637         _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
01638                 std::forward_iterator_tag);
01639       //@}
01640 
01641       /**
01642        *  @brief Fills the %deque with copies of value.
01643        *  @param  __value  Initial value.
01644        *  @return   Nothing.
01645        *  @pre _M_start and _M_finish have already been initialized,
01646        *  but none of the %deque's elements have yet been constructed.
01647        *
01648        *  This function is called only when the user provides an explicit size
01649        *  (with or without an explicit exemplar value).
01650        */
01651       void
01652       _M_fill_initialize(const value_type& __value);
01653 
01654 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01655       // called by deque(n).
01656       void
01657       _M_default_initialize();
01658 #endif
01659 
01660       // Internal assign functions follow.  The *_aux functions do the actual
01661       // assignment work for the range versions.
01662 
01663       // called by the range assign to implement [23.1.1]/9
01664 
01665       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01666       // 438. Ambiguity in the "do the right thing" clause
01667       template<typename _Integer>
01668         void
01669         _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
01670         { _M_fill_assign(__n, __val); }
01671 
01672       // called by the range assign to implement [23.1.1]/9
01673       template<typename _InputIterator>
01674         void
01675         _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
01676                __false_type)
01677         {
01678       typedef typename std::iterator_traits<_InputIterator>::
01679         iterator_category _IterCategory;
01680       _M_assign_aux(__first, __last, _IterCategory());
01681     }
01682 
01683       // called by the second assign_dispatch above
01684       template<typename _InputIterator>
01685         void
01686         _M_assign_aux(_InputIterator __first, _InputIterator __last,
01687               std::input_iterator_tag);
01688 
01689       // called by the second assign_dispatch above
01690       template<typename _ForwardIterator>
01691         void
01692         _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
01693               std::forward_iterator_tag)
01694         {
01695       const size_type __len = std::distance(__first, __last);
01696       if (__len > size())
01697         {
01698           _ForwardIterator __mid = __first;
01699           std::advance(__mid, size());
01700           std::copy(__first, __mid, begin());
01701           insert(end(), __mid, __last);
01702         }
01703       else
01704         _M_erase_at_end(std::copy(__first, __last, begin()));
01705     }
01706 
01707       // Called by assign(n,t), and the range assign when it turns out
01708       // to be the same thing.
01709       void
01710       _M_fill_assign(size_type __n, const value_type& __val)
01711       {
01712     if (__n > size())
01713       {
01714         std::fill(begin(), end(), __val);
01715         insert(end(), __n - size(), __val);
01716       }
01717     else
01718       {
01719         _M_erase_at_end(begin() + difference_type(__n));
01720         std::fill(begin(), end(), __val);
01721       }
01722       }
01723 
01724       //@{
01725       /// Helper functions for push_* and pop_*.
01726 #ifndef __GXX_EXPERIMENTAL_CXX0X__
01727       void _M_push_back_aux(const value_type&);
01728 
01729       void _M_push_front_aux(const value_type&);
01730 #else
01731       template<typename... _Args>
01732         void _M_push_back_aux(_Args&&... __args);
01733 
01734       template<typename... _Args>
01735         void _M_push_front_aux(_Args&&... __args);
01736 #endif
01737 
01738       void _M_pop_back_aux();
01739 
01740       void _M_pop_front_aux();
01741       //@}
01742 
01743       // Internal insert functions follow.  The *_aux functions do the actual
01744       // insertion work when all shortcuts fail.
01745 
01746       // called by the range insert to implement [23.1.1]/9
01747 
01748       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01749       // 438. Ambiguity in the "do the right thing" clause
01750       template<typename _Integer>
01751         void
01752         _M_insert_dispatch(iterator __pos,
01753                _Integer __n, _Integer __x, __true_type)
01754         { _M_fill_insert(__pos, __n, __x); }
01755 
01756       // called by the range insert to implement [23.1.1]/9
01757       template<typename _InputIterator>
01758         void
01759         _M_insert_dispatch(iterator __pos,
01760                _InputIterator __first, _InputIterator __last,
01761                __false_type)
01762         {
01763       typedef typename std::iterator_traits<_InputIterator>::
01764         iterator_category _IterCategory;
01765           _M_range_insert_aux(__pos, __first, __last, _IterCategory());
01766     }
01767 
01768       // called by the second insert_dispatch above
01769       template<typename _InputIterator>
01770         void
01771         _M_range_insert_aux(iterator __pos, _InputIterator __first,
01772                 _InputIterator __last, std::input_iterator_tag);
01773 
01774       // called by the second insert_dispatch above
01775       template<typename _ForwardIterator>
01776         void
01777         _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
01778                 _ForwardIterator __last, std::forward_iterator_tag);
01779 
01780       // Called by insert(p,n,x), and the range insert when it turns out to be
01781       // the same thing.  Can use fill functions in optimal situations,
01782       // otherwise passes off to insert_aux(p,n,x).
01783       void
01784       _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
01785 
01786       // called by insert(p,x)
01787 #ifndef __GXX_EXPERIMENTAL_CXX0X__
01788       iterator
01789       _M_insert_aux(iterator __pos, const value_type& __x);
01790 #else
01791       template<typename... _Args>
01792         iterator
01793         _M_insert_aux(iterator __pos, _Args&&... __args);
01794 #endif
01795 
01796       // called by insert(p,n,x) via fill_insert
01797       void
01798       _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
01799 
01800       // called by range_insert_aux for forward iterators
01801       template<typename _ForwardIterator>
01802         void
01803         _M_insert_aux(iterator __pos,
01804               _ForwardIterator __first, _ForwardIterator __last,
01805               size_type __n);
01806 
01807 
01808       // Internal erase functions follow.
01809 
01810       void
01811       _M_destroy_data_aux(iterator __first, iterator __last);
01812 
01813       // Called by ~deque().
01814       // NB: Doesn't deallocate the nodes.
01815       template<typename _Alloc1>
01816         void
01817         _M_destroy_data(iterator __first, iterator __last, const _Alloc1&)
01818         { _M_destroy_data_aux(__first, __last); }
01819 
01820       void
01821       _M_destroy_data(iterator __first, iterator __last,
01822               const std::allocator<_Tp>&)
01823       {
01824     if (!__has_trivial_destructor(value_type))
01825       _M_destroy_data_aux(__first, __last);
01826       }
01827 
01828       // Called by erase(q1, q2).
01829       void
01830       _M_erase_at_begin(iterator __pos)
01831       {
01832     _M_destroy_data(begin(), __pos, _M_get_Tp_allocator());
01833     _M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node);
01834     this->_M_impl._M_start = __pos;
01835       }
01836 
01837       // Called by erase(q1, q2), resize(), clear(), _M_assign_aux,
01838       // _M_fill_assign, operator=.
01839       void
01840       _M_erase_at_end(iterator __pos)
01841       {
01842     _M_destroy_data(__pos, end(), _M_get_Tp_allocator());
01843     _M_destroy_nodes(__pos._M_node + 1,
01844              this->_M_impl._M_finish._M_node + 1);
01845     this->_M_impl._M_finish = __pos;
01846       }
01847 
01848 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01849       // Called by resize(sz).
01850       void
01851       _M_default_append(size_type __n);
01852 
01853       bool
01854       _M_shrink_to_fit();
01855 #endif
01856 
01857       //@{
01858       /// Memory-handling helpers for the previous internal insert functions.
01859       iterator
01860       _M_reserve_elements_at_front(size_type __n)
01861       {
01862     const size_type __vacancies = this->_M_impl._M_start._M_cur
01863                                   - this->_M_impl._M_start._M_first;
01864     if (__n > __vacancies)
01865       _M_new_elements_at_front(__n - __vacancies);
01866     return this->_M_impl._M_start - difference_type(__n);
01867       }
01868 
01869       iterator
01870       _M_reserve_elements_at_back(size_type __n)
01871       {
01872     const size_type __vacancies = (this->_M_impl._M_finish._M_last
01873                        - this->_M_impl._M_finish._M_cur) - 1;
01874     if (__n > __vacancies)
01875       _M_new_elements_at_back(__n - __vacancies);
01876     return this->_M_impl._M_finish + difference_type(__n);
01877       }
01878 
01879       void
01880       _M_new_elements_at_front(size_type __new_elements);
01881 
01882       void
01883       _M_new_elements_at_back(size_type __new_elements);
01884       //@}
01885 
01886 
01887       //@{
01888       /**
01889        *  @brief Memory-handling helpers for the major %map.
01890        *
01891        *  Makes sure the _M_map has space for new nodes.  Does not
01892        *  actually add the nodes.  Can invalidate _M_map pointers.
01893        *  (And consequently, %deque iterators.)
01894        */
01895       void
01896       _M_reserve_map_at_back(size_type __nodes_to_add = 1)
01897       {
01898     if (__nodes_to_add + 1 > this->_M_impl._M_map_size
01899         - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
01900       _M_reallocate_map(__nodes_to_add, false);
01901       }
01902 
01903       void
01904       _M_reserve_map_at_front(size_type __nodes_to_add = 1)
01905       {
01906     if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
01907                        - this->_M_impl._M_map))
01908       _M_reallocate_map(__nodes_to_add, true);
01909       }
01910 
01911       void
01912       _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
01913       //@}
01914     };
01915 
01916 
01917   /**
01918    *  @brief  Deque equality comparison.
01919    *  @param  __x  A %deque.
01920    *  @param  __y  A %deque of the same type as @a __x.
01921    *  @return  True iff the size and elements of the deques are equal.
01922    *
01923    *  This is an equivalence relation.  It is linear in the size of the
01924    *  deques.  Deques are considered equivalent if their sizes are equal,
01925    *  and if corresponding elements compare equal.
01926   */
01927   template<typename _Tp, typename _Alloc>
01928     inline bool
01929     operator==(const deque<_Tp, _Alloc>& __x,
01930                          const deque<_Tp, _Alloc>& __y)
01931     { return __x.size() == __y.size()
01932              && std::equal(__x.begin(), __x.end(), __y.begin()); }
01933 
01934   /**
01935    *  @brief  Deque ordering relation.
01936    *  @param  __x  A %deque.
01937    *  @param  __y  A %deque of the same type as @a __x.
01938    *  @return  True iff @a x is lexicographically less than @a __y.
01939    *
01940    *  This is a total ordering relation.  It is linear in the size of the
01941    *  deques.  The elements must be comparable with @c <.
01942    *
01943    *  See std::lexicographical_compare() for how the determination is made.
01944   */
01945   template<typename _Tp, typename _Alloc>
01946     inline bool
01947     operator<(const deque<_Tp, _Alloc>& __x,
01948           const deque<_Tp, _Alloc>& __y)
01949     { return std::lexicographical_compare(__x.begin(), __x.end(),
01950                       __y.begin(), __y.end()); }
01951 
01952   /// Based on operator==
01953   template<typename _Tp, typename _Alloc>
01954     inline bool
01955     operator!=(const deque<_Tp, _Alloc>& __x,
01956            const deque<_Tp, _Alloc>& __y)
01957     { return !(__x == __y); }
01958 
01959   /// Based on operator<
01960   template<typename _Tp, typename _Alloc>
01961     inline bool
01962     operator>(const deque<_Tp, _Alloc>& __x,
01963           const deque<_Tp, _Alloc>& __y)
01964     { return __y < __x; }
01965 
01966   /// Based on operator<
01967   template<typename _Tp, typename _Alloc>
01968     inline bool
01969     operator<=(const deque<_Tp, _Alloc>& __x,
01970            const deque<_Tp, _Alloc>& __y)
01971     { return !(__y < __x); }
01972 
01973   /// Based on operator<
01974   template<typename _Tp, typename _Alloc>
01975     inline bool
01976     operator>=(const deque<_Tp, _Alloc>& __x,
01977            const deque<_Tp, _Alloc>& __y)
01978     { return !(__x < __y); }
01979 
01980   /// See std::deque::swap().
01981   template<typename _Tp, typename _Alloc>
01982     inline void
01983     swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y)
01984     { __x.swap(__y); }
01985 
01986 #undef _GLIBCXX_DEQUE_BUF_SIZE
01987 
01988 _GLIBCXX_END_NAMESPACE_CONTAINER
01989 } // namespace std
01990 
01991 #endif /* _STL_DEQUE_H */