libstdc++-v3/include/bits/stl_deque.h

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