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