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