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

   1 // Deque implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002 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 /** @file stl_deque.h
  57  *  This is an internal header file, included by other library headers.
  58  *  You should not attempt to use it directly.
  59  */
  60
  61 #ifndef __GLIBCPP_INTERNAL_DEQUE_H
  62 #define __GLIBCPP_INTERNAL_DEQUE_H
  63
  64 #include <bits/concept_check.h>
  65 #include <bits/stl_iterator_base_types.h>
  66 #include <bits/stl_iterator_base_funcs.h>
  67
  68 namespace std
  69 {
  70   /**
  71    *  @if maint
  72    *  @brief This function controls the size of memory nodes.
  73    *  @param  size  The size of an element.
  74    *  @return   The number (not byte size) of elements per node.
  75    *
  76    *  This function started off as a compiler kludge from SGI, but seems to
  77    *  be a useful wrapper around a repeated constant expression.  The '512' is
  78    *  tuneable (and no other code needs to change), but no investigation has
  79    *  been done since inheriting the SGI code.
  80    *  @endif
  81   */
  82   inline size_t
  83   __deque_buf_size(size_t __size)
  84   { return __size < 512 ? size_t(512 / __size) : size_t(1); }
  85
  86
  87   /**
  88    *  @brief A deque::iterator.
  89    *
  90    *  Quite a bit of intelligence here.  Much of the functionality of deque is
  91    *  actually passed off to this class.  A deque holds two of these internally,
  92    *  marking its valid range.  Access to elements is done as offsets of either
  93    *  of those two, relying on operator overloading in this class.
  94    *
  95    *  @if maint
  96    *  All the functions are op overloads except for _M_set_node.
  97    *  @endif
  98   */
  99   template <typename _Tp, typename _Ref, typename _Ptr>
 100     struct _Deque_iterator
 101   {
 102     typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
 103     typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
 104     static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
 105
 106     typedef random_access_iterator_tag iterator_category;
 107     typedef _Tp                        value_type;
 108     typedef _Ptr                       pointer;
 109     typedef _Ref                       reference;
 110     typedef size_t                     size_type;
 111     typedef ptrdiff_t                  difference_type;
 112     typedef _Tp**                      _Map_pointer;
 113     typedef _Deque_iterator            _Self;
 114
 115     _Tp* _M_cur;
 116     _Tp* _M_first;
 117     _Tp* _M_last;
 118     _Map_pointer _M_node;
 119
 120     _Deque_iterator(_Tp* __x, _Map_pointer __y)
 121       : _M_cur(__x), _M_first(*__y),
 122         _M_last(*__y + _S_buffer_size()), _M_node(__y) {}
 123     _Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
 124     _Deque_iterator(const iterator& __x)
 125       : _M_cur(__x._M_cur), _M_first(__x._M_first),
 126         _M_last(__x._M_last), _M_node(__x._M_node) {}
 127
 128     reference operator*() const { return *_M_cur; }
 129     pointer operator->() const { return _M_cur; }
 130
 131     _Self& operator++() {
 132       ++_M_cur;
 133       if (_M_cur == _M_last) {
 134         _M_set_node(_M_node + 1);
 135         _M_cur = _M_first;
 136       }
 137       return *this;
 138     }
 139     _Self operator++(int)  {
 140       _Self __tmp = *this;
 141       ++*this;
 142       return __tmp;
 143     }
 144
 145     _Self& operator--() {
 146       if (_M_cur == _M_first) {
 147         _M_set_node(_M_node - 1);
 148         _M_cur = _M_last;
 149       }
 150       --_M_cur;
 151       return *this;
 152     }
 153     _Self operator--(int) {
 154       _Self __tmp = *this;
 155       --*this;
 156       return __tmp;
 157     }
 158
 159     _Self& operator+=(difference_type __n)
 160     {
 161       difference_type __offset = __n + (_M_cur - _M_first);
 162       if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
 163         _M_cur += __n;
 164       else {
 165         difference_type __node_offset =
 166           __offset > 0 ? __offset / difference_type(_S_buffer_size())
 167                      : -difference_type((-__offset - 1) / _S_buffer_size()) - 1;
 168         _M_set_node(_M_node + __node_offset);
 169         _M_cur = _M_first +
 170           (__offset - __node_offset * difference_type(_S_buffer_size()));
 171       }
 172       return *this;
 173     }
 174
 175     _Self operator+(difference_type __n) const
 176     {
 177       _Self __tmp = *this;
 178       return __tmp += __n;
 179     }
 180
 181     _Self& operator-=(difference_type __n) { return *this += -__n; }
 182
 183     _Self operator-(difference_type __n) const {
 184       _Self __tmp = *this;
 185       return __tmp -= __n;
 186     }
 187
 188     reference operator[](difference_type __n) const { return *(*this + __n); }
 189
 190     /** @if maint
 191      *  Prepares to traverse new_node.  Sets everything except _M_cur, which
 192      *  should therefore be set by the caller immediately afterwards, based on
 193      *  _M_first and _M_last.
 194      *  @endif
 195     */
 196     void
 197     _M_set_node(_Map_pointer __new_node)
 198     {
 199       _M_node = __new_node;
 200       _M_first = *__new_node;
 201       _M_last = _M_first + difference_type(_S_buffer_size());
 202     }
 203   };
 204
 205   // Note: we also provide overloads whose operands are of the same type in
 206   // order to avoid ambiguous overload resolution when std::rel_ops operators
 207   // are in scope (for additional details, see libstdc++/3628)
 208   template <typename _Tp, typename _Ref, typename _Ptr>
 209   inline bool
 210   operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
 211            const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
 212   {
 213     return __x._M_cur == __y._M_cur;
 214   }
 215
 216   template <typename _Tp, typename _RefL, typename _PtrL,
 217                           typename _RefR, typename _PtrR>
 218   inline bool
 219   operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
 220            const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
 221   {
 222     return __x._M_cur == __y._M_cur;
 223   }
 224
 225   template <typename _Tp, typename _Ref, typename _Ptr>
 226   inline bool
 227   operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
 228            const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
 229   {
 230     return !(__x == __y);
 231   }
 232
 233   template <typename _Tp, typename _RefL, typename _PtrL,
 234                           typename _RefR, typename _PtrR>
 235   inline bool
 236   operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
 237            const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
 238   {
 239     return !(__x == __y);
 240   }
 241
 242   template <typename _Tp, typename _Ref, typename _Ptr>
 243   inline bool
 244   operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
 245            const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
 246   {
 247     return (__x._M_node == __y._M_node) ?
 248       (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
 249   }
 250
 251   template <typename _Tp, typename _RefL, typename _PtrL,
 252                           typename _RefR, typename _PtrR>
 253   inline bool
 254   operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
 255            const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
 256   {
 257     return (__x._M_node == __y._M_node) ?
 258       (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
 259   }
 260
 261   template <typename _Tp, typename _Ref, typename _Ptr>
 262   inline bool
 263   operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
 264            const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
 265   {
 266     return __y < __x;
 267   }
 268
 269   template <typename _Tp, typename _RefL, typename _PtrL,
 270                           typename _RefR, typename _PtrR>
 271   inline bool
 272   operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
 273            const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
 274   {
 275     return __y < __x;
 276   }
 277
 278   template <typename _Tp, typename _Ref, typename _Ptr>
 279   inline bool
 280   operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
 281            const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
 282   {
 283     return !(__y < __x);
 284   }
 285
 286   template <typename _Tp, typename _RefL, typename _PtrL,
 287                           typename _RefR, typename _PtrR>
 288   inline bool
 289   operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
 290            const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
 291   {
 292     return !(__y < __x);
 293   }
 294
 295   template <typename _Tp, typename _Ref, typename _Ptr>
 296   inline bool
 297   operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
 298            const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
 299   {
 300     return !(__x < __y);
 301   }
 302
 303   template <typename _Tp, typename _RefL, typename _PtrL,
 304                           typename _RefR, typename _PtrR>
 305   inline bool
 306   operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
 307            const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
 308   {
 309     return !(__x < __y);
 310   }
 311
 312   // _GLIBCPP_RESOLVE_LIB_DEFECTS
 313   // According to the resolution of DR179 not only the various comparison
 314   // operators but also operator- must accept mixed iterator/const_iterator
 315   // parameters.
 316   template <typename _Tp, typename _RefL, typename _PtrL,
 317                           typename _RefR, typename _PtrR>
 318   inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
 319   operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
 320           const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
 321   {
 322     return _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
 323       (_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size()) *
 324       (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first) +
 325       (__y._M_last - __y._M_cur);
 326   }
 327
 328   template <typename _Tp, typename _Ref, typename _Ptr>
 329   inline _Deque_iterator<_Tp, _Ref, _Ptr>
 330   operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
 331   {
 332     return __x + __n;
 333   }
 334
 335
 336   /// @if maint Primary default version.  @endif
 337   /**
 338    *  @if maint
 339    *  Deque base class.  It has two purposes.  First, its constructor
 340    *  and destructor allocate (but don't initialize) storage.  This makes
 341    *  %exception safety easier.  Second, the base class encapsulates all of
 342    *  the differences between SGI-style allocators and standard-conforming
 343    *  allocators.  (See stl_alloc.h for more on this topic.)  There are two
 344    *  versions:  this ordinary one, and the space-saving specialization for
 345    *  instanceless allocators.
 346    *  @endif
 347   */
 348   template <typename _Tp, typename _Alloc, bool __is_static>
 349     class _Deque_alloc_base
 350   {
 351   public:
 352     typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
 353     allocator_type get_allocator() const { return _M_node_allocator; }
 354
 355     _Deque_alloc_base(const allocator_type& __a)
 356       : _M_node_allocator(__a), _M_map_allocator(__a),
 357         _M_map(0), _M_map_size(0)
 358     {}
 359
 360   protected:
 361     typedef typename _Alloc_traits<_Tp*, _Alloc>::allocator_type
 362             _Map_allocator_type;
 363
 364     _Tp*
 365     _M_allocate_node()
 366     {
 367       return _M_node_allocator.allocate(__deque_buf_size(sizeof(_Tp)));
 368     }
 369
 370     void
 371     _M_deallocate_node(_Tp* __p)
 372     {
 373       _M_node_allocator.deallocate(__p, __deque_buf_size(sizeof(_Tp)));
 374     }
 375
 376     _Tp**
 377     _M_allocate_map(size_t __n)
 378       { return _M_map_allocator.allocate(__n); }
 379
 380     void
 381     _M_deallocate_map(_Tp** __p, size_t __n)
 382       { _M_map_allocator.deallocate(__p, __n); }
 383
 384     allocator_type       _M_node_allocator;
 385     _Map_allocator_type  _M_map_allocator;
 386     _Tp**                _M_map;
 387     size_t               _M_map_size;
 388   };
 389
 390   /// @if maint Specialization for instanceless allocators.  @endif
 391   template <typename _Tp, typename _Alloc>
 392     class _Deque_alloc_base<_Tp, _Alloc, true>
 393   {
 394   public:
 395     typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
 396     allocator_type get_allocator() const { return allocator_type(); }
 397
 398     _Deque_alloc_base(const allocator_type&)
 399       : _M_map(0), _M_map_size(0)
 400     {}
 401
 402   protected:
 403     typedef typename _Alloc_traits<_Tp,_Alloc>::_Alloc_type  _Node_alloc_type;
 404     typedef typename _Alloc_traits<_Tp*,_Alloc>::_Alloc_type _Map_alloc_type;
 405
 406     _Tp*
 407     _M_allocate_node()
 408     {
 409       return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp)));
 410     }
 411
 412     void
 413     _M_deallocate_node(_Tp* __p)
 414     {
 415       _Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp)));
 416     }
 417
 418     _Tp**
 419     _M_allocate_map(size_t __n)
 420       { return _Map_alloc_type::allocate(__n); }
 421
 422     void
 423     _M_deallocate_map(_Tp** __p, size_t __n)
 424       { _Map_alloc_type::deallocate(__p, __n); }
 425
 426     _Tp**   _M_map;
 427     size_t  _M_map_size;
 428   };
 429
 430
 431   /**
 432    *  @if maint
 433    *  Deque base class.  Using _Alloc_traits in the instantiation of the parent
 434    *  class provides the compile-time dispatching mentioned in the parent's
 435    *  docs.  This class provides the unified face for %deque's allocation.
 436    *
 437    *  Nothing in this class ever constructs or destroys an actual Tp element.
 438    *  (Deque handles that itself.)  Only/All memory management is performed
 439    *  here.
 440    *  @endif
 441   */
 442   template <typename _Tp, typename _Alloc>
 443     class _Deque_base
 444     : public _Deque_alloc_base<_Tp,_Alloc,
 445                                 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
 446   {
 447   public:
 448     typedef _Deque_alloc_base<_Tp,_Alloc,
 449                                _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
 450             _Base;
 451     typedef typename _Base::allocator_type             allocator_type;
 452     typedef _Deque_iterator<_Tp,_Tp&,_Tp*>             iterator;
 453     typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
 454
 455     _Deque_base(const allocator_type& __a, size_t __num_elements)
 456       : _Base(__a), _M_start(), _M_finish()
 457       { _M_initialize_map(__num_elements); }
 458     _Deque_base(const allocator_type& __a)
 459       : _Base(__a), _M_start(), _M_finish() {}
 460     ~_Deque_base();
 461
 462   protected:
 463     void _M_initialize_map(size_t);
 464     void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
 465     void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
 466     enum { _S_initial_map_size = 8 };
 467
 468     iterator _M_start;
 469     iterator _M_finish;
 470   };
 471
 472
 473   template <typename _Tp, typename _Alloc>
 474   _Deque_base<_Tp,_Alloc>::~_Deque_base()
 475   {
 476     if (_M_map)
 477     {
 478       _M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1);
 479       _M_deallocate_map(_M_map, _M_map_size);
 480     }
 481   }
 482
 483   /**
 484    *  @if maint
 485    *  @brief Layout storage.
 486    *  @param  num_elements  The count of T's for which to allocate space
 487    *                        at first.
 488    *  @return   Nothing.
 489    *
 490    *  The initial underlying memory layout is a bit complicated...
 491    *  @endif
 492   */
 493   template <typename _Tp, typename _Alloc>
 494   void
 495   _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
 496   {
 497     size_t __num_nodes =
 498       __num_elements / __deque_buf_size(sizeof(_Tp)) + 1;
 499
 500     _M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2);
 501     _M_map = _M_allocate_map(_M_map_size);
 502
 503     // For "small" maps (needing less than _M_map_size nodes), allocation
 504     // starts in the middle elements and grows outwards.  So nstart may be the
 505     // beginning of _M_map, but for small maps it may be as far in as _M_map+3.
 506
 507     _Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2;
 508     _Tp** __nfinish = __nstart + __num_nodes;
 509
 510     try
 511       { _M_create_nodes(__nstart, __nfinish); }
 512     catch(...)
 513       {
 514         _M_deallocate_map(_M_map, _M_map_size);
 515         _M_map = 0;
 516         _M_map_size = 0;
 517         __throw_exception_again;
 518       }
 519
 520     _M_start._M_set_node(__nstart);
 521     _M_finish._M_set_node(__nfinish - 1);
 522     _M_start._M_cur = _M_start._M_first;
 523     _M_finish._M_cur = _M_finish._M_first +
 524                        __num_elements % __deque_buf_size(sizeof(_Tp));
 525   }
 526
 527   template <typename _Tp, typename _Alloc>
 528   void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
 529   {
 530     _Tp** __cur;
 531     try
 532       {
 533         for (__cur = __nstart; __cur < __nfinish; ++__cur)
 534           *__cur = _M_allocate_node();
 535       }
 536     catch(...)
 537       {
 538         _M_destroy_nodes(__nstart, __cur);
 539         __throw_exception_again;
 540       }
 541   }
 542
 543   template <typename _Tp, typename _Alloc>
 544   void
 545   _Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish)
 546   {
 547     for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
 548       _M_deallocate_node(*__n);
 549   }
 550
 551
 552   /**
 553    *  @brief  A standard container using fixed-size memory allocation and
 554    *  constant-time manipulation of elements at either end.
 555    *
 556    *  @ingroup Containers
 557    *  @ingroup Sequences
 558    *
 559    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
 560    *  <a href="tables.html#66">reversible container</a>, and a
 561    *  <a href="tables.html#67">sequence</a>, including the
 562    *  <a href="tables.html#68">optional sequence requirements</a>.
 563    *
 564    *  In previous HP/SGI versions of deque, there was an extra template
 565    *  parameter so users could control the node size.  This extension turned
 566    *  out to violate the C++ standard (it can be detected using template
 567    *  template parameters), and it was removed.
 568    *
 569    *  @if maint
 570    *  Here's how a deque<Tp> manages memory.  Each deque has 4 members:
 571    *
 572    *  - Tp**        _M_map
 573    *  - size_t      _M_map_size
 574    *  - iterator    _M_start, _M_finish
 575    *
 576    *  map_size is at least 8.  %map is an array of map_size pointers-to-"nodes".
 577    *  (The name %map has nothing to do with the std::map class, and "nodes"
 578    *  should not be confused with std::list's usage of "node".)
 579    *
 580    *  A "node" has no specific type name as such, but it is referred to as
 581    *  "node" in this file.  It is a simple array-of-Tp.  If Tp is very large,
 582    *  there will be one Tp element per node (i.e., an "array" of one).
 583    *  For non-huge Tp's, node size is inversely related to Tp size:  the
 584    *  larger the Tp, the fewer Tp's will fit in a node.  The goal here is to
 585    *  keep the total size of a node relatively small and constant over different
 586    *  Tp's, to improve allocator efficiency.
 587    *
 588    *  **** As I write this, the nodes are /not/ allocated using the high-speed
 589    *  memory pool.  There are 20 hours left in the year; perhaps I can fix
 590    *  this before 2002.
 591    *
 592    *  Not every pointer in the %map array will point to a node.  If the initial
 593    *  number of elements in the deque is small, the /middle/ %map pointers will
 594    *  be valid, and the ones at the edges will be unused.  This same situation
 595    *  will arise as the %map grows:  available %map pointers, if any, will be on
 596    *  the ends.  As new nodes are created, only a subset of the %map's pointers
 597    *  need to be copied "outward".
 598    *
 599    *  Class invariants:
 600    * - For any nonsingular iterator i:
 601    *    - i.node points to a member of the %map array.  (Yes, you read that
 602    *      correctly:  i.node does not actually point to a node.)  The member of
 603    *      the %map array is what actually points to the node.
 604    *    - i.first == *(i.node)    (This points to the node (first Tp element).)
 605    *    - i.last  == i.first + node_size
 606    *    - i.cur is a pointer in the range [i.first, i.last).  NOTE:
 607    *      the implication of this is that i.cur is always a dereferenceable
 608    *      pointer, even if i is a past-the-end iterator.
 609    * - Start and Finish are always nonsingular iterators.  NOTE: this means that
 610    *   an empty deque must have one node, a deque with <N elements (where N is
 611    *   the node buffer size) must have one node, a deque with N through (2N-1)
 612    *   elements must have two nodes, etc.
 613    * - For every node other than start.node and finish.node, every element in
 614    *   the node is an initialized object.  If start.node == finish.node, then
 615    *   [start.cur, finish.cur) are initialized objects, and the elements outside
 616    *   that range are uninitialized storage.  Otherwise, [start.cur, start.last)
 617    *   and [finish.first, finish.cur) are initialized objects, and [start.first,
 618    *   start.cur) and [finish.cur, finish.last) are uninitialized storage.
 619    * - [%map, %map + map_size) is a valid, non-empty range.
 620    * - [start.node, finish.node] is a valid range contained within
 621    *   [%map, %map + map_size).
 622    * - A pointer in the range [%map, %map + map_size) points to an allocated
 623    *   node if and only if the pointer is in the range
 624    *   [start.node, finish.node].
 625    *
 626    *  Here's the magic:  nothing in deque is "aware" of the discontiguous
 627    *  storage!
 628    *
 629    *  The memory setup and layout occurs in the parent, _Base, and the iterator
 630    *  class is entirely responsible for "leaping" from one node to the next.
 631    *  All the implementation routines for deque itself work only through the
 632    *  start and finish iterators.  This keeps the routines simple and sane,
 633    *  and we can use other standard algorithms as well.
 634    *  @endif
 635   */
 636   template <typename _Tp, typename _Alloc = allocator<_Tp> >
 637     class deque : protected _Deque_base<_Tp, _Alloc>
 638   {
 639     // concept requirements
 640     __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
 641
 642     typedef _Deque_base<_Tp, _Alloc>           _Base;
 643
 644   public:
 645     typedef _Tp                                value_type;
 646     typedef value_type*                        pointer;
 647     typedef const value_type*                  const_pointer;
 648     typedef typename _Base::iterator           iterator;
 649     typedef typename _Base::const_iterator     const_iterator;
 650     typedef std::reverse_iterator<const_iterator>   const_reverse_iterator;
 651     typedef std::reverse_iterator<iterator>         reverse_iterator;
 652     typedef value_type&                        reference;
 653     typedef const value_type&                  const_reference;
 654     typedef size_t                             size_type;
 655     typedef ptrdiff_t                          difference_type;
 656     typedef typename _Base::allocator_type     allocator_type;
 657
 658   protected:
 659     typedef pointer*                           _Map_pointer;
 660     static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
 661
 662     // Functions controlling memory layout, and nothing else.
 663     using _Base::_M_initialize_map;
 664     using _Base::_M_create_nodes;
 665     using _Base::_M_destroy_nodes;
 666     using _Base::_M_allocate_node;
 667     using _Base::_M_deallocate_node;
 668     using _Base::_M_allocate_map;
 669     using _Base::_M_deallocate_map;
 670
 671     /** @if maint
 672      *  A total of four data members accumulated down the heirarchy.  If the
 673      *  _Alloc type requires separate instances, then two of them will also be
 674      *  included in each deque.
 675      *  @endif
 676     */
 677     using _Base::_M_map;
 678     using _Base::_M_map_size;
 679     using _Base::_M_start;
 680     using _Base::_M_finish;
 681
 682   public:
 683     // [23.2.1.1] construct/copy/destroy
 684     // (assign() and get_allocator() are also listed in this section)
 685     /**
 686      *  @brief  Default constructor creates no elements.
 687     */
 688     explicit
 689     deque(const allocator_type& __a = allocator_type())
 690       : _Base(__a, 0) {}
 691
 692     /**
 693      *  @brief  Create a %deque with copies of an exemplar element.
 694      *  @param  n  The number of elements to initially create.
 695      *  @param  value  An element to copy.
 696      *
 697      *  This constructor fills the %deque with @a n copies of @a value.
 698     */
 699     deque(size_type __n, const value_type& __value,
 700           const allocator_type& __a = allocator_type())
 701       : _Base(__a, __n)
 702       { _M_fill_initialize(__value); }
 703
 704     /**
 705      *  @brief  Create a %deque with default elements.
 706      *  @param  n  The number of elements to initially create.
 707      *
 708      *  This constructor fills the %deque with @a n copies of a
 709      *  default-constructed element.
 710     */
 711     explicit
 712     deque(size_type __n)
 713       : _Base(allocator_type(), __n)
 714       { _M_fill_initialize(value_type()); }
 715
 716     /**
 717      *  @brief  %Deque copy constructor.
 718      *  @param  x  A %deque of identical element and allocator types.
 719      *
 720      *  The newly-created %deque uses a copy of the allocation object used
 721      *  by @a x.
 722     */
 723     deque(const deque& __x)
 724       : _Base(__x.get_allocator(), __x.size())
 725       { uninitialized_copy(__x.begin(), __x.end(), _M_start); }
 726
 727     /**
 728      *  @brief  Builds a %deque from a range.
 729      *  @param  first  An input iterator.
 730      *  @param  last  An input iterator.
 731      *
 732      *  Create a %deque consisting of copies of the elements from [first,last).
 733      *
 734      *  If the iterators are forward, bidirectional, or random-access, then
 735      *  this will call the elements' copy constructor N times (where N is
 736      *  distance(first,last)) and do no memory reallocation.  But if only
 737      *  input iterators are used, then this will do at most 2N calls to the
 738      *  copy constructor, and logN memory reallocations.
 739     */
 740     template<typename _InputIterator>
 741       deque(_InputIterator __first, _InputIterator __last,
 742             const allocator_type& __a = allocator_type())
 743         : _Base(__a)
 744       {
 745         // Check whether it's an integral type.  If so, it's not an iterator.
 746         typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 747         _M_initialize_dispatch(__first, __last, _Integral());
 748       }
 749
 750     /**
 751      *  The dtor only erases the elements, and note that if the elements
 752      *  themselves are pointers, the pointed-to memory is not touched in any
 753      *  way.  Managing the pointer is the user's responsibilty.
 754     */
 755     ~deque() { _Destroy(_M_start, _M_finish); }
 756
 757     /**
 758      *  @brief  %Deque assignment operator.
 759      *  @param  x  A %deque of identical element and allocator types.
 760      *
 761      *  All the elements of @a x are copied, but unlike the copy constructor,
 762      *  the allocator object is not copied.
 763     */
 764     deque&
 765     operator=(const deque& __x);
 766
 767     /**
 768      *  @brief  Assigns a given value to a %deque.
 769      *  @param  n  Number of elements to be assigned.
 770      *  @param  val  Value to be assigned.
 771      *
 772      *  This function fills a %deque with @a n copies of the given value.
 773      *  Note that the assignment completely changes the %deque and that the
 774      *  resulting %deque's size is the same as the number of elements assigned.
 775      *  Old data may be lost.
 776     */
 777     void
 778     assign(size_type __n, const value_type& __val) { _M_fill_assign(__n, __val); }
 779
 780     /**
 781      *  @brief  Assigns a range to a %deque.
 782      *  @param  first  An input iterator.
 783      *  @param  last   An input iterator.
 784      *
 785      *  This function fills a %deque with copies of the elements in the
 786      *  range [first,last).
 787      *
 788      *  Note that the assignment completely changes the %deque and that the
 789      *  resulting %deque's size is the same as the number of elements assigned.
 790      *  Old data may be lost.
 791     */
 792     template<typename _InputIterator>
 793       void
 794       assign(_InputIterator __first, _InputIterator __last)
 795       {
 796         typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 797         _M_assign_dispatch(__first, __last, _Integral());
 798       }
 799
 800     /// Get a copy of the memory allocation object.
 801     allocator_type
 802     get_allocator() const { return _Base::get_allocator(); }
 803
 804     // iterators
 805     /**
 806      *  Returns a read/write iterator that points to the first element in the
 807      *  %deque.  Iteration is done in ordinary element order.
 808     */
 809     iterator
 810     begin() { return _M_start; }
 811
 812     /**
 813      *  Returns a read-only (constant) iterator that points to the first element
 814      *  in the %deque.  Iteration is done in ordinary element order.
 815     */
 816     const_iterator
 817     begin() const { return _M_start; }
 818
 819     /**
 820      *  Returns a read/write iterator that points one past the last element in
 821      *  the %deque.  Iteration is done in ordinary element order.
 822     */
 823     iterator
 824     end() { return _M_finish; }
 825
 826     /**
 827      *  Returns a read-only (constant) iterator that points one past the last
 828      *  element in the %deque.  Iteration is done in ordinary element order.
 829     */
 830     const_iterator
 831     end() const { return _M_finish; }
 832
 833     /**
 834      *  Returns a read/write reverse iterator that points to the last element in
 835      *  the %deque.  Iteration is done in reverse element order.
 836     */
 837     reverse_iterator
 838     rbegin() { return reverse_iterator(_M_finish); }
 839
 840     /**
 841      *  Returns a read-only (constant) reverse iterator that points to the last
 842      *  element in the %deque.  Iteration is done in reverse element order.
 843     */
 844     const_reverse_iterator
 845     rbegin() const { return const_reverse_iterator(_M_finish); }
 846
 847     /**
 848      *  Returns a read/write reverse iterator that points to one before the
 849      *  first element in the %deque.  Iteration is done in reverse element
 850      *  order.
 851     */
 852     reverse_iterator
 853     rend() { return reverse_iterator(_M_start); }
 854
 855     /**
 856      *  Returns a read-only (constant) reverse iterator that points to one
 857      *  before the first element in the %deque.  Iteration is done in reverse
 858      *  element order.
 859     */
 860     const_reverse_iterator
 861     rend() const { return const_reverse_iterator(_M_start); }
 862
 863     // [23.2.1.2] capacity
 864     /**  Returns the number of elements in the %deque.  */
 865     size_type
 866     size() const { return _M_finish - _M_start; }
 867
 868     /**  Returns the size() of the largest possible %deque.  */
 869     size_type
 870     max_size() const { return size_type(-1); }
 871
 872     /**
 873      *  @brief  Resizes the %deque to the specified number of elements.
 874      *  @param  new_size  Number of elements the %deque should contain.
 875      *  @param  x  Data with which new elements should be populated.
 876      *
 877      *  This function will %resize the %deque to the specified number of
 878      *  elements.  If the number is smaller than the %deque's current size the
 879      *  %deque is truncated, otherwise the %deque is extended and new elements
 880      *  are populated with given data.
 881     */
 882     void
 883     resize(size_type __new_size, const value_type& __x)
 884     {
 885       const size_type __len = size();
 886       if (__new_size < __len)
 887         erase(_M_start + __new_size, _M_finish);
 888       else
 889         insert(_M_finish, __new_size - __len, __x);
 890     }
 891
 892     /**
 893      *  @brief  Resizes the %deque to the specified number of elements.
 894      *  @param  new_size  Number of elements the %deque should contain.
 895      *
 896      *  This function will resize the %deque to the specified number of
 897      *  elements.  If the number is smaller than the %deque's current size the
 898      *  %deque is truncated, otherwise the %deque is extended and new elements
 899      *  are default-constructed.
 900     */
 901     void
 902     resize(size_type new_size) { resize(new_size, value_type()); }
 903
 904     /**
 905      *  Returns true if the %deque is empty.  (Thus begin() would equal end().)
 906     */
 907     bool empty() const { return _M_finish == _M_start; }
 908
 909     // element access
 910     /**
 911      *  @brief  Subscript access to the data contained in the %deque.
 912      *  @param  n  The index of the element for which data should be accessed.
 913      *  @return  Read/write reference to data.
 914      *
 915      *  This operator allows for easy, array-style, data access.
 916      *  Note that data access with this operator is unchecked and out_of_range
 917      *  lookups are not defined. (For checked lookups see at().)
 918     */
 919     reference
 920     operator[](size_type __n) { return _M_start[difference_type(__n)]; }
 921
 922     /**
 923      *  @brief  Subscript access to the data contained in the %deque.
 924      *  @param  n  The index of the element for which data should be accessed.
 925      *  @return  Read-only (constant) reference to data.
 926      *
 927      *  This operator allows for easy, array-style, data access.
 928      *  Note that data access with this operator is unchecked and out_of_range
 929      *  lookups are not defined. (For checked lookups see at().)
 930     */
 931     const_reference
 932     operator[](size_type __n) const { return _M_start[difference_type(__n)]; }
 933
 934   protected:
 935     /// @if maint Safety check used only from at().  @endif
 936     void
 937     _M_range_check(size_type __n) const
 938     {
 939       if (__n >= this->size())
 940         __throw_out_of_range("deque [] access out of range");
 941     }
 942
 943   public:
 944     /**
 945      *  @brief  Provides access to the data contained in the %deque.
 946      *  @param  n  The index of the element for which data should be accessed.
 947      *  @return  Read/write reference to data.
 948      *  @throw  std::out_of_range  If @a n is an invalid index.
 949      *
 950      *  This function provides for safer data access.  The parameter is first
 951      *  checked that it is in the range of the deque.  The function throws
 952      *  out_of_range if the check fails.
 953     */
 954     reference
 955     at(size_type __n) { _M_range_check(__n); return (*this)[__n]; }
 956
 957     /**
 958      *  @brief  Provides access to the data contained in the %deque.
 959      *  @param  n  The index of the element for which data should be accessed.
 960      *  @return  Read-only (constant) reference to data.
 961      *  @throw  std::out_of_range  If @a n is an invalid index.
 962      *
 963      *  This function provides for safer data access.  The parameter is first
 964      *  checked that it is in the range of the deque.  The function throws
 965      *  out_of_range if the check fails.
 966     */
 967     const_reference
 968     at(size_type __n) const { _M_range_check(__n); return (*this)[__n]; }
 969
 970     /**
 971      *  Returns a read/write reference to the data at the first element of the
 972      *  %deque.
 973     */
 974     reference
 975     front() { return *_M_start; }
 976
 977     /**
 978      *  Returns a read-only (constant) reference to the data at the first
 979      *  element of the %deque.
 980     */
 981     const_reference
 982     front() const { return *_M_start; }
 983
 984     /**
 985      *  Returns a read/write reference to the data at the last element of the
 986      *  %deque.
 987     */
 988     reference
 989     back()
 990     {
 991       iterator __tmp = _M_finish;
 992       --__tmp;
 993       return *__tmp;
 994     }
 995
 996     /**
 997      *  Returns a read-only (constant) reference to the data at the last
 998      *  element of the %deque.
 999     */
1000     const_reference
1001     back() const
1002     {
1003       const_iterator __tmp = _M_finish;
1004       --__tmp;
1005       return *__tmp;
1006     }
1007
1008     // [23.2.1.2] modifiers
1009     /**
1010      *  @brief  Add data to the front of the %deque.
1011      *  @param  x  Data to be added.
1012      *
1013      *  This is a typical stack operation.  The function creates an element at
1014      *  the front of the %deque and assigns the given data to it.  Due to the
1015      *  nature of a %deque this operation can be done in constant time.
1016     */
1017     void
1018     push_front(const value_type& __x)
1019     {
1020       if (_M_start._M_cur != _M_start._M_first) {
1021         _Construct(_M_start._M_cur - 1, __x);
1022         --_M_start._M_cur;
1023       }
1024       else
1025         _M_push_front_aux(__x);
1026     }
1027
1028   #ifdef _GLIBCPP_DEPRECATED
1029     /**
1030      *  @brief  Add data to the front of the %deque.
1031      *
1032      *  This is a typical stack operation.  The function creates a
1033      *  default-constructed element at the front of the %deque.  Due to the
1034      *  nature of a %deque this operation can be done in constant time.  You
1035      *  should consider using push_front(value_type()) instead.
1036      *
1037      *  @note This was deprecated in 3.2 and will be removed in 3.4.  You must
1038      *        define @c _GLIBCPP_DEPRECATED to make this visible in 3.2; see
1039      *        c++config.h.
1040     */
1041     void
1042     push_front()
1043     {
1044       if (_M_start._M_cur != _M_start._M_first) {
1045         _Construct(_M_start._M_cur - 1);
1046         --_M_start._M_cur;
1047       }
1048       else
1049         _M_push_front_aux();
1050     }
1051   #endif
1052
1053     /**
1054      *  @brief  Add data to the end of the %deque.
1055      *  @param  x  Data to be added.
1056      *
1057      *  This is a typical stack operation.  The function creates an element at
1058      *  the end of the %deque and assigns the given data to it.  Due to the
1059      *  nature of a %deque this operation can be done in constant time.
1060     */
1061     void
1062     push_back(const value_type& __x)
1063     {
1064       if (_M_finish._M_cur != _M_finish._M_last - 1) {
1065         _Construct(_M_finish._M_cur, __x);
1066         ++_M_finish._M_cur;
1067       }
1068       else
1069         _M_push_back_aux(__x);
1070     }
1071
1072   #ifdef _GLIBCPP_DEPRECATED
1073     /**
1074      *  @brief  Add data to the end of the %deque.
1075      *
1076      *  This is a typical stack operation.  The function creates a
1077      *  default-constructed element at the end of the %deque.  Due to the nature
1078      *  of a %deque this operation can be done in constant time.  You should
1079      *  consider using push_back(value_type()) instead.
1080      *
1081      *  @note This was deprecated in 3.2 and will be removed in 3.4.  You must
1082      *        define @c _GLIBCPP_DEPRECATED to make this visible in 3.2; see
1083      *        c++config.h.
1084     */
1085     void
1086     push_back()
1087     {
1088       if (_M_finish._M_cur != _M_finish._M_last - 1) {
1089         _Construct(_M_finish._M_cur);
1090         ++_M_finish._M_cur;
1091       }
1092       else
1093         _M_push_back_aux();
1094     }
1095   #endif
1096
1097     /**
1098      *  @brief  Removes first element.
1099      *
1100      *  This is a typical stack operation.  It shrinks the %deque by one.
1101      *
1102      *  Note that no data is returned, and if the first element's data is
1103      *  needed, it should be retrieved before pop_front() is called.
1104     */
1105     void
1106     pop_front()
1107     {
1108       if (_M_start._M_cur != _M_start._M_last - 1) {
1109         _Destroy(_M_start._M_cur);
1110         ++_M_start._M_cur;
1111       }
1112       else
1113         _M_pop_front_aux();
1114     }
1115
1116     /**
1117      *  @brief  Removes last element.
1118      *
1119      *  This is a typical stack operation.  It shrinks the %deque by one.
1120      *
1121      *  Note that no data is returned, and if the last element's data is
1122      *  needed, it should be retrieved before pop_back() is called.
1123     */
1124     void
1125     pop_back()
1126     {
1127       if (_M_finish._M_cur != _M_finish._M_first) {
1128         --_M_finish._M_cur;
1129         _Destroy(_M_finish._M_cur);
1130       }
1131       else
1132         _M_pop_back_aux();
1133     }
1134
1135     /**
1136      *  @brief  Inserts given value into %deque before specified iterator.
1137      *  @param  position  An iterator into the %deque.
1138      *  @param  x  Data to be inserted.
1139      *  @return  An iterator that points to the inserted data.
1140      *
1141      *  This function will insert a copy of the given value before the specified
1142      *  location.
1143     */
1144     iterator
1145     insert(iterator position, const value_type& __x);
1146
1147   #ifdef _GLIBCPP_DEPRECATED
1148     /**
1149      *  @brief  Inserts an element into the %deque.
1150      *  @param  position  An iterator into the %deque.
1151      *  @return  An iterator that points to the inserted element.
1152      *
1153      *  This function will insert a default-constructed element before the
1154      *  specified location.  You should consider using
1155      *  insert(position,value_type()) instead.
1156      *
1157      *  @note This was deprecated in 3.2 and will be removed in 3.4.  You must
1158      *        define @c _GLIBCPP_DEPRECATED to make this visible in 3.2; see
1159      *        c++config.h.
1160     */
1161     iterator
1162     insert(iterator __position)
1163     { return insert(__position, value_type()); }
1164   #endif
1165
1166     /**
1167      *  @brief  Inserts a number of copies of given data into the %deque.
1168      *  @param  position  An iterator into the %deque.
1169      *  @param  n  Number of elements to be inserted.
1170      *  @param  x  Data to be inserted.
1171      *
1172      *  This function will insert a specified number of copies of the given data
1173      *  before the location specified by @a position.
1174     */
1175     void
1176     insert(iterator __position, size_type __n, const value_type& __x)
1177     { _M_fill_insert(__position, __n, __x); }
1178
1179     /**
1180      *  @brief  Inserts a range into the %deque.
1181      *  @param  pos  An iterator into the %deque.
1182      *  @param  first  An input iterator.
1183      *  @param  last   An input iterator.
1184      *
1185      *  This function will insert copies of the data in the range [first,last)
1186      *  into the %deque before the location specified by @a pos.  This is
1187      *  known as "range insert."
1188     */
1189     template<typename _InputIterator>
1190       void
1191       insert(iterator __pos, _InputIterator __first, _InputIterator __last)
1192       {
1193         // Check whether it's an integral type.  If so, it's not an iterator.
1194         typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
1195         _M_insert_dispatch(__pos, __first, __last, _Integral());
1196       }
1197
1198     /**
1199      *  @brief  Remove element at given position.
1200      *  @param  position  Iterator pointing to element to be erased.
1201      *  @return  An iterator pointing to the next element (or end()).
1202      *
1203      *  This function will erase the element at the given position and thus
1204      *  shorten the %deque by one.
1205      *
1206      *  The user is cautioned that
1207      *  this function only erases the element, and that if the element is itself
1208      *  a pointer, the pointed-to memory is not touched in any way.  Managing
1209      *  the pointer is the user's responsibilty.
1210     */
1211     iterator
1212     erase(iterator __position);
1213
1214     /**
1215      *  @brief  Remove a range of elements.
1216      *  @param  first  Iterator pointing to the first element to be erased.
1217      *  @param  last  Iterator pointing to one past the last element to be
1218      *                erased.
1219      *  @return  An iterator pointing to the element pointed to by @a last
1220      *           prior to erasing (or end()).
1221      *
1222      *  This function will erase the elements in the range [first,last) and
1223      *  shorten the %deque accordingly.
1224      *
1225      *  The user is cautioned that
1226      *  this function only erases the elements, and that if the elements
1227      *  themselves are pointers, the pointed-to memory is not touched in any
1228      *  way.  Managing the pointer is the user's responsibilty.
1229     */
1230     iterator
1231     erase(iterator __first, iterator __last);
1232
1233     /**
1234      *  @brief  Swaps data with another %deque.
1235      *  @param  x  A %deque of the same element and allocator types.
1236      *
1237      *  This exchanges the elements between two deques in constant time.
1238      *  (Four pointers, so it should be quite fast.)
1239      *  Note that the global std::swap() function is specialized such that
1240      *  std::swap(d1,d2) will feed to this function.
1241     */
1242     void
1243     swap(deque& __x)
1244     {
1245       std::swap(_M_start, __x._M_start);
1246       std::swap(_M_finish, __x._M_finish);
1247       std::swap(_M_map, __x._M_map);
1248       std::swap(_M_map_size, __x._M_map_size);
1249     }
1250
1251     /**
1252      *  Erases all the elements.  Note that this function only erases the
1253      *  elements, and that if the elements themselves are pointers, the
1254      *  pointed-to memory is not touched in any way.  Managing the pointer is
1255      *  the user's responsibilty.
1256     */
1257     void clear();
1258
1259   protected:
1260     // Internal constructor functions follow.
1261
1262     // called by the range constructor to implement [23.1.1]/9
1263     template<typename _Integer>
1264       void
1265       _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1266       {
1267         _M_initialize_map(__n);
1268         _M_fill_initialize(__x);
1269       }
1270
1271     // called by the range constructor to implement [23.1.1]/9
1272     template<typename _InputIter>
1273       void
1274       _M_initialize_dispatch(_InputIter __first, _InputIter __last,
1275                              __false_type)
1276       {
1277         typedef typename iterator_traits<_InputIter>::iterator_category
1278                          _IterCategory;
1279         _M_range_initialize(__first, __last, _IterCategory());
1280       }
1281
1282     // called by the second initialize_dispatch above
1283     //@{
1284     /**
1285      *  @if maint
1286      *  @brief Fills the deque with whatever is in [first,last).
1287      *  @param  first  An input iterator.
1288      *  @param  last  An input iterator.
1289      *  @return   Nothing.
1290      *
1291      *  If the iterators are actually forward iterators (or better), then the
1292      *  memory layout can be done all at once.  Else we move forward using
1293      *  push_back on each value from the iterator.
1294      *  @endif
1295     */
1296     template <typename _InputIterator>
1297       void
1298       _M_range_initialize(_InputIterator __first, _InputIterator __last,
1299                           input_iterator_tag);
1300
1301     // called by the second initialize_dispatch above
1302     template <typename _ForwardIterator>
1303       void
1304       _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
1305                           forward_iterator_tag);
1306     //@}
1307
1308     /**
1309      *  @if maint
1310      *  @brief Fills the %deque with copies of value.
1311      *  @param  value  Initial value.
1312      *  @return   Nothing.
1313      *  @pre _M_start and _M_finish have already been initialized, but none of
1314      *       the %deque's elements have yet been constructed.
1315      *
1316      *  This function is called only when the user provides an explicit size
1317      *  (with or without an explicit exemplar value).
1318      *  @endif
1319     */
1320     void
1321     _M_fill_initialize(const value_type& __value);
1322
1323
1324     // Internal assign functions follow.  The *_aux functions do the actual
1325     // assignment work for the range versions.
1326
1327     // called by the range assign to implement [23.1.1]/9
1328     template<typename _Integer>
1329       void
1330       _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1331       {
1332         _M_fill_assign(static_cast<size_type>(__n),
1333                        static_cast<value_type>(__val));
1334       }
1335
1336     // called by the range assign to implement [23.1.1]/9
1337     template<typename _InputIter>
1338       void
1339       _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type)
1340       {
1341         typedef typename iterator_traits<_InputIter>::iterator_category
1342                          _IterCategory;
1343         _M_assign_aux(__first, __last, _IterCategory());
1344       }
1345
1346     // called by the second assign_dispatch above
1347     template <typename _InputIterator>
1348       void
1349       _M_assign_aux(_InputIterator __first, _InputIterator __last,
1350                     input_iterator_tag);
1351
1352     // called by the second assign_dispatch above
1353     template <typename _ForwardIterator>
1354       void
1355       _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1356                     forward_iterator_tag)
1357       {
1358         size_type __len = distance(__first, __last);
1359         if (__len > size()) {
1360           _ForwardIterator __mid = __first;
1361           advance(__mid, size());
1362           copy(__first, __mid, begin());
1363           insert(end(), __mid, __last);
1364         }
1365         else
1366           erase(copy(__first, __last, begin()), end());
1367       }
1368
1369     // Called by assign(n,t), and the range assign when it turns out to be the
1370     // same thing.
1371     void
1372     _M_fill_assign(size_type __n, const value_type& __val)
1373     {
1374       if (__n > size())
1375       {
1376         fill(begin(), end(), __val);
1377         insert(end(), __n - size(), __val);
1378       }
1379       else
1380       {
1381         erase(begin() + __n, end());
1382         fill(begin(), end(), __val);
1383       }
1384     }
1385
1386
1387     //@{
1388     /**
1389      *  @if maint
1390      *  @brief Helper functions for push_* and pop_*.
1391      *  @endif
1392     */
1393     void _M_push_back_aux(const value_type&);
1394     void _M_push_front_aux(const value_type&);
1395   #ifdef _GLIBCPP_DEPRECATED
1396     void _M_push_back_aux();
1397     void _M_push_front_aux();
1398   #endif
1399     void _M_pop_back_aux();
1400     void _M_pop_front_aux();
1401     //@}
1402
1403
1404     // Internal insert functions follow.  The *_aux functions do the actual
1405     // insertion work when all shortcuts fail.
1406
1407     // called by the range insert to implement [23.1.1]/9
1408     template<typename _Integer>
1409       void
1410       _M_insert_dispatch(iterator __pos,
1411                          _Integer __n, _Integer __x, __true_type)
1412       {
1413         _M_fill_insert(__pos, static_cast<size_type>(__n),
1414                        static_cast<value_type>(__x));
1415       }
1416
1417     // called by the range insert to implement [23.1.1]/9
1418     template<typename _InputIterator>
1419       void
1420       _M_insert_dispatch(iterator __pos,
1421                          _InputIterator __first, _InputIterator __last,
1422                          __false_type)
1423       {
1424         typedef typename iterator_traits<_InputIterator>::iterator_category
1425                          _IterCategory;
1426         _M_range_insert_aux(__pos, __first, __last, _IterCategory());
1427       }
1428
1429     // called by the second insert_dispatch above
1430     template <typename _InputIterator>
1431       void
1432       _M_range_insert_aux(iterator __pos, _InputIterator __first,
1433                           _InputIterator __last, input_iterator_tag);
1434
1435     // called by the second insert_dispatch above
1436     template <typename _ForwardIterator>
1437       void
1438       _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
1439                           _ForwardIterator __last, forward_iterator_tag);
1440
1441     // Called by insert(p,n,x), and the range insert when it turns out to be
1442     // the same thing.  Can use fill functions in optimal situations, otherwise
1443     // passes off to insert_aux(p,n,x).
1444     void
1445     _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
1446
1447     // called by insert(p,x)
1448     iterator
1449     _M_insert_aux(iterator __pos, const value_type& __x);
1450
1451     // called by insert(p,n,x) via fill_insert
1452     void
1453     _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
1454
1455     // called by range_insert_aux for forward iterators
1456     template <typename _ForwardIterator>
1457       void
1458       _M_insert_aux(iterator __pos,
1459                     _ForwardIterator __first, _ForwardIterator __last,
1460                     size_type __n);
1461
1462   #ifdef _GLIBCPP_DEPRECATED
1463     // unused, see comment in implementation
1464     iterator _M_insert_aux(iterator __pos);
1465   #endif
1466
1467     //@{
1468     /**
1469      *  @if maint
1470      *  @brief Memory-handling helpers for the previous internal insert
1471      *         functions.
1472      *  @endif
1473     */
1474     iterator
1475     _M_reserve_elements_at_front(size_type __n)
1476     {
1477       size_type __vacancies = _M_start._M_cur - _M_start._M_first;
1478       if (__n > __vacancies)
1479         _M_new_elements_at_front(__n - __vacancies);
1480       return _M_start - difference_type(__n);
1481     }
1482
1483     iterator
1484     _M_reserve_elements_at_back(size_type __n)
1485     {
1486       size_type __vacancies = (_M_finish._M_last - _M_finish._M_cur) - 1;
1487       if (__n > __vacancies)
1488         _M_new_elements_at_back(__n - __vacancies);
1489       return _M_finish + difference_type(__n);
1490     }
1491
1492     void
1493     _M_new_elements_at_front(size_type __new_elements);
1494
1495     void
1496     _M_new_elements_at_back(size_type __new_elements);
1497     //@}
1498
1499
1500     //@{
1501     /**
1502      *  @if maint
1503      *  @brief Memory-handling helpers for the major %map.
1504      *
1505      *  Makes sure the _M_map has space for new nodes.  Does not actually add
1506      *  the nodes.  Can invalidate _M_map pointers.  (And consequently, %deque
1507      *  iterators.)
1508      *  @endif
1509     */
1510     void
1511     _M_reserve_map_at_back (size_type __nodes_to_add = 1)
1512     {
1513       if (__nodes_to_add + 1 > _M_map_size - (_M_finish._M_node - _M_map))
1514         _M_reallocate_map(__nodes_to_add, false);
1515     }
1516
1517     void
1518     _M_reserve_map_at_front (size_type __nodes_to_add = 1)
1519     {
1520       if (__nodes_to_add > size_type(_M_start._M_node - _M_map))
1521         _M_reallocate_map(__nodes_to_add, true);
1522     }
1523
1524     void
1525     _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
1526     //@}
1527   };
1528
1529
1530   /**
1531    *  @brief  Deque equality comparison.
1532    *  @param  x  A %deque.
1533    *  @param  y  A %deque of the same type as @a x.
1534    *  @return  True iff the size and elements of the deques are equal.
1535    *
1536    *  This is an equivalence relation.  It is linear in the size of the
1537    *  deques.  Deques are considered equivalent if their sizes are equal,
1538    *  and if corresponding elements compare equal.
1539   */
1540   template <typename _Tp, typename _Alloc>
1541   inline bool operator==(const deque<_Tp, _Alloc>& __x,
1542                          const deque<_Tp, _Alloc>& __y)
1543   {
1544     return __x.size() == __y.size() &&
1545            equal(__x.begin(), __x.end(), __y.begin());
1546   }
1547
1548   /**
1549    *  @brief  Deque ordering relation.
1550    *  @param  x  A %deque.
1551    *  @param  y  A %deque of the same type as @a x.
1552    *  @return  True iff @a x is lexographically less than @a y.
1553    *
1554    *  This is a total ordering relation.  It is linear in the size of the
1555    *  deques.  The elements must be comparable with @c <.
1556    *
1557    *  See std::lexographical_compare() for how the determination is made.
1558   */
1559   template <typename _Tp, typename _Alloc>
1560   inline bool operator<(const deque<_Tp, _Alloc>& __x,
1561                         const deque<_Tp, _Alloc>& __y)
1562   {
1563     return lexicographical_compare(__x.begin(), __x.end(),
1564                                    __y.begin(), __y.end());
1565   }
1566
1567   /// Based on operator==
1568   template <typename _Tp, typename _Alloc>
1569   inline bool operator!=(const deque<_Tp, _Alloc>& __x,
1570                          const deque<_Tp, _Alloc>& __y) {
1571     return !(__x == __y);
1572   }
1573
1574   /// Based on operator<
1575   template <typename _Tp, typename _Alloc>
1576   inline bool operator>(const deque<_Tp, _Alloc>& __x,
1577                         const deque<_Tp, _Alloc>& __y) {
1578     return __y < __x;
1579   }
1580
1581   /// Based on operator<
1582   template <typename _Tp, typename _Alloc>
1583   inline bool operator<=(const deque<_Tp, _Alloc>& __x,
1584                          const deque<_Tp, _Alloc>& __y) {
1585     return !(__y < __x);
1586   }
1587
1588   /// Based on operator<
1589   template <typename _Tp, typename _Alloc>
1590   inline bool operator>=(const deque<_Tp, _Alloc>& __x,
1591                          const deque<_Tp, _Alloc>& __y) {
1592     return !(__x < __y);
1593   }
1594
1595   /// See std::deque::swap().
1596   template <typename _Tp, typename _Alloc>
1597   inline void swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y)
1598   {
1599     __x.swap(__y);
1600   }
1601 } // namespace std
1602
1603 #endif /* __GLIBCPP_INTERNAL_DEQUE_H */