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 namespace std
  71 {
  72
  73 // Note: this function is simply a kludge to work around several compilers'
  74 //  bugs in handling constant expressions.
  75 inline size_t __deque_buf_size(size_t __size) {
  76   return __size < 512 ? size_t(512 / __size) : size_t(1);
  77 }
  78
  79 template <class _Tp, class _Ref, class _Ptr>
  80 struct _Deque_iterator {
  81   typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
  82   typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
  83   static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
  84
  85   typedef random_access_iterator_tag iterator_category;
  86   typedef _Tp value_type;
  87   typedef _Ptr pointer;
  88   typedef _Ref reference;
  89   typedef size_t size_type;
  90   typedef ptrdiff_t difference_type;
  91   typedef _Tp** _Map_pointer;
  92
  93   typedef _Deque_iterator _Self;
  94
  95   _Tp* _M_cur;
  96   _Tp* _M_first;
  97   _Tp* _M_last;
  98   _Map_pointer _M_node;
  99
 100   _Deque_iterator(_Tp* __x, _Map_pointer __y)
 101     : _M_cur(__x), _M_first(*__y),
 102       _M_last(*__y + _S_buffer_size()), _M_node(__y) {}
 103   _Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
 104   _Deque_iterator(const iterator& __x)
 105     : _M_cur(__x._M_cur), _M_first(__x._M_first),
 106       _M_last(__x._M_last), _M_node(__x._M_node) {}
 107
 108   reference operator*() const { return *_M_cur; }
 109   pointer operator->() const { return _M_cur; }
 110
 111   difference_type operator-(const _Self& __x) const {
 112     return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +
 113       (_M_cur - _M_first) + (__x._M_last - __x._M_cur);
 114   }
 115
 116   _Self& operator++() {
 117     ++_M_cur;
 118     if (_M_cur == _M_last) {
 119       _M_set_node(_M_node + 1);
 120       _M_cur = _M_first;
 121     }
 122     return *this;
 123   }
 124   _Self operator++(int)  {
 125     _Self __tmp = *this;
 126     ++*this;
 127     return __tmp;
 128   }
 129
 130   _Self& operator--() {
 131     if (_M_cur == _M_first) {
 132       _M_set_node(_M_node - 1);
 133       _M_cur = _M_last;
 134     }
 135     --_M_cur;
 136     return *this;
 137   }
 138   _Self operator--(int) {
 139     _Self __tmp = *this;
 140     --*this;
 141     return __tmp;
 142   }
 143
 144   _Self& operator+=(difference_type __n)
 145   {
 146     difference_type __offset = __n + (_M_cur - _M_first);
 147     if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
 148       _M_cur += __n;
 149     else {
 150       difference_type __node_offset =
 151         __offset > 0 ? __offset / difference_type(_S_buffer_size())
 152                    : -difference_type((-__offset - 1) / _S_buffer_size()) - 1;
 153       _M_set_node(_M_node + __node_offset);
 154       _M_cur = _M_first +
 155         (__offset - __node_offset * difference_type(_S_buffer_size()));
 156     }
 157     return *this;
 158   }
 159
 160   _Self operator+(difference_type __n) const
 161   {
 162     _Self __tmp = *this;
 163     return __tmp += __n;
 164   }
 165
 166   _Self& operator-=(difference_type __n) { return *this += -__n; }
 167
 168   _Self operator-(difference_type __n) const {
 169     _Self __tmp = *this;
 170     return __tmp -= __n;
 171   }
 172
 173   reference operator[](difference_type __n) const { return *(*this + __n); }
 174
 175   bool operator==(const _Self& __x) const { return _M_cur == __x._M_cur; }
 176   bool operator!=(const _Self& __x) const { return !(*this == __x); }
 177   bool operator<(const _Self& __x) const {
 178     return (_M_node == __x._M_node) ?
 179       (_M_cur < __x._M_cur) : (_M_node < __x._M_node);
 180   }
 181   bool operator>(const _Self& __x) const  { return __x < *this; }
 182   bool operator<=(const _Self& __x) const { return !(__x < *this); }
 183   bool operator>=(const _Self& __x) const { return !(*this < __x); }
 184
 185   void _M_set_node(_Map_pointer __new_node) {
 186     _M_node = __new_node;
 187     _M_first = *__new_node;
 188     _M_last = _M_first + difference_type(_S_buffer_size());
 189   }
 190 };
 191
 192 template <class _Tp, class _Ref, class _Ptr>
 193 inline _Deque_iterator<_Tp, _Ref, _Ptr>
 194 operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
 195 {
 196   return __x + __n;
 197 }
 198
 199
 200 // Deque base class.  It has two purposes.  First, its constructor
 201 //  and destructor allocate (but don't initialize) storage.  This makes
 202 //  exception safety easier.  Second, the base class encapsulates all of
 203 //  the differences between SGI-style allocators and standard-conforming
 204 //  allocators.
 205
 206 // Base class for ordinary allocators.
 207 template <class _Tp, class _Alloc, bool __is_static>
 208 class _Deque_alloc_base {
 209 public:
 210   typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
 211   allocator_type get_allocator() const { return _M_node_allocator; }
 212
 213   _Deque_alloc_base(const allocator_type& __a)
 214     : _M_node_allocator(__a), _M_map_allocator(__a),
 215       _M_map(0), _M_map_size(0)
 216   {}
 217
 218 protected:
 219   typedef typename _Alloc_traits<_Tp*, _Alloc>::allocator_type
 220           _Map_allocator_type;
 221
 222   allocator_type      _M_node_allocator;
 223   _Map_allocator_type _M_map_allocator;
 224
 225   _Tp* _M_allocate_node() {
 226     return _M_node_allocator.allocate(__deque_buf_size(sizeof(_Tp)));
 227   }
 228   void _M_deallocate_node(_Tp* __p) {
 229     _M_node_allocator.deallocate(__p, __deque_buf_size(sizeof(_Tp)));
 230   }
 231   _Tp** _M_allocate_map(size_t __n)
 232     { return _M_map_allocator.allocate(__n); }
 233   void _M_deallocate_map(_Tp** __p, size_t __n)
 234     { _M_map_allocator.deallocate(__p, __n); }
 235
 236   _Tp** _M_map;
 237   size_t _M_map_size;
 238 };
 239
 240 // Specialization for instanceless allocators.
 241 template <class _Tp, class _Alloc>
 242 class _Deque_alloc_base<_Tp, _Alloc, true>
 243 {
 244 public:
 245   typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
 246   allocator_type get_allocator() const { return allocator_type(); }
 247
 248   _Deque_alloc_base(const allocator_type&) : _M_map(0), _M_map_size(0) {}
 249
 250 protected:
 251   typedef typename _Alloc_traits<_Tp, _Alloc>::_Alloc_type _Node_alloc_type;
 252   typedef typename _Alloc_traits<_Tp*, _Alloc>::_Alloc_type _Map_alloc_type;
 253
 254   _Tp* _M_allocate_node() {
 255     return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp)));
 256   }
 257   void _M_deallocate_node(_Tp* __p) {
 258     _Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp)));
 259   }
 260   _Tp** _M_allocate_map(size_t __n)
 261     { return _Map_alloc_type::allocate(__n); }
 262   void _M_deallocate_map(_Tp** __p, size_t __n)
 263     { _Map_alloc_type::deallocate(__p, __n); }
 264
 265   _Tp** _M_map;
 266   size_t _M_map_size;
 267 };
 268
 269 template <class _Tp, class _Alloc>
 270 class _Deque_base
 271   : public _Deque_alloc_base<_Tp,_Alloc,
 272                               _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
 273 {
 274 public:
 275   typedef _Deque_alloc_base<_Tp,_Alloc,
 276                              _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
 277           _Base;
 278   typedef typename _Base::allocator_type allocator_type;
 279   typedef _Deque_iterator<_Tp,_Tp&,_Tp*>             iterator;
 280   typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
 281
 282   _Deque_base(const allocator_type& __a, size_t __num_elements)
 283     : _Base(__a), _M_start(), _M_finish()
 284     { _M_initialize_map(__num_elements); }
 285   _Deque_base(const allocator_type& __a)
 286     : _Base(__a), _M_start(), _M_finish() {}
 287   ~_Deque_base();
 288
 289 protected:
 290   void _M_initialize_map(size_t);
 291   void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
 292   void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
 293   enum { _S_initial_map_size = 8 };
 294
 295 protected:
 296   iterator _M_start;
 297   iterator _M_finish;
 298 };
 299
 300 // Non-inline member functions from _Deque_base.
 301
 302 template <class _Tp, class _Alloc>
 303 _Deque_base<_Tp,_Alloc>::~_Deque_base() {
 304   if (_M_map) {
 305     _M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1);
 306     _M_deallocate_map(_M_map, _M_map_size);
 307   }
 308 }
 309
 310 template <class _Tp, class _Alloc>
 311 void
 312 _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
 313 {
 314   size_t __num_nodes =
 315     __num_elements / __deque_buf_size(sizeof(_Tp)) + 1;
 316
 317   _M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2);
 318   _M_map = _M_allocate_map(_M_map_size);
 319
 320   _Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2;
 321   _Tp** __nfinish = __nstart + __num_nodes;
 322
 323   __STL_TRY {
 324     _M_create_nodes(__nstart, __nfinish);
 325   }
 326   __STL_UNWIND((_M_deallocate_map(_M_map, _M_map_size),
 327                 _M_map = 0, _M_map_size = 0));
 328   _M_start._M_set_node(__nstart);
 329   _M_finish._M_set_node(__nfinish - 1);
 330   _M_start._M_cur = _M_start._M_first;
 331   _M_finish._M_cur = _M_finish._M_first +
 332                __num_elements % __deque_buf_size(sizeof(_Tp));
 333 }
 334
 335 template <class _Tp, class _Alloc>
 336 void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
 337 {
 338   _Tp** __cur;
 339   __STL_TRY {
 340     for (__cur = __nstart; __cur < __nfinish; ++__cur)
 341       *__cur = _M_allocate_node();
 342   }
 343   __STL_UNWIND(_M_destroy_nodes(__nstart, __cur));
 344 }
 345
 346 template <class _Tp, class _Alloc>
 347 void
 348 _Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish)
 349 {
 350   for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
 351     _M_deallocate_node(*__n);
 352 }
 353
 354 template <class _Tp, class _Alloc = allocator<_Tp> >
 355 class deque : protected _Deque_base<_Tp, _Alloc> {
 356
 357   // requirements:
 358
 359   __STL_CLASS_REQUIRES(_Tp, _Assignable);
 360
 361   typedef _Deque_base<_Tp, _Alloc> _Base;
 362 public:                         // Basic types
 363   typedef _Tp value_type;
 364   typedef value_type* pointer;
 365   typedef const value_type* const_pointer;
 366   typedef value_type& reference;
 367   typedef const value_type& const_reference;
 368   typedef size_t size_type;
 369   typedef ptrdiff_t difference_type;
 370
 371   typedef typename _Base::allocator_type allocator_type;
 372   allocator_type get_allocator() const { return _Base::get_allocator(); }
 373
 374 public:                         // Iterators
 375   typedef typename _Base::iterator       iterator;
 376   typedef typename _Base::const_iterator const_iterator;
 377
 378   typedef reverse_iterator<const_iterator> const_reverse_iterator;
 379   typedef reverse_iterator<iterator> reverse_iterator;
 380
 381 protected:                      // Internal typedefs
 382   typedef pointer* _Map_pointer;
 383   static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
 384
 385 protected:
 386   using _Base::_M_initialize_map;
 387   using _Base::_M_create_nodes;
 388   using _Base::_M_destroy_nodes;
 389   using _Base::_M_allocate_node;
 390   using _Base::_M_deallocate_node;
 391   using _Base::_M_allocate_map;
 392   using _Base::_M_deallocate_map;
 393
 394   using _Base::_M_map;
 395   using _Base::_M_map_size;
 396   using _Base::_M_start;
 397   using _Base::_M_finish;
 398
 399 public:                         // Basic accessors
 400   iterator begin() { return _M_start; }
 401   iterator end() { return _M_finish; }
 402   const_iterator begin() const { return _M_start; }
 403   const_iterator end() const { return _M_finish; }
 404
 405   reverse_iterator rbegin() { return reverse_iterator(_M_finish); }
 406   reverse_iterator rend() { return reverse_iterator(_M_start); }
 407   const_reverse_iterator rbegin() const
 408     { return const_reverse_iterator(_M_finish); }
 409   const_reverse_iterator rend() const
 410     { return const_reverse_iterator(_M_start); }
 411
 412   reference operator[](size_type __n)
 413     { return _M_start[difference_type(__n)]; }
 414   const_reference operator[](size_type __n) const
 415     { return _M_start[difference_type(__n)]; }
 416
 417   void _M_range_check(size_type __n) const {
 418     if (__n >= this->size())
 419       __throw_range_error("deque");
 420   }
 421
 422   reference at(size_type __n)
 423     { _M_range_check(__n); return (*this)[__n]; }
 424   const_reference at(size_type __n) const
 425     { _M_range_check(__n); return (*this)[__n]; }
 426
 427   reference front() { return *_M_start; }
 428   reference back() {
 429     iterator __tmp = _M_finish;
 430     --__tmp;
 431     return *__tmp;
 432   }
 433   const_reference front() const { return *_M_start; }
 434   const_reference back() const {
 435     const_iterator __tmp = _M_finish;
 436     --__tmp;
 437     return *__tmp;
 438   }
 439
 440   size_type size() const { return _M_finish - _M_start; }
 441   size_type max_size() const { return size_type(-1); }
 442   bool empty() const { return _M_finish == _M_start; }
 443
 444 public:                         // Constructor, destructor.
 445   explicit deque(const allocator_type& __a = allocator_type())
 446     : _Base(__a, 0) {}
 447   deque(const deque& __x) : _Base(__x.get_allocator(), __x.size())
 448     { uninitialized_copy(__x.begin(), __x.end(), _M_start); }
 449   deque(size_type __n, const value_type& __value,
 450         const allocator_type& __a = allocator_type()) : _Base(__a, __n)
 451     { _M_fill_initialize(__value); }
 452   explicit deque(size_type __n) : _Base(allocator_type(), __n)
 453     { _M_fill_initialize(value_type()); }
 454
 455   // Check whether it's an integral type.  If so, it's not an iterator.
 456   template <class _InputIterator>
 457   deque(_InputIterator __first, _InputIterator __last,
 458         const allocator_type& __a = allocator_type()) : _Base(__a) {
 459     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 460     _M_initialize_dispatch(__first, __last, _Integral());
 461   }
 462
 463   template <class _Integer>
 464   void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) {
 465     _M_initialize_map(__n);
 466     _M_fill_initialize(__x);
 467   }
 468
 469   template <class _InputIter>
 470   void _M_initialize_dispatch(_InputIter __first, _InputIter __last,
 471                               __false_type) {
 472     _M_range_initialize(__first, __last, __ITERATOR_CATEGORY(__first));
 473   }
 474
 475   ~deque() { destroy(_M_start, _M_finish); }
 476
 477   deque& operator= (const deque& __x) {
 478     const size_type __len = size();
 479     if (&__x != this) {
 480       if (__len >= __x.size())
 481         erase(copy(__x.begin(), __x.end(), _M_start), _M_finish);
 482       else {
 483         const_iterator __mid = __x.begin() + difference_type(__len);
 484         copy(__x.begin(), __mid, _M_start);
 485         insert(_M_finish, __mid, __x.end());
 486       }
 487     }
 488     return *this;
 489   }
 490
 491   void swap(deque& __x) {
 492     std::swap(_M_start, __x._M_start);
 493     std::swap(_M_finish, __x._M_finish);
 494     std::swap(_M_map, __x._M_map);
 495     std::swap(_M_map_size, __x._M_map_size);
 496   }
 497
 498 public:
 499   // assign(), a generalized assignment member function.  Two
 500   // versions: one that takes a count, and one that takes a range.
 501   // The range version is a member template, so we dispatch on whether
 502   // or not the type is an integer.
 503
 504   void _M_fill_assign(size_type __n, const _Tp& __val) {
 505     if (__n > size()) {
 506       fill(begin(), end(), __val);
 507       insert(end(), __n - size(), __val);
 508     }
 509     else {
 510       erase(begin() + __n, end());
 511       fill(begin(), end(), __val);
 512     }
 513   }
 514
 515   void assign(size_type __n, const _Tp& __val) {
 516     _M_fill_assign(__n, __val);
 517   }
 518
 519   template <class _InputIterator>
 520   void assign(_InputIterator __first, _InputIterator __last) {
 521     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 522     _M_assign_dispatch(__first, __last, _Integral());
 523   }
 524
 525 private:                        // helper functions for assign()
 526
 527   template <class _Integer>
 528   void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
 529     { _M_fill_assign((size_type) __n, (_Tp) __val); }
 530
 531   template <class _InputIterator>
 532   void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
 533                           __false_type) {
 534     _M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first));
 535   }
 536
 537   template <class _InputIterator>
 538   void _M_assign_aux(_InputIterator __first, _InputIterator __last,
 539                      input_iterator_tag);
 540
 541   template <class _ForwardIterator>
 542   void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
 543                      forward_iterator_tag) {
 544     size_type __len = 0;
 545     distance(__first, __last, __len);
 546     if (__len > size()) {
 547       _ForwardIterator __mid = __first;
 548       advance(__mid, size());
 549       copy(__first, __mid, begin());
 550       insert(end(), __mid, __last);
 551     }
 552     else
 553       erase(copy(__first, __last, begin()), end());
 554   }
 555
 556 public:                         // push_* and pop_*
 557
 558   void push_back(const value_type& __t) {
 559     if (_M_finish._M_cur != _M_finish._M_last - 1) {
 560       construct(_M_finish._M_cur, __t);
 561       ++_M_finish._M_cur;
 562     }
 563     else
 564       _M_push_back_aux(__t);
 565   }
 566
 567   void push_back() {
 568     if (_M_finish._M_cur != _M_finish._M_last - 1) {
 569       construct(_M_finish._M_cur);
 570       ++_M_finish._M_cur;
 571     }
 572     else
 573       _M_push_back_aux();
 574   }
 575
 576   void push_front(const value_type& __t) {
 577     if (_M_start._M_cur != _M_start._M_first) {
 578       construct(_M_start._M_cur - 1, __t);
 579       --_M_start._M_cur;
 580     }
 581     else
 582       _M_push_front_aux(__t);
 583   }
 584
 585   void push_front() {
 586     if (_M_start._M_cur != _M_start._M_first) {
 587       construct(_M_start._M_cur - 1);
 588       --_M_start._M_cur;
 589     }
 590     else
 591       _M_push_front_aux();
 592   }
 593
 594
 595   void pop_back() {
 596     if (_M_finish._M_cur != _M_finish._M_first) {
 597       --_M_finish._M_cur;
 598       destroy(_M_finish._M_cur);
 599     }
 600     else
 601       _M_pop_back_aux();
 602   }
 603
 604   void pop_front() {
 605     if (_M_start._M_cur != _M_start._M_last - 1) {
 606       destroy(_M_start._M_cur);
 607       ++_M_start._M_cur;
 608     }
 609     else
 610       _M_pop_front_aux();
 611   }
 612
 613 public:                         // Insert
 614
 615   iterator insert(iterator position, const value_type& __x) {
 616     if (position._M_cur == _M_start._M_cur) {
 617       push_front(__x);
 618       return _M_start;
 619     }
 620     else if (position._M_cur == _M_finish._M_cur) {
 621       push_back(__x);
 622       iterator __tmp = _M_finish;
 623       --__tmp;
 624       return __tmp;
 625     }
 626     else {
 627       return _M_insert_aux(position, __x);
 628     }
 629   }
 630
 631   iterator insert(iterator __position)
 632     { return insert(__position, value_type()); }
 633
 634   void insert(iterator __pos, size_type __n, const value_type& __x)
 635     { _M_fill_insert(__pos, __n, __x); }
 636
 637   void _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
 638
 639   // Check whether it's an integral type.  If so, it's not an iterator.
 640   template <class _InputIterator>
 641   void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
 642     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 643     _M_insert_dispatch(__pos, __first, __last, _Integral());
 644   }
 645
 646   template <class _Integer>
 647   void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
 648                           __true_type) {
 649     _M_fill_insert(__pos, (size_type) __n, (value_type) __x);
 650   }
 651
 652   template <class _InputIterator>
 653   void _M_insert_dispatch(iterator __pos,
 654                           _InputIterator __first, _InputIterator __last,
 655                           __false_type) {
 656     insert(__pos, __first, __last, __ITERATOR_CATEGORY(__first));
 657   }
 658
 659   void resize(size_type __new_size, const value_type& __x) {
 660     const size_type __len = size();
 661     if (__new_size < __len)
 662       erase(_M_start + __new_size, _M_finish);
 663     else
 664       insert(_M_finish, __new_size - __len, __x);
 665   }
 666
 667   void resize(size_type new_size) { resize(new_size, value_type()); }
 668
 669 public:                         // Erase
 670   iterator erase(iterator __pos) {
 671     iterator __next = __pos;
 672     ++__next;
 673     size_type __index = __pos - _M_start;
 674     if (__index < (size() >> 1)) {
 675       copy_backward(_M_start, __pos, __next);
 676       pop_front();
 677     }
 678     else {
 679       copy(__next, _M_finish, __pos);
 680       pop_back();
 681     }
 682     return _M_start + __index;
 683   }
 684
 685   iterator erase(iterator __first, iterator __last);
 686   void clear();
 687
 688 protected:                        // Internal construction/destruction
 689
 690   void _M_fill_initialize(const value_type& __value);
 691
 692   template <class _InputIterator>
 693   void _M_range_initialize(_InputIterator __first, _InputIterator __last,
 694                         input_iterator_tag);
 695
 696   template <class _ForwardIterator>
 697   void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
 698                         forward_iterator_tag);
 699
 700 protected:                        // Internal push_* and pop_*
 701
 702   void _M_push_back_aux(const value_type&);
 703   void _M_push_back_aux();
 704   void _M_push_front_aux(const value_type&);
 705   void _M_push_front_aux();
 706   void _M_pop_back_aux();
 707   void _M_pop_front_aux();
 708
 709 protected:                        // Internal insert functions
 710
 711   template <class _InputIterator>
 712   void insert(iterator __pos, _InputIterator __first, _InputIterator __last,
 713               input_iterator_tag);
 714
 715   template <class _ForwardIterator>
 716   void insert(iterator __pos,
 717               _ForwardIterator __first, _ForwardIterator __last,
 718               forward_iterator_tag);
 719
 720   iterator _M_insert_aux(iterator __pos, const value_type& __x);
 721   iterator _M_insert_aux(iterator __pos);
 722   void _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
 723
 724   template <class _ForwardIterator>
 725   void _M_insert_aux(iterator __pos,
 726                      _ForwardIterator __first, _ForwardIterator __last,
 727                      size_type __n);
 728
 729   iterator _M_reserve_elements_at_front(size_type __n) {
 730     size_type __vacancies = _M_start._M_cur - _M_start._M_first;
 731     if (__n > __vacancies)
 732       _M_new_elements_at_front(__n - __vacancies);
 733     return _M_start - difference_type(__n);
 734   }
 735
 736   iterator _M_reserve_elements_at_back(size_type __n) {
 737     size_type __vacancies = (_M_finish._M_last - _M_finish._M_cur) - 1;
 738     if (__n > __vacancies)
 739       _M_new_elements_at_back(__n - __vacancies);
 740     return _M_finish + difference_type(__n);
 741   }
 742
 743   void _M_new_elements_at_front(size_type __new_elements);
 744   void _M_new_elements_at_back(size_type __new_elements);
 745
 746 protected:                      // Allocation of _M_map and nodes
 747
 748   // Makes sure the _M_map has space for new nodes.  Does not actually
 749   //  add the nodes.  Can invalidate _M_map pointers.  (And consequently,
 750   //  deque iterators.)
 751
 752   void _M_reserve_map_at_back (size_type __nodes_to_add = 1) {
 753     if (__nodes_to_add + 1 > _M_map_size - (_M_finish._M_node - _M_map))
 754       _M_reallocate_map(__nodes_to_add, false);
 755   }
 756
 757   void _M_reserve_map_at_front (size_type __nodes_to_add = 1) {
 758     if (__nodes_to_add > size_type(_M_start._M_node - _M_map))
 759       _M_reallocate_map(__nodes_to_add, true);
 760   }
 761
 762   void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
 763 };
 764
 765 // Non-inline member functions
 766
 767 template <class _Tp, class _Alloc>
 768 template <class _InputIter>
 769 void deque<_Tp, _Alloc>
 770   ::_M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag)
 771 {
 772   iterator __cur = begin();
 773   for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
 774     *__cur = *__first;
 775   if (__first == __last)
 776     erase(__cur, end());
 777   else
 778     insert(end(), __first, __last);
 779 }
 780
 781 template <class _Tp, class _Alloc>
 782 void deque<_Tp, _Alloc>::_M_fill_insert(iterator __pos,
 783                                         size_type __n, const value_type& __x)
 784 {
 785   if (__pos._M_cur == _M_start._M_cur) {
 786     iterator __new_start = _M_reserve_elements_at_front(__n);
 787     __STL_TRY {
 788       uninitialized_fill(__new_start, _M_start, __x);
 789       _M_start = __new_start;
 790     }
 791     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
 792   }
 793   else if (__pos._M_cur == _M_finish._M_cur) {
 794     iterator __new_finish = _M_reserve_elements_at_back(__n);
 795     __STL_TRY {
 796       uninitialized_fill(_M_finish, __new_finish, __x);
 797       _M_finish = __new_finish;
 798     }
 799     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
 800                                   __new_finish._M_node + 1));
 801   }
 802   else
 803     _M_insert_aux(__pos, __n, __x);
 804 }
 805
 806 template <class _Tp, class _Alloc>
 807 typename deque<_Tp,_Alloc>::iterator
 808 deque<_Tp,_Alloc>::erase(iterator __first, iterator __last)
 809 {
 810   if (__first == _M_start && __last == _M_finish) {
 811     clear();
 812     return _M_finish;
 813   }
 814   else {
 815     difference_type __n = __last - __first;
 816     difference_type __elems_before = __first - _M_start;
 817     if (static_cast<size_type>(__elems_before) < (size() - __n) / 2) {
 818       copy_backward(_M_start, __first, __last);
 819       iterator __new_start = _M_start + __n;
 820       destroy(_M_start, __new_start);
 821       _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
 822       _M_start = __new_start;
 823     }
 824     else {
 825       copy(__last, _M_finish, __first);
 826       iterator __new_finish = _M_finish - __n;
 827       destroy(__new_finish, _M_finish);
 828       _M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1);
 829       _M_finish = __new_finish;
 830     }
 831     return _M_start + __elems_before;
 832   }
 833 }
 834
 835 template <class _Tp, class _Alloc>
 836 void deque<_Tp,_Alloc>::clear()
 837 {
 838   for (_Map_pointer __node = _M_start._M_node + 1;
 839        __node < _M_finish._M_node;
 840        ++__node) {
 841     destroy(*__node, *__node + _S_buffer_size());
 842     _M_deallocate_node(*__node);
 843   }
 844
 845   if (_M_start._M_node != _M_finish._M_node) {
 846     destroy(_M_start._M_cur, _M_start._M_last);
 847     destroy(_M_finish._M_first, _M_finish._M_cur);
 848     _M_deallocate_node(_M_finish._M_first);
 849   }
 850   else
 851     destroy(_M_start._M_cur, _M_finish._M_cur);
 852
 853   _M_finish = _M_start;
 854 }
 855
 856 // Precondition: _M_start and _M_finish have already been initialized,
 857 // but none of the deque's elements have yet been constructed.
 858 template <class _Tp, class _Alloc>
 859 void deque<_Tp,_Alloc>::_M_fill_initialize(const value_type& __value) {
 860   _Map_pointer __cur;
 861   __STL_TRY {
 862     for (__cur = _M_start._M_node; __cur < _M_finish._M_node; ++__cur)
 863       uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value);
 864     uninitialized_fill(_M_finish._M_first, _M_finish._M_cur, __value);
 865   }
 866   __STL_UNWIND(destroy(_M_start, iterator(*__cur, __cur)));
 867 }
 868
 869 template <class _Tp, class _Alloc> template <class _InputIterator>
 870 void deque<_Tp,_Alloc>::_M_range_initialize(_InputIterator __first,
 871                                             _InputIterator __last,
 872                                             input_iterator_tag)
 873 {
 874   _M_initialize_map(0);
 875   __STL_TRY {
 876     for ( ; __first != __last; ++__first)
 877       push_back(*__first);
 878   }
 879   __STL_UNWIND(clear());
 880 }
 881
 882 template <class _Tp, class _Alloc> template <class _ForwardIterator>
 883 void deque<_Tp,_Alloc>::_M_range_initialize(_ForwardIterator __first,
 884                                             _ForwardIterator __last,
 885                                             forward_iterator_tag)
 886 {
 887   size_type __n = 0;
 888   distance(__first, __last, __n);
 889   _M_initialize_map(__n);
 890
 891   _Map_pointer __cur_node;
 892   __STL_TRY {
 893     for (__cur_node = _M_start._M_node;
 894          __cur_node < _M_finish._M_node;
 895          ++__cur_node) {
 896       _ForwardIterator __mid = __first;
 897       advance(__mid, _S_buffer_size());
 898       uninitialized_copy(__first, __mid, *__cur_node);
 899       __first = __mid;
 900     }
 901     uninitialized_copy(__first, __last, _M_finish._M_first);
 902   }
 903   __STL_UNWIND(destroy(_M_start, iterator(*__cur_node, __cur_node)));
 904 }
 905
 906 // Called only if _M_finish._M_cur == _M_finish._M_last - 1.
 907 template <class _Tp, class _Alloc>
 908 void deque<_Tp,_Alloc>::_M_push_back_aux(const value_type& __t)
 909 {
 910   value_type __t_copy = __t;
 911   _M_reserve_map_at_back();
 912   *(_M_finish._M_node + 1) = _M_allocate_node();
 913   __STL_TRY {
 914     construct(_M_finish._M_cur, __t_copy);
 915     _M_finish._M_set_node(_M_finish._M_node + 1);
 916     _M_finish._M_cur = _M_finish._M_first;
 917   }
 918   __STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1)));
 919 }
 920
 921 // Called only if _M_finish._M_cur == _M_finish._M_last - 1.
 922 template <class _Tp, class _Alloc>
 923 void deque<_Tp,_Alloc>::_M_push_back_aux()
 924 {
 925   _M_reserve_map_at_back();
 926   *(_M_finish._M_node + 1) = _M_allocate_node();
 927   __STL_TRY {
 928     construct(_M_finish._M_cur);
 929     _M_finish._M_set_node(_M_finish._M_node + 1);
 930     _M_finish._M_cur = _M_finish._M_first;
 931   }
 932   __STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1)));
 933 }
 934
 935 // Called only if _M_start._M_cur == _M_start._M_first.
 936 template <class _Tp, class _Alloc>
 937 void  deque<_Tp,_Alloc>::_M_push_front_aux(const value_type& __t)
 938 {
 939   value_type __t_copy = __t;
 940   _M_reserve_map_at_front();
 941   *(_M_start._M_node - 1) = _M_allocate_node();
 942   __STL_TRY {
 943     _M_start._M_set_node(_M_start._M_node - 1);
 944     _M_start._M_cur = _M_start._M_last - 1;
 945     construct(_M_start._M_cur, __t_copy);
 946   }
 947   __STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1))));
 948 }
 949
 950 // Called only if _M_start._M_cur == _M_start._M_first.
 951 template <class _Tp, class _Alloc>
 952 void deque<_Tp,_Alloc>::_M_push_front_aux()
 953 {
 954   _M_reserve_map_at_front();
 955   *(_M_start._M_node - 1) = _M_allocate_node();
 956   __STL_TRY {
 957     _M_start._M_set_node(_M_start._M_node - 1);
 958     _M_start._M_cur = _M_start._M_last - 1;
 959     construct(_M_start._M_cur);
 960   }
 961   __STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1))));
 962 }
 963
 964 // Called only if _M_finish._M_cur == _M_finish._M_first.
 965 template <class _Tp, class _Alloc>
 966 void deque<_Tp,_Alloc>::_M_pop_back_aux()
 967 {
 968   _M_deallocate_node(_M_finish._M_first);
 969   _M_finish._M_set_node(_M_finish._M_node - 1);
 970   _M_finish._M_cur = _M_finish._M_last - 1;
 971   destroy(_M_finish._M_cur);
 972 }
 973
 974 // Called only if _M_start._M_cur == _M_start._M_last - 1.  Note that
 975 // if the deque has at least one element (a precondition for this member
 976 // function), and if _M_start._M_cur == _M_start._M_last, then the deque
 977 // must have at least two nodes.
 978 template <class _Tp, class _Alloc>
 979 void deque<_Tp,_Alloc>::_M_pop_front_aux()
 980 {
 981   destroy(_M_start._M_cur);
 982   _M_deallocate_node(_M_start._M_first);
 983   _M_start._M_set_node(_M_start._M_node + 1);
 984   _M_start._M_cur = _M_start._M_first;
 985 }
 986
 987 template <class _Tp, class _Alloc> template <class _InputIterator>
 988 void deque<_Tp,_Alloc>::insert(iterator __pos,
 989                                _InputIterator __first, _InputIterator __last,
 990                                input_iterator_tag)
 991 {
 992   copy(__first, __last, inserter(*this, __pos));
 993 }
 994
 995 template <class _Tp, class _Alloc> template <class _ForwardIterator>
 996 void
 997 deque<_Tp,_Alloc>::insert(iterator __pos,
 998                           _ForwardIterator __first, _ForwardIterator __last,
 999                           forward_iterator_tag) {
1000   size_type __n = 0;
1001   distance(__first, __last, __n);
1002   if (__pos._M_cur == _M_start._M_cur) {
1003     iterator __new_start = _M_reserve_elements_at_front(__n);
1004     __STL_TRY {
1005       uninitialized_copy(__first, __last, __new_start);
1006       _M_start = __new_start;
1007     }
1008     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
1009   }
1010   else if (__pos._M_cur == _M_finish._M_cur) {
1011     iterator __new_finish = _M_reserve_elements_at_back(__n);
1012     __STL_TRY {
1013       uninitialized_copy(__first, __last, _M_finish);
1014       _M_finish = __new_finish;
1015     }
1016     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
1017                                   __new_finish._M_node + 1));
1018   }
1019   else
1020     _M_insert_aux(__pos, __first, __last, __n);
1021 }
1022
1023 template <class _Tp, class _Alloc>
1024 typename deque<_Tp, _Alloc>::iterator
1025 deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, const value_type& __x)
1026 {
1027   difference_type __index = __pos - _M_start;
1028   value_type __x_copy = __x;
1029   if (static_cast<size_type>(__index) < size() / 2) {
1030     push_front(front());
1031     iterator __front1 = _M_start;
1032     ++__front1;
1033     iterator __front2 = __front1;
1034     ++__front2;
1035     __pos = _M_start + __index;
1036     iterator __pos1 = __pos;
1037     ++__pos1;
1038     copy(__front2, __pos1, __front1);
1039   }
1040   else {
1041     push_back(back());
1042     iterator __back1 = _M_finish;
1043     --__back1;
1044     iterator __back2 = __back1;
1045     --__back2;
1046     __pos = _M_start + __index;
1047     copy_backward(__pos, __back2, __back1);
1048   }
1049   *__pos = __x_copy;
1050   return __pos;
1051 }
1052
1053 template <class _Tp, class _Alloc>
1054 typename deque<_Tp,_Alloc>::iterator
1055 deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos)
1056 {
1057   difference_type __index = __pos - _M_start;
1058   if (static_cast<size_type>(__index) < size() / 2) {
1059     push_front(front());
1060     iterator __front1 = _M_start;
1061     ++__front1;
1062     iterator __front2 = __front1;
1063     ++__front2;
1064     __pos = _M_start + __index;
1065     iterator __pos1 = __pos;
1066     ++__pos1;
1067     copy(__front2, __pos1, __front1);
1068   }
1069   else {
1070     push_back(back());
1071     iterator __back1 = _M_finish;
1072     --__back1;
1073     iterator __back2 = __back1;
1074     --__back2;
1075     __pos = _M_start + __index;
1076     copy_backward(__pos, __back2, __back1);
1077   }
1078   *__pos = value_type();
1079   return __pos;
1080 }
1081
1082 template <class _Tp, class _Alloc>
1083 void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
1084                                       size_type __n,
1085                                       const value_type& __x)
1086 {
1087   const difference_type __elems_before = __pos - _M_start;
1088   size_type __length = this->size();
1089   value_type __x_copy = __x;
1090   if (__elems_before < difference_type(__length / 2)) {
1091     iterator __new_start = _M_reserve_elements_at_front(__n);
1092     iterator __old_start = _M_start;
1093     __pos = _M_start + __elems_before;
1094     __STL_TRY {
1095       if (__elems_before >= difference_type(__n)) {
1096         iterator __start_n = _M_start + difference_type(__n);
1097         uninitialized_copy(_M_start, __start_n, __new_start);
1098         _M_start = __new_start;
1099         copy(__start_n, __pos, __old_start);
1100         fill(__pos - difference_type(__n), __pos, __x_copy);
1101       }
1102       else {
1103         __uninitialized_copy_fill(_M_start, __pos, __new_start,
1104                                   _M_start, __x_copy);
1105         _M_start = __new_start;
1106         fill(__old_start, __pos, __x_copy);
1107       }
1108     }
1109     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
1110   }
1111   else {
1112     iterator __new_finish = _M_reserve_elements_at_back(__n);
1113     iterator __old_finish = _M_finish;
1114     const difference_type __elems_after =
1115       difference_type(__length) - __elems_before;
1116     __pos = _M_finish - __elems_after;
1117     __STL_TRY {
1118       if (__elems_after > difference_type(__n)) {
1119         iterator __finish_n = _M_finish - difference_type(__n);
1120         uninitialized_copy(__finish_n, _M_finish, _M_finish);
1121         _M_finish = __new_finish;
1122         copy_backward(__pos, __finish_n, __old_finish);
1123         fill(__pos, __pos + difference_type(__n), __x_copy);
1124       }
1125       else {
1126         __uninitialized_fill_copy(_M_finish, __pos + difference_type(__n),
1127                                   __x_copy, __pos, _M_finish);
1128         _M_finish = __new_finish;
1129         fill(__pos, __old_finish, __x_copy);
1130       }
1131     }
1132     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
1133                                   __new_finish._M_node + 1));
1134   }
1135 }
1136
1137 template <class _Tp, class _Alloc> template <class _ForwardIterator>
1138 void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
1139                                       _ForwardIterator __first,
1140                                       _ForwardIterator __last,
1141                                       size_type __n)
1142 {
1143   const difference_type __elemsbefore = __pos - _M_start;
1144   size_type __length = size();
1145   if (static_cast<size_type>(__elemsbefore) < __length / 2) {
1146     iterator __new_start = _M_reserve_elements_at_front(__n);
1147     iterator __old_start = _M_start;
1148     __pos = _M_start + __elemsbefore;
1149     __STL_TRY {
1150       if (__elemsbefore >= difference_type(__n)) {
1151         iterator __start_n = _M_start + difference_type(__n);
1152         uninitialized_copy(_M_start, __start_n, __new_start);
1153         _M_start = __new_start;
1154         copy(__start_n, __pos, __old_start);
1155         copy(__first, __last, __pos - difference_type(__n));
1156       }
1157       else {
1158         _ForwardIterator __mid = __first;
1159         advance(__mid, difference_type(__n) - __elemsbefore);
1160         __uninitialized_copy_copy(_M_start, __pos, __first, __mid,
1161                                   __new_start);
1162         _M_start = __new_start;
1163         copy(__mid, __last, __old_start);
1164       }
1165     }
1166     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
1167   }
1168   else {
1169     iterator __new_finish = _M_reserve_elements_at_back(__n);
1170     iterator __old_finish = _M_finish;
1171     const difference_type __elemsafter =
1172       difference_type(__length) - __elemsbefore;
1173     __pos = _M_finish - __elemsafter;
1174     __STL_TRY {
1175       if (__elemsafter > difference_type(__n)) {
1176         iterator __finish_n = _M_finish - difference_type(__n);
1177         uninitialized_copy(__finish_n, _M_finish, _M_finish);
1178         _M_finish = __new_finish;
1179         copy_backward(__pos, __finish_n, __old_finish);
1180         copy(__first, __last, __pos);
1181       }
1182       else {
1183         _ForwardIterator __mid = __first;
1184         advance(__mid, __elemsafter);
1185         __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);
1186         _M_finish = __new_finish;
1187         copy(__first, __mid, __pos);
1188       }
1189     }
1190     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
1191                                   __new_finish._M_node + 1));
1192   }
1193 }
1194
1195 template <class _Tp, class _Alloc>
1196 void deque<_Tp,_Alloc>::_M_new_elements_at_front(size_type __new_elems)
1197 {
1198   size_type __new_nodes
1199       = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
1200   _M_reserve_map_at_front(__new_nodes);
1201   size_type __i;
1202   __STL_TRY {
1203     for (__i = 1; __i <= __new_nodes; ++__i)
1204       *(_M_start._M_node - __i) = _M_allocate_node();
1205   }
1206 #       ifdef __STL_USE_EXCEPTIONS
1207   catch(...) {
1208     for (size_type __j = 1; __j < __i; ++__j)
1209       _M_deallocate_node(*(_M_start._M_node - __j));
1210     throw;
1211   }
1212 #       endif /* __STL_USE_EXCEPTIONS */
1213 }
1214
1215 template <class _Tp, class _Alloc>
1216 void deque<_Tp,_Alloc>::_M_new_elements_at_back(size_type __new_elems)
1217 {
1218   size_type __new_nodes
1219       = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
1220   _M_reserve_map_at_back(__new_nodes);
1221   size_type __i;
1222   __STL_TRY {
1223     for (__i = 1; __i <= __new_nodes; ++__i)
1224       *(_M_finish._M_node + __i) = _M_allocate_node();
1225   }
1226 #       ifdef __STL_USE_EXCEPTIONS
1227   catch(...) {
1228     for (size_type __j = 1; __j < __i; ++__j)
1229       _M_deallocate_node(*(_M_finish._M_node + __j));
1230     throw;
1231   }
1232 #       endif /* __STL_USE_EXCEPTIONS */
1233 }
1234
1235 template <class _Tp, class _Alloc>
1236 void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add,
1237                                           bool __add_at_front)
1238 {
1239   size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1;
1240   size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
1241
1242   _Map_pointer __new_nstart;
1243   if (_M_map_size > 2 * __new_num_nodes) {
1244     __new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2
1245                      + (__add_at_front ? __nodes_to_add : 0);
1246     if (__new_nstart < _M_start._M_node)
1247       copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
1248     else
1249       copy_backward(_M_start._M_node, _M_finish._M_node + 1,
1250                     __new_nstart + __old_num_nodes);
1251   }
1252   else {
1253     size_type __new_map_size =
1254       _M_map_size + max(_M_map_size, __nodes_to_add) + 2;
1255
1256     _Map_pointer __new_map = _M_allocate_map(__new_map_size);
1257     __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
1258                          + (__add_at_front ? __nodes_to_add : 0);
1259     copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
1260     _M_deallocate_map(_M_map, _M_map_size);
1261
1262     _M_map = __new_map;
1263     _M_map_size = __new_map_size;
1264   }
1265
1266   _M_start._M_set_node(__new_nstart);
1267   _M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
1268 }
1269
1270
1271 // Nonmember functions.
1272
1273 template <class _Tp, class _Alloc>
1274 inline bool operator==(const deque<_Tp, _Alloc>& __x,
1275                        const deque<_Tp, _Alloc>& __y) {
1276   return __x.size() == __y.size() &&
1277          equal(__x.begin(), __x.end(), __y.begin());
1278 }
1279
1280 template <class _Tp, class _Alloc>
1281 inline bool operator<(const deque<_Tp, _Alloc>& __x,
1282                       const deque<_Tp, _Alloc>& __y) {
1283   return lexicographical_compare(__x.begin(), __x.end(),
1284                                  __y.begin(), __y.end());
1285 }
1286
1287 template <class _Tp, class _Alloc>
1288 inline bool operator!=(const deque<_Tp, _Alloc>& __x,
1289                        const deque<_Tp, _Alloc>& __y) {
1290   return !(__x == __y);
1291 }
1292
1293 template <class _Tp, class _Alloc>
1294 inline bool operator>(const deque<_Tp, _Alloc>& __x,
1295                       const deque<_Tp, _Alloc>& __y) {
1296   return __y < __x;
1297 }
1298
1299 template <class _Tp, class _Alloc>
1300 inline bool operator<=(const deque<_Tp, _Alloc>& __x,
1301                        const deque<_Tp, _Alloc>& __y) {
1302   return !(__y < __x);
1303 }
1304 template <class _Tp, class _Alloc>
1305 inline bool operator>=(const deque<_Tp, _Alloc>& __x,
1306                        const deque<_Tp, _Alloc>& __y) {
1307   return !(__x < __y);
1308 }
1309
1310 template <class _Tp, class _Alloc>
1311 inline void swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y) {
1312   __x.swap(__y);
1313 }
1314
1315 } // namespace std
1316
1317 #endif /* __SGI_STL_INTERNAL_DEQUE_H */
1318
1319 // Local Variables:
1320 // mode:C++
1321 // End: