reactos/include/c++/stlport/stl/_deque.h

   1 /*
   2  *
   3  * Copyright (c) 1994
   4  * Hewlett-Packard Company
   5  *
   6  * Copyright (c) 1996,1997
   7  * Silicon Graphics Computer Systems, Inc.
   8  *
   9  * Copyright (c) 1997
  10  * Moscow Center for SPARC Technology
  11  *
  12  * Copyright (c) 1999
  13  * Boris Fomitchev
  14  *
  15  * This material is provided "as is", with absolutely no warranty expressed
  16  * or implied. Any use is at your own risk.
  17  *
  18  * Permission to use or copy this software for any purpose is hereby granted
  19  * without fee, provided the above notices are retained on all copies.
  20  * Permission to modify the code and to distribute modified code is granted,
  21  * provided the above notices are retained, and a notice that the code was
  22  * modified is included with the above copyright notice.
  23  *
  24  */
  25
  26 /* NOTE: This is an internal header file, included by other STL headers.
  27  *   You should not attempt to use it directly.
  28  */
  29
  30 #ifndef _STLP_INTERNAL_DEQUE_H
  31 #define _STLP_INTERNAL_DEQUE_H
  32
  33 #ifndef _STLP_INTERNAL_ALGOBASE_H
  34 #  include <stl/_algobase.h>
  35 #endif
  36
  37 #ifndef _STLP_INTERNAL_ALLOC_H
  38 #  include <stl/_alloc.h>
  39 #endif
  40
  41 #ifndef _STLP_INTERNAL_ITERATOR_H
  42 #  include <stl/_iterator.h>
  43 #endif
  44
  45 #ifndef _STLP_INTERNAL_UNINITIALIZED_H
  46 #  include <stl/_uninitialized.h>
  47 #endif
  48
  49 #ifndef _STLP_RANGE_ERRORS_H
  50 #  include <stl/_range_errors.h>
  51 #endif
  52
  53 /* Class invariants:
  54  *  For any nonsingular iterator i:
  55  *    i.node is the address of an element in the map array.  The
  56  *      contents of i.node is a pointer to the beginning of a node.
  57  *    i.first == *(i.node)
  58  *    i.last  == i.first + node_size
  59  *    i.cur is a pointer in the range [i.first, i.last).  NOTE:
  60  *      the implication of this is that i.cur is always a dereferenceable
  61  *      pointer, even if i is a past-the-end iterator.
  62  *  Start and Finish are always nonsingular iterators.  NOTE: this means
  63  *    that an empty deque must have one node, and that a deque
  64  *    with N elements, where N is the buffer size, must have two nodes.
  65  *  For every node other than start.node and finish.node, every element
  66  *    in the node is an initialized object.  If start.node == finish.node,
  67  *    then [start.cur, finish.cur) are initialized objects, and
  68  *    the elements outside that range are uninitialized storage.  Otherwise,
  69  *    [start.cur, start.last) and [finish.first, finish.cur) are initialized
  70  *    objects, and [start.first, start.cur) and [finish.cur, finish.last)
  71  *    are uninitialized storage.
  72  *  [map, map + map_size) is a valid, non-empty range.
  73  *  [start.node, finish.node] is a valid range contained within
  74  *    [map, map + map_size).
  75  *  A pointer in the range [map, map + map_size) points to an allocated node
  76  *    if and only if the pointer is in the range [start.node, finish.node].
  77  */
  78
  79 _STLP_BEGIN_NAMESPACE
  80
  81 _STLP_MOVE_TO_PRIV_NAMESPACE
  82
  83 template <class _Tp>
  84 struct _Deque_iterator_base {
  85
  86   static size_t _S_buffer_size() {
  87     const size_t blocksize = _MAX_BYTES;
  88     return (sizeof(_Tp) < blocksize ? (blocksize / sizeof(_Tp)) : 1);
  89   }
  90
  91   typedef random_access_iterator_tag iterator_category;
  92
  93   typedef _Tp value_type;
  94   typedef size_t size_type;
  95   typedef ptrdiff_t difference_type;
  96
  97   typedef value_type** _Map_pointer;
  98
  99   typedef _Deque_iterator_base< _Tp > _Self;
 100
 101   value_type* _M_cur;
 102   value_type* _M_first;
 103   value_type* _M_last;
 104   _Map_pointer _M_node;
 105
 106   _Deque_iterator_base(value_type* __x, _Map_pointer __y)
 107     : _M_cur(__x), _M_first(*__y),
 108       _M_last(*__y + _S_buffer_size()), _M_node(__y) {}
 109
 110   _Deque_iterator_base() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
 111
 112 // see comment in doc/README.evc4 and doc/README.evc8
 113 #if defined (_STLP_MSVC) && (_STLP_MSVC <= 1401) && defined (MIPS) && defined (NDEBUG)
 114   _Deque_iterator_base(_Deque_iterator_base const& __other)
 115   : _M_cur(__other._M_cur), _M_first(__other._M_first),
 116     _M_last(__other._M_last), _M_node(__other._M_node) {}
 117 #endif
 118
 119   difference_type _M_subtract(const _Self& __x) const {
 120     return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +
 121       (_M_cur - _M_first) + (__x._M_last - __x._M_cur);
 122   }
 123
 124   void _M_increment() {
 125     if (++_M_cur == _M_last) {
 126       _M_set_node(_M_node + 1);
 127       _M_cur = _M_first;
 128     }
 129   }
 130
 131   void _M_decrement() {
 132     if (_M_cur == _M_first) {
 133       _M_set_node(_M_node - 1);
 134       _M_cur = _M_last;
 135     }
 136     --_M_cur;
 137   }
 138
 139   void _M_advance(difference_type __n) {
 140     const size_t buffersize = _S_buffer_size();
 141     difference_type __offset = __n + (_M_cur - _M_first);
 142     if (__offset >= 0 && __offset < difference_type(buffersize))
 143       _M_cur += __n;
 144     else {
 145       difference_type __node_offset =
 146         __offset > 0 ? __offset / buffersize
 147                    : -difference_type((-__offset - 1) / buffersize) - 1;
 148       _M_set_node(_M_node + __node_offset);
 149       _M_cur = _M_first +
 150
 151         (__offset - __node_offset * difference_type(buffersize));
 152     }
 153   }
 154
 155   void _M_set_node(_Map_pointer __new_node) {
 156     _M_last = (_M_first = *(_M_node = __new_node)) + difference_type(_S_buffer_size());
 157   }
 158 };
 159
 160
 161 template <class _Tp, class _Traits>
 162 struct _Deque_iterator : public _Deque_iterator_base< _Tp> {
 163   typedef random_access_iterator_tag iterator_category;
 164   typedef _Tp value_type;
 165   typedef typename _Traits::reference  reference;
 166   typedef typename _Traits::pointer    pointer;
 167   typedef size_t size_type;
 168   typedef ptrdiff_t difference_type;
 169   typedef value_type** _Map_pointer;
 170
 171   typedef _Deque_iterator_base< _Tp > _Base;
 172   typedef _Deque_iterator<_Tp, _Traits> _Self;
 173   typedef typename _Traits::_NonConstTraits     _NonConstTraits;
 174   typedef _Deque_iterator<_Tp, _NonConstTraits> iterator;
 175   typedef typename _Traits::_ConstTraits        _ConstTraits;
 176   typedef _Deque_iterator<_Tp, _ConstTraits>    const_iterator;
 177
 178   _Deque_iterator(value_type* __x, _Map_pointer __y) :
 179     _Deque_iterator_base<value_type>(__x,__y) {}
 180
 181   _Deque_iterator() {}
 182   //copy constructor for iterator and constructor from iterator for const_iterator
 183   _Deque_iterator(const iterator& __x) :
 184     _Deque_iterator_base<value_type>(__x) {}
 185
 186   reference operator*() const {
 187     return *this->_M_cur;
 188   }
 189
 190   _STLP_DEFINE_ARROW_OPERATOR
 191
 192   difference_type operator-(const const_iterator& __x) const { return this->_M_subtract(__x); }
 193
 194   _Self& operator++() { this->_M_increment(); return *this; }
 195   _Self operator++(int)  {
 196     _Self __tmp = *this;
 197     ++*this;
 198     return __tmp;
 199   }
 200
 201   _Self& operator--() { this->_M_decrement(); return *this; }
 202   _Self operator--(int) {
 203     _Self __tmp = *this;
 204     --*this;
 205     return __tmp;
 206   }
 207
 208   _Self& operator+=(difference_type __n) { this->_M_advance(__n); return *this; }
 209   _Self operator+(difference_type __n) const {
 210     _Self __tmp = *this;
 211     return __tmp += __n;
 212   }
 213
 214   _Self& operator-=(difference_type __n) { return *this += -__n; }
 215   _Self operator-(difference_type __n) const {
 216     _Self __tmp = *this;
 217     return __tmp -= __n;
 218   }
 219
 220   reference operator[](difference_type __n) const { return *(*this + __n); }
 221 };
 222
 223
 224 template <class _Tp, class _Traits>
 225 inline _Deque_iterator<_Tp, _Traits> _STLP_CALL
 226 operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Traits>& __x)
 227 { return __x + __n; }
 228
 229
 230 #if defined (_STLP_USE_SEPARATE_RELOPS_NAMESPACE)
 231 template <class _Tp>
 232 inline bool _STLP_CALL
 233 operator==(const _Deque_iterator_base<_Tp >& __x,
 234            const _Deque_iterator_base<_Tp >& __y)
 235 { return __x._M_cur == __y._M_cur; }
 236
 237 template <class _Tp>
 238 inline bool _STLP_CALL
 239 operator < (const _Deque_iterator_base<_Tp >& __x,
 240             const _Deque_iterator_base<_Tp >& __y) {
 241   return (__x._M_node == __y._M_node) ?
 242     (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
 243 }
 244
 245 template <class _Tp>
 246 inline bool _STLP_CALL
 247 operator!=(const _Deque_iterator_base<_Tp >& __x,
 248            const _Deque_iterator_base<_Tp >& __y)
 249 { return __x._M_cur != __y._M_cur; }
 250
 251 template <class _Tp>
 252 inline bool _STLP_CALL
 253 operator>(const _Deque_iterator_base<_Tp >& __x,
 254           const _Deque_iterator_base<_Tp >& __y)
 255 { return __y < __x; }
 256
 257 template <class _Tp>
 258 inline bool  _STLP_CALL operator>=(const _Deque_iterator_base<_Tp >& __x,
 259                                    const _Deque_iterator_base<_Tp >& __y)
 260 { return !(__x < __y); }
 261
 262 template <class _Tp>
 263 inline bool  _STLP_CALL operator<=(const _Deque_iterator_base<_Tp >& __x,
 264                                    const _Deque_iterator_base<_Tp >& __y)
 265 { return !(__y < __x); }
 266
 267 #else /* _STLP_USE_SEPARATE_RELOPS_NAMESPACE */
 268
 269 template <class _Tp, class _Traits1, class _Traits2>
 270 inline bool  _STLP_CALL
 271 operator==(const _Deque_iterator<_Tp, _Traits1 >& __x,
 272            const _Deque_iterator<_Tp, _Traits2 >& __y)
 273 { return __x._M_cur == __y._M_cur; }
 274
 275 template <class _Tp, class _Traits1, class _Traits2>
 276 inline bool _STLP_CALL
 277 operator < (const _Deque_iterator<_Tp, _Traits1 >& __x,
 278             const _Deque_iterator<_Tp, _Traits2 >& __y) {
 279   return (__x._M_node == __y._M_node) ?
 280     (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
 281 }
 282
 283 template <class _Tp>
 284 inline bool _STLP_CALL
 285 operator!=(const _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >& __x,
 286            const _Deque_iterator<_Tp, _Const_traits<_Tp> >& __y)
 287 { return __x._M_cur != __y._M_cur; }
 288
 289 template <class _Tp>
 290 inline bool _STLP_CALL
 291 operator>(const _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >& __x,
 292           const _Deque_iterator<_Tp, _Const_traits<_Tp> >& __y)
 293 { return __y < __x; }
 294
 295 template <class _Tp>
 296 inline bool  _STLP_CALL
 297 operator>=(const _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >& __x,
 298            const _Deque_iterator<_Tp, _Const_traits<_Tp> >& __y)
 299 { return !(__x < __y); }
 300
 301 template <class _Tp>
 302 inline bool _STLP_CALL
 303 operator<=(const _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >& __x,
 304            const _Deque_iterator<_Tp, _Const_traits<_Tp> >& __y)
 305 { return !(__y < __x); }
 306 #endif /* _STLP_USE_SEPARATE_RELOPS_NAMESPACE */
 307
 308 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
 309 _STLP_MOVE_TO_STD_NAMESPACE
 310 template <class _Tp, class _Traits>
 311 struct __type_traits<_STLP_PRIV _Deque_iterator<_Tp, _Traits> > {
 312   typedef __false_type   has_trivial_default_constructor;
 313   typedef __true_type    has_trivial_copy_constructor;
 314   typedef __true_type    has_trivial_assignment_operator;
 315   typedef __true_type    has_trivial_destructor;
 316   typedef __false_type   is_POD_type;
 317 };
 318 _STLP_MOVE_TO_PRIV_NAMESPACE
 319 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
 320
 321 #if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
 322 _STLP_MOVE_TO_STD_NAMESPACE
 323 template <class _Tp, class _Traits> inline _Tp*  _STLP_CALL
 324 value_type(const _STLP_PRIV _Deque_iterator<_Tp, _Traits  >&) { return (_Tp*)0; }
 325 template <class _Tp, class _Traits> inline random_access_iterator_tag _STLP_CALL
 326 iterator_category(const _STLP_PRIV _Deque_iterator<_Tp, _Traits  >&) { return random_access_iterator_tag(); }
 327 template <class _Tp, class _Traits> inline ptrdiff_t* _STLP_CALL
 328 distance_type(const _STLP_PRIV _Deque_iterator<_Tp, _Traits  >&) { return 0; }
 329 _STLP_MOVE_TO_PRIV_NAMESPACE
 330 #endif
 331
 332 /* Deque base class.  It has two purposes.  First, its constructor
 333  *  and destructor allocate (but don't initialize) storage.  This makes
 334  *  exception safety easier.  Second, the base class encapsulates all of
 335  *  the differences between SGI-style allocators and standard-conforming
 336  *  allocators.
 337  */
 338
 339 template <class _Tp, class _Alloc>
 340 class _Deque_base {
 341   typedef _Deque_base<_Tp, _Alloc> _Self;
 342 public:
 343   typedef _Tp value_type;
 344   _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
 345   typedef _Alloc allocator_type;
 346   typedef _STLP_alloc_proxy<size_t, value_type,  allocator_type> _Alloc_proxy;
 347
 348   typedef typename _Alloc_traits<_Tp*, _Alloc>::allocator_type _Map_alloc_type;
 349   typedef _STLP_alloc_proxy<value_type**, value_type*, _Map_alloc_type> _Map_alloc_proxy;
 350
 351   typedef _Deque_iterator<_Tp, _Nonconst_traits<_Tp> > iterator;
 352   typedef _Deque_iterator<_Tp, _Const_traits<_Tp> >    const_iterator;
 353
 354   static size_t _STLP_CALL buffer_size() { return _Deque_iterator_base<_Tp>::_S_buffer_size(); }
 355
 356   _Deque_base(const allocator_type& __a, size_t __num_elements)
 357     : _M_start(), _M_finish(), _M_map(_STLP_CONVERT_ALLOCATOR(__a, _Tp*), 0),
 358       _M_map_size(__a, (size_t)0)
 359   { _M_initialize_map(__num_elements); }
 360
 361   _Deque_base(const allocator_type& __a)
 362     : _M_start(), _M_finish(), _M_map(_STLP_CONVERT_ALLOCATOR(__a, _Tp*), 0),
 363       _M_map_size(__a, (size_t)0) {}
 364
 365 #if !defined (_STLP_NO_MOVE_SEMANTIC)
 366   _Deque_base(__move_source<_Self> src)
 367     : _M_start(src.get()._M_start), _M_finish(src.get()._M_finish),
 368       _M_map(__move_source<_Map_alloc_proxy>(src.get()._M_map)),
 369       _M_map_size(__move_source<_Alloc_proxy>(src.get()._M_map_size)) {
 370     src.get()._M_map._M_data = 0;
 371     src.get()._M_map_size._M_data = 0;
 372     src.get()._M_finish = src.get()._M_start;
 373   }
 374 #endif
 375
 376   ~_Deque_base();
 377
 378 protected:
 379   void _M_initialize_map(size_t);
 380   void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
 381   void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
 382   enum { _S_initial_map_size = 8 };
 383
 384 protected:
 385   iterator _M_start;
 386   iterator _M_finish;
 387   _Map_alloc_proxy  _M_map;
 388   _Alloc_proxy      _M_map_size;
 389 };
 390
 391 #if defined (_STLP_USE_PTR_SPECIALIZATIONS)
 392 #  define deque _STLP_PTR_IMPL_NAME(deque)
 393 #elif defined (_STLP_DEBUG)
 394 #  define deque _STLP_NON_DBG_NAME(deque)
 395 #else
 396 _STLP_MOVE_TO_STD_NAMESPACE
 397 #endif
 398
 399 template <class _Tp, _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Tp>) >
 400 class deque : protected _STLP_PRIV _Deque_base<_Tp, _Alloc>
 401 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (deque)
 402             , public __stlport_class<deque<_Tp, _Alloc> >
 403 #endif
 404 {
 405   typedef _STLP_PRIV _Deque_base<_Tp, _Alloc> _Base;
 406   typedef deque<_Tp, _Alloc> _Self;
 407 public:                         // Basic types
 408   typedef _Tp value_type;
 409   typedef value_type* pointer;
 410   typedef const value_type* const_pointer;
 411   typedef value_type& reference;
 412   typedef const value_type& const_reference;
 413   typedef size_t size_type;
 414   typedef ptrdiff_t difference_type;
 415   typedef random_access_iterator_tag _Iterator_category;
 416   _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
 417   typedef typename _Base::allocator_type allocator_type;
 418
 419 public:                         // Iterators
 420   typedef typename _Base::iterator       iterator;
 421   typedef typename _Base::const_iterator const_iterator;
 422
 423   _STLP_DECLARE_RANDOM_ACCESS_REVERSE_ITERATORS;
 424
 425 protected:                      // Internal typedefs
 426   typedef pointer* _Map_pointer;
 427 #if defined (_STLP_NO_MOVE_SEMANTIC)
 428   typedef __false_type _Movable;
 429 #endif
 430
 431 public:                         // Basic accessors
 432   iterator begin() { return this->_M_start; }
 433   iterator end() { return this->_M_finish; }
 434   const_iterator begin() const { return const_iterator(this->_M_start); }
 435   const_iterator end() const { return const_iterator(this->_M_finish); }
 436
 437   reverse_iterator rbegin() { return reverse_iterator(this->_M_finish); }
 438   reverse_iterator rend() { return reverse_iterator(this->_M_start); }
 439   const_reverse_iterator rbegin() const
 440     { return const_reverse_iterator(this->_M_finish); }
 441   const_reverse_iterator rend() const
 442     { return const_reverse_iterator(this->_M_start); }
 443
 444   reference operator[](size_type __n)
 445     { return this->_M_start[difference_type(__n)]; }
 446   const_reference operator[](size_type __n) const
 447     { return this->_M_start[difference_type(__n)]; }
 448
 449   void _M_range_check(size_type __n) const {
 450     if (__n >= this->size())
 451       __stl_throw_out_of_range("deque");
 452   }
 453   reference at(size_type __n)
 454     { _M_range_check(__n); return (*this)[__n]; }
 455   const_reference at(size_type __n) const
 456     { _M_range_check(__n); return (*this)[__n]; }
 457
 458   reference front() { return *this->_M_start; }
 459   reference back() {
 460     iterator __tmp = this->_M_finish;
 461     --__tmp;
 462     return *__tmp;
 463   }
 464   const_reference front() const { return *this->_M_start; }
 465   const_reference back() const {
 466     const_iterator __tmp = this->_M_finish;
 467     --__tmp;
 468     return *__tmp;
 469   }
 470
 471   size_type size() const { return this->_M_finish - this->_M_start; }
 472   size_type max_size() const { return size_type(-1); }
 473   bool empty() const { return this->_M_finish == this->_M_start; }
 474   allocator_type get_allocator() const { return this->_M_map_size; }
 475
 476 public:                         // Constructor, destructor.
 477 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
 478   explicit deque(const allocator_type& __a = allocator_type())
 479 #else
 480   deque()
 481     : _STLP_PRIV _Deque_base<_Tp, _Alloc>(allocator_type(), 0) {}
 482   deque(const allocator_type& __a)
 483 #endif
 484     : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__a, 0) {}
 485
 486   deque(const _Self& __x)
 487     : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__x.get_allocator(), __x.size())
 488   { _STLP_PRIV __ucopy(__x.begin(), __x.end(), this->_M_start); }
 489
 490 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
 491 private:
 492   void _M_initialize(size_type __n, const value_type& __val = _STLP_DEFAULT_CONSTRUCTED(_Tp)) {
 493     typedef typename _TrivialInit<_Tp>::_Ret _TrivialInit;
 494     _M_fill_initialize(__val, _TrivialInit());
 495   }
 496 public:
 497   explicit deque(size_type __n)
 498     : _STLP_PRIV _Deque_base<_Tp, _Alloc>(allocator_type(), __n)
 499   { _M_initialize(__n); }
 500   deque(size_type __n, const value_type& __val, const allocator_type& __a = allocator_type())
 501 #else
 502   explicit deque(size_type __n)
 503     : _STLP_PRIV _Deque_base<_Tp, _Alloc>(allocator_type(), __n) {
 504     typedef typename _TrivialInit<_Tp>::_Ret _TrivialInit;
 505     _M_fill_initialize(_STLP_DEFAULT_CONSTRUCTED(_Tp), _TrivialInit());
 506   }
 507   deque(size_type __n, const value_type& __val)
 508     : _STLP_PRIV _Deque_base<_Tp, _Alloc>(allocator_type(), __n)
 509   { _M_fill_initialize(__val, __false_type()); }
 510   deque(size_type __n, const value_type& __val, const allocator_type& __a)
 511 #endif
 512     : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__a, __n)
 513   { _M_fill_initialize(__val, __false_type()); }
 514
 515 #if defined (_STLP_MEMBER_TEMPLATES)
 516 protected:
 517   template <class _Integer>
 518   void _M_initialize_dispatch(_Integer __n, _Integer __x, const __true_type&) {
 519     this->_M_initialize_map(__n);
 520     _M_fill_initialize(__x, __false_type());
 521   }
 522
 523   template <class _InputIter>
 524   void _M_initialize_dispatch(_InputIter __first, _InputIter __last,
 525                               const __false_type&) {
 526     _M_range_initialize(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
 527   }
 528
 529 public:
 530   // Check whether it's an integral type.  If so, it's not an iterator.
 531   template <class _InputIterator>
 532   deque(_InputIterator __first, _InputIterator __last,
 533         const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
 534     : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__a) {
 535     typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
 536     _M_initialize_dispatch(__first, __last, _Integral());
 537   }
 538
 539 #  if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
 540   template <class _InputIterator>
 541   deque(_InputIterator __first, _InputIterator __last)
 542     : _STLP_PRIV _Deque_base<_Tp, _Alloc>(allocator_type()) {
 543     typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
 544     _M_initialize_dispatch(__first, __last, _Integral());
 545   }
 546 #  endif
 547
 548 #else
 549   deque(const value_type* __first, const value_type* __last,
 550         const allocator_type& __a = allocator_type() )
 551     : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__a, __last - __first)
 552   { _STLP_PRIV __ucopy(__first, __last, this->_M_start); }
 553
 554   deque(const_iterator __first, const_iterator __last,
 555         const allocator_type& __a = allocator_type() )
 556     : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__a, __last - __first)
 557   { _STLP_PRIV __ucopy(__first, __last, this->_M_start); }
 558 #endif /* _STLP_MEMBER_TEMPLATES */
 559
 560 #if !defined (_STLP_NO_MOVE_SEMANTIC)
 561   deque(__move_source<_Self> src)
 562     : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__move_source<_Base>(src.get()))
 563   {}
 564 #endif
 565
 566   ~deque()
 567   { _STLP_STD::_Destroy_Range(this->_M_start, this->_M_finish); }
 568
 569   _Self& operator= (const _Self& __x);
 570
 571   void swap(_Self& __x) {
 572     _STLP_STD::swap(this->_M_start, __x._M_start);
 573     _STLP_STD::swap(this->_M_finish, __x._M_finish);
 574     this->_M_map.swap(__x._M_map);
 575     this->_M_map_size.swap(__x._M_map_size);
 576   }
 577 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
 578   void _M_swap_workaround(_Self& __x) { swap(__x); }
 579 #endif
 580
 581 public:
 582   // assign(), a generalized assignment member function.  Two
 583   // versions: one that takes a count, and one that takes a range.
 584   // The range version is a member template, so we dispatch on whether
 585   // or not the type is an integer.
 586
 587   void _M_fill_assign(size_type __n, const _Tp& __val) {
 588     if (__n > size()) {
 589       _STLP_STD::fill(begin(), end(), __val);
 590       insert(end(), __n - size(), __val);
 591     }
 592     else {
 593       erase(begin() + __n, end());
 594       _STLP_STD::fill(begin(), end(), __val);
 595     }
 596   }
 597
 598   void assign(size_type __n, const _Tp& __val) {
 599     _M_fill_assign(__n, __val);
 600   }
 601
 602 #if defined (_STLP_MEMBER_TEMPLATES)
 603   template <class _InputIterator>
 604   void assign(_InputIterator __first, _InputIterator __last) {
 605     typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
 606     _M_assign_dispatch(__first, __last, _Integral());
 607   }
 608
 609 private:                        // helper functions for assign()
 610
 611   template <class _Integer>
 612   void _M_assign_dispatch(_Integer __n, _Integer __val,
 613                           const __true_type& /*_IsIntegral*/)
 614   { _M_fill_assign((size_type) __n, (_Tp) __val); }
 615
 616   template <class _InputIterator>
 617   void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
 618                           const __false_type& /*_IsIntegral*/) {
 619     _M_assign_aux(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
 620   }
 621
 622   template <class _InputIter>
 623   void _M_assign_aux(_InputIter __first, _InputIter __last, const input_iterator_tag &) {
 624     iterator __cur = begin();
 625     for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
 626       *__cur = *__first;
 627     if (__first == __last)
 628       erase(__cur, end());
 629     else
 630       insert(end(), __first, __last);
 631   }
 632
 633   template <class _ForwardIterator>
 634   void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
 635                      const forward_iterator_tag &) {
 636 #else
 637   void assign(const value_type *__first, const value_type *__last) {
 638     size_type __size = size();
 639     size_type __len = __last - __first;
 640     if (__len > __size) {
 641       const value_type *__mid = __first + __size;
 642       _STLP_STD::copy(__first, __mid, begin());
 643       insert(end(), __mid, __last);
 644     }
 645     else {
 646       erase(_STLP_STD::copy(__first, __last, begin()), end());
 647     }
 648   }
 649   void assign(const_iterator __first, const_iterator __last) {
 650     typedef const_iterator _ForwardIterator;
 651 #endif /* _STLP_MEMBER_TEMPLATES */
 652     size_type __len = _STLP_STD::distance(__first, __last);
 653     if (__len > size()) {
 654       _ForwardIterator __mid = __first;
 655       _STLP_STD::advance(__mid, size());
 656       _STLP_STD::copy(__first, __mid, begin());
 657       insert(end(), __mid, __last);
 658     }
 659     else {
 660       erase(_STLP_STD::copy(__first, __last, begin()), end());
 661     }
 662   }
 663
 664
 665 public:                         // push_* and pop_*
 666
 667 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
 668   void push_back(const value_type& __t = _STLP_DEFAULT_CONSTRUCTED(_Tp)) {
 669 #else
 670   void push_back(const value_type& __t) {
 671 #endif /*!_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
 672     if (this->_M_finish._M_cur != this->_M_finish._M_last - 1) {
 673       _Copy_Construct(this->_M_finish._M_cur, __t);
 674       ++this->_M_finish._M_cur;
 675     }
 676     else
 677       _M_push_back_aux_v(__t);
 678   }
 679 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
 680   void push_front(const value_type& __t = _STLP_DEFAULT_CONSTRUCTED(_Tp))   {
 681 #else
 682   void push_front(const value_type& __t)   {
 683 #endif /*!_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
 684     if (this->_M_start._M_cur != this->_M_start._M_first) {
 685       _Copy_Construct(this->_M_start._M_cur - 1, __t);
 686       --this->_M_start._M_cur;
 687     }
 688     else
 689       _M_push_front_aux_v(__t);
 690   }
 691
 692 #if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
 693   void push_back() {
 694     if (this->_M_finish._M_cur != this->_M_finish._M_last - 1) {
 695       _STLP_STD::_Construct(this->_M_finish._M_cur);
 696       ++this->_M_finish._M_cur;
 697     }
 698     else
 699       _M_push_back_aux();
 700   }
 701   void push_front() {
 702     if (this->_M_start._M_cur != this->_M_start._M_first) {
 703       _STLP_STD::_Construct(this->_M_start._M_cur - 1);
 704       --this->_M_start._M_cur;
 705     }
 706     else
 707       _M_push_front_aux();
 708   }
 709 #endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
 710
 711   void pop_back() {
 712     if (this->_M_finish._M_cur != this->_M_finish._M_first) {
 713       --this->_M_finish._M_cur;
 714       _STLP_STD::_Destroy(this->_M_finish._M_cur);
 715     }
 716     else {
 717       _M_pop_back_aux();
 718       _STLP_STD::_Destroy(this->_M_finish._M_cur);
 719     }
 720   }
 721
 722   void pop_front() {
 723     _STLP_STD::_Destroy(this->_M_start._M_cur);
 724     _M_pop_front_aux();
 725   }
 726
 727 public:                         // Insert
 728
 729 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
 730   iterator insert(iterator __pos, const value_type& __x = _STLP_DEFAULT_CONSTRUCTED(_Tp)) {
 731 #else
 732   iterator insert(iterator __pos, const value_type& __x) {
 733 #endif /*!_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
 734 #if !defined (_STLP_NO_MOVE_SEMANTIC)
 735     typedef typename __move_traits<_Tp>::implemented _Movable;
 736 #endif
 737     if (__pos._M_cur == this->_M_start._M_cur) {
 738       push_front(__x);
 739       return this->_M_start;
 740     }
 741     else if (__pos._M_cur == this->_M_finish._M_cur) {
 742       push_back(__x);
 743       iterator __tmp = this->_M_finish;
 744       --__tmp;
 745       return __tmp;
 746     }
 747     else {
 748       return _M_fill_insert_aux(__pos, 1, __x, _Movable());
 749     }
 750   }
 751
 752 #if defined(_STLP_DONT_SUP_DFLT_PARAM) && !defined(_STLP_NO_ANACHRONISMS)
 753   iterator insert(iterator __pos)
 754   { return insert(__pos, _STLP_DEFAULT_CONSTRUCTED(_Tp)); }
 755 #endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
 756
 757   void insert(iterator __pos, size_type __n, const value_type& __x)
 758   { _M_fill_insert(__pos, __n, __x); }
 759
 760 protected:
 761   iterator _M_fill_insert_aux(iterator __pos, size_type __n, const value_type& __x, const __true_type& /*_Movable*/);
 762   iterator _M_fill_insert_aux(iterator __pos, size_type __n, const value_type& __x, const __false_type& /*_Movable*/);
 763
 764   void _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
 765
 766 #if defined (_STLP_MEMBER_TEMPLATES)
 767   template <class _Integer>
 768   void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
 769                           const __true_type& /*_IsIntegral*/) {
 770     _M_fill_insert(__pos, (size_type) __n, (value_type) __x);
 771   }
 772
 773   template <class _InputIterator>
 774   void _M_insert_dispatch(iterator __pos,
 775                           _InputIterator __first, _InputIterator __last,
 776                           const __false_type& /*_IsIntegral*/) {
 777     _M_insert(__pos, __first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
 778   }
 779
 780 public:
 781   // Check whether it's an integral type.  If so, it's not an iterator.
 782   template <class _InputIterator>
 783   void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
 784     typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
 785     _M_insert_dispatch(__pos, __first, __last, _Integral());
 786   }
 787
 788 #else /* _STLP_MEMBER_TEMPLATES */
 789   void _M_insert_range_aux(iterator __pos,
 790                            const value_type* __first, const value_type* __last,
 791                            size_type __n, const __true_type& /*_Movable*/);
 792   void _M_insert_range_aux(iterator __pos,
 793                            const value_type* __first, const value_type* __last,
 794                            size_type __n, const __false_type& /*_Movable*/);
 795   void _M_insert_range_aux(iterator __pos,
 796                            const_iterator __first, const_iterator __last,
 797                            size_type __n, const __true_type& /*_Movable*/);
 798   void _M_insert_range_aux(iterator __pos,
 799                            const_iterator __first, const_iterator __last,
 800                            size_type __n, const __false_type& /*_Movable*/);
 801 public:
 802   void insert(iterator __pos,
 803               const value_type* __first, const value_type* __last);
 804   void insert(iterator __pos,
 805               const_iterator __first, const_iterator __last);
 806
 807 #endif /* _STLP_MEMBER_TEMPLATES */
 808
 809 public:
 810 #if !defined(_STLP_DONT_SUP_DFLT_PARAM)
 811   void resize(size_type __new_size,
 812               const value_type& __x = _STLP_DEFAULT_CONSTRUCTED(_Tp)) {
 813 #else
 814   void resize(size_type __new_size, const value_type& __x) {
 815 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
 816     const size_type __len = size();
 817     if (__new_size < __len)
 818       erase(this->_M_start + __new_size, this->_M_finish);
 819     else
 820       insert(this->_M_finish, __new_size - __len, __x);
 821   }
 822
 823 #if defined (_STLP_DONT_SUP_DFLT_PARAM)
 824   void resize(size_type __new_size)
 825   { resize(__new_size, _STLP_DEFAULT_CONSTRUCTED(_Tp)); }
 826 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
 827
 828 protected:
 829   iterator _M_erase(iterator __pos, const __true_type& /*_Movable*/);
 830   iterator _M_erase(iterator __pos, const __false_type& /*_Movable*/);
 831
 832   iterator _M_erase(iterator __first, iterator __last, const __true_type& /*_Movable*/);
 833   iterator _M_erase(iterator __first, iterator __last, const __false_type& /*_Movable*/);
 834 public:                         // Erase
 835   iterator erase(iterator __pos) {
 836 #if !defined (_STLP_NO_MOVE_SEMANTIC)
 837     typedef typename __move_traits<_Tp>::implemented _Movable;
 838 #endif
 839     return _M_erase(__pos, _Movable());
 840   }
 841   iterator erase(iterator __first, iterator __last) {
 842 #if !defined (_STLP_NO_MOVE_SEMANTIC)
 843     typedef typename __move_traits<_Tp>::implemented _Movable;
 844 #endif
 845     if (__first == this->_M_start && __last == this->_M_finish) {
 846       clear();
 847       return this->_M_finish;
 848     }
 849     else {
 850       if (__first == __last)
 851         return __first;
 852       return _M_erase(__first, __last, _Movable());
 853     }
 854   }
 855   void clear();
 856
 857 protected:                        // Internal construction/destruction
 858
 859   void _M_fill_initialize(const value_type& __val, const __true_type& /*_TrivialInit*/)
 860   {}
 861   void _M_fill_initialize(const value_type& __val, const __false_type& /*_TrivialInit*/);
 862
 863 #if defined (_STLP_MEMBER_TEMPLATES)
 864   template <class _InputIterator>
 865   void _M_range_initialize(_InputIterator __first, _InputIterator __last,
 866                            const input_iterator_tag &) {
 867     this->_M_initialize_map(0);
 868     _STLP_TRY {
 869       for ( ; __first != __last; ++__first)
 870         push_back(*__first);
 871     }
 872     _STLP_UNWIND(clear())
 873   }
 874   template <class _ForwardIterator>
 875   void  _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
 876                             const forward_iterator_tag &)  {
 877    size_type __n = _STLP_STD::distance(__first, __last);
 878    this->_M_initialize_map(__n);
 879    _Map_pointer __cur_node = this->_M_start._M_node;
 880    _STLP_TRY {
 881     for (; __cur_node < this->_M_finish._M_node; ++__cur_node) {
 882       _ForwardIterator __mid = __first;
 883       _STLP_STD::advance(__mid, this->buffer_size());
 884       _STLP_STD::uninitialized_copy(__first, __mid, *__cur_node);
 885       __first = __mid;
 886     }
 887     _STLP_STD::uninitialized_copy(__first, __last, this->_M_finish._M_first);
 888    }
 889   _STLP_UNWIND(_STLP_STD::_Destroy_Range(this->_M_start, iterator(*__cur_node, __cur_node)))
 890  }
 891 #endif /* _STLP_MEMBER_TEMPLATES */
 892
 893 protected:                        // Internal push_* and pop_*
 894
 895   void _M_push_back_aux_v(const value_type&);
 896   void _M_push_front_aux_v(const value_type&);
 897 #if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
 898   void _M_push_back_aux();
 899   void _M_push_front_aux();
 900 #endif /*_STLP_DONT_SUP_DFLT_PARAM !_STLP_NO_ANACHRONISMS*/
 901   void _M_pop_back_aux();
 902   void _M_pop_front_aux();
 903
 904 protected:                        // Internal insert functions
 905
 906 #if defined (_STLP_MEMBER_TEMPLATES)
 907
 908   template <class _InputIterator>
 909   void _M_insert(iterator __pos,
 910                 _InputIterator __first,
 911                 _InputIterator __last,
 912                 const input_iterator_tag &) {
 913     _STLP_STD::copy(__first, __last, inserter(*this, __pos));
 914   }
 915
 916   template <class _ForwardIterator>
 917   void  _M_insert(iterator __pos,
 918                   _ForwardIterator __first, _ForwardIterator __last,
 919                   const forward_iterator_tag &) {
 920 #if !defined (_STLP_NO_MOVE_SEMANTIC)
 921     typedef typename __move_traits<_Tp>::implemented _Movable;
 922 #endif
 923     size_type __n = _STLP_STD::distance(__first, __last);
 924     if (__pos._M_cur == this->_M_start._M_cur) {
 925       iterator __new_start = _M_reserve_elements_at_front(__n);
 926       _STLP_TRY {
 927         uninitialized_copy(__first, __last, __new_start);
 928         this->_M_start = __new_start;
 929       }
 930       _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
 931     }
 932     else if (__pos._M_cur == this->_M_finish._M_cur) {
 933       iterator __new_finish = _M_reserve_elements_at_back(__n);
 934       _STLP_TRY {
 935         uninitialized_copy(__first, __last, this->_M_finish);
 936         this->_M_finish = __new_finish;
 937       }
 938       _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
 939     }
 940     else
 941       _M_insert_range_aux(__pos, __first, __last, __n, _Movable());
 942   }
 943
 944   template <class _ForwardIterator>
 945   void _M_insert_range_aux(iterator __pos,
 946                            _ForwardIterator __first, _ForwardIterator __last,
 947                            size_type __n, const __true_type& /*_Movable*/) {
 948     const difference_type __elemsbefore = __pos - this->_M_start;
 949     size_type __length = size();
 950     if (__elemsbefore <= difference_type(__length / 2)) {
 951       iterator __new_start = _M_reserve_elements_at_front(__n);
 952       __pos = this->_M_start + __elemsbefore;
 953       _STLP_TRY {
 954         iterator __dst = __new_start;
 955         iterator __src = this->_M_start;
 956         for (; __src != __pos; ++__dst, ++__src) {
 957           _STLP_STD::_Move_Construct(&(*__dst), *__src);
 958           _STLP_STD::_Destroy_Moved(&(*__src));
 959         }
 960         this->_M_start = __new_start;
 961         uninitialized_copy(__first, __last, __dst);
 962       }
 963       _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
 964     }
 965     else {
 966       iterator __new_finish = _M_reserve_elements_at_back(__n);
 967       const difference_type __elemsafter = difference_type(__length) - __elemsbefore;
 968       __pos = this->_M_finish - __elemsafter;
 969       _STLP_TRY {
 970         iterator __dst = __new_finish;
 971         iterator __src = this->_M_finish;
 972         for (--__src, --__dst; __src >= __pos; --__src, --__dst) {
 973           _STLP_STD::_Move_Construct(&(*__dst), *__src);
 974           _STLP_STD::_Destroy_Moved(&(*__src));
 975         }
 976         this->_M_finish = __new_finish;
 977         uninitialized_copy(__first, __last, __pos);
 978       }
 979       _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
 980     }
 981   }
 982
 983   template <class _ForwardIterator>
 984   void _M_insert_range_aux(iterator __pos,
 985                            _ForwardIterator __first, _ForwardIterator __last,
 986                            size_type __n, const __false_type& /*_Movable*/) {
 987     const difference_type __elemsbefore = __pos - this->_M_start;
 988     size_type __length = size();
 989     if (__elemsbefore <= difference_type(__length / 2)) {
 990       iterator __new_start = _M_reserve_elements_at_front(__n);
 991       iterator __old_start = this->_M_start;
 992       __pos = this->_M_start + __elemsbefore;
 993       _STLP_TRY {
 994         if (__elemsbefore >= difference_type(__n)) {
 995           iterator __start_n = this->_M_start + difference_type(__n);
 996           _STLP_STD::uninitialized_copy(this->_M_start, __start_n, __new_start);
 997           this->_M_start = __new_start;
 998           _STLP_STD::copy(__start_n, __pos, __old_start);
 999           _STLP_STD::copy(__first, __last, __pos - difference_type(__n));
1000         }
1001         else {
1002           _ForwardIterator __mid = __first;
1003           _STLP_STD::advance(__mid, difference_type(__n) - __elemsbefore);
1004           _STLP_PRIV __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid, __new_start);
1005           this->_M_start = __new_start;
1006           _STLP_STD::copy(__mid, __last, __old_start);
1007         }
1008       }
1009       _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
1010     }
1011     else {
1012       iterator __new_finish = _M_reserve_elements_at_back(__n);
1013       iterator __old_finish = this->_M_finish;
1014       const difference_type __elemsafter = difference_type(__length) - __elemsbefore;
1015       __pos = this->_M_finish - __elemsafter;
1016       _STLP_TRY {
1017         if (__elemsafter > difference_type(__n)) {
1018           iterator __finish_n = this->_M_finish - difference_type(__n);
1019           _STLP_STD::uninitialized_copy(__finish_n, this->_M_finish, this->_M_finish);
1020           this->_M_finish = __new_finish;
1021           _STLP_STD::copy_backward(__pos, __finish_n, __old_finish);
1022           _STLP_STD::copy(__first, __last, __pos);
1023         }
1024         else {
1025           _ForwardIterator __mid = __first;
1026           _STLP_STD::advance(__mid, __elemsafter);
1027           _STLP_PRIV __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish);
1028           this->_M_finish = __new_finish;
1029           _STLP_STD::copy(__first, __mid, __pos);
1030         }
1031       }
1032       _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
1033     }
1034   }
1035 #endif /* _STLP_MEMBER_TEMPLATES */
1036
1037   iterator _M_reserve_elements_at_front(size_type __n) {
1038     size_type __vacancies = this->_M_start._M_cur - this->_M_start._M_first;
1039     if (__n > __vacancies)
1040       _M_new_elements_at_front(__n - __vacancies);
1041     return this->_M_start - difference_type(__n);
1042   }
1043
1044   iterator _M_reserve_elements_at_back(size_type __n) {
1045     size_type __vacancies = (this->_M_finish._M_last - this->_M_finish._M_cur) - 1;
1046     if (__n > __vacancies)
1047       _M_new_elements_at_back(__n - __vacancies);
1048     return this->_M_finish + difference_type(__n);
1049   }
1050
1051   void _M_new_elements_at_front(size_type __new_elements);
1052   void _M_new_elements_at_back(size_type __new_elements);
1053
1054 protected:                      // Allocation of _M_map and nodes
1055
1056   // Makes sure the _M_map has space for new nodes.  Does not actually
1057   //  add the nodes.  Can invalidate _M_map pointers.  (And consequently,
1058   //  deque iterators.)
1059
1060   void _M_reserve_map_at_back (size_type __nodes_to_add = 1) {
1061     if (__nodes_to_add + 1 > this->_M_map_size._M_data - (this->_M_finish._M_node - this->_M_map._M_data))
1062       _M_reallocate_map(__nodes_to_add, false);
1063   }
1064
1065   void _M_reserve_map_at_front (size_type __nodes_to_add = 1) {
1066     if (__nodes_to_add > size_type(this->_M_start._M_node - this->_M_map._M_data))
1067       _M_reallocate_map(__nodes_to_add, true);
1068   }
1069
1070   void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
1071 };
1072
1073 #if defined (deque)
1074 #  undef deque
1075 _STLP_MOVE_TO_STD_NAMESPACE
1076 #endif
1077
1078 _STLP_END_NAMESPACE
1079
1080 #if !defined (_STLP_LINK_TIME_INSTANTIATION)
1081 #  include <stl/_deque.c>
1082 #endif
1083
1084 #if defined (_STLP_USE_PTR_SPECIALIZATIONS)
1085 #  include <stl/pointers/_deque.h>
1086 #endif
1087
1088 #if defined (_STLP_DEBUG)
1089 #  include <stl/debug/_deque.h>
1090 #endif
1091
1092 _STLP_BEGIN_NAMESPACE
1093
1094 #define _STLP_TEMPLATE_CONTAINER deque<_Tp, _Alloc>
1095 #define _STLP_TEMPLATE_HEADER    template <class _Tp, class _Alloc>
1096 #include <stl/_relops_cont.h>
1097 #undef _STLP_TEMPLATE_CONTAINER
1098 #undef _STLP_TEMPLATE_HEADER
1099
1100 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_MOVE_SEMANTIC)
1101 template <class _Tp, class _Alloc>
1102 struct __move_traits<deque<_Tp, _Alloc> > {
1103   typedef __true_type implemented;
1104   typedef typename __move_traits<_Alloc>::complete complete;
1105 };
1106 #endif
1107
1108 _STLP_END_NAMESPACE
1109
1110 #endif /* _STLP_INTERNAL_DEQUE_H */
1111
1112 // Local Variables:
1113 // mode:C++
1114 // End:
1115