contrib/libstdc++/stl/stl_deque.h

   1 /*
   2  *
   3  * Copyright (c) 1994
   4  * Hewlett-Packard Company
   5  *
   6  * Permission to use, copy, modify, distribute and sell this software
   7  * and its documentation for any purpose is hereby granted without fee,
   8  * provided that the above copyright notice appear in all copies and
   9  * that both that copyright notice and this permission notice appear
  10  * in supporting documentation.  Hewlett-Packard Company makes no
  11  * representations about the suitability of this software for any
  12  * purpose.  It is provided "as is" without express or implied warranty.
  13  *
  14  *
  15  * Copyright (c) 1997
  16  * Silicon Graphics Computer Systems, Inc.
  17  *
  18  * Permission to use, copy, modify, distribute and sell this software
  19  * and its documentation for any purpose is hereby granted without fee,
  20  * provided that the above copyright notice appear in all copies and
  21  * that both that copyright notice and this permission notice appear
  22  * in supporting documentation.  Silicon Graphics makes no
  23  * representations about the suitability of this software for any
  24  * purpose.  It is provided "as is" without express or implied warranty.
  25  */
  26
  27 /* NOTE: This is an internal header file, included by other STL headers.
  28  *   You should not attempt to use it directly.
  29  */
  30
  31 #ifndef __SGI_STL_INTERNAL_DEQUE_H
  32 #define __SGI_STL_INTERNAL_DEQUE_H
  33
  34 /* Class invariants:
  35  *  For any nonsingular iterator i:
  36  *    i.node is the address of an element in the map array.  The
  37  *      contents of i.node is a pointer to the beginning of a node.
  38  *    i.first == *(i.node)
  39  *    i.last  == i.first + node_size
  40  *    i.cur is a pointer in the range [i.first, i.last).  NOTE:
  41  *      the implication of this is that i.cur is always a dereferenceable
  42  *      pointer, even if i is a past-the-end iterator.
  43  *  Start and Finish are always nonsingular iterators.  NOTE: this means
  44  *    that an empty deque must have one node, and that a deque
  45  *    with N elements, where N is the buffer size, must have two nodes.
  46  *  For every node other than start.node and finish.node, every element
  47  *    in the node is an initialized object.  If start.node == finish.node,
  48  *    then [start.cur, finish.cur) are initialized objects, and
  49  *    the elements outside that range are uninitialized storage.  Otherwise,
  50  *    [start.cur, start.last) and [finish.first, finish.cur) are initialized
  51  *    objects, and [start.first, start.cur) and [finish.cur, finish.last)
  52  *    are uninitialized storage.
  53  *  [map, map + map_size) is a valid, non-empty range.
  54  *  [start.node, finish.node] is a valid range contained within
  55  *    [map, map + map_size).
  56  *  A pointer in the range [map, map + map_size) points to an allocated node
  57  *    if and only if the pointer is in the range [start.node, finish.node].
  58  */
  59
  60
  61 /*
  62  * In previous versions of deque, node_size was fixed by the
  63  * implementation.  In this version, however, users can select
  64  * the node size.  Deque has three template parameters; the third,
  65  * a number of type size_t, is the number of elements per node.
  66  * If the third template parameter is 0 (which is the default),
  67  * then deque will use a default node size.
  68  *
  69  * The only reason for using an alternate node size is if your application
  70  * requires a different performance tradeoff than the default.  If,
  71  * for example, your program contains many deques each of which contains
  72  * only a few elements, then you might want to save memory (possibly
  73  * by sacrificing some speed) by using smaller nodes.
  74  *
  75  * Unfortunately, some compilers have trouble with non-type template
  76  * parameters; stl_config.h defines __STL_NON_TYPE_TMPL_PARAM_BUG if
  77  * that is the case.  If your compiler is one of them, then you will
  78  * not be able to use alternate node sizes; you will have to use the
  79  * default value.
  80  */
  81
  82 __STL_BEGIN_NAMESPACE
  83
  84 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  85 #pragma set woff 1174
  86 #pragma set woff 1375
  87 #endif
  88
  89 // Note: this function is simply a kludge to work around several compilers'
  90 //  bugs in handling constant expressions.
  91 inline size_t
  92 __deque_buf_size(size_t __n, size_t __size)
  93 {
  94   return __n != 0 ? __n : (__size < 512 ? size_t(512 / __size) : size_t(1));
  95 }
  96
  97 #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
  98 template <class _Tp, class _Ref, class _Ptr, size_t __bufsiz>
  99 struct _Deque_iterator {
 100   typedef _Deque_iterator<_Tp,_Tp&,_Tp*,__bufsiz>             iterator;
 101   typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*,__bufsiz> const_iterator;
 102   static size_t
 103     _S_buffer_size() { return __deque_buf_size(__bufsiz, sizeof(_Tp)); }
 104 #else /* __STL_NON_TYPE_TMPL_PARAM_BUG */
 105 template <class _Tp, class _Ref, class _Ptr>
 106 struct _Deque_iterator {
 107   typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
 108   typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
 109   static size_t
 110     _S_buffer_size() { return __deque_buf_size(0, sizeof(_Tp)); }
 111 #endif
 112
 113   typedef random_access_iterator_tag iterator_category;
 114   typedef _Tp value_type;
 115   typedef _Ptr pointer;
 116   typedef _Ref reference;
 117   typedef size_t size_type;
 118   typedef ptrdiff_t difference_type;
 119   typedef _Tp** _Map_pointer;
 120
 121   typedef _Deque_iterator _Self;
 122
 123   _Tp* _M_cur;
 124   _Tp* _M_first;
 125   _Tp* _M_last;
 126   _Map_pointer _M_node;
 127
 128   _Deque_iterator(_Tp* __x, _Map_pointer __y)
 129     : _M_cur(__x), _M_first(*__y),
 130       _M_last(*__y + _S_buffer_size()), _M_node(__y) {}
 131   _Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
 132   _Deque_iterator(const iterator& __x)
 133     : _M_cur(__x._M_cur), _M_first(__x._M_first),
 134       _M_last(__x._M_last), _M_node(__x._M_node) {}
 135
 136   reference operator*() const { return *_M_cur; }
 137 #ifndef __SGI_STL_NO_ARROW_OPERATOR
 138   pointer operator->() const { return _M_cur; }
 139 #endif /* __SGI_STL_NO_ARROW_OPERATOR */
 140
 141   difference_type operator-(const _Self& __x) const {
 142     return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +
 143       (_M_cur - _M_first) + (__x._M_last - __x._M_cur);
 144   }
 145
 146   _Self& operator++() {
 147     ++_M_cur;
 148     if (_M_cur == _M_last) {
 149       _M_set_node(_M_node + 1);
 150       _M_cur = _M_first;
 151     }
 152     return *this;
 153   }
 154   _Self operator++(int)  {
 155     _Self __tmp = *this;
 156     ++*this;
 157     return __tmp;
 158   }
 159
 160   _Self& operator--() {
 161     if (_M_cur == _M_first) {
 162       _M_set_node(_M_node - 1);
 163       _M_cur = _M_last;
 164     }
 165     --_M_cur;
 166     return *this;
 167   }
 168   _Self operator--(int) {
 169     _Self __tmp = *this;
 170     --*this;
 171     return __tmp;
 172   }
 173
 174   _Self& operator+=(difference_type __n)
 175   {
 176     difference_type __offset = __n + (_M_cur - _M_first);
 177     if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
 178       _M_cur += __n;
 179     else {
 180       difference_type __node_offset =
 181         __offset > 0 ? __offset / difference_type(_S_buffer_size())
 182                    : -difference_type((-__offset - 1) / _S_buffer_size()) - 1;
 183       _M_set_node(_M_node + __node_offset);
 184       _M_cur = _M_first +
 185         (__offset - __node_offset * difference_type(_S_buffer_size()));
 186     }
 187     return *this;
 188   }
 189
 190   _Self operator+(difference_type __n) const
 191   {
 192     _Self __tmp = *this;
 193     return __tmp += __n;
 194   }
 195
 196   _Self& operator-=(difference_type __n) { return *this += -__n; }
 197
 198   _Self operator-(difference_type __n) const {
 199     _Self __tmp = *this;
 200     return __tmp -= __n;
 201   }
 202
 203   reference operator[](difference_type __n) const { return *(*this + __n); }
 204
 205   bool operator==(const _Self& __x) const { return _M_cur == __x._M_cur; }
 206   bool operator!=(const _Self& __x) const { return !(*this == __x); }
 207   bool operator<(const _Self& __x) const {
 208     return (_M_node == __x._M_node) ?
 209       (_M_cur < __x._M_cur) : (_M_node < __x._M_node);
 210   }
 211
 212   void _M_set_node(_Map_pointer __new_node) {
 213     _M_node = __new_node;
 214     _M_first = *__new_node;
 215     _M_last = _M_first + difference_type(_S_buffer_size());
 216   }
 217 };
 218
 219 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
 220
 221 #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
 222
 223 template <class _Tp, class _Ref, class _Ptr, size_t __bufsiz>
 224 inline random_access_iterator_tag
 225 iterator_category(const _Deque_iterator<_Tp,_Ref,_Ptr,__bufsiz>&) {
 226   return random_access_iterator_tag();
 227 }
 228
 229 template <class _Tp, class _Ref, class _Ptr, size_t __bufsiz>
 230 inline _Tp*
 231 value_type(const _Deque_iterator<_Tp,_Ref,_Ptr,__bufsiz>&) {
 232   return 0;
 233 }
 234
 235 template <class _Tp, class _Ref, class _Ptr, size_t __bufsiz>
 236 inline ptrdiff_t*
 237 distance_type(const _Deque_iterator<_Tp,_Ref,_Ptr,__bufsiz>&) {
 238   return 0;
 239 }
 240
 241 #else /* __STL_NON_TYPE_TMPL_PARAM_BUG */
 242
 243 template <class _Tp, class _Ref, class _Ptr>
 244 inline random_access_iterator_tag
 245 iterator_category(const _Deque_iterator<_Tp,_Ref,_Ptr>&)
 246 {
 247   return random_access_iterator_tag();
 248 }
 249
 250 template <class _Tp, class _Ref, class _Ptr>
 251 inline _Tp*
 252 value_type(const _Deque_iterator<_Tp,_Ref,_Ptr>&) { return 0; }
 253
 254 template <class _Tp, class _Ref, class _Ptr>
 255 inline ptrdiff_t*
 256 distance_type(const _Deque_iterator<_Tp,_Ref,_Ptr>&) {
 257   return 0;
 258 }
 259
 260 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */
 261
 262 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 263
 264 // Deque base class.  It has two purposes.  First, its constructor
 265 //  and destructor allocate (but don't initialize) storage.  This makes
 266 //  exception safety easier.  Second, the base class encapsulates all of
 267 //  the differences between SGI-style allocators and standard-conforming
 268 //  allocators.
 269
 270 #ifdef __STL_USE_STD_ALLOCATORS
 271
 272 // Base class for ordinary allocators.
 273 template <class _Tp, class _Alloc, size_t __bufsiz, bool __is_static>
 274 class _Deque_alloc_base {
 275 public:
 276   typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
 277   allocator_type get_allocator() const { return node_allocator; }
 278
 279   _Deque_alloc_base(const allocator_type& __a)
 280     : node_allocator(__a), map_allocator(__a), _M_map(0), _M_map_size(0)
 281   {}
 282
 283 protected:
 284   typedef typename _Alloc_traits<_Tp*, _Alloc>::allocator_type
 285           map_allocator_type;
 286
 287   allocator_type node_allocator;
 288   map_allocator_type map_allocator;
 289
 290   _Tp* _M_allocate_node() {
 291     return node_allocator.allocate(__deque_buf_size(__bufsiz,sizeof(_Tp)));
 292   }
 293   void _M_deallocate_node(_Tp* __p) {
 294     node_allocator.deallocate(__p, __deque_buf_size(__bufsiz,sizeof(_Tp)));
 295   }
 296   _Tp** _M_allocate_map(size_t __n)
 297     { return map_allocator.allocate(__n); }
 298   void _M_deallocate_map(_Tp** __p, size_t __n)
 299     { map_allocator.deallocate(__p, __n); }
 300
 301   _Tp** _M_map;
 302   size_t _M_map_size;
 303 };
 304
 305 // Specialization for instanceless allocators.
 306 template <class _Tp, class _Alloc, size_t __bufsiz>
 307 class _Deque_alloc_base<_Tp, _Alloc, __bufsiz, true>
 308 {
 309 public:
 310   typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
 311   allocator_type get_allocator() const { return allocator_type(); }
 312
 313   _Deque_alloc_base(const allocator_type&) : _M_map(0), _M_map_size(0) {}
 314
 315 protected:
 316   typedef typename _Alloc_traits<_Tp, _Alloc>::_Alloc_type _Node_alloc_type;
 317   typedef typename _Alloc_traits<_Tp*, _Alloc>::_Alloc_type _Map_alloc_type;
 318
 319   _Tp* _M_allocate_node()
 320     { return _Node_alloc_type::allocate(__deque_buf_size(__bufsiz,
 321                                                          sizeof(_Tp))); }
 322   void _M_deallocate_node(_Tp* __p)
 323     { _Node_alloc_type::deallocate(__p, __deque_buf_size(__bufsiz,
 324                                                          sizeof(_Tp))); }
 325   _Tp** _M_allocate_map(size_t __n)
 326     { return _Map_alloc_type::allocate(__n); }
 327   void _M_deallocate_map(_Tp** __p, size_t __n)
 328     { _Map_alloc_type::deallocate(__p, __n); }
 329
 330   _Tp** _M_map;
 331   size_t _M_map_size;
 332 };
 333
 334 template <class _Tp, class _Alloc, size_t __bufsiz>
 335 class _Deque_base
 336   : public _Deque_alloc_base<_Tp,_Alloc,__bufsiz,
 337                               _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
 338 {
 339 public:
 340   typedef _Deque_alloc_base<_Tp,_Alloc,__bufsiz,
 341                              _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
 342           _Base;
 343   typedef typename _Base::allocator_type allocator_type;
 344   typedef _Deque_iterator<_Tp,_Tp&,_Tp*,__bufsiz>              iterator;
 345   typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*, __bufsiz> const_iterator;
 346
 347   _Deque_base(const allocator_type& __a, size_t __num_elements)
 348     : _Base(__a), _M_start(), _M_finish()
 349     { _M_initialize_map(__num_elements); }
 350   _Deque_base(const allocator_type& __a)
 351     : _Base(__a), _M_start(), _M_finish() {}
 352   ~_Deque_base();
 353
 354 protected:
 355   void _M_initialize_map(size_t);
 356   void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
 357   void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
 358   enum { _S_initial_map_size = 8 };
 359
 360 protected:
 361   iterator _M_start;
 362   iterator _M_finish;
 363 };
 364
 365 #else /* __STL_USE_STD_ALLOCATORS */
 366
 367 template <class _Tp, class _Alloc, size_t __bufsiz>
 368 class _Deque_base {
 369 public:
 370 #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
 371   typedef _Deque_iterator<_Tp,_Tp&,_Tp*,__bufsiz>              iterator;
 372   typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*, __bufsiz> const_iterator;
 373 #else /* __STL_NON_TYPE_TMPL_PARAM_BUG */
 374   typedef _Deque_iterator<_Tp,_Tp&,_Tp*>                      iterator;
 375   typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*>          const_iterator;
 376 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */
 377
 378   typedef _Alloc allocator_type;
 379   allocator_type get_allocator() const { return allocator_type(); }
 380
 381   _Deque_base(const allocator_type&, size_t __num_elements)
 382     : _M_map(0), _M_map_size(0),  _M_start(), _M_finish() {
 383     _M_initialize_map(__num_elements);
 384   }
 385   _Deque_base(const allocator_type&)
 386     : _M_map(0), _M_map_size(0),  _M_start(), _M_finish() {}
 387   ~_Deque_base();
 388
 389 protected:
 390   void _M_initialize_map(size_t);
 391   void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
 392   void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
 393   enum { _S_initial_map_size = 8 };
 394
 395 protected:
 396   _Tp** _M_map;
 397   size_t _M_map_size;
 398   iterator _M_start;
 399   iterator _M_finish;
 400
 401   typedef simple_alloc<_Tp, _Alloc>  _Node_alloc_type;
 402   typedef simple_alloc<_Tp*, _Alloc> _Map_alloc_type;
 403
 404   _Tp* _M_allocate_node()
 405     { return _Node_alloc_type::allocate(__deque_buf_size(__bufsiz,
 406                                                          sizeof(_Tp))); }
 407   void _M_deallocate_node(_Tp* __p)
 408     { _Node_alloc_type::deallocate(__p, __deque_buf_size(__bufsiz,
 409                                                          sizeof(_Tp))); }
 410   _Tp** _M_allocate_map(size_t __n)
 411     { return _Map_alloc_type::allocate(__n); }
 412   void _M_deallocate_map(_Tp** __p, size_t __n)
 413     { _Map_alloc_type::deallocate(__p, __n); }
 414 };
 415
 416 #endif /* __STL_USE_STD_ALLOCATORS */
 417
 418 // Non-inline member functions from _Deque_base.
 419
 420 template <class _Tp, class _Alloc, size_t __bufsiz>
 421 _Deque_base<_Tp,_Alloc,__bufsiz>::~_Deque_base() {
 422   if (_M_map) {
 423     _M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1);
 424     _M_deallocate_map(_M_map, _M_map_size);
 425   }
 426 }
 427
 428 template <class _Tp, class _Alloc, size_t __bufsiz>
 429 void
 430 _Deque_base<_Tp,_Alloc,__bufsiz>::_M_initialize_map(size_t __num_elements)
 431 {
 432   size_t __num_nodes =
 433     __num_elements / __deque_buf_size(__bufsiz, sizeof(_Tp)) + 1;
 434
 435   _M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2);
 436   _M_map = _M_allocate_map(_M_map_size);
 437
 438   _Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2;
 439   _Tp** __nfinish = __nstart + __num_nodes;
 440
 441   __STL_TRY {
 442     _M_create_nodes(__nstart, __nfinish);
 443   }
 444   __STL_UNWIND((_M_deallocate_map(_M_map, _M_map_size),
 445                 _M_map = 0, _M_map_size = 0));
 446   _M_start._M_set_node(__nstart);
 447   _M_finish._M_set_node(__nfinish - 1);
 448   _M_start._M_cur = _M_start._M_first;
 449   _M_finish._M_cur = _M_finish._M_first +
 450                __num_elements % __deque_buf_size(__bufsiz, sizeof(_Tp));
 451 }
 452
 453 template <class _Tp, class _Alloc, size_t __bufsiz>
 454 void
 455 _Deque_base<_Tp,_Alloc,__bufsiz>::_M_create_nodes(_Tp** __nstart,
 456                                                   _Tp** __nfinish)
 457 {
 458   _Tp** __cur;
 459   __STL_TRY {
 460     for (__cur = __nstart; __cur < __nfinish; ++__cur)
 461       *__cur = _M_allocate_node();
 462   }
 463   __STL_UNWIND(_M_destroy_nodes(__nstart, __cur));
 464 }
 465
 466 template <class _Tp, class _Alloc, size_t __bufsiz>
 467 void
 468 _Deque_base<_Tp,_Alloc,__bufsiz>::_M_destroy_nodes(_Tp** __nstart,
 469                                                    _Tp** __nfinish)
 470 {
 471   for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
 472     _M_deallocate_node(*__n);
 473 }
 474
 475 // See __deque_buf_size().  The only reason that the default value is 0
 476 //  is as a workaround for bugs in the way that some compilers handle
 477 //  constant expressions.
 478 template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp),
 479           size_t __bufsiz = 0>
 480 class deque : protected _Deque_base<_Tp, _Alloc, __bufsiz> {
 481   typedef _Deque_base<_Tp, _Alloc, __bufsiz> _Base;
 482 public:                         // Basic types
 483   typedef _Tp value_type;
 484   typedef value_type* pointer;
 485   typedef const value_type* const_pointer;
 486   typedef value_type& reference;
 487   typedef const value_type& const_reference;
 488   typedef size_t size_type;
 489   typedef ptrdiff_t difference_type;
 490
 491   typedef typename _Base::allocator_type allocator_type;
 492   allocator_type get_allocator() const { return _Base::get_allocator(); }
 493
 494 public:                         // Iterators
 495   typedef typename _Base::iterator       iterator;
 496   typedef typename _Base::const_iterator const_iterator;
 497
 498 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
 499   typedef reverse_iterator<const_iterator> const_reverse_iterator;
 500   typedef reverse_iterator<iterator> reverse_iterator;
 501 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 502   typedef reverse_iterator<const_iterator, value_type, const_reference,
 503                            difference_type>
 504           const_reverse_iterator;
 505   typedef reverse_iterator<iterator, value_type, reference, difference_type>
 506           reverse_iterator;
 507 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 508
 509 protected:                      // Internal typedefs
 510   typedef pointer* _Map_pointer;
 511   static size_t _S_buffer_size()
 512     { return __deque_buf_size(__bufsiz, sizeof(_Tp)); }
 513
 514 protected:
 515 #ifdef __STL_USE_NAMESPACES
 516   using _Base::_M_initialize_map;
 517   using _Base::_M_create_nodes;
 518   using _Base::_M_destroy_nodes;
 519   using _Base::_M_allocate_node;
 520   using _Base::_M_deallocate_node;
 521   using _Base::_M_allocate_map;
 522   using _Base::_M_deallocate_map;
 523
 524   using _Base::_M_map;
 525   using _Base::_M_map_size;
 526   using _Base::_M_start;
 527   using _Base::_M_finish;
 528 #endif /* __STL_USE_NAMESPACES */
 529
 530 public:                         // Basic accessors
 531   iterator begin() { return _M_start; }
 532   iterator end() { return _M_finish; }
 533   const_iterator begin() const { return _M_start; }
 534   const_iterator end() const { return _M_finish; }
 535
 536   reverse_iterator rbegin() { return reverse_iterator(_M_finish); }
 537   reverse_iterator rend() { return reverse_iterator(_M_start); }
 538   const_reverse_iterator rbegin() const
 539     { return const_reverse_iterator(_M_finish); }
 540   const_reverse_iterator rend() const
 541     { return const_reverse_iterator(_M_start); }
 542
 543   reference operator[](size_type __n)
 544     { return _M_start[difference_type(__n)]; }
 545   const_reference operator[](size_type __n) const
 546     { return _M_start[difference_type(__n)]; }
 547
 548   reference front() { return *_M_start; }
 549   reference back() {
 550     iterator __tmp = _M_finish;
 551     --__tmp;
 552     return *__tmp;
 553   }
 554   const_reference front() const { return *_M_start; }
 555   const_reference back() const {
 556     const_iterator __tmp = _M_finish;
 557     --__tmp;
 558     return *__tmp;
 559   }
 560
 561   size_type size() const { return _M_finish - _M_start;; }
 562   size_type max_size() const { return size_type(-1); }
 563   bool empty() const { return _M_finish == _M_start; }
 564
 565 public:                         // Constructor, destructor.
 566   explicit deque(const allocator_type& __a = allocator_type())
 567     : _Base(__a, 0) {}
 568   deque(const deque& __x) : _Base(__x.get_allocator(), __x.size())
 569     { uninitialized_copy(__x.begin(), __x.end(), _M_start); }
 570   deque(size_type __n, const value_type& __value,
 571         const allocator_type& __a = allocator_type()) : _Base(__a, __n)
 572     { _M_fill_initialize(__value); }
 573   explicit deque(size_type __n) : _Base(allocator_type(), __n)
 574     { _M_fill_initialize(value_type()); }
 575
 576 #ifdef __STL_MEMBER_TEMPLATES
 577
 578   // Check whether it's an integral type.  If so, it's not an iterator.
 579   template <class _InputIterator>
 580   deque(_InputIterator __first, _InputIterator __last,
 581         const allocator_type& __a = allocator_type()) : _Base(__a) {
 582     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 583     _M_initialize_dispatch(__first, __last, _Integral());
 584   }
 585
 586   template <class _Integer>
 587   void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) {
 588     _M_initialize_map(__n);
 589     _M_fill_initialize(__x);
 590   }
 591
 592   template <class _InputIter>
 593   void _M_initialize_dispatch(_InputIter __first, _InputIter __last,
 594                               __false_type) {
 595     _M_range_initialize(__first, __last, __ITERATOR_CATEGORY(__first));
 596   }
 597
 598 #else /* __STL_MEMBER_TEMPLATES */
 599
 600   deque(const value_type* __first, const value_type* __last,
 601         const allocator_type& __a = allocator_type())
 602     : _Base(__a, __last - __first)
 603     { uninitialized_copy(__first, __last, _M_start); }
 604   deque(const_iterator __first, const_iterator __last,
 605         const allocator_type& __a = allocator_type())
 606     : _Base(__a, __last - __first)
 607     { uninitialized_copy(__first, __last, _M_start); }
 608
 609 #endif /* __STL_MEMBER_TEMPLATES */
 610
 611   ~deque() { destroy(_M_start, _M_finish); }
 612
 613   deque& operator= (const deque& __x) {
 614     const size_type __len = size();
 615     if (&__x != this) {
 616       if (__len >= __x.size())
 617         erase(copy(__x.begin(), __x.end(), _M_start), _M_finish);
 618       else {
 619         const_iterator __mid = __x.begin() + difference_type(__len);
 620         copy(__x.begin(), __mid, _M_start);
 621         insert(_M_finish, __mid, __x.end());
 622       }
 623     }
 624     return *this;
 625   }
 626
 627   void swap(deque& __x) {
 628     __STD::swap(_M_start, __x._M_start);
 629     __STD::swap(_M_finish, __x._M_finish);
 630     __STD::swap(_M_map, __x._M_map);
 631     __STD::swap(_M_map_size, __x._M_map_size);
 632   }
 633
 634 public:
 635   // assign(), a generalized assignment member function.  Two
 636   // versions: one that takes a count, and one that takes a range.
 637   // The range version is a member template, so we dispatch on whether
 638   // or not the type is an integer.
 639
 640   void assign(size_type __n, const _Tp& __val) {
 641     if (__n > size()) {
 642       fill(begin(), end(), __val);
 643       insert(end(), __n - size(), __val);
 644     }
 645     else {
 646       erase(begin() + __n, end());
 647       fill(begin(), end(), __val);
 648     }
 649   }
 650
 651 #ifdef __STL_MEMBER_TEMPLATES
 652
 653   template <class _InputIterator>
 654   void assign(_InputIterator __first, _InputIterator __last) {
 655     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 656     _M_assign_dispatch(__first, __last, _Integral());
 657   }
 658
 659 private:                        // helper functions for assign()
 660
 661   template <class _Integer>
 662   void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
 663     { assign((size_type) __n, (_Tp) __val); }
 664
 665   template <class _InputIterator>
 666   void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
 667                           __false_type) {
 668     _M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first));
 669   }
 670
 671   template <class _InputIterator>
 672   void _M_assign_aux(_InputIterator __first, _InputIterator __last,
 673                      input_iterator_tag);
 674
 675   template <class _ForwardIterator>
 676   void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
 677                      forward_iterator_tag) {
 678     size_type __len = 0;
 679     distance(__first, __last, __len);
 680     if (__len > size()) {
 681       _ForwardIterator __mid = __first;
 682       advance(__mid, size());
 683       copy(__first, __mid, begin());
 684       insert(end(), __mid, __last);
 685     }
 686     else
 687       erase(copy(__first, __last, begin()), end());
 688   }
 689
 690 #endif /* __STL_MEMBER_TEMPLATES */
 691
 692 public:                         // push_* and pop_*
 693
 694   void push_back(const value_type& __t) {
 695     if (_M_finish._M_cur != _M_finish._M_last - 1) {
 696       construct(_M_finish._M_cur, __t);
 697       ++_M_finish._M_cur;
 698     }
 699     else
 700       _M_push_back_aux(__t);
 701   }
 702
 703   void push_back() {
 704     if (_M_finish._M_cur != _M_finish._M_last - 1) {
 705       construct(_M_finish._M_cur);
 706       ++_M_finish._M_cur;
 707     }
 708     else
 709       _M_push_back_aux();
 710   }
 711
 712   void push_front(const value_type& __t) {
 713     if (_M_start._M_cur != _M_start._M_first) {
 714       construct(_M_start._M_cur - 1, __t);
 715       --_M_start._M_cur;
 716     }
 717     else
 718       _M_push_front_aux(__t);
 719   }
 720
 721   void push_front() {
 722     if (_M_start._M_cur != _M_start._M_first) {
 723       construct(_M_start._M_cur - 1);
 724       --_M_start._M_cur;
 725     }
 726     else
 727       _M_push_front_aux();
 728   }
 729
 730
 731   void pop_back() {
 732     if (_M_finish._M_cur != _M_finish._M_first) {
 733       --_M_finish._M_cur;
 734       destroy(_M_finish._M_cur);
 735     }
 736     else
 737       _M_pop_back_aux();
 738   }
 739
 740   void pop_front() {
 741     if (_M_start._M_cur != _M_start._M_last - 1) {
 742       destroy(_M_start._M_cur);
 743       ++_M_start._M_cur;
 744     }
 745     else
 746       _M_pop_front_aux();
 747   }
 748
 749 public:                         // Insert
 750
 751   iterator insert(iterator position, const value_type& __x) {
 752     if (position._M_cur == _M_start._M_cur) {
 753       push_front(__x);
 754       return _M_start;
 755     }
 756     else if (position._M_cur == _M_finish._M_cur) {
 757       push_back(__x);
 758       iterator __tmp = _M_finish;
 759       --__tmp;
 760       return __tmp;
 761     }
 762     else {
 763       return _M_insert_aux(position, __x);
 764     }
 765   }
 766
 767   iterator insert(iterator __position)
 768     { return insert(__position, value_type()); }
 769
 770   void insert(iterator __pos, size_type __n, const value_type& __x);
 771
 772 #ifdef __STL_MEMBER_TEMPLATES
 773
 774   // Check whether it's an integral type.  If so, it's not an iterator.
 775   template <class _InputIterator>
 776   void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
 777     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 778     _M_insert_dispatch(__pos, __first, __last, _Integral());
 779   }
 780
 781   template <class _Integer>
 782   void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
 783                           __true_type) {
 784     insert(__pos, (size_type) __n, (value_type) __x);
 785   }
 786
 787   template <class _InputIterator>
 788   void _M_insert_dispatch(iterator __pos,
 789                           _InputIterator __first, _InputIterator __last,
 790                           __false_type) {
 791     insert(__pos, __first, __last, __ITERATOR_CATEGORY(__first));
 792   }
 793
 794 #else /* __STL_MEMBER_TEMPLATES */
 795
 796   void insert(iterator __pos,
 797               const value_type* __first, const value_type* __last);
 798   void insert(iterator __pos,
 799               const_iterator __first, const_iterator __last);
 800
 801 #endif /* __STL_MEMBER_TEMPLATES */
 802
 803   void resize(size_type __new_size, const value_type& __x) {
 804     const size_type __len = size();
 805     if (__new_size < __len)
 806       erase(_M_start + __new_size, _M_finish);
 807     else
 808       insert(_M_finish, __new_size - __len, __x);
 809   }
 810
 811   void resize(size_type new_size) { resize(new_size, value_type()); }
 812
 813 public:                         // Erase
 814   iterator erase(iterator __pos) {
 815     iterator __next = __pos;
 816     ++__next;
 817     difference_type __index = __pos - _M_start;
 818     if (static_cast<size_type>(__index) < (size() >> 1)) {
 819       copy_backward(_M_start, __pos, __next);
 820       pop_front();
 821     }
 822     else {
 823       copy(__next, _M_finish, __pos);
 824       pop_back();
 825     }
 826     return _M_start + __index;
 827   }
 828
 829   iterator erase(iterator __first, iterator __last);
 830   void clear();
 831
 832 protected:                        // Internal construction/destruction
 833
 834   void _M_fill_initialize(const value_type& __value);
 835
 836 #ifdef __STL_MEMBER_TEMPLATES
 837
 838   template <class _InputIterator>
 839   void _M_range_initialize(_InputIterator __first, _InputIterator __last,
 840                         input_iterator_tag);
 841
 842   template <class _ForwardIterator>
 843   void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
 844                         forward_iterator_tag);
 845
 846 #endif /* __STL_MEMBER_TEMPLATES */
 847
 848 protected:                        // Internal push_* and pop_*
 849
 850   void _M_push_back_aux(const value_type&);
 851   void _M_push_back_aux();
 852   void _M_push_front_aux(const value_type&);
 853   void _M_push_front_aux();
 854   void _M_pop_back_aux();
 855   void _M_pop_front_aux();
 856
 857 protected:                        // Internal insert functions
 858
 859 #ifdef __STL_MEMBER_TEMPLATES
 860
 861   template <class _InputIterator>
 862   void insert(iterator __pos, _InputIterator __first, _InputIterator __last,
 863               input_iterator_tag);
 864
 865   template <class _ForwardIterator>
 866   void insert(iterator __pos,
 867               _ForwardIterator __first, _ForwardIterator __last,
 868               forward_iterator_tag);
 869
 870 #endif /* __STL_MEMBER_TEMPLATES */
 871
 872   iterator _M_insert_aux(iterator __pos, const value_type& __x);
 873   iterator _M_insert_aux(iterator __pos);
 874   void _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
 875
 876 #ifdef __STL_MEMBER_TEMPLATES
 877
 878   template <class _ForwardIterator>
 879   void _M_insert_aux(iterator __pos,
 880                      _ForwardIterator __first, _ForwardIterator __last,
 881                      size_type __n);
 882
 883 #else /* __STL_MEMBER_TEMPLATES */
 884
 885   void _M_insert_aux(iterator __pos,
 886                      const value_type* __first, const value_type* __last,
 887                      size_type __n);
 888
 889   void _M_insert_aux(iterator __pos,
 890                      const_iterator __first, const_iterator __last,
 891                      size_type __n);
 892
 893 #endif /* __STL_MEMBER_TEMPLATES */
 894
 895   iterator _M_reserve_elements_at_front(size_type __n) {
 896     size_type __vacancies = _M_start._M_cur - _M_start._M_first;
 897     if (__n > __vacancies)
 898       _M_new_elements_at_front(__n - __vacancies);
 899     return _M_start - difference_type(__n);
 900   }
 901
 902   iterator _M_reserve_elements_at_back(size_type __n) {
 903     size_type __vacancies = (_M_finish._M_last - _M_finish._M_cur) - 1;
 904     if (__n > __vacancies)
 905       _M_new_elements_at_back(__n - __vacancies);
 906     return _M_finish + difference_type(__n);
 907   }
 908
 909   void _M_new_elements_at_front(size_type __new_elements);
 910   void _M_new_elements_at_back(size_type __new_elements);
 911
 912 protected:                      // Allocation of _M_map and nodes
 913
 914   // Makes sure the _M_map has space for new nodes.  Does not actually
 915   //  add the nodes.  Can invalidate _M_map pointers.  (And consequently,
 916   //  deque iterators.)
 917
 918   void _M_reserve_map_at_back (size_type __nodes_to_add = 1) {
 919     if (__nodes_to_add + 1 > _M_map_size - (_M_finish._M_node - _M_map))
 920       _M_reallocate_map(__nodes_to_add, false);
 921   }
 922
 923   void _M_reserve_map_at_front (size_type __nodes_to_add = 1) {
 924     if (__nodes_to_add > size_type(_M_start._M_node - _M_map))
 925       _M_reallocate_map(__nodes_to_add, true);
 926   }
 927
 928   void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
 929
 930 #ifdef __STL_NON_TYPE_TMPL_PARAM_BUG
 931 public:
 932   bool operator==(const deque<_Tp,_Alloc,0>& __x) const {
 933     return size() == __x.size() && equal(begin(), end(), __x.begin());
 934   }
 935   bool operator!=(const deque<_Tp,_Alloc,0>& __x) const {
 936     return size() != __x.size() || !equal(begin(), end(), __x.begin());
 937   }
 938   bool operator<(const deque<_Tp,_Alloc,0>& __x) const {
 939     return lexicographical_compare(begin(), end(), __x.begin(), __x.end());
 940   }
 941 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */
 942 };
 943
 944 // Non-inline member functions
 945
 946 #ifdef __STL_MEMBER_TEMPLATES
 947
 948 template <class _Tp, class _Alloc, size_t __bufsize>
 949 template <class _InputIter>
 950 void deque<_Tp, _Alloc, __bufsize>
 951   ::_M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag)
 952 {
 953   iterator __cur = begin();
 954   for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
 955     *__cur = *__first;
 956   if (__first == __last)
 957     erase(__cur, end());
 958   else
 959     insert(end(), __first, __last);
 960 }
 961
 962 #endif /* __STL_MEMBER_TEMPLATES */
 963
 964 template <class _Tp, class _Alloc, size_t __bufsize>
 965 void
 966 deque<_Tp, _Alloc, __bufsize>::insert(iterator __pos,
 967                                       size_type __n, const value_type& __x)
 968 {
 969   if (__pos._M_cur == _M_start._M_cur) {
 970     iterator __new_start = _M_reserve_elements_at_front(__n);
 971     uninitialized_fill(__new_start, _M_start, __x);
 972     _M_start = __new_start;
 973   }
 974   else if (__pos._M_cur == _M_finish._M_cur) {
 975     iterator __new_finish = _M_reserve_elements_at_back(__n);
 976     uninitialized_fill(_M_finish, __new_finish, __x);
 977     _M_finish = __new_finish;
 978   }
 979   else
 980     _M_insert_aux(__pos, __n, __x);
 981 }
 982
 983 #ifndef __STL_MEMBER_TEMPLATES
 984
 985 template <class _Tp, class _Alloc, size_t __bufsize>
 986 void deque<_Tp, _Alloc, __bufsize>::insert(iterator __pos,
 987                                            const value_type* __first,
 988                                            const value_type* __last) {
 989   size_type __n = __last - __first;
 990   if (__pos._M_cur == _M_start._M_cur) {
 991     iterator __new_start = _M_reserve_elements_at_front(__n);
 992     __STL_TRY {
 993       uninitialized_copy(__first, __last, __new_start);
 994       _M_start = __new_start;
 995     }
 996     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
 997   }
 998   else if (__pos._M_cur == _M_finish._M_cur) {
 999     iterator __new_finish = _M_reserve_elements_at_back(__n);
1000     __STL_TRY {
1001       uninitialized_copy(__first, __last, _M_finish);
1002       _M_finish = __new_finish;
1003     }
1004     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
1005                                   __new_finish._M_node + 1));
1006   }
1007   else
1008     _M_insert_aux(__pos, __first, __last, __n);
1009 }
1010
1011 template <class _Tp, class _Alloc, size_t __bufsize>
1012 void deque<_Tp,_Alloc,__bufsize>::insert(iterator __pos,
1013                                          const_iterator __first,
1014                                          const_iterator __last)
1015 {
1016   size_type __n = __last - __first;
1017   if (__pos._M_cur == _M_start._M_cur) {
1018     iterator __new_start = _M_reserve_elements_at_front(__n);
1019     __STL_TRY {
1020       uninitialized_copy(__first, __last, __new_start);
1021       _M_start = __new_start;
1022     }
1023     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
1024   }
1025   else if (__pos._M_cur == _M_finish._M_cur) {
1026     iterator __new_finish = _M_reserve_elements_at_back(__n);
1027     __STL_TRY {
1028       uninitialized_copy(__first, __last, _M_finish);
1029       _M_finish = __new_finish;
1030     }
1031     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
1032                  __new_finish._M_node + 1));
1033   }
1034   else
1035     _M_insert_aux(__pos, __first, __last, __n);
1036 }
1037
1038 #endif /* __STL_MEMBER_TEMPLATES */
1039
1040 template <class _Tp, class _Alloc, size_t __bufsize>
1041 deque<_Tp,_Alloc,__bufsize>::iterator
1042 deque<_Tp,_Alloc,__bufsize>::erase(iterator __first, iterator __last)
1043 {
1044   if (__first == _M_start && __last == _M_finish) {
1045     clear();
1046     return _M_finish;
1047   }
1048   else {
1049     difference_type __n = __last - __first;
1050     difference_type __elems_before = __first - _M_start;
1051     if (static_cast<size_type>(__elems_before) < (size() - __n) / 2) {
1052       copy_backward(_M_start, __first, __last);
1053       iterator __new_start = _M_start + __n;
1054       destroy(_M_start, __new_start);
1055       _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
1056       _M_start = __new_start;
1057     }
1058     else {
1059       copy(__last, _M_finish, __first);
1060       iterator __new_finish = _M_finish - __n;
1061       destroy(__new_finish, _M_finish);
1062       _M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1);
1063       _M_finish = __new_finish;
1064     }
1065     return _M_start + __elems_before;
1066   }
1067 }
1068
1069 template <class _Tp, class _Alloc, size_t __bufsize>
1070 void deque<_Tp,_Alloc,__bufsize>::clear()
1071 {
1072   for (_Map_pointer __node = _M_start._M_node + 1;
1073        __node < _M_finish._M_node;
1074        ++__node) {
1075     destroy(*__node, *__node + _S_buffer_size());
1076     _M_deallocate_node(*__node);
1077   }
1078
1079   if (_M_start._M_node != _M_finish._M_node) {
1080     destroy(_M_start._M_cur, _M_start._M_last);
1081     destroy(_M_finish._M_first, _M_finish._M_cur);
1082     _M_deallocate_node(_M_finish._M_first);
1083   }
1084   else
1085     destroy(_M_start._M_cur, _M_finish._M_cur);
1086
1087   _M_finish = _M_start;
1088 }
1089
1090 // Precondition: _M_start and _M_finish have already been initialized,
1091 // but none of the deque's elements have yet been constructed.
1092 template <class _Tp, class _Alloc, size_t __bufsize>
1093 void
1094 deque<_Tp,_Alloc,__bufsize>::_M_fill_initialize(const value_type& __value) {
1095   _Map_pointer __cur;
1096   __STL_TRY {
1097     for (__cur = _M_start._M_node; __cur < _M_finish._M_node; ++__cur)
1098       uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value);
1099     uninitialized_fill(_M_finish._M_first, _M_finish._M_cur, __value);
1100   }
1101   __STL_UNWIND(destroy(_M_start, iterator(*__cur, __cur)));
1102 }
1103
1104 #ifdef __STL_MEMBER_TEMPLATES
1105
1106 template <class _Tp, class _Alloc, size_t __bufsize>
1107 template <class _InputIterator>
1108 void
1109 deque<_Tp,_Alloc,__bufsize>::_M_range_initialize(_InputIterator __first,
1110                                                  _InputIterator __last,
1111                                                  input_iterator_tag)
1112 {
1113   _M_initialize_map(0);
1114   for ( ; __first != __last; ++__first)
1115     push_back(*__first);
1116 }
1117
1118 template <class _Tp, class _Alloc, size_t __bufsize>
1119 template <class _ForwardIterator>
1120 void
1121 deque<_Tp,_Alloc,__bufsize>::_M_range_initialize(_ForwardIterator __first,
1122                                                  _ForwardIterator __last,
1123                                                  forward_iterator_tag)
1124 {
1125   size_type __n = 0;
1126   distance(__first, __last, __n);
1127   _M_initialize_map(__n);
1128
1129   _Map_pointer __cur_node;
1130   __STL_TRY {
1131     for (__cur_node = _M_start._M_node;
1132          __cur_node < _M_finish._M_node;
1133          ++__cur_node) {
1134       _ForwardIterator __mid = __first;
1135       advance(__mid, _S_buffer_size());
1136       uninitialized_copy(__first, __mid, *__cur_node);
1137       __first = __mid;
1138     }
1139     uninitialized_copy(__first, __last, _M_finish._M_first);
1140   }
1141   __STL_UNWIND(destroy(_M_start, iterator(*__cur_node, __cur_node)));
1142 }
1143
1144 #endif /* __STL_MEMBER_TEMPLATES */
1145
1146 // Called only if _M_finish._M_cur == _M_finish._M_last - 1.
1147 template <class _Tp, class _Alloc, size_t __bufsize>
1148 void
1149 deque<_Tp,_Alloc,__bufsize>::_M_push_back_aux(const value_type& __t)
1150 {
1151   value_type __t_copy = __t;
1152   _M_reserve_map_at_back();
1153   *(_M_finish._M_node + 1) = _M_allocate_node();
1154   __STL_TRY {
1155     construct(_M_finish._M_cur, __t_copy);
1156     _M_finish._M_set_node(_M_finish._M_node + 1);
1157     _M_finish._M_cur = _M_finish._M_first;
1158   }
1159   __STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1)));
1160 }
1161
1162 // Called only if _M_finish._M_cur == _M_finish._M_last - 1.
1163 template <class _Tp, class _Alloc, size_t __bufsize>
1164 void
1165 deque<_Tp,_Alloc,__bufsize>::_M_push_back_aux()
1166 {
1167   _M_reserve_map_at_back();
1168   *(_M_finish._M_node + 1) = _M_allocate_node();
1169   __STL_TRY {
1170     construct(_M_finish._M_cur);
1171     _M_finish._M_set_node(_M_finish._M_node + 1);
1172     _M_finish._M_cur = _M_finish._M_first;
1173   }
1174   __STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1)));
1175 }
1176
1177 // Called only if _M_start._M_cur == _M_start._M_first.
1178 template <class _Tp, class _Alloc, size_t __bufsize>
1179 void
1180 deque<_Tp,_Alloc,__bufsize>::_M_push_front_aux(const value_type& __t)
1181 {
1182   value_type __t_copy = __t;
1183   _M_reserve_map_at_front();
1184   *(_M_start._M_node - 1) = _M_allocate_node();
1185   __STL_TRY {
1186     _M_start._M_set_node(_M_start._M_node - 1);
1187     _M_start._M_cur = _M_start._M_last - 1;
1188     construct(_M_start._M_cur, __t_copy);
1189   }
1190   __STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1))));
1191 }
1192
1193 // Called only if _M_start._M_cur == _M_start._M_first.
1194 template <class _Tp, class _Alloc, size_t __bufsize>
1195 void
1196 deque<_Tp,_Alloc,__bufsize>::_M_push_front_aux()
1197 {
1198   _M_reserve_map_at_front();
1199   *(_M_start._M_node - 1) = _M_allocate_node();
1200   __STL_TRY {
1201     _M_start._M_set_node(_M_start._M_node - 1);
1202     _M_start._M_cur = _M_start._M_last - 1;
1203     construct(_M_start._M_cur);
1204   }
1205   __STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1))));
1206 }
1207
1208 // Called only if _M_finish._M_cur == _M_finish._M_first.
1209 template <class _Tp, class _Alloc, size_t __bufsize>
1210 void
1211 deque<_Tp,_Alloc,__bufsize>::_M_pop_back_aux()
1212 {
1213   _M_deallocate_node(_M_finish._M_first);
1214   _M_finish._M_set_node(_M_finish._M_node - 1);
1215   _M_finish._M_cur = _M_finish._M_last - 1;
1216   destroy(_M_finish._M_cur);
1217 }
1218
1219 // Called only if _M_start._M_cur == _M_start._M_last - 1.  Note that
1220 // if the deque has at least one element (a precondition for this member
1221 // function), and if _M_start._M_cur == _M_start._M_last, then the deque
1222 // must have at least two nodes.
1223 template <class _Tp, class _Alloc, size_t __bufsize>
1224 void
1225 deque<_Tp,_Alloc,__bufsize>::_M_pop_front_aux()
1226 {
1227   destroy(_M_start._M_cur);
1228   _M_deallocate_node(_M_start._M_first);
1229   _M_start._M_set_node(_M_start._M_node + 1);
1230   _M_start._M_cur = _M_start._M_first;
1231 }
1232
1233 #ifdef __STL_MEMBER_TEMPLATES
1234
1235 template <class _Tp, class _Alloc, size_t __bufsize>
1236 template <class _InputIterator>
1237 void
1238 deque<_Tp,_Alloc,__bufsize>::insert(iterator __pos,
1239                                     _InputIterator __first,
1240                                     _InputIterator __last,
1241                                     input_iterator_tag)
1242 {
1243   copy(__first, __last, inserter(*this, __pos));
1244 }
1245
1246 template <class _Tp, class _Alloc, size_t __bufsize>
1247 template <class _ForwardIterator>
1248 void
1249 deque<_Tp,_Alloc,__bufsize>::insert(iterator __pos,
1250                                     _ForwardIterator __first,
1251                                     _ForwardIterator __last,
1252                                     forward_iterator_tag) {
1253   size_type __n = 0;
1254   distance(__first, __last, __n);
1255   if (__pos._M_cur == _M_start._M_cur) {
1256     iterator __new_start = _M_reserve_elements_at_front(__n);
1257     __STL_TRY {
1258       uninitialized_copy(__first, __last, __new_start);
1259       _M_start = __new_start;
1260     }
1261     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
1262   }
1263   else if (__pos._M_cur == _M_finish._M_cur) {
1264     iterator __new_finish = _M_reserve_elements_at_back(__n);
1265     __STL_TRY {
1266       uninitialized_copy(__first, __last, _M_finish);
1267       _M_finish = __new_finish;
1268     }
1269     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
1270                                   __new_finish._M_node + 1));
1271   }
1272   else
1273     _M_insert_aux(__pos, __first, __last, __n);
1274 }
1275
1276 #endif /* __STL_MEMBER_TEMPLATES */
1277
1278 template <class _Tp, class _Alloc, size_t __bufsize>
1279 typename deque<_Tp, _Alloc, __bufsize>::iterator
1280 deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos,
1281                                            const value_type& __x)
1282 {
1283   difference_type __index = __pos - _M_start;
1284   value_type __x_copy = __x;
1285   if (static_cast<size_type>(__index) < size() / 2) {
1286     push_front(front());
1287     iterator __front1 = _M_start;
1288     ++__front1;
1289     iterator __front2 = __front1;
1290     ++__front2;
1291     __pos = _M_start + __index;
1292     iterator __pos1 = __pos;
1293     ++__pos1;
1294     copy(__front2, __pos1, __front1);
1295   }
1296   else {
1297     push_back(back());
1298     iterator __back1 = _M_finish;
1299     --__back1;
1300     iterator __back2 = __back1;
1301     --__back2;
1302     __pos = _M_start + __index;
1303     copy_backward(__pos, __back2, __back1);
1304   }
1305   *__pos = __x_copy;
1306   return __pos;
1307 }
1308
1309 template <class _Tp, class _Alloc, size_t __bufsize>
1310 typename deque<_Tp,_Alloc,__bufsize>::iterator
1311 deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos)
1312 {
1313   difference_type __index = __pos - _M_start;
1314   if (static_cast<size_type>(__index) < size() / 2) {
1315     push_front(front());
1316     iterator __front1 = _M_start;
1317     ++__front1;
1318     iterator __front2 = __front1;
1319     ++__front2;
1320     __pos = _M_start + __index;
1321     iterator __pos1 = __pos;
1322     ++__pos1;
1323     copy(__front2, __pos1, __front1);
1324   }
1325   else {
1326     push_back(back());
1327     iterator __back1 = _M_finish;
1328     --__back1;
1329     iterator __back2 = __back1;
1330     --__back2;
1331     __pos = _M_start + __index;
1332     copy_backward(__pos, __back2, __back1);
1333   }
1334   *__pos = value_type();
1335   return __pos;
1336 }
1337
1338 template <class _Tp, class _Alloc, size_t __bufsize>
1339 void
1340 deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos,
1341                                            size_type __n,
1342                                            const value_type& __x)
1343 {
1344   const difference_type __elems_before = __pos - _M_start;
1345   size_type __length = size();
1346   value_type __x_copy = __x;
1347   if (static_cast<size_type>(__elems_before) < __length / 2) {
1348     iterator __new_start = _M_reserve_elements_at_front(__n);
1349     iterator __old_start = _M_start;
1350     __pos = _M_start + __elems_before;
1351     __STL_TRY {
1352       if (__elems_before >= difference_type(__n)) {
1353         iterator __start_n = _M_start + difference_type(__n);
1354         uninitialized_copy(_M_start, __start_n, __new_start);
1355         _M_start = __new_start;
1356         copy(__start_n, __pos, __old_start);
1357         fill(__pos - difference_type(__n), __pos, __x_copy);
1358       }
1359       else {
1360         __uninitialized_copy_fill(_M_start, __pos, __new_start,
1361                                   _M_start, __x_copy);
1362         _M_start = __new_start;
1363         fill(__old_start, __pos, __x_copy);
1364       }
1365     }
1366     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
1367   }
1368   else {
1369     iterator __new_finish = _M_reserve_elements_at_back(__n);
1370     iterator __old_finish = _M_finish;
1371     const difference_type __elems_after =
1372       difference_type(__length) - __elems_before;
1373     __pos = _M_finish - __elems_after;
1374     __STL_TRY {
1375       if (__elems_after > difference_type(__n)) {
1376         iterator __finish_n = _M_finish - difference_type(__n);
1377         uninitialized_copy(__finish_n, _M_finish, _M_finish);
1378         _M_finish = __new_finish;
1379         copy_backward(__pos, __finish_n, __old_finish);
1380         fill(__pos, __pos + difference_type(__n), __x_copy);
1381       }
1382       else {
1383         __uninitialized_fill_copy(_M_finish, __pos + difference_type(__n),
1384                                   __x_copy, __pos, _M_finish);
1385         _M_finish = __new_finish;
1386         fill(__pos, __old_finish, __x_copy);
1387       }
1388     }
1389     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
1390                                   __new_finish._M_node + 1));
1391   }
1392 }
1393
1394 #ifdef __STL_MEMBER_TEMPLATES
1395
1396 template <class _Tp, class _Alloc, size_t __bufsize>
1397 template <class _ForwardIterator>
1398 void
1399 deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos,
1400                                            _ForwardIterator __first,
1401                                            _ForwardIterator __last,
1402                                            size_type __n)
1403 {
1404   const difference_type __elemsbefore = __pos - _M_start;
1405   size_type __length = size();
1406   if (static_cast<size_type>(__elemsbefore) < __length / 2) {
1407     iterator __new_start = _M_reserve_elements_at_front(__n);
1408     iterator __old_start = _M_start;
1409     __pos = _M_start + __elemsbefore;
1410     __STL_TRY {
1411       if (__elemsbefore >= difference_type(__n)) {
1412         iterator __start_n = _M_start + difference_type(__n);
1413         uninitialized_copy(_M_start, __start_n, __new_start);
1414         _M_start = __new_start;
1415         copy(__start_n, __pos, __old_start);
1416         copy(__first, __last, __pos - difference_type(__n));
1417       }
1418       else {
1419         _ForwardIterator __mid = __first;
1420         advance(__mid, difference_type(__n) - __elemsbefore);
1421         __uninitialized_copy_copy(_M_start, __pos, __first, __mid,
1422                                   __new_start);
1423         _M_start = __new_start;
1424         copy(__mid, __last, __old_start);
1425       }
1426     }
1427     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
1428   }
1429   else {
1430     iterator __new_finish = _M_reserve_elements_at_back(__n);
1431     iterator __old_finish = _M_finish;
1432     const difference_type __elemsafter =
1433       difference_type(__length) - __elemsbefore;
1434     __pos = _M_finish - __elemsafter;
1435     __STL_TRY {
1436       if (__elemsafter > difference_type(__n)) {
1437         iterator __finish_n = _M_finish - difference_type(__n);
1438         uninitialized_copy(__finish_n, _M_finish, _M_finish);
1439         _M_finish = __new_finish;
1440         copy_backward(__pos, __finish_n, __old_finish);
1441         copy(__first, __last, __pos);
1442       }
1443       else {
1444         _ForwardIterator __mid = __first;
1445         advance(__mid, __elemsafter);
1446         __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);
1447         _M_finish = __new_finish;
1448         copy(__first, __mid, __pos);
1449       }
1450     }
1451     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
1452                                   __new_finish._M_node + 1));
1453   }
1454 }
1455
1456 #else /* __STL_MEMBER_TEMPLATES */
1457
1458 template <class _Tp, class _Alloc, size_t __bufsize>
1459 void
1460 deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos,
1461                                            const value_type* __first,
1462                                            const value_type* __last,
1463                                            size_type __n)
1464 {
1465   const difference_type __elemsbefore = __pos - _M_start;
1466   size_type __length = size();
1467   if (__elemsbefore < __length / 2) {
1468     iterator __new_start = _M_reserve_elements_at_front(__n);
1469     iterator __old_start = _M_start;
1470     __pos = _M_start + __elemsbefore;
1471     __STL_TRY {
1472       if (__elemsbefore >= difference_type(__n)) {
1473         iterator __start_n = _M_start + difference_type(__n);
1474         uninitialized_copy(_M_start, __start_n, __new_start);
1475         _M_start = __new_start;
1476         copy(__start_n, __pos, __old_start);
1477         copy(__first, __last, __pos - difference_type(__n));
1478       }
1479       else {
1480         const value_type* __mid =
1481           __first + (difference_type(__n) - __elemsbefore);
1482         __uninitialized_copy_copy(_M_start, __pos, __first, __mid,
1483                                   __new_start);
1484         _M_start = __new_start;
1485         copy(__mid, __last, __old_start);
1486       }
1487     }
1488     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
1489   }
1490   else {
1491     iterator __new_finish = _M_reserve_elements_at_back(__n);
1492     iterator __old_finish = _M_finish;
1493     const difference_type __elemsafter =
1494       difference_type(__length) - __elemsbefore;
1495     __pos = _M_finish - __elemsafter;
1496     __STL_TRY {
1497       if (__elemsafter > difference_type(__n)) {
1498         iterator __finish_n = _M_finish - difference_type(__n);
1499         uninitialized_copy(__finish_n, _M_finish, _M_finish);
1500         _M_finish = __new_finish;
1501         copy_backward(__pos, __finish_n, __old_finish);
1502         copy(__first, __last, __pos);
1503       }
1504       else {
1505         const value_type* __mid = __first + __elemsafter;
1506         __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);
1507         _M_finish = __new_finish;
1508         copy(__first, __mid, __pos);
1509       }
1510     }
1511     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
1512                                   __new_finish._M_node + 1));
1513   }
1514 }
1515
1516 template <class _Tp, class _Alloc, size_t __bufsize>
1517 void
1518 deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos,
1519                                            const_iterator __first,
1520                                            const_iterator __last,
1521                                            size_type __n)
1522 {
1523   const difference_type __elemsbefore = __pos - _M_start;
1524   size_type __length = size();
1525   if (__elemsbefore < __length / 2) {
1526     iterator __new_start = _M_reserve_elements_at_front(__n);
1527     iterator __old_start = _M_start;
1528     __pos = _M_start + __elemsbefore;
1529     __STL_TRY {
1530       if (__elemsbefore >= __n) {
1531         iterator __start_n = _M_start + __n;
1532         uninitialized_copy(_M_start, __start_n, __new_start);
1533         _M_start = __new_start;
1534         copy(__start_n, __pos, __old_start);
1535         copy(__first, __last, __pos - difference_type(__n));
1536       }
1537       else {
1538         const_iterator __mid = __first + (__n - __elemsbefore);
1539         __uninitialized_copy_copy(_M_start, __pos, __first, __mid,
1540                                   __new_start);
1541         _M_start = __new_start;
1542         copy(__mid, __last, __old_start);
1543       }
1544     }
1545     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
1546   }
1547   else {
1548     iterator __new_finish = _M_reserve_elements_at_back(__n);
1549     iterator __old_finish = _M_finish;
1550     const difference_type __elemsafter = __length - __elemsbefore;
1551     __pos = _M_finish - __elemsafter;
1552     __STL_TRY {
1553       if (__elemsafter > __n) {
1554         iterator __finish_n = _M_finish - difference_type(__n);
1555         uninitialized_copy(__finish_n, _M_finish, _M_finish);
1556         _M_finish = __new_finish;
1557         copy_backward(__pos, __finish_n, __old_finish);
1558         copy(__first, __last, __pos);
1559       }
1560       else {
1561         const_iterator __mid = __first + __elemsafter;
1562         __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);
1563         _M_finish = __new_finish;
1564         copy(__first, __mid, __pos);
1565       }
1566     }
1567     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
1568                  __new_finish._M_node + 1));
1569   }
1570 }
1571
1572 #endif /* __STL_MEMBER_TEMPLATES */
1573
1574 template <class _Tp, class _Alloc, size_t __bufsize>
1575 void
1576 deque<_Tp,_Alloc,__bufsize>::_M_new_elements_at_front(size_type __new_elems)
1577 {
1578   size_type __new_nodes
1579       = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
1580   _M_reserve_map_at_front(__new_nodes);
1581   size_type __i;
1582   __STL_TRY {
1583     for (__i = 1; __i <= __new_nodes; ++__i)
1584       *(_M_start._M_node - __i) = _M_allocate_node();
1585   }
1586 #       ifdef __STL_USE_EXCEPTIONS
1587   catch(...) {
1588     for (size_type __j = 1; __j < __i; ++__j)
1589       _M_deallocate_node(*(_M_start._M_node - __j));
1590     throw;
1591   }
1592 #       endif /* __STL_USE_EXCEPTIONS */
1593 }
1594
1595 template <class _Tp, class _Alloc, size_t __bufsize>
1596 void
1597 deque<_Tp,_Alloc,__bufsize>::_M_new_elements_at_back(size_type __new_elems)
1598 {
1599   size_type __new_nodes
1600       = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
1601   _M_reserve_map_at_back(__new_nodes);
1602   size_type __i;
1603   __STL_TRY {
1604     for (__i = 1; __i <= __new_nodes; ++__i)
1605       *(_M_finish._M_node + __i) = _M_allocate_node();
1606   }
1607 #       ifdef __STL_USE_EXCEPTIONS
1608   catch(...) {
1609     for (size_type __j = 1; __j < __i; ++__j)
1610       _M_deallocate_node(*(_M_finish._M_node + __j));
1611     throw;
1612   }
1613 #       endif /* __STL_USE_EXCEPTIONS */
1614 }
1615
1616 template <class _Tp, class _Alloc, size_t __bufsize>
1617 void
1618 deque<_Tp,_Alloc,__bufsize>::_M_reallocate_map(size_type __nodes_to_add,
1619                                               bool __add_at_front)
1620 {
1621   size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1;
1622   size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
1623
1624   _Map_pointer __new_nstart;
1625   if (_M_map_size > 2 * __new_num_nodes) {
1626     __new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2
1627                      + (__add_at_front ? __nodes_to_add : 0);
1628     if (__new_nstart < _M_start._M_node)
1629       copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
1630     else
1631       copy_backward(_M_start._M_node, _M_finish._M_node + 1,
1632                     __new_nstart + __old_num_nodes);
1633   }
1634   else {
1635     size_type __new_map_size =
1636       _M_map_size + max(_M_map_size, __nodes_to_add) + 2;
1637
1638     _Map_pointer __new_map = _M_allocate_map(__new_map_size);
1639     __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
1640                          + (__add_at_front ? __nodes_to_add : 0);
1641     copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
1642     _M_deallocate_map(_M_map, _M_map_size);
1643
1644     _M_map = __new_map;
1645     _M_map_size = __new_map_size;
1646   }
1647
1648   _M_start._M_set_node(__new_nstart);
1649   _M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
1650 }
1651
1652
1653 // Nonmember functions.
1654
1655 #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
1656
1657 template <class _Tp, class _Alloc, size_t __bufsiz>
1658 bool operator==(const deque<_Tp, _Alloc, __bufsiz>& __x,
1659                 const deque<_Tp, _Alloc, __bufsiz>& __y)
1660 {
1661   return __x.size() == __y.size() &&
1662          equal(__x.begin(), __x.end(), __y.begin());
1663 }
1664
1665 template <class _Tp, class _Alloc, size_t __bufsiz>
1666 bool operator<(const deque<_Tp, _Alloc, __bufsiz>& __x,
1667                const deque<_Tp, _Alloc, __bufsiz>& __y)
1668 {
1669   return lexicographical_compare(__x.begin(), __x.end(),
1670                                  __y.begin(), __y.end());
1671 }
1672
1673 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */
1674
1675 #if defined(__STL_FUNCTION_TMPL_PARTIAL_ORDER) && \
1676     !defined(__STL_NON_TYPE_TMPL_PARAM_BUG)
1677
1678 template <class _Tp, class _Alloc, size_t __bufsiz>
1679 inline void
1680 swap(deque<_Tp,_Alloc,__bufsiz>& __x, deque<_Tp,_Alloc,__bufsiz>& __y)
1681 {
1682   __x.swap(__y);
1683 }
1684
1685 #endif
1686
1687 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
1688 #pragma reset woff 1174
1689 #pragma reset woff 1375
1690 #endif
1691
1692 __STL_END_NAMESPACE
1693
1694 #endif /* __SGI_STL_INTERNAL_DEQUE_H */
1695
1696 // Local Variables:
1697 // mode:C++
1698 // End: