- Main Page
- Namespaces
- Classes
- Files
- Related Pages

# /Users/fpy/titan-1-5-MBARI/Mers/Executives/DeductiveController/Configs/TI_DSP_BIOS/stl/stl_deque.h

    00001 /*
    00002  *
    00003  * Copyright (c) 1994
    00004  * Hewlett-Packard Company
    00005  *
    00006  * Permission to use, copy, modify, distribute and sell this software
    00007  * and its documentation for any purpose is hereby granted without fee,
    00008  * provided that the above copyright notice appear in all copies and
    00009  * that both that copyright notice and this permission notice appear
    00010  * in supporting documentation.  Hewlett-Packard Company makes no
    00011  * representations about the suitability of this software for any
    00012  * purpose.  It is provided "as is" without express or implied warranty.
    00013  *
    00014  *
    00015  * Copyright (c) 1997
    00016  * Silicon Graphics Computer Systems, Inc.
    00017  *
    00018  * Permission to use, copy, modify, distribute and sell this software
    00019  * and its documentation for any purpose is hereby granted without fee,
    00020  * provided that the above copyright notice appear in all copies and
    00021  * that both that copyright notice and this permission notice appear
    00022  * in supporting documentation.  Silicon Graphics makes no
    00023  * representations about the suitability of this software for any
    00024  * purpose.  It is provided "as is" without express or implied warranty.
    00025  */
    00026
    00027 /* NOTE: This is an internal header file, included by other STL headers.
    00028  *   You should not attempt to use it directly.
    00029  */
    00030
    00031 #ifndef __SGI_STL_INTERNAL_DEQUE_H
    00032 #define __SGI_STL_INTERNAL_DEQUE_H
    00033
    00034 /* Class invariants:
    00035  *  For any nonsingular iterator i:
    00036  *    i.node is the address of an element in the map array.  The
    00037  *      contents of i.node is a pointer to the beginning of a node.
    00038  *    i.first == *(i.node)
    00039  *    i.last  == i.first + node_size
    00040  *    i.cur is a pointer in the range [i.first, i.last).  NOTE:
    00041  *      the implication of this is that i.cur is always a dereferenceable
    00042  *      pointer, even if i is a past-the-end iterator.
    00043  *  Start and Finish are always nonsingular iterators.  NOTE: this means
    00044  *    that an empty deque must have one node, and that a deque
    00045  *    with N elements, where N is the buffer size, must have two nodes.
    00046  *  For every node other than start.node and finish.node, every element
    00047  *    in the node is an initialized object.  If start.node == finish.node,
    00048  *    then [start.cur, finish.cur) are initialized objects, and
    00049  *    the elements outside that range are uninitialized storage.  Otherwise,
    00050  *    [start.cur, start.last) and [finish.first, finish.cur) are initialized
    00051  *    objects, and [start.first, start.cur) and [finish.cur, finish.last)
    00052  *    are uninitialized storage.
    00053  *  [map, map + map_size) is a valid, non-empty range.
    00054  *  [start.node, finish.node] is a valid range contained within
    00055  *    [map, map + map_size).
    00056  *  A pointer in the range [map, map + map_size) points to an allocated node
    00057  *    if and only if the pointer is in the range [start.node, finish.node].
    00058  */
    00059
    00060
    00061 /*
    00062  * In previous versions of deque, node_size was fixed by the
    00063  * implementation.  In this version, however, users can select
    00064  * the node size.  Deque has three template parameters; the third,
    00065  * a number of type size_t, is the number of elements per node.
    00066  * If the third template parameter is 0 (which is the default),
    00067  * then deque will use a default node size.
    00068  *
    00069  * The only reason for using an alternate node size is if your application
    00070  * requires a different performance tradeoff than the default.  If,
    00071  * for example, your program contains many deques each of which contains
    00072  * only a few elements, then you might want to save memory (possibly
    00073  * by sacrificing some speed) by using smaller nodes.
    00074  *
    00075  * Unfortunately, some compilers have trouble with non-type template
    00076  * parameters; stl_config.h defines __STL_NON_TYPE_TMPL_PARAM_BUG if
    00077  * that is the case.  If your compiler is one of them, then you will
    00078  * not be able to use alternate node sizes; you will have to use the
    00079  * default value.
    00080  */
    00081
    00082 __STL_BEGIN_NAMESPACE
    00083
    00084 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
    00085 #pragma set woff 1174
    00086 #pragma set woff 1375
    00087 #endif
    00088
    00089 // Note: this function is simply a kludge to work around several compilers'
    00090 //  bugs in handling constant expressions.
    00091 inline size_t
    00092 __deque_buf_size(size_t __n, size_t __size)
    00093 {
    00094   return __n != 0 ? __n : (__size < 512 ? size_t(512 / __size) : size_t(1));
    00095 }
    00096
    00097 #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
    00098 template <class _Tp, class _Ref, class _Ptr, size_t __bufsiz>
    00099 struct _Deque_iterator {
    00100   typedef _Deque_iterator<_Tp,_Tp&,_Tp*,__bufsiz>             iterator;
    00101   typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*,__bufsiz> const_iterator;
    00102   static size_t
    00103     _S_buffer_size() { return __deque_buf_size(__bufsiz, sizeof(_Tp)); }
    00104 #else /* __STL_NON_TYPE_TMPL_PARAM_BUG */
    00105 template <class _Tp, class _Ref, class _Ptr>
    00106 struct _Deque_iterator {
    00107   typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
    00108   typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
    00109   static size_t
    00110     _S_buffer_size() { return __deque_buf_size(0, sizeof(_Tp)); }
    00111 #endif
    00112
    00113   typedef 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
    00121   typedef _Deque_iterator _Self;
    00122
    00123   _Tp* _M_cur;
    00124   _Tp* _M_first;
    00125   _Tp* _M_last;
    00126   _Map_pointer _M_node;
    00127
    00128   _Deque_iterator(_Tp* __x, _Map_pointer __y)
    00129     : _M_cur(__x), _M_first(*__y),
    00130       _M_last(*__y + _S_buffer_size()), _M_node(__y) {}
    00131   _Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
    00132   _Deque_iterator(const iterator& __x)
    00133     : _M_cur(__x._M_cur), _M_first(__x._M_first),
    00134       _M_last(__x._M_last), _M_node(__x._M_node) {}
    00135
    00136   reference operator*() const { return *_M_cur; }
    00137 #ifndef __SGI_STL_NO_ARROW_OPERATOR
    00138   pointer operator->() const { return _M_cur; }
    00139 #endif /* __SGI_STL_NO_ARROW_OPERATOR */
    00140
    00141   difference_type operator-(const _Self& __x) const {
    00142     return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +
    00143       (_M_cur - _M_first) + (__x._M_last - __x._M_cur);
    00144   }
    00145
    00146   _Self& operator++() {
    00147     ++_M_cur;
    00148     if (_M_cur == _M_last) {
    00149       _M_set_node(_M_node + 1);
    00150       _M_cur = _M_first;
    00151     }
    00152     return *this;
    00153   }
    00154   _Self operator++(int)  {
    00155     _Self __tmp = *this;
    00156     ++*this;
    00157     return __tmp;
    00158   }
    00159
    00160   _Self& operator--() {
    00161     if (_M_cur == _M_first) {
    00162       _M_set_node(_M_node - 1);
    00163       _M_cur = _M_last;
    00164     }
    00165     --_M_cur;
    00166     return *this;
    00167   }
    00168   _Self operator--(int) {
    00169     _Self __tmp = *this;
    00170     --*this;
    00171     return __tmp;
    00172   }
    00173
    00174   _Self& operator+=(difference_type __n)
    00175   {
    00176     difference_type __offset = __n + (_M_cur - _M_first);
    00177     if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
    00178       _M_cur += __n;
    00179     else {
    00180       difference_type __node_offset =
    00181         __offset > 0 ? __offset / difference_type(_S_buffer_size())
    00182                    : -difference_type((-__offset - 1) / _S_buffer_size()) - 1;
    00183       _M_set_node(_M_node + __node_offset);
    00184       _M_cur = _M_first +
    00185         (__offset - __node_offset * difference_type(_S_buffer_size()));
    00186     }
    00187     return *this;
    00188   }
    00189
    00190   _Self operator+(difference_type __n) const
    00191   {
    00192     _Self __tmp = *this;
    00193     return __tmp += __n;
    00194   }
    00195
    00196   _Self& operator-=(difference_type __n) { return *this += -__n; }
    00197
    00198   _Self operator-(difference_type __n) const {
    00199     _Self __tmp = *this;
    00200     return __tmp -= __n;
    00201   }
    00202
    00203   reference operator[](difference_type __n) const { return *(*this + __n); }
    00204
    00205   bool operator==(const _Self& __x) const { return _M_cur == __x._M_cur; }
    00206   bool operator!=(const _Self& __x) const { return !(*this == __x); }
    00207   bool operator<(const _Self& __x) const {
    00208     return (_M_node == __x._M_node) ?
    00209       (_M_cur < __x._M_cur) : (_M_node < __x._M_node);
    00210   }
    00211
    00212   void _M_set_node(_Map_pointer __new_node) {
    00213     _M_node = __new_node;
    00214     _M_first = *__new_node;
    00215     _M_last = _M_first + difference_type(_S_buffer_size());
    00216   }
    00217 };
    00218
    00219 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
    00220
    00221 #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
    00222
    00223 template <class _Tp, class _Ref, class _Ptr, size_t __bufsiz>
    00224 inline random_access_iterator_tag
    00225 iterator_category(const _Deque_iterator<_Tp,_Ref,_Ptr,__bufsiz>&) {
    00226   return random_access_iterator_tag();
    00227 }
    00228
    00229 template <class _Tp, class _Ref, class _Ptr, size_t __bufsiz>
    00230 inline _Tp*
    00231 value_type(const _Deque_iterator<_Tp,_Ref,_Ptr,__bufsiz>&) {
    00232   return 0;
    00233 }
    00234
    00235 template <class _Tp, class _Ref, class _Ptr, size_t __bufsiz>
    00236 inline ptrdiff_t*
    00237 distance_type(const _Deque_iterator<_Tp,_Ref,_Ptr,__bufsiz>&) {
    00238   return 0;
    00239 }
    00240
    00241 #else /* __STL_NON_TYPE_TMPL_PARAM_BUG */
    00242
    00243 template <class _Tp, class _Ref, class _Ptr>
    00244 inline random_access_iterator_tag
    00245 iterator_category(const _Deque_iterator<_Tp,_Ref,_Ptr>&)
    00246 {
    00247   return random_access_iterator_tag();
    00248 }
    00249
    00250 template <class _Tp, class _Ref, class _Ptr>
    00251 inline _Tp*
    00252 value_type(const _Deque_iterator<_Tp,_Ref,_Ptr>&) { return 0; }
    00253
    00254 template <class _Tp, class _Ref, class _Ptr>
    00255 inline ptrdiff_t*
    00256 distance_type(const _Deque_iterator<_Tp,_Ref,_Ptr>&) {
    00257   return 0;
    00258 }
    00259
    00260 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */
    00261
    00262 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    00263
    00264 // Deque base class.  It has two purposes.  First, its constructor
    00265 //  and destructor allocate (but don't initialize) storage.  This makes
    00266 //  exception safety easier.  Second, the base class encapsulates all of
    00267 //  the differences between SGI-style allocators and standard-conforming
    00268 //  allocators.
    00269
    00270 #ifdef __STL_USE_STD_ALLOCATORS
    00271
    00272 // Base class for ordinary allocators.
    00273 template <class _Tp, class _Alloc, size_t __bufsiz, bool __is_static>
    00274 class _Deque_alloc_base {
    00275 public:
    00276   typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
    00277   allocator_type get_allocator() const { return node_allocator; }
    00278
    00279   _Deque_alloc_base(const allocator_type& __a)
    00280     : node_allocator(__a), map_allocator(__a), _M_map(0), _M_map_size(0)
    00281   {}
    00282
    00283 protected:
    00284   typedef typename _Alloc_traits<_Tp*, _Alloc>::allocator_type
    00285           map_allocator_type;
    00286
    00287   allocator_type node_allocator;
    00288   map_allocator_type map_allocator;
    00289
    00290   _Tp* _M_allocate_node() {
    00291     return node_allocator.allocate(__deque_buf_size(__bufsiz,sizeof(_Tp)));
    00292   }
    00293   void _M_deallocate_node(_Tp* __p) {
    00294     node_allocator.deallocate(__p, __deque_buf_size(__bufsiz,sizeof(_Tp)));
    00295   }
    00296   _Tp** _M_allocate_map(size_t __n)
    00297     { return map_allocator.allocate(__n); }
    00298   void _M_deallocate_map(_Tp** __p, size_t __n)
    00299     { map_allocator.deallocate(__p, __n); }
    00300
    00301   _Tp** _M_map;
    00302   size_t _M_map_size;
    00303 };
    00304
    00305 // Specialization for instanceless allocators.
    00306 template <class _Tp, class _Alloc, size_t __bufsiz>
    00307 class _Deque_alloc_base<_Tp, _Alloc, __bufsiz, true>
    00308 {
    00309 public:
    00310   typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
    00311   allocator_type get_allocator() const { return allocator_type(); }
    00312
    00313   _Deque_alloc_base(const allocator_type&) : _M_map(0), _M_map_size(0) {}
    00314
    00315 protected:
    00316   typedef typename _Alloc_traits<_Tp, _Alloc>::_Alloc_type _Node_alloc_type;
    00317   typedef typename _Alloc_traits<_Tp*, _Alloc>::_Alloc_type _Map_alloc_type;
    00318
    00319   _Tp* _M_allocate_node()
    00320     { return _Node_alloc_type::allocate(__deque_buf_size(__bufsiz,
    00321                                                          sizeof(_Tp))); }
    00322   void _M_deallocate_node(_Tp* __p)
    00323     { _Node_alloc_type::deallocate(__p, __deque_buf_size(__bufsiz,
    00324                                                          sizeof(_Tp))); }
    00325   _Tp** _M_allocate_map(size_t __n)
    00326     { return _Map_alloc_type::allocate(__n); }
    00327   void _M_deallocate_map(_Tp** __p, size_t __n)
    00328     { _Map_alloc_type::deallocate(__p, __n); }
    00329
    00330   _Tp** _M_map;
    00331   size_t _M_map_size;
    00332 };
    00333
    00334 template <class _Tp, class _Alloc, size_t __bufsiz>
    00335 class _Deque_base
    00336   : public _Deque_alloc_base<_Tp,_Alloc,__bufsiz,
    00337                               _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
    00338 {
    00339 public:
    00340   typedef _Deque_alloc_base<_Tp,_Alloc,__bufsiz,
    00341                              _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
    00342           _Base;
    00343   typedef typename _Base::allocator_type allocator_type;
    00344   typedef _Deque_iterator<_Tp,_Tp&,_Tp*,__bufsiz>              iterator;
    00345   typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*, __bufsiz> const_iterator;
    00346
    00347   _Deque_base(const allocator_type& __a, size_t __num_elements)
    00348     : _Base(__a), _M_start(), _M_finish()
    00349     { _M_initialize_map(__num_elements); }
    00350   _Deque_base(const allocator_type& __a)
    00351     : _Base(__a), _M_start(), _M_finish() {}
    00352   ~_Deque_base();
    00353
    00354 protected:
    00355   void _M_initialize_map(size_t);
    00356   void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
    00357   void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
    00358   enum { _S_initial_map_size = 8 };
    00359
    00360 protected:
    00361   iterator _M_start;
    00362   iterator _M_finish;
    00363 };
    00364
    00365 #else /* __STL_USE_STD_ALLOCATORS */
    00366
    00367 template <class _Tp, class _Alloc, size_t __bufsiz>
    00368 class _Deque_base {
    00369 public:
    00370 #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
    00371   typedef _Deque_iterator<_Tp,_Tp&,_Tp*,__bufsiz>              iterator;
    00372   typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*, __bufsiz> const_iterator;
    00373 #else /* __STL_NON_TYPE_TMPL_PARAM_BUG */
    00374   typedef _Deque_iterator<_Tp,_Tp&,_Tp*>                      iterator;
    00375   typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*>          const_iterator;
    00376 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */
    00377
    00378   typedef _Alloc allocator_type;
    00379   allocator_type get_allocator() const { return allocator_type(); }
    00380
    00381   _Deque_base(const allocator_type&, size_t __num_elements)
    00382     : _M_map(0), _M_map_size(0),  _M_start(), _M_finish() {
    00383     _M_initialize_map(__num_elements);
    00384   }
    00385   _Deque_base(const allocator_type&)
    00386     : _M_map(0), _M_map_size(0),  _M_start(), _M_finish() {}
    00387   ~_Deque_base();
    00388
    00389 protected:
    00390   void _M_initialize_map(size_t);
    00391   void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
    00392   void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
    00393   enum { _S_initial_map_size = 8 };
    00394
    00395 protected:
    00396   _Tp** _M_map;
    00397   size_t _M_map_size;
    00398   iterator _M_start;
    00399   iterator _M_finish;
    00400
    00401   typedef simple_alloc<_Tp, _Alloc>  _Node_alloc_type;
    00402   typedef simple_alloc<_Tp*, _Alloc> _Map_alloc_type;
    00403
    00404   _Tp* _M_allocate_node()
    00405     { return _Node_alloc_type::allocate(__deque_buf_size(__bufsiz,
    00406                                                          sizeof(_Tp))); }
    00407   void _M_deallocate_node(_Tp* __p)
    00408     { _Node_alloc_type::deallocate(__p, __deque_buf_size(__bufsiz,
    00409                                                          sizeof(_Tp))); }
    00410   _Tp** _M_allocate_map(size_t __n)
    00411     { return _Map_alloc_type::allocate(__n); }
    00412   void _M_deallocate_map(_Tp** __p, size_t __n)
    00413     { _Map_alloc_type::deallocate(__p, __n); }
    00414 };
    00415
    00416 #endif /* __STL_USE_STD_ALLOCATORS */
    00417
    00418 // Non-inline member functions from _Deque_base.
    00419
    00420 template <class _Tp, class _Alloc, size_t __bufsiz>
    00421 _Deque_base<_Tp,_Alloc,__bufsiz>::~_Deque_base() {
    00422   if (_M_map) {
    00423     _M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1);
    00424     _M_deallocate_map(_M_map, _M_map_size);
    00425   }
    00426 }
    00427
    00428 template <class _Tp, class _Alloc, size_t __bufsiz>
    00429 void
    00430 _Deque_base<_Tp,_Alloc,__bufsiz>::_M_initialize_map(size_t __num_elements)
    00431 {
    00432   size_t __num_nodes =
    00433     __num_elements / __deque_buf_size(__bufsiz, sizeof(_Tp)) + 1;
    00434
    00435   _M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2);
    00436   _M_map = _M_allocate_map(_M_map_size);
    00437
    00438   _Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2;
    00439   _Tp** __nfinish = __nstart + __num_nodes;
    00440
    00441   __STL_TRY {
    00442     _M_create_nodes(__nstart, __nfinish);
    00443   }
    00444   __STL_UNWIND((_M_deallocate_map(_M_map, _M_map_size),
    00445                 _M_map = 0, _M_map_size = 0));
    00446   _M_start._M_set_node(__nstart);
    00447   _M_finish._M_set_node(__nfinish - 1);
    00448   _M_start._M_cur = _M_start._M_first;
    00449   _M_finish._M_cur = _M_finish._M_first +
    00450                __num_elements % __deque_buf_size(__bufsiz, sizeof(_Tp));
    00451 }
    00452
    00453 template <class _Tp, class _Alloc, size_t __bufsiz>
    00454 void
    00455 _Deque_base<_Tp,_Alloc,__bufsiz>::_M_create_nodes(_Tp** __nstart,
    00456                                                   _Tp** __nfinish)
    00457 {
    00458   _Tp** __cur;
    00459   __STL_TRY {
    00460     for (__cur = __nstart; __cur < __nfinish; ++__cur)
    00461       *__cur = _M_allocate_node();
    00462   }
    00463   __STL_UNWIND(_M_destroy_nodes(__nstart, __cur));
    00464 }
    00465
    00466 template <class _Tp, class _Alloc, size_t __bufsiz>
    00467 void
    00468 _Deque_base<_Tp,_Alloc,__bufsiz>::_M_destroy_nodes(_Tp** __nstart,
    00469                                                    _Tp** __nfinish)
    00470 {
    00471   for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
    00472     _M_deallocate_node(*__n);
    00473 }
    00474
    00475 // See __deque_buf_size().  The only reason that the default value is 0
    00476 //  is as a workaround for bugs in the way that some compilers handle
    00477 //  constant expressions.
    00478 template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp),
    00479           size_t __bufsiz = 0>
    00480 class deque : protected _Deque_base<_Tp, _Alloc, __bufsiz> {
    00481   typedef _Deque_base<_Tp, _Alloc, __bufsiz> _Base;
    00482 public:                         // Basic types
    00483   typedef _Tp value_type;
    00484   typedef value_type* pointer;
    00485   typedef const value_type* const_pointer;
    00486   typedef value_type& reference;
    00487   typedef const value_type& const_reference;
    00488   typedef size_t size_type;
    00489   typedef ptrdiff_t difference_type;
    00490
    00491   typedef typename _Base::allocator_type allocator_type;
    00492   allocator_type get_allocator() const { return _Base::get_allocator(); }
    00493
    00494 public:                         // Iterators
    00495   typedef typename _Base::iterator       iterator;
    00496   typedef typename _Base::const_iterator const_iterator;
    00497
    00498 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
    00499   typedef reverse_iterator<const_iterator> const_reverse_iterator;
    00500   typedef reverse_iterator<iterator> reverse_iterator;
    00501 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    00502   typedef reverse_iterator<const_iterator, value_type, const_reference,
    00503                            difference_type>
    00504           const_reverse_iterator;
    00505   typedef reverse_iterator<iterator, value_type, reference, difference_type>
    00506           reverse_iterator;
    00507 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    00508
    00509 protected:                      // Internal typedefs
    00510   typedef pointer* _Map_pointer;
    00511   static size_t _S_buffer_size()
    00512     { return __deque_buf_size(__bufsiz, sizeof(_Tp)); }
    00513
    00514 protected:
    00515 #ifdef __STL_USE_NAMESPACES
    00516   using _Base::_M_initialize_map;
    00517   using _Base::_M_create_nodes;
    00518   using _Base::_M_destroy_nodes;
    00519   using _Base::_M_allocate_node;
    00520   using _Base::_M_deallocate_node;
    00521   using _Base::_M_allocate_map;
    00522   using _Base::_M_deallocate_map;
    00523
    00524   using _Base::_M_map;
    00525   using _Base::_M_map_size;
    00526   using _Base::_M_start;
    00527   using _Base::_M_finish;
    00528 #endif /* __STL_USE_NAMESPACES */
    00529
    00530 public:                         // Basic accessors
    00531   iterator begin() { return _M_start; }
    00532   iterator end() { return _M_finish; }
    00533   const_iterator begin() const { return _M_start; }
    00534   const_iterator end() const { return _M_finish; }
    00535
    00536   reverse_iterator rbegin() { return reverse_iterator(_M_finish); }
    00537   reverse_iterator rend() { return reverse_iterator(_M_start); }
    00538   const_reverse_iterator rbegin() const
    00539     { return const_reverse_iterator(_M_finish); }
    00540   const_reverse_iterator rend() const
    00541     { return const_reverse_iterator(_M_start); }
    00542
    00543   reference operator[](size_type __n)
    00544     { return _M_start[difference_type(__n)]; }
    00545   const_reference operator[](size_type __n) const
    00546     { return _M_start[difference_type(__n)]; }
    00547
    00548   reference front() { return *_M_start; }
    00549   reference back() {
    00550     iterator __tmp = _M_finish;
    00551     --__tmp;
    00552     return *__tmp;
    00553   }
    00554   const_reference front() const { return *_M_start; }
    00555   const_reference back() const {
    00556     const_iterator __tmp = _M_finish;
    00557     --__tmp;
    00558     return *__tmp;
    00559   }
    00560
    00561   size_type size() const { return _M_finish - _M_start;; }
    00562   size_type max_size() const { return size_type(-1); }
    00563   bool empty() const { return _M_finish == _M_start; }
    00564
    00565 public:                         // Constructor, destructor.
    00566   explicit deque(const allocator_type& __a = allocator_type())
    00567     : _Base(__a, 0) {}
    00568   deque(const deque& __x) : _Base(__x.get_allocator(), __x.size())
    00569     { uninitialized_copy(__x.begin(), __x.end(), _M_start); }
    00570   deque(size_type __n, const value_type& __value,
    00571         const allocator_type& __a = allocator_type()) : _Base(__a, __n)
    00572     { _M_fill_initialize(__value); }
    00573   explicit deque(size_type __n) : _Base(allocator_type(), __n)
    00574     { _M_fill_initialize(value_type()); }
    00575
    00576 #ifdef __STL_MEMBER_TEMPLATES
    00577
    00578   // Check whether it's an integral type.  If so, it's not an iterator.
    00579   template <class _InputIterator>
    00580   deque(_InputIterator __first, _InputIterator __last,
    00581         const allocator_type& __a = allocator_type()) : _Base(__a) {
    00582     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    00583     _M_initialize_dispatch(__first, __last, _Integral());
    00584   }
    00585
    00586   template <class _Integer>
    00587   void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) {
    00588     _M_initialize_map(__n);
    00589     _M_fill_initialize(__x);
    00590   }
    00591
    00592   template <class _InputIter>
    00593   void _M_initialize_dispatch(_InputIter __first, _InputIter __last,
    00594                               __false_type) {
    00595     _M_range_initialize(__first, __last, __ITERATOR_CATEGORY(__first));
    00596   }
    00597
    00598 #else /* __STL_MEMBER_TEMPLATES */
    00599
    00600   deque(const value_type* __first, const value_type* __last,
    00601         const allocator_type& __a = allocator_type())
    00602     : _Base(__a, __last - __first)
    00603     { uninitialized_copy(__first, __last, _M_start); }
    00604   deque(const_iterator __first, const_iterator __last,
    00605         const allocator_type& __a = allocator_type())
    00606     : _Base(__a, __last - __first)
    00607     { uninitialized_copy(__first, __last, _M_start); }
    00608
    00609 #endif /* __STL_MEMBER_TEMPLATES */
    00610
    00611   ~deque() { destroy(_M_start, _M_finish); }
    00612
    00613   deque& operator= (const deque& __x) {
    00614     const size_type __len = size();
    00615     if (&__x != this) {
    00616       if (__len >= __x.size())
    00617         erase(copy(__x.begin(), __x.end(), _M_start), _M_finish);
    00618       else {
    00619         const_iterator __mid = __x.begin() + difference_type(__len);
    00620         copy(__x.begin(), __mid, _M_start);
    00621         insert(_M_finish, __mid, __x.end());
    00622       }
    00623     }
    00624     return *this;
    00625   }
    00626
    00627   void swap(deque& __x) {
    00628     __STD::swap(_M_start, __x._M_start);
    00629     __STD::swap(_M_finish, __x._M_finish);
    00630     __STD::swap(_M_map, __x._M_map);
    00631     __STD::swap(_M_map_size, __x._M_map_size);
    00632   }
    00633
    00634 public:
    00635   // assign(), a generalized assignment member function.  Two
    00636   // versions: one that takes a count, and one that takes a range.
    00637   // The range version is a member template, so we dispatch on whether
    00638   // or not the type is an integer.
    00639
    00640   void assign(size_type __n, const _Tp& __val) {
    00641     if (__n > size()) {
    00642       fill(begin(), end(), __val);
    00643       insert(end(), __n - size(), __val);
    00644     }
    00645     else {
    00646       erase(begin() + __n, end());
    00647       fill(begin(), end(), __val);
    00648     }
    00649   }
    00650
    00651 #ifdef __STL_MEMBER_TEMPLATES
    00652
    00653   template <class _InputIterator>
    00654   void assign(_InputIterator __first, _InputIterator __last) {
    00655     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    00656     _M_assign_dispatch(__first, __last, _Integral());
    00657   }
    00658
    00659 private:                        // helper functions for assign()
    00660
    00661   template <class _Integer>
    00662   void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
    00663     { assign((size_type) __n, (_Tp) __val); }
    00664
    00665   template <class _InputIterator>
    00666   void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
    00667                           __false_type) {
    00668     _M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first));
    00669   }
    00670
    00671   template <class _InputIterator>
    00672   void _M_assign_aux(_InputIterator __first, _InputIterator __last,
    00673                      input_iterator_tag);
    00674
    00675   template <class _ForwardIterator>
    00676   void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
    00677                      forward_iterator_tag) {
    00678     size_type __len = 0;
    00679     distance(__first, __last, __len);
    00680     if (__len > size()) {
    00681       _ForwardIterator __mid = __first;
    00682       advance(__mid, size());
    00683       copy(__first, __mid, begin());
    00684       insert(end(), __mid, __last);
    00685     }
    00686     else
    00687       erase(copy(__first, __last, begin()), end());
    00688   }
    00689
    00690 #endif /* __STL_MEMBER_TEMPLATES */
    00691
    00692 public:                         // push_* and pop_*
    00693
    00694   void push_back(const value_type& __t) {
    00695     if (_M_finish._M_cur != _M_finish._M_last - 1) {
    00696       construct(_M_finish._M_cur, __t);
    00697       ++_M_finish._M_cur;
    00698     }
    00699     else
    00700       _M_push_back_aux(__t);
    00701   }
    00702
    00703   void push_back() {
    00704     if (_M_finish._M_cur != _M_finish._M_last - 1) {
    00705       construct(_M_finish._M_cur);
    00706       ++_M_finish._M_cur;
    00707     }
    00708     else
    00709       _M_push_back_aux();
    00710   }
    00711
    00712   void push_front(const value_type& __t) {
    00713     if (_M_start._M_cur != _M_start._M_first) {
    00714       construct(_M_start._M_cur - 1, __t);
    00715       --_M_start._M_cur;
    00716     }
    00717     else
    00718       _M_push_front_aux(__t);
    00719   }
    00720
    00721   void push_front() {
    00722     if (_M_start._M_cur != _M_start._M_first) {
    00723       construct(_M_start._M_cur - 1);
    00724       --_M_start._M_cur;
    00725     }
    00726     else
    00727       _M_push_front_aux();
    00728   }
    00729
    00730
    00731   void pop_back() {
    00732     if (_M_finish._M_cur != _M_finish._M_first) {
    00733       --_M_finish._M_cur;
    00734       destroy(_M_finish._M_cur);
    00735     }
    00736     else
    00737       _M_pop_back_aux();
    00738   }
    00739
    00740   void pop_front() {
    00741     if (_M_start._M_cur != _M_start._M_last - 1) {
    00742       destroy(_M_start._M_cur);
    00743       ++_M_start._M_cur;
    00744     }
    00745     else
    00746       _M_pop_front_aux();
    00747   }
    00748
    00749 public:                         // Insert
    00750
    00751   iterator insert(iterator position, const value_type& __x) {
    00752     if (position._M_cur == _M_start._M_cur) {
    00753       push_front(__x);
    00754       return _M_start;
    00755     }
    00756     else if (position._M_cur == _M_finish._M_cur) {
    00757       push_back(__x);
    00758       iterator __tmp = _M_finish;
    00759       --__tmp;
    00760       return __tmp;
    00761     }
    00762     else {
    00763       return _M_insert_aux(position, __x);
    00764     }
    00765   }
    00766
    00767   iterator insert(iterator __position)
    00768     { return insert(__position, value_type()); }
    00769
    00770   void insert(iterator __pos, size_type __n, const value_type& __x);
    00771
    00772 #ifdef __STL_MEMBER_TEMPLATES
    00773
    00774   // Check whether it's an integral type.  If so, it's not an iterator.
    00775   template <class _InputIterator>
    00776   void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
    00777     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    00778     _M_insert_dispatch(__pos, __first, __last, _Integral());
    00779   }
    00780
    00781   template <class _Integer>
    00782   void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
    00783                           __true_type) {
    00784     insert(__pos, (size_type) __n, (value_type) __x);
    00785   }
    00786
    00787   template <class _InputIterator>
    00788   void _M_insert_dispatch(iterator __pos,
    00789                           _InputIterator __first, _InputIterator __last,
    00790                           __false_type) {
    00791     insert(__pos, __first, __last, __ITERATOR_CATEGORY(__first));
    00792   }
    00793
    00794 #else /* __STL_MEMBER_TEMPLATES */
    00795
    00796   void insert(iterator __pos,
    00797               const value_type* __first, const value_type* __last);
    00798   void insert(iterator __pos,
    00799               const_iterator __first, const_iterator __last);
    00800
    00801 #endif /* __STL_MEMBER_TEMPLATES */
    00802
    00803   void resize(size_type __new_size, const value_type& __x) {
    00804     const size_type __len = size();
    00805     if (__new_size < __len)
    00806       erase(_M_start + __new_size, _M_finish);
    00807     else
    00808       insert(_M_finish, __new_size - __len, __x);
    00809   }
    00810
    00811   void resize(size_type new_size) { resize(new_size, value_type()); }
    00812
    00813 public:                         // Erase
    00814   iterator erase(iterator __pos) {
    00815     iterator __next = __pos;
    00816     ++__next;
    00817     difference_type __index = __pos - _M_start;
    00818     if (static_cast<size_type>(__index) < (size() >> 1)) {
    00819       copy_backward(_M_start, __pos, __next);
    00820       pop_front();
    00821     }
    00822     else {
    00823       copy(__next, _M_finish, __pos);
    00824       pop_back();
    00825     }
    00826     return _M_start + __index;
    00827   }
    00828
    00829   iterator erase(iterator __first, iterator __last);
    00830   void clear();
    00831
    00832 protected:                        // Internal construction/destruction
    00833
    00834   void _M_fill_initialize(const value_type& __value);
    00835
    00836 #ifdef __STL_MEMBER_TEMPLATES
    00837
    00838   template <class _InputIterator>
    00839   void _M_range_initialize(_InputIterator __first, _InputIterator __last,
    00840                         input_iterator_tag);
    00841
    00842   template <class _ForwardIterator>
    00843   void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
    00844                         forward_iterator_tag);
    00845
    00846 #endif /* __STL_MEMBER_TEMPLATES */
    00847
    00848 protected:                        // Internal push_* and pop_*
    00849
    00850   void _M_push_back_aux(const value_type&);
    00851   void _M_push_back_aux();
    00852   void _M_push_front_aux(const value_type&);
    00853   void _M_push_front_aux();
    00854   void _M_pop_back_aux();
    00855   void _M_pop_front_aux();
    00856
    00857 protected:                        // Internal insert functions
    00858
    00859 #ifdef __STL_MEMBER_TEMPLATES
    00860
    00861   template <class _InputIterator>
    00862   void insert(iterator __pos, _InputIterator __first, _InputIterator __last,
    00863               input_iterator_tag);
    00864
    00865   template <class _ForwardIterator>
    00866   void insert(iterator __pos,
    00867               _ForwardIterator __first, _ForwardIterator __last,
    00868               forward_iterator_tag);
    00869
    00870 #endif /* __STL_MEMBER_TEMPLATES */
    00871
    00872   iterator _M_insert_aux(iterator __pos, const value_type& __x);
    00873   iterator _M_insert_aux(iterator __pos);
    00874   void _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
    00875
    00876 #ifdef __STL_MEMBER_TEMPLATES
    00877
    00878   template <class _ForwardIterator>
    00879   void _M_insert_aux(iterator __pos,
    00880                      _ForwardIterator __first, _ForwardIterator __last,
    00881                      size_type __n);
    00882
    00883 #else /* __STL_MEMBER_TEMPLATES */
    00884
    00885   void _M_insert_aux(iterator __pos,
    00886                      const value_type* __first, const value_type* __last,
    00887                      size_type __n);
    00888
    00889   void _M_insert_aux(iterator __pos,
    00890                      const_iterator __first, const_iterator __last,
    00891                      size_type __n);
    00892
    00893 #endif /* __STL_MEMBER_TEMPLATES */
    00894
    00895   iterator _M_reserve_elements_at_front(size_type __n) {
    00896     size_type __vacancies = _M_start._M_cur - _M_start._M_first;
    00897     if (__n > __vacancies)
    00898       _M_new_elements_at_front(__n - __vacancies);
    00899     return _M_start - difference_type(__n);
    00900   }
    00901
    00902   iterator _M_reserve_elements_at_back(size_type __n) {
    00903     size_type __vacancies = (_M_finish._M_last - _M_finish._M_cur) - 1;
    00904     if (__n > __vacancies)
    00905       _M_new_elements_at_back(__n - __vacancies);
    00906     return _M_finish + difference_type(__n);
    00907   }
    00908
    00909   void _M_new_elements_at_front(size_type __new_elements);
    00910   void _M_new_elements_at_back(size_type __new_elements);
    00911
    00912 protected:                      // Allocation of _M_map and nodes
    00913
    00914   // Makes sure the _M_map has space for new nodes.  Does not actually
    00915   //  add the nodes.  Can invalidate _M_map pointers.  (And consequently,
    00916   //  deque iterators.)
    00917
    00918   void _M_reserve_map_at_back (size_type __nodes_to_add = 1) {
    00919     if (__nodes_to_add + 1 > _M_map_size - (_M_finish._M_node - _M_map))
    00920       _M_reallocate_map(__nodes_to_add, false);
    00921   }
    00922
    00923   void _M_reserve_map_at_front (size_type __nodes_to_add = 1) {
    00924     if (__nodes_to_add > size_type(_M_start._M_node - _M_map))
    00925       _M_reallocate_map(__nodes_to_add, true);
    00926   }
    00927
    00928   void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
    00929
    00930 #ifdef __STL_NON_TYPE_TMPL_PARAM_BUG
    00931 public:
    00932   bool operator==(const deque<_Tp,_Alloc,0>& __x) const {
    00933     return size() == __x.size() && equal(begin(), end(), __x.begin());
    00934   }
    00935   bool operator!=(const deque<_Tp,_Alloc,0>& __x) const {
    00936     return size() != __x.size() || !equal(begin(), end(), __x.begin());
    00937   }
    00938   bool operator<(const deque<_Tp,_Alloc,0>& __x) const {
    00939     return lexicographical_compare(begin(), end(), __x.begin(), __x.end());
    00940   }
    00941 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */
    00942 };
    00943
    00944 // Non-inline member functions
    00945
    00946 #ifdef __STL_MEMBER_TEMPLATES
    00947
    00948 template <class _Tp, class _Alloc, size_t __bufsize>
    00949 template <class _InputIter>
    00950 void deque<_Tp, _Alloc, __bufsize>
    00951   ::_M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag)
    00952 {
    00953   iterator __cur = begin();
    00954   for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
    00955     *__cur = *__first;
    00956   if (__first == __last)
    00957     erase(__cur, end());
    00958   else
    00959     insert(end(), __first, __last);
    00960 }
    00961
    00962 #endif /* __STL_MEMBER_TEMPLATES */
    00963
    00964 template <class _Tp, class _Alloc, size_t __bufsize>
    00965 void
    00966 deque<_Tp, _Alloc, __bufsize>::insert(iterator __pos,
    00967                                       size_type __n, const value_type& __x)
    00968 {
    00969   if (__pos._M_cur == _M_start._M_cur) {
    00970     iterator __new_start = _M_reserve_elements_at_front(__n);
    00971     uninitialized_fill(__new_start, _M_start, __x);
    00972     _M_start = __new_start;
    00973   }
    00974   else if (__pos._M_cur == _M_finish._M_cur) {
    00975     iterator __new_finish = _M_reserve_elements_at_back(__n);
    00976     uninitialized_fill(_M_finish, __new_finish, __x);
    00977     _M_finish = __new_finish;
    00978   }
    00979   else
    00980     _M_insert_aux(__pos, __n, __x);
    00981 }
    00982
    00983 #ifndef __STL_MEMBER_TEMPLATES
    00984
    00985 template <class _Tp, class _Alloc, size_t __bufsize>
    00986 void deque<_Tp, _Alloc, __bufsize>::insert(iterator __pos,
    00987                                            const value_type* __first,
    00988                                            const value_type* __last) {
    00989   size_type __n = __last - __first;
    00990   if (__pos._M_cur == _M_start._M_cur) {
    00991     iterator __new_start = _M_reserve_elements_at_front(__n);
    00992     __STL_TRY {
    00993       uninitialized_copy(__first, __last, __new_start);
    00994       _M_start = __new_start;
    00995     }
    00996     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
    00997   }
    00998   else if (__pos._M_cur == _M_finish._M_cur) {
    00999     iterator __new_finish = _M_reserve_elements_at_back(__n);
    01000     __STL_TRY {
    01001       uninitialized_copy(__first, __last, _M_finish);
    01002       _M_finish = __new_finish;
    01003     }
    01004     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
    01005                                   __new_finish._M_node + 1));
    01006   }
    01007   else
    01008     _M_insert_aux(__pos, __first, __last, __n);
    01009 }
    01010
    01011 template <class _Tp, class _Alloc, size_t __bufsize>
    01012 void deque<_Tp,_Alloc,__bufsize>::insert(iterator __pos,
    01013                                          const_iterator __first,
    01014                                          const_iterator __last)
    01015 {
    01016   size_type __n = __last - __first;
    01017   if (__pos._M_cur == _M_start._M_cur) {
    01018     iterator __new_start = _M_reserve_elements_at_front(__n);
    01019     __STL_TRY {
    01020       uninitialized_copy(__first, __last, __new_start);
    01021       _M_start = __new_start;
    01022     }
    01023     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
    01024   }
    01025   else if (__pos._M_cur == _M_finish._M_cur) {
    01026     iterator __new_finish = _M_reserve_elements_at_back(__n);
    01027     __STL_TRY {
    01028       uninitialized_copy(__first, __last, _M_finish);
    01029       _M_finish = __new_finish;
    01030     }
    01031     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
    01032                  __new_finish._M_node + 1));
    01033   }
    01034   else
    01035     _M_insert_aux(__pos, __first, __last, __n);
    01036 }
    01037
    01038 #endif /* __STL_MEMBER_TEMPLATES */
    01039
    01040 template <class _Tp, class _Alloc, size_t __bufsize>
    01041 deque<_Tp,_Alloc,__bufsize>::iterator
    01042 deque<_Tp,_Alloc,__bufsize>::erase(iterator __first, iterator __last)
    01043 {
    01044   if (__first == _M_start && __last == _M_finish) {
    01045     clear();
    01046     return _M_finish;
    01047   }
    01048   else {
    01049     difference_type __n = __last - __first;
    01050     difference_type __elems_before = __first - _M_start;
    01051     if (static_cast<size_type>(__elems_before) < (size() - __n) / 2) {
    01052       copy_backward(_M_start, __first, __last);
    01053       iterator __new_start = _M_start + __n;
    01054       destroy(_M_start, __new_start);
    01055       _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
    01056       _M_start = __new_start;
    01057     }
    01058     else {
    01059       copy(__last, _M_finish, __first);
    01060       iterator __new_finish = _M_finish - __n;
    01061       destroy(__new_finish, _M_finish);
    01062       _M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1);
    01063       _M_finish = __new_finish;
    01064     }
    01065     return _M_start + __elems_before;
    01066   }
    01067 }
    01068
    01069 template <class _Tp, class _Alloc, size_t __bufsize>
    01070 void deque<_Tp,_Alloc,__bufsize>::clear()
    01071 {
    01072   for (_Map_pointer __node = _M_start._M_node + 1;
    01073        __node < _M_finish._M_node;
    01074        ++__node) {
    01075     destroy(*__node, *__node + _S_buffer_size());
    01076     _M_deallocate_node(*__node);
    01077   }
    01078
    01079   if (_M_start._M_node != _M_finish._M_node) {
    01080     destroy(_M_start._M_cur, _M_start._M_last);
    01081     destroy(_M_finish._M_first, _M_finish._M_cur);
    01082     _M_deallocate_node(_M_finish._M_first);
    01083   }
    01084   else
    01085     destroy(_M_start._M_cur, _M_finish._M_cur);
    01086
    01087   _M_finish = _M_start;
    01088 }
    01089
    01090 // Precondition: _M_start and _M_finish have already been initialized,
    01091 // but none of the deque's elements have yet been constructed.
    01092 template <class _Tp, class _Alloc, size_t __bufsize>
    01093 void
    01094 deque<_Tp,_Alloc,__bufsize>::_M_fill_initialize(const value_type& __value) {
    01095   _Map_pointer __cur;
    01096   __STL_TRY {
    01097     for (__cur = _M_start._M_node; __cur < _M_finish._M_node; ++__cur)
    01098       uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value);
    01099     uninitialized_fill(_M_finish._M_first, _M_finish._M_cur, __value);
    01100   }
    01101   __STL_UNWIND(destroy(_M_start, iterator(*__cur, __cur)));
    01102 }
    01103
    01104 #ifdef __STL_MEMBER_TEMPLATES
    01105
    01106 template <class _Tp, class _Alloc, size_t __bufsize>
    01107 template <class _InputIterator>
    01108 void
    01109 deque<_Tp,_Alloc,__bufsize>::_M_range_initialize(_InputIterator __first,
    01110                                                  _InputIterator __last,
    01111                                                  input_iterator_tag)
    01112 {
    01113   _M_initialize_map(0);
    01114   for ( ; __first != __last; ++__first)
    01115     push_back(*__first);
    01116 }
    01117
    01118 template <class _Tp, class _Alloc, size_t __bufsize>
    01119 template <class _ForwardIterator>
    01120 void
    01121 deque<_Tp,_Alloc,__bufsize>::_M_range_initialize(_ForwardIterator __first,
    01122                                                  _ForwardIterator __last,
    01123                                                  forward_iterator_tag)
    01124 {
    01125   size_type __n = 0;
    01126   distance(__first, __last, __n);
    01127   _M_initialize_map(__n);
    01128
    01129   _Map_pointer __cur_node;
    01130   __STL_TRY {
    01131     for (__cur_node = _M_start._M_node;
    01132          __cur_node < _M_finish._M_node;
    01133          ++__cur_node) {
    01134       _ForwardIterator __mid = __first;
    01135       advance(__mid, _S_buffer_size());
    01136       uninitialized_copy(__first, __mid, *__cur_node);
    01137       __first = __mid;
    01138     }
    01139     uninitialized_copy(__first, __last, _M_finish._M_first);
    01140   }
    01141   __STL_UNWIND(destroy(_M_start, iterator(*__cur_node, __cur_node)));
    01142 }
    01143
    01144 #endif /* __STL_MEMBER_TEMPLATES */
    01145
    01146 // Called only if _M_finish._M_cur == _M_finish._M_last - 1.
    01147 template <class _Tp, class _Alloc, size_t __bufsize>
    01148 void
    01149 deque<_Tp,_Alloc,__bufsize>::_M_push_back_aux(const value_type& __t)
    01150 {
    01151   value_type __t_copy = __t;
    01152   _M_reserve_map_at_back();
    01153   *(_M_finish._M_node + 1) = _M_allocate_node();
    01154   __STL_TRY {
    01155     construct(_M_finish._M_cur, __t_copy);
    01156     _M_finish._M_set_node(_M_finish._M_node + 1);
    01157     _M_finish._M_cur = _M_finish._M_first;
    01158   }
    01159   __STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1)));
    01160 }
    01161
    01162 // Called only if _M_finish._M_cur == _M_finish._M_last - 1.
    01163 template <class _Tp, class _Alloc, size_t __bufsize>
    01164 void
    01165 deque<_Tp,_Alloc,__bufsize>::_M_push_back_aux()
    01166 {
    01167   _M_reserve_map_at_back();
    01168   *(_M_finish._M_node + 1) = _M_allocate_node();
    01169   __STL_TRY {
    01170     construct(_M_finish._M_cur);
    01171     _M_finish._M_set_node(_M_finish._M_node + 1);
    01172     _M_finish._M_cur = _M_finish._M_first;
    01173   }
    01174   __STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1)));
    01175 }
    01176
    01177 // Called only if _M_start._M_cur == _M_start._M_first.
    01178 template <class _Tp, class _Alloc, size_t __bufsize>
    01179 void
    01180 deque<_Tp,_Alloc,__bufsize>::_M_push_front_aux(const value_type& __t)
    01181 {
    01182   value_type __t_copy = __t;
    01183   _M_reserve_map_at_front();
    01184   *(_M_start._M_node - 1) = _M_allocate_node();
    01185   __STL_TRY {
    01186     _M_start._M_set_node(_M_start._M_node - 1);
    01187     _M_start._M_cur = _M_start._M_last - 1;
    01188     construct(_M_start._M_cur, __t_copy);
    01189   }
    01190   __STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1))));
    01191 }
    01192
    01193 // Called only if _M_start._M_cur == _M_start._M_first.
    01194 template <class _Tp, class _Alloc, size_t __bufsize>
    01195 void
    01196 deque<_Tp,_Alloc,__bufsize>::_M_push_front_aux()
    01197 {
    01198   _M_reserve_map_at_front();
    01199   *(_M_start._M_node - 1) = _M_allocate_node();
    01200   __STL_TRY {
    01201     _M_start._M_set_node(_M_start._M_node - 1);
    01202     _M_start._M_cur = _M_start._M_last - 1;
    01203     construct(_M_start._M_cur);
    01204   }
    01205   __STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1))));
    01206 }
    01207
    01208 // Called only if _M_finish._M_cur == _M_finish._M_first.
    01209 template <class _Tp, class _Alloc, size_t __bufsize>
    01210 void
    01211 deque<_Tp,_Alloc,__bufsize>::_M_pop_back_aux()
    01212 {
    01213   _M_deallocate_node(_M_finish._M_first);
    01214   _M_finish._M_set_node(_M_finish._M_node - 1);
    01215   _M_finish._M_cur = _M_finish._M_last - 1;
    01216   destroy(_M_finish._M_cur);
    01217 }
    01218
    01219 // Called only if _M_start._M_cur == _M_start._M_last - 1.  Note that
    01220 // if the deque has at least one element (a precondition for this member
    01221 // function), and if _M_start._M_cur == _M_start._M_last, then the deque
    01222 // must have at least two nodes.
    01223 template <class _Tp, class _Alloc, size_t __bufsize>
    01224 void
    01225 deque<_Tp,_Alloc,__bufsize>::_M_pop_front_aux()
    01226 {
    01227   destroy(_M_start._M_cur);
    01228   _M_deallocate_node(_M_start._M_first);
    01229   _M_start._M_set_node(_M_start._M_node + 1);
    01230   _M_start._M_cur = _M_start._M_first;
    01231 }
    01232
    01233 #ifdef __STL_MEMBER_TEMPLATES
    01234
    01235 template <class _Tp, class _Alloc, size_t __bufsize>
    01236 template <class _InputIterator>
    01237 void
    01238 deque<_Tp,_Alloc,__bufsize>::insert(iterator __pos,
    01239                                     _InputIterator __first,
    01240                                     _InputIterator __last,
    01241                                     input_iterator_tag)
    01242 {
    01243   copy(__first, __last, inserter(*this, __pos));
    01244 }
    01245
    01246 template <class _Tp, class _Alloc, size_t __bufsize>
    01247 template <class _ForwardIterator>
    01248 void
    01249 deque<_Tp,_Alloc,__bufsize>::insert(iterator __pos,
    01250                                     _ForwardIterator __first,
    01251                                     _ForwardIterator __last,
    01252                                     forward_iterator_tag) {
    01253   size_type __n = 0;
    01254   distance(__first, __last, __n);
    01255   if (__pos._M_cur == _M_start._M_cur) {
    01256     iterator __new_start = _M_reserve_elements_at_front(__n);
    01257     __STL_TRY {
    01258       uninitialized_copy(__first, __last, __new_start);
    01259       _M_start = __new_start;
    01260     }
    01261     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
    01262   }
    01263   else if (__pos._M_cur == _M_finish._M_cur) {
    01264     iterator __new_finish = _M_reserve_elements_at_back(__n);
    01265     __STL_TRY {
    01266       uninitialized_copy(__first, __last, _M_finish);
    01267       _M_finish = __new_finish;
    01268     }
    01269     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
    01270                                   __new_finish._M_node + 1));
    01271   }
    01272   else
    01273     _M_insert_aux(__pos, __first, __last, __n);
    01274 }
    01275
    01276 #endif /* __STL_MEMBER_TEMPLATES */
    01277
    01278 template <class _Tp, class _Alloc, size_t __bufsize>
    01279 typename deque<_Tp, _Alloc, __bufsize>::iterator
    01280 deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos,
    01281                                            const value_type& __x)
    01282 {
    01283   difference_type __index = __pos - _M_start;
    01284   value_type __x_copy = __x;
    01285   if (static_cast<size_type>(__index) < size() / 2) {
    01286     push_front(front());
    01287     iterator __front1 = _M_start;
    01288     ++__front1;
    01289     iterator __front2 = __front1;
    01290     ++__front2;
    01291     __pos = _M_start + __index;
    01292     iterator __pos1 = __pos;
    01293     ++__pos1;
    01294     copy(__front2, __pos1, __front1);
    01295   }
    01296   else {
    01297     push_back(back());
    01298     iterator __back1 = _M_finish;
    01299     --__back1;
    01300     iterator __back2 = __back1;
    01301     --__back2;
    01302     __pos = _M_start + __index;
    01303     copy_backward(__pos, __back2, __back1);
    01304   }
    01305   *__pos = __x_copy;
    01306   return __pos;
    01307 }
    01308
    01309 template <class _Tp, class _Alloc, size_t __bufsize>
    01310 typename deque<_Tp,_Alloc,__bufsize>::iterator
    01311 deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos)
    01312 {
    01313   difference_type __index = __pos - _M_start;
    01314   if (static_cast<size_type>(__index) < size() / 2) {
    01315     push_front(front());
    01316     iterator __front1 = _M_start;
    01317     ++__front1;
    01318     iterator __front2 = __front1;
    01319     ++__front2;
    01320     __pos = _M_start + __index;
    01321     iterator __pos1 = __pos;
    01322     ++__pos1;
    01323     copy(__front2, __pos1, __front1);
    01324   }
    01325   else {
    01326     push_back(back());
    01327     iterator __back1 = _M_finish;
    01328     --__back1;
    01329     iterator __back2 = __back1;
    01330     --__back2;
    01331     __pos = _M_start + __index;
    01332     copy_backward(__pos, __back2, __back1);
    01333   }
    01334   *__pos = value_type();
    01335   return __pos;
    01336 }
    01337
    01338 template <class _Tp, class _Alloc, size_t __bufsize>
    01339 void
    01340 deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos,
    01341                                            size_type __n,
    01342                                            const value_type& __x)
    01343 {
    01344   const difference_type __elems_before = __pos - _M_start;
    01345   size_type __length = size();
    01346   value_type __x_copy = __x;
    01347   if (static_cast<size_type>(__elems_before) < __length / 2) {
    01348     iterator __new_start = _M_reserve_elements_at_front(__n);
    01349     iterator __old_start = _M_start;
    01350     __pos = _M_start + __elems_before;
    01351     __STL_TRY {
    01352       if (__elems_before >= difference_type(__n)) {
    01353         iterator __start_n = _M_start + difference_type(__n);
    01354         uninitialized_copy(_M_start, __start_n, __new_start);
    01355         _M_start = __new_start;
    01356         copy(__start_n, __pos, __old_start);
    01357         fill(__pos - difference_type(__n), __pos, __x_copy);
    01358       }
    01359       else {
    01360         __uninitialized_copy_fill(_M_start, __pos, __new_start,
    01361                                   _M_start, __x_copy);
    01362         _M_start = __new_start;
    01363         fill(__old_start, __pos, __x_copy);
    01364       }
    01365     }
    01366     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
    01367   }
    01368   else {
    01369     iterator __new_finish = _M_reserve_elements_at_back(__n);
    01370     iterator __old_finish = _M_finish;
    01371     const difference_type __elems_after =
    01372       difference_type(__length) - __elems_before;
    01373     __pos = _M_finish - __elems_after;
    01374     __STL_TRY {
    01375       if (__elems_after > difference_type(__n)) {
    01376         iterator __finish_n = _M_finish - difference_type(__n);
    01377         uninitialized_copy(__finish_n, _M_finish, _M_finish);
    01378         _M_finish = __new_finish;
    01379         copy_backward(__pos, __finish_n, __old_finish);
    01380         fill(__pos, __pos + difference_type(__n), __x_copy);
    01381       }
    01382       else {
    01383         __uninitialized_fill_copy(_M_finish, __pos + difference_type(__n),
    01384                                   __x_copy, __pos, _M_finish);
    01385         _M_finish = __new_finish;
    01386         fill(__pos, __old_finish, __x_copy);
    01387       }
    01388     }
    01389     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
    01390                                   __new_finish._M_node + 1));
    01391   }
    01392 }
    01393
    01394 #ifdef __STL_MEMBER_TEMPLATES
    01395
    01396 template <class _Tp, class _Alloc, size_t __bufsize>
    01397 template <class _ForwardIterator>
    01398 void
    01399 deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos,
    01400                                            _ForwardIterator __first,
    01401                                            _ForwardIterator __last,
    01402                                            size_type __n)
    01403 {
    01404   const difference_type __elemsbefore = __pos - _M_start;
    01405   size_type __length = size();
    01406   if (static_cast<size_type>(__elemsbefore) < __length / 2) {
    01407     iterator __new_start = _M_reserve_elements_at_front(__n);
    01408     iterator __old_start = _M_start;
    01409     __pos = _M_start + __elemsbefore;
    01410     __STL_TRY {
    01411       if (__elemsbefore >= difference_type(__n)) {
    01412         iterator __start_n = _M_start + difference_type(__n);
    01413         uninitialized_copy(_M_start, __start_n, __new_start);
    01414         _M_start = __new_start;
    01415         copy(__start_n, __pos, __old_start);
    01416         copy(__first, __last, __pos - difference_type(__n));
    01417       }
    01418       else {
    01419         _ForwardIterator __mid = __first;
    01420         advance(__mid, difference_type(__n) - __elemsbefore);
    01421         __uninitialized_copy_copy(_M_start, __pos, __first, __mid,
    01422                                   __new_start);
    01423         _M_start = __new_start;
    01424         copy(__mid, __last, __old_start);
    01425       }
    01426     }
    01427     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
    01428   }
    01429   else {
    01430     iterator __new_finish = _M_reserve_elements_at_back(__n);
    01431     iterator __old_finish = _M_finish;
    01432     const difference_type __elemsafter =
    01433       difference_type(__length) - __elemsbefore;
    01434     __pos = _M_finish - __elemsafter;
    01435     __STL_TRY {
    01436       if (__elemsafter > difference_type(__n)) {
    01437         iterator __finish_n = _M_finish - difference_type(__n);
    01438         uninitialized_copy(__finish_n, _M_finish, _M_finish);
    01439         _M_finish = __new_finish;
    01440         copy_backward(__pos, __finish_n, __old_finish);
    01441         copy(__first, __last, __pos);
    01442       }
    01443       else {
    01444         _ForwardIterator __mid = __first;
    01445         advance(__mid, __elemsafter);
    01446         __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);
    01447         _M_finish = __new_finish;
    01448         copy(__first, __mid, __pos);
    01449       }
    01450     }
    01451     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
    01452                                   __new_finish._M_node + 1));
    01453   }
    01454 }
    01455
    01456 #else /* __STL_MEMBER_TEMPLATES */
    01457
    01458 template <class _Tp, class _Alloc, size_t __bufsize>
    01459 void
    01460 deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos,
    01461                                            const value_type* __first,
    01462                                            const value_type* __last,
    01463                                            size_type __n)
    01464 {
    01465   const difference_type __elemsbefore = __pos - _M_start;
    01466   size_type __length = size();
    01467   if (__elemsbefore < __length / 2) {
    01468     iterator __new_start = _M_reserve_elements_at_front(__n);
    01469     iterator __old_start = _M_start;
    01470     __pos = _M_start + __elemsbefore;
    01471     __STL_TRY {
    01472       if (__elemsbefore >= difference_type(__n)) {
    01473         iterator __start_n = _M_start + difference_type(__n);
    01474         uninitialized_copy(_M_start, __start_n, __new_start);
    01475         _M_start = __new_start;
    01476         copy(__start_n, __pos, __old_start);
    01477         copy(__first, __last, __pos - difference_type(__n));
    01478       }
    01479       else {
    01480         const value_type* __mid =
    01481           __first + (difference_type(__n) - __elemsbefore);
    01482         __uninitialized_copy_copy(_M_start, __pos, __first, __mid,
    01483                                   __new_start);
    01484         _M_start = __new_start;
    01485         copy(__mid, __last, __old_start);
    01486       }
    01487     }
    01488     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
    01489   }
    01490   else {
    01491     iterator __new_finish = _M_reserve_elements_at_back(__n);
    01492     iterator __old_finish = _M_finish;
    01493     const difference_type __elemsafter =
    01494       difference_type(__length) - __elemsbefore;
    01495     __pos = _M_finish - __elemsafter;
    01496     __STL_TRY {
    01497       if (__elemsafter > difference_type(__n)) {
    01498         iterator __finish_n = _M_finish - difference_type(__n);
    01499         uninitialized_copy(__finish_n, _M_finish, _M_finish);
    01500         _M_finish = __new_finish;
    01501         copy_backward(__pos, __finish_n, __old_finish);
    01502         copy(__first, __last, __pos);
    01503       }
    01504       else {
    01505         const value_type* __mid = __first + __elemsafter;
    01506         __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);
    01507         _M_finish = __new_finish;
    01508         copy(__first, __mid, __pos);
    01509       }
    01510     }
    01511     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
    01512                                   __new_finish._M_node + 1));
    01513   }
    01514 }
    01515
    01516 template <class _Tp, class _Alloc, size_t __bufsize>
    01517 void
    01518 deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos,
    01519                                            const_iterator __first,
    01520                                            const_iterator __last,
    01521                                            size_type __n)
    01522 {
    01523   const difference_type __elemsbefore = __pos - _M_start;
    01524   size_type __length = size();
    01525   if (__elemsbefore < __length / 2) {
    01526     iterator __new_start = _M_reserve_elements_at_front(__n);
    01527     iterator __old_start = _M_start;
    01528     __pos = _M_start + __elemsbefore;
    01529     __STL_TRY {
    01530       if (__elemsbefore >= __n) {
    01531         iterator __start_n = _M_start + __n;
    01532         uninitialized_copy(_M_start, __start_n, __new_start);
    01533         _M_start = __new_start;
    01534         copy(__start_n, __pos, __old_start);
    01535         copy(__first, __last, __pos - difference_type(__n));
    01536       }
    01537       else {
    01538         const_iterator __mid = __first + (__n - __elemsbefore);
    01539         __uninitialized_copy_copy(_M_start, __pos, __first, __mid,
    01540                                   __new_start);
    01541         _M_start = __new_start;
    01542         copy(__mid, __last, __old_start);
    01543       }
    01544     }
    01545     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
    01546   }
    01547   else {
    01548     iterator __new_finish = _M_reserve_elements_at_back(__n);
    01549     iterator __old_finish = _M_finish;
    01550     const difference_type __elemsafter = __length - __elemsbefore;
    01551     __pos = _M_finish - __elemsafter;
    01552     __STL_TRY {
    01553       if (__elemsafter > __n) {
    01554         iterator __finish_n = _M_finish - difference_type(__n);
    01555         uninitialized_copy(__finish_n, _M_finish, _M_finish);
    01556         _M_finish = __new_finish;
    01557         copy_backward(__pos, __finish_n, __old_finish);
    01558         copy(__first, __last, __pos);
    01559       }
    01560       else {
    01561         const_iterator __mid = __first + __elemsafter;
    01562         __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);
    01563         _M_finish = __new_finish;
    01564         copy(__first, __mid, __pos);
    01565       }
    01566     }
    01567     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
    01568                  __new_finish._M_node + 1));
    01569   }
    01570 }
    01571
    01572 #endif /* __STL_MEMBER_TEMPLATES */
    01573
    01574 template <class _Tp, class _Alloc, size_t __bufsize>
    01575 void
    01576 deque<_Tp,_Alloc,__bufsize>::_M_new_elements_at_front(size_type __new_elems)
    01577 {
    01578   size_type __new_nodes
    01579       = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
    01580   _M_reserve_map_at_front(__new_nodes);
    01581   size_type __i;
    01582   __STL_TRY {
    01583     for (__i = 1; __i <= __new_nodes; ++__i)
    01584       *(_M_start._M_node - __i) = _M_allocate_node();
    01585   }
    01586 #       ifdef __STL_USE_EXCEPTIONS
    01587   catch(...) {
    01588     for (size_type __j = 1; __j < __i; ++__j)
    01589       _M_deallocate_node(*(_M_start._M_node - __j));
    01590     throw;
    01591   }
    01592 #       endif /* __STL_USE_EXCEPTIONS */
    01593 }
    01594
    01595 template <class _Tp, class _Alloc, size_t __bufsize>
    01596 void
    01597 deque<_Tp,_Alloc,__bufsize>::_M_new_elements_at_back(size_type __new_elems)
    01598 {
    01599   size_type __new_nodes
    01600       = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
    01601   _M_reserve_map_at_back(__new_nodes);
    01602   size_type __i;
    01603   __STL_TRY {
    01604     for (__i = 1; __i <= __new_nodes; ++__i)
    01605       *(_M_finish._M_node + __i) = _M_allocate_node();
    01606   }
    01607 #       ifdef __STL_USE_EXCEPTIONS
    01608   catch(...) {
    01609     for (size_type __j = 1; __j < __i; ++__j)
    01610       _M_deallocate_node(*(_M_finish._M_node + __j));
    01611     throw;
    01612   }
    01613 #       endif /* __STL_USE_EXCEPTIONS */
    01614 }
    01615
    01616 template <class _Tp, class _Alloc, size_t __bufsize>
    01617 void
    01618 deque<_Tp,_Alloc,__bufsize>::_M_reallocate_map(size_type __nodes_to_add,
    01619                                               bool __add_at_front)
    01620 {
    01621   size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1;
    01622   size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
    01623
    01624   _Map_pointer __new_nstart;
    01625   if (_M_map_size > 2 * __new_num_nodes) {
    01626     __new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2
    01627                      + (__add_at_front ? __nodes_to_add : 0);
    01628     if (__new_nstart < _M_start._M_node)
    01629       copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
    01630     else
    01631       copy_backward(_M_start._M_node, _M_finish._M_node + 1,
    01632                     __new_nstart + __old_num_nodes);
    01633   }
    01634   else {
    01635     size_type __new_map_size =
    01636       _M_map_size + max(_M_map_size, __nodes_to_add) + 2;
    01637
    01638     _Map_pointer __new_map = _M_allocate_map(__new_map_size);
    01639     __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
    01640                          + (__add_at_front ? __nodes_to_add : 0);
    01641     copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
    01642     _M_deallocate_map(_M_map, _M_map_size);
    01643
    01644     _M_map = __new_map;
    01645     _M_map_size = __new_map_size;
    01646   }
    01647
    01648   _M_start._M_set_node(__new_nstart);
    01649   _M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
    01650 }
    01651
    01652
    01653 // Nonmember functions.
    01654
    01655 #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
    01656
    01657 template <class _Tp, class _Alloc, size_t __bufsiz>
    01658 bool operator==(const deque<_Tp, _Alloc, __bufsiz>& __x,
    01659                 const deque<_Tp, _Alloc, __bufsiz>& __y)
    01660 {
    01661   return __x.size() == __y.size() &&
    01662          equal(__x.begin(), __x.end(), __y.begin());
    01663 }
    01664
    01665 template <class _Tp, class _Alloc, size_t __bufsiz>
    01666 bool operator<(const deque<_Tp, _Alloc, __bufsiz>& __x,
    01667                const deque<_Tp, _Alloc, __bufsiz>& __y)
    01668 {
    01669   return lexicographical_compare(__x.begin(), __x.end(),
    01670                                  __y.begin(), __y.end());
    01671 }
    01672
    01673 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */
    01674
    01675 #if defined(__STL_FUNCTION_TMPL_PARTIAL_ORDER) && \
    01676     !defined(__STL_NON_TYPE_TMPL_PARAM_BUG)
    01677
    01678 template <class _Tp, class _Alloc, size_t __bufsiz>
    01679 inline void
    01680 swap(deque<_Tp,_Alloc,__bufsiz>& __x, deque<_Tp,_Alloc,__bufsiz>& __y)
    01681 {
    01682   __x.swap(__y);
    01683 }
    01684
    01685 #endif
    01686
    01687 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
    01688 #pragma reset woff 1174
    01689 #pragma reset woff 1375
    01690 #endif
    01691
    01692 __STL_END_NAMESPACE
    01693
    01694 #endif /* __SGI_STL_INTERNAL_DEQUE_H */
    01695
    01696 // Local Variables:
    01697 // mode:C++
    01698 // End: