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