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

   1 // Deque implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
   4 // 2011 Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 3, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // Under Section 7 of GPL version 3, you are granted additional
  18 // permissions described in the GCC Runtime Library Exception, version
  19 // 3.1, as published by the Free Software Foundation.
  20
  21 // You should have received a copy of the GNU General Public License and
  22 // a copy of the GCC Runtime Library Exception along with this program;
  23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 // <http://www.gnu.org/licenses/>.
  25
  26 /*
  27  *
  28  * Copyright (c) 1994
  29  * Hewlett-Packard Company
  30  *
  31  * Permission to use, copy, modify, distribute and sell this software
  32  * and its documentation for any purpose is hereby granted without fee,
  33  * provided that the above copyright notice appear in all copies and
  34  * that both that copyright notice and this permission notice appear
  35  * in supporting documentation.  Hewlett-Packard Company makes no
  36  * representations about the suitability of this software for any
  37  * purpose.  It is provided "as is" without express or implied warranty.
  38  *
  39  *
  40  * Copyright (c) 1997
  41  * Silicon Graphics Computer Systems, Inc.
  42  *
  43  * Permission to use, copy, modify, distribute and sell this software
  44  * and its documentation for any purpose is hereby granted without fee,
  45  * provided that the above copyright notice appear in all copies and
  46  * that both that copyright notice and this permission notice appear
  47  * in supporting documentation.  Silicon Graphics makes no
  48  * representations about the suitability of this software for any
  49  * purpose.  It is provided "as is" without express or implied warranty.
  50  */
  51
  52 /** @file bits/stl_deque.h
  53  *  This is an internal header file, included by other library headers.
  54  *  Do not attempt to use it directly. @headername{deque}
  55  */
  56
  57 #ifndef _STL_DEQUE_H
  58 #define _STL_DEQUE_H 1
  59
  60 #include <bits/concept_check.h>
  61 #include <bits/stl_iterator_base_types.h>
  62 #include <bits/stl_iterator_base_funcs.h>
  63 #include <initializer_list>
  64
  65 namespace std _GLIBCXX_VISIBILITY(default)
  66 {
  67 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
  68
  69   /**
  70    *  @brief This function controls the size of memory nodes.
  71    *  @param  size  The size of an element.
  72    *  @return   The number (not byte size) of elements per node.
  73    *
  74    *  This function started off as a compiler kludge from SGI, but
  75    *  seems to be a useful wrapper around a repeated constant
  76    *  expression.  The @b 512 is tunable (and no other code needs to
  77    *  change), but no investigation has been done since inheriting the
  78    *  SGI code.  Touch _GLIBCXX_DEQUE_BUF_SIZE only if you know what
  79    *  you are doing, however: changing it breaks the binary
  80    *  compatibility!!
  81   */
  82
  83 #ifndef _GLIBCXX_DEQUE_BUF_SIZE
  84 #define _GLIBCXX_DEQUE_BUF_SIZE 512
  85 #endif
  86
  87   inline size_t
  88   __deque_buf_size(size_t __size)
  89   { return (__size < _GLIBCXX_DEQUE_BUF_SIZE
  90             ? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) : size_t(1)); }
  91
  92
  93   /**
  94    *  @brief A deque::iterator.
  95    *
  96    *  Quite a bit of intelligence here.  Much of the functionality of
  97    *  deque is actually passed off to this class.  A deque holds two
  98    *  of these internally, marking its valid range.  Access to
  99    *  elements is done as offsets of either of those two, relying on
 100    *  operator overloading in this class.
 101    *
 102    *  All the functions are op overloads except for _M_set_node.
 103   */
 104   template<typename _Tp, typename _Ref, typename _Ptr>
 105     struct _Deque_iterator
 106     {
 107       typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
 108       typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
 109
 110       static size_t _S_buffer_size()
 111       { return __deque_buf_size(sizeof(_Tp)); }
 112
 113       typedef std::random_access_iterator_tag iterator_category;
 114       typedef _Tp                             value_type;
 115       typedef _Ptr                            pointer;
 116       typedef _Ref                            reference;
 117       typedef size_t                          size_type;
 118       typedef ptrdiff_t                       difference_type;
 119       typedef _Tp**                           _Map_pointer;
 120       typedef _Deque_iterator                 _Self;
 121
 122       _Tp* _M_cur;
 123       _Tp* _M_first;
 124       _Tp* _M_last;
 125       _Map_pointer _M_node;
 126
 127       _Deque_iterator(_Tp* __x, _Map_pointer __y)
 128       : _M_cur(__x), _M_first(*__y),
 129         _M_last(*__y + _S_buffer_size()), _M_node(__y) { }
 130
 131       _Deque_iterator()
 132       : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) { }
 133
 134       _Deque_iterator(const iterator& __x)
 135       : _M_cur(__x._M_cur), _M_first(__x._M_first),
 136         _M_last(__x._M_last), _M_node(__x._M_node) { }
 137
 138       reference
 139       operator*() const
 140       { return *_M_cur; }
 141
 142       pointer
 143       operator->() const
 144       { return _M_cur; }
 145
 146       _Self&
 147       operator++()
 148       {
 149         ++_M_cur;
 150         if (_M_cur == _M_last)
 151           {
 152             _M_set_node(_M_node + 1);
 153             _M_cur = _M_first;
 154           }
 155         return *this;
 156       }
 157
 158       _Self
 159       operator++(int)
 160       {
 161         _Self __tmp = *this;
 162         ++*this;
 163         return __tmp;
 164       }
 165
 166       _Self&
 167       operator--()
 168       {
 169         if (_M_cur == _M_first)
 170           {
 171             _M_set_node(_M_node - 1);
 172             _M_cur = _M_last;
 173           }
 174         --_M_cur;
 175         return *this;
 176       }
 177
 178       _Self
 179       operator--(int)
 180       {
 181         _Self __tmp = *this;
 182         --*this;
 183         return __tmp;
 184       }
 185
 186       _Self&
 187       operator+=(difference_type __n)
 188       {
 189         const difference_type __offset = __n + (_M_cur - _M_first);
 190         if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
 191           _M_cur += __n;
 192         else
 193           {
 194             const difference_type __node_offset =
 195               __offset > 0 ? __offset / difference_type(_S_buffer_size())
 196                            : -difference_type((-__offset - 1)
 197                                               / _S_buffer_size()) - 1;
 198             _M_set_node(_M_node + __node_offset);
 199             _M_cur = _M_first + (__offset - __node_offset
 200                                  * difference_type(_S_buffer_size()));
 201           }
 202         return *this;
 203       }
 204
 205       _Self
 206       operator+(difference_type __n) const
 207       {
 208         _Self __tmp = *this;
 209         return __tmp += __n;
 210       }
 211
 212       _Self&
 213       operator-=(difference_type __n)
 214       { return *this += -__n; }
 215
 216       _Self
 217       operator-(difference_type __n) const
 218       {
 219         _Self __tmp = *this;
 220         return __tmp -= __n;
 221       }
 222
 223       reference
 224       operator[](difference_type __n) const
 225       { return *(*this + __n); }
 226
 227       /**
 228        *  Prepares to traverse new_node.  Sets everything except
 229        *  _M_cur, which should therefore be set by the caller
 230        *  immediately afterwards, based on _M_first and _M_last.
 231        */
 232       void
 233       _M_set_node(_Map_pointer __new_node)
 234       {
 235         _M_node = __new_node;
 236         _M_first = *__new_node;
 237         _M_last = _M_first + difference_type(_S_buffer_size());
 238       }
 239     };
 240
 241   // Note: we also provide overloads whose operands are of the same type in
 242   // order to avoid ambiguous overload resolution when std::rel_ops operators
 243   // are in scope (for additional details, see libstdc++/3628)
 244   template<typename _Tp, typename _Ref, typename _Ptr>
 245     inline bool
 246     operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
 247                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
 248     { return __x._M_cur == __y._M_cur; }
 249
 250   template<typename _Tp, typename _RefL, typename _PtrL,
 251            typename _RefR, typename _PtrR>
 252     inline bool
 253     operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
 254                const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
 255     { return __x._M_cur == __y._M_cur; }
 256
 257   template<typename _Tp, typename _Ref, typename _Ptr>
 258     inline bool
 259     operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
 260                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
 261     { return !(__x == __y); }
 262
 263   template<typename _Tp, typename _RefL, typename _PtrL,
 264            typename _RefR, typename _PtrR>
 265     inline bool
 266     operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
 267                const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
 268     { return !(__x == __y); }
 269
 270   template<typename _Tp, typename _Ref, typename _Ptr>
 271     inline bool
 272     operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
 273               const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
 274     { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
 275                                           : (__x._M_node < __y._M_node); }
 276
 277   template<typename _Tp, typename _RefL, typename _PtrL,
 278            typename _RefR, typename _PtrR>
 279     inline bool
 280     operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
 281               const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
 282     { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
 283                                           : (__x._M_node < __y._M_node); }
 284
 285   template<typename _Tp, typename _Ref, typename _Ptr>
 286     inline bool
 287     operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
 288               const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
 289     { return __y < __x; }
 290
 291   template<typename _Tp, typename _RefL, typename _PtrL,
 292            typename _RefR, typename _PtrR>
 293     inline bool
 294     operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
 295               const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
 296     { return __y < __x; }
 297
 298   template<typename _Tp, typename _Ref, typename _Ptr>
 299     inline bool
 300     operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
 301                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
 302     { return !(__y < __x); }
 303
 304   template<typename _Tp, typename _RefL, typename _PtrL,
 305            typename _RefR, typename _PtrR>
 306     inline bool
 307     operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
 308                const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
 309     { return !(__y < __x); }
 310
 311   template<typename _Tp, typename _Ref, typename _Ptr>
 312     inline bool
 313     operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
 314                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
 315     { return !(__x < __y); }
 316
 317   template<typename _Tp, typename _RefL, typename _PtrL,
 318            typename _RefR, typename _PtrR>
 319     inline bool
 320     operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
 321                const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
 322     { return !(__x < __y); }
 323
 324   // _GLIBCXX_RESOLVE_LIB_DEFECTS
 325   // According to the resolution of DR179 not only the various comparison
 326   // operators but also operator- must accept mixed iterator/const_iterator
 327   // parameters.
 328   template<typename _Tp, typename _Ref, typename _Ptr>
 329     inline typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type
 330     operator-(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
 331               const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
 332     {
 333       return typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type
 334         (_Deque_iterator<_Tp, _Ref, _Ptr>::_S_buffer_size())
 335         * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
 336         + (__y._M_last - __y._M_cur);
 337     }
 338
 339   template<typename _Tp, typename _RefL, typename _PtrL,
 340            typename _RefR, typename _PtrR>
 341     inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
 342     operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
 343               const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
 344     {
 345       return typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
 346         (_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size())
 347         * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
 348         + (__y._M_last - __y._M_cur);
 349     }
 350
 351   template<typename _Tp, typename _Ref, typename _Ptr>
 352     inline _Deque_iterator<_Tp, _Ref, _Ptr>
 353     operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
 354     { return __x + __n; }
 355
 356   template<typename _Tp>
 357     void
 358     fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>&,
 359          const _Deque_iterator<_Tp, _Tp&, _Tp*>&, const _Tp&);
 360
 361   template<typename _Tp>
 362     _Deque_iterator<_Tp, _Tp&, _Tp*>
 363     copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
 364          _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
 365          _Deque_iterator<_Tp, _Tp&, _Tp*>);
 366
 367   template<typename _Tp>
 368     inline _Deque_iterator<_Tp, _Tp&, _Tp*>
 369     copy(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
 370          _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
 371          _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
 372     { return std::copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
 373                        _Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),
 374                        __result); }
 375
 376   template<typename _Tp>
 377     _Deque_iterator<_Tp, _Tp&, _Tp*>
 378     copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
 379                   _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
 380                   _Deque_iterator<_Tp, _Tp&, _Tp*>);
 381
 382   template<typename _Tp>
 383     inline _Deque_iterator<_Tp, _Tp&, _Tp*>
 384     copy_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
 385                   _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
 386                   _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
 387     { return std::copy_backward(_Deque_iterator<_Tp,
 388                                 const _Tp&, const _Tp*>(__first),
 389                                 _Deque_iterator<_Tp,
 390                                 const _Tp&, const _Tp*>(__last),
 391                                 __result); }
 392
 393 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 394   template<typename _Tp>
 395     _Deque_iterator<_Tp, _Tp&, _Tp*>
 396     move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
 397          _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
 398          _Deque_iterator<_Tp, _Tp&, _Tp*>);
 399
 400   template<typename _Tp>
 401     inline _Deque_iterator<_Tp, _Tp&, _Tp*>
 402     move(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
 403          _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
 404          _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
 405     { return std::move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
 406                        _Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),
 407                        __result); }
 408
 409   template<typename _Tp>
 410     _Deque_iterator<_Tp, _Tp&, _Tp*>
 411     move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
 412                   _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
 413                   _Deque_iterator<_Tp, _Tp&, _Tp*>);
 414
 415   template<typename _Tp>
 416     inline _Deque_iterator<_Tp, _Tp&, _Tp*>
 417     move_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
 418                   _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
 419                   _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
 420     { return std::move_backward(_Deque_iterator<_Tp,
 421                                 const _Tp&, const _Tp*>(__first),
 422                                 _Deque_iterator<_Tp,
 423                                 const _Tp&, const _Tp*>(__last),
 424                                 __result); }
 425 #endif
 426
 427   /**
 428    *  Deque base class.  This class provides the unified face for %deque's
 429    *  allocation.  This class's constructor and destructor allocate and
 430    *  deallocate (but do not initialize) storage.  This makes %exception
 431    *  safety easier.
 432    *
 433    *  Nothing in this class ever constructs or destroys an actual Tp element.
 434    *  (Deque handles that itself.)  Only/All memory management is performed
 435    *  here.
 436   */
 437   template<typename _Tp, typename _Alloc>
 438     class _Deque_base
 439     {
 440     public:
 441       typedef _Alloc                  allocator_type;
 442
 443       allocator_type
 444       get_allocator() const
 445       { return allocator_type(_M_get_Tp_allocator()); }
 446
 447       typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
 448       typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
 449
 450       _Deque_base()
 451       : _M_impl()
 452       { _M_initialize_map(0); }
 453
 454       _Deque_base(size_t __num_elements)
 455       : _M_impl()
 456       { _M_initialize_map(__num_elements); }
 457
 458       _Deque_base(const allocator_type& __a, size_t __num_elements)
 459       : _M_impl(__a)
 460       { _M_initialize_map(__num_elements); }
 461
 462       _Deque_base(const allocator_type& __a)
 463       : _M_impl(__a)
 464       { }
 465
 466 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 467       _Deque_base(_Deque_base&& __x)
 468       : _M_impl(__x._M_get_Tp_allocator())
 469       {
 470         _M_initialize_map(0);
 471         if (__x._M_impl._M_map)
 472           {
 473             std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
 474             std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
 475             std::swap(this->_M_impl._M_map, __x._M_impl._M_map);
 476             std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size);
 477           }
 478       }
 479 #endif
 480
 481       ~_Deque_base();
 482
 483     protected:
 484       //This struct encapsulates the implementation of the std::deque
 485       //standard container and at the same time makes use of the EBO
 486       //for empty allocators.
 487       typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type;
 488
 489       typedef typename _Alloc::template rebind<_Tp>::other  _Tp_alloc_type;
 490
 491       struct _Deque_impl
 492       : public _Tp_alloc_type
 493       {
 494         _Tp** _M_map;
 495         size_t _M_map_size;
 496         iterator _M_start;
 497         iterator _M_finish;
 498
 499         _Deque_impl()
 500         : _Tp_alloc_type(), _M_map(0), _M_map_size(0),
 501           _M_start(), _M_finish()
 502         { }
 503
 504         _Deque_impl(const _Tp_alloc_type& __a)
 505         : _Tp_alloc_type(__a), _M_map(0), _M_map_size(0),
 506           _M_start(), _M_finish()
 507         { }
 508       };
 509
 510       _Tp_alloc_type&
 511       _M_get_Tp_allocator()
 512       { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
 513
 514       const _Tp_alloc_type&
 515       _M_get_Tp_allocator() const
 516       { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
 517
 518       _Map_alloc_type
 519       _M_get_map_allocator() const
 520       { return _Map_alloc_type(_M_get_Tp_allocator()); }
 521
 522       _Tp*
 523       _M_allocate_node()
 524       {
 525         return _M_impl._Tp_alloc_type::allocate(__deque_buf_size(sizeof(_Tp)));
 526       }
 527
 528       void
 529       _M_deallocate_node(_Tp* __p)
 530       {
 531         _M_impl._Tp_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp)));
 532       }
 533
 534       _Tp**
 535       _M_allocate_map(size_t __n)
 536       { return _M_get_map_allocator().allocate(__n); }
 537
 538       void
 539       _M_deallocate_map(_Tp** __p, size_t __n)
 540       { _M_get_map_allocator().deallocate(__p, __n); }
 541
 542     protected:
 543       void _M_initialize_map(size_t);
 544       void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
 545       void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
 546       enum { _S_initial_map_size = 8 };
 547
 548       _Deque_impl _M_impl;
 549     };
 550
 551   template<typename _Tp, typename _Alloc>
 552     _Deque_base<_Tp, _Alloc>::
 553     ~_Deque_base()
 554     {
 555       if (this->_M_impl._M_map)
 556         {
 557           _M_destroy_nodes(this->_M_impl._M_start._M_node,
 558                            this->_M_impl._M_finish._M_node + 1);
 559           _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
 560         }
 561     }
 562
 563   /**
 564    *  @brief Layout storage.
 565    *  @param  num_elements  The count of T's for which to allocate space
 566    *                        at first.
 567    *  @return   Nothing.
 568    *
 569    *  The initial underlying memory layout is a bit complicated...
 570   */
 571   template<typename _Tp, typename _Alloc>
 572     void
 573     _Deque_base<_Tp, _Alloc>::
 574     _M_initialize_map(size_t __num_elements)
 575     {
 576       const size_t __num_nodes = (__num_elements/ __deque_buf_size(sizeof(_Tp))
 577                                   + 1);
 578
 579       this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,
 580                                            size_t(__num_nodes + 2));
 581       this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
 582
 583       // For "small" maps (needing less than _M_map_size nodes), allocation
 584       // starts in the middle elements and grows outwards.  So nstart may be
 585       // the beginning of _M_map, but for small maps it may be as far in as
 586       // _M_map+3.
 587
 588       _Tp** __nstart = (this->_M_impl._M_map
 589                         + (this->_M_impl._M_map_size - __num_nodes) / 2);
 590       _Tp** __nfinish = __nstart + __num_nodes;
 591
 592       __try
 593         { _M_create_nodes(__nstart, __nfinish); }
 594       __catch(...)
 595         {
 596           _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
 597           this->_M_impl._M_map = 0;
 598           this->_M_impl._M_map_size = 0;
 599           __throw_exception_again;
 600         }
 601
 602       this->_M_impl._M_start._M_set_node(__nstart);
 603       this->_M_impl._M_finish._M_set_node(__nfinish - 1);
 604       this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
 605       this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
 606                                         + __num_elements
 607                                         % __deque_buf_size(sizeof(_Tp)));
 608     }
 609
 610   template<typename _Tp, typename _Alloc>
 611     void
 612     _Deque_base<_Tp, _Alloc>::
 613     _M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
 614     {
 615       _Tp** __cur;
 616       __try
 617         {
 618           for (__cur = __nstart; __cur < __nfinish; ++__cur)
 619             *__cur = this->_M_allocate_node();
 620         }
 621       __catch(...)
 622         {
 623           _M_destroy_nodes(__nstart, __cur);
 624           __throw_exception_again;
 625         }
 626     }
 627
 628   template<typename _Tp, typename _Alloc>
 629     void
 630     _Deque_base<_Tp, _Alloc>::
 631     _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish)
 632     {
 633       for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
 634         _M_deallocate_node(*__n);
 635     }
 636
 637   /**
 638    *  @brief  A standard container using fixed-size memory allocation and
 639    *  constant-time manipulation of elements at either end.
 640    *
 641    *  @ingroup sequences
 642    *
 643    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
 644    *  <a href="tables.html#66">reversible container</a>, and a
 645    *  <a href="tables.html#67">sequence</a>, including the
 646    *  <a href="tables.html#68">optional sequence requirements</a>.
 647    *
 648    *  In previous HP/SGI versions of deque, there was an extra template
 649    *  parameter so users could control the node size.  This extension turned
 650    *  out to violate the C++ standard (it can be detected using template
 651    *  template parameters), and it was removed.
 652    *
 653    *  Here's how a deque<Tp> manages memory.  Each deque has 4 members:
 654    *
 655    *  - Tp**        _M_map
 656    *  - size_t      _M_map_size
 657    *  - iterator    _M_start, _M_finish
 658    *
 659    *  map_size is at least 8.  %map is an array of map_size
 660    *  pointers-to-@anodes.  (The name %map has nothing to do with the
 661    *  std::map class, and @b nodes should not be confused with
 662    *  std::list's usage of @a node.)
 663    *
 664    *  A @a node has no specific type name as such, but it is referred
 665    *  to as @a node in this file.  It is a simple array-of-Tp.  If Tp
 666    *  is very large, there will be one Tp element per node (i.e., an
 667    *  @a array of one).  For non-huge Tp's, node size is inversely
 668    *  related to Tp size: the larger the Tp, the fewer Tp's will fit
 669    *  in a node.  The goal here is to keep the total size of a node
 670    *  relatively small and constant over different Tp's, to improve
 671    *  allocator efficiency.
 672    *
 673    *  Not every pointer in the %map array will point to a node.  If
 674    *  the initial number of elements in the deque is small, the
 675    *  /middle/ %map pointers will be valid, and the ones at the edges
 676    *  will be unused.  This same situation will arise as the %map
 677    *  grows: available %map pointers, if any, will be on the ends.  As
 678    *  new nodes are created, only a subset of the %map's pointers need
 679    *  to be copied @a outward.
 680    *
 681    *  Class invariants:
 682    * - For any nonsingular iterator i:
 683    *    - i.node points to a member of the %map array.  (Yes, you read that
 684    *      correctly:  i.node does not actually point to a node.)  The member of
 685    *      the %map array is what actually points to the node.
 686    *    - i.first == *(i.node)    (This points to the node (first Tp element).)
 687    *    - i.last  == i.first + node_size
 688    *    - i.cur is a pointer in the range [i.first, i.last).  NOTE:
 689    *      the implication of this is that i.cur is always a dereferenceable
 690    *      pointer, even if i is a past-the-end iterator.
 691    * - Start and Finish are always nonsingular iterators.  NOTE: this
 692    * means that an empty deque must have one node, a deque with <N
 693    * elements (where N is the node buffer size) must have one node, a
 694    * deque with N through (2N-1) elements must have two nodes, etc.
 695    * - For every node other than start.node and finish.node, every
 696    * element in the node is an initialized object.  If start.node ==
 697    * finish.node, then [start.cur, finish.cur) are initialized
 698    * objects, and the elements outside that range are uninitialized
 699    * storage.  Otherwise, [start.cur, start.last) and [finish.first,
 700    * finish.cur) are initialized objects, and [start.first, start.cur)
 701    * and [finish.cur, finish.last) are uninitialized storage.
 702    * - [%map, %map + map_size) is a valid, non-empty range.
 703    * - [start.node, finish.node] is a valid range contained within
 704    *   [%map, %map + map_size).
 705    * - A pointer in the range [%map, %map + map_size) points to an allocated
 706    *   node if and only if the pointer is in the range
 707    *   [start.node, finish.node].
 708    *
 709    *  Here's the magic:  nothing in deque is @b aware of the discontiguous
 710    *  storage!
 711    *
 712    *  The memory setup and layout occurs in the parent, _Base, and the iterator
 713    *  class is entirely responsible for @a leaping from one node to the next.
 714    *  All the implementation routines for deque itself work only through the
 715    *  start and finish iterators.  This keeps the routines simple and sane,
 716    *  and we can use other standard algorithms as well.
 717   */
 718   template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
 719     class deque : protected _Deque_base<_Tp, _Alloc>
 720     {
 721       // concept requirements
 722       typedef typename _Alloc::value_type        _Alloc_value_type;
 723       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
 724       __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
 725
 726       typedef _Deque_base<_Tp, _Alloc>           _Base;
 727       typedef typename _Base::_Tp_alloc_type     _Tp_alloc_type;
 728
 729     public:
 730       typedef _Tp                                        value_type;
 731       typedef typename _Tp_alloc_type::pointer           pointer;
 732       typedef typename _Tp_alloc_type::const_pointer     const_pointer;
 733       typedef typename _Tp_alloc_type::reference         reference;
 734       typedef typename _Tp_alloc_type::const_reference   const_reference;
 735       typedef typename _Base::iterator                   iterator;
 736       typedef typename _Base::const_iterator             const_iterator;
 737       typedef std::reverse_iterator<const_iterator>      const_reverse_iterator;
 738       typedef std::reverse_iterator<iterator>            reverse_iterator;
 739       typedef size_t                             size_type;
 740       typedef ptrdiff_t                          difference_type;
 741       typedef _Alloc                             allocator_type;
 742
 743     protected:
 744       typedef pointer*                           _Map_pointer;
 745
 746       static size_t _S_buffer_size()
 747       { return __deque_buf_size(sizeof(_Tp)); }
 748
 749       // Functions controlling memory layout, and nothing else.
 750       using _Base::_M_initialize_map;
 751       using _Base::_M_create_nodes;
 752       using _Base::_M_destroy_nodes;
 753       using _Base::_M_allocate_node;
 754       using _Base::_M_deallocate_node;
 755       using _Base::_M_allocate_map;
 756       using _Base::_M_deallocate_map;
 757       using _Base::_M_get_Tp_allocator;
 758
 759       /**
 760        *  A total of four data members accumulated down the hierarchy.
 761        *  May be accessed via _M_impl.*
 762        */
 763       using _Base::_M_impl;
 764
 765     public:
 766       // [23.2.1.1] construct/copy/destroy
 767       // (assign() and get_allocator() are also listed in this section)
 768       /**
 769        *  @brief  Default constructor creates no elements.
 770        */
 771       deque()
 772       : _Base() { }
 773
 774       /**
 775        *  @brief  Creates a %deque with no elements.
 776        *  @param  a  An allocator object.
 777        */
 778       explicit
 779       deque(const allocator_type& __a)
 780       : _Base(__a, 0) { }
 781
 782 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 783       /**
 784        *  @brief  Creates a %deque with default constructed elements.
 785        *  @param  n  The number of elements to initially create.
 786        *
 787        *  This constructor fills the %deque with @a n default
 788        *  constructed elements.
 789        */
 790       explicit
 791       deque(size_type __n)
 792       : _Base(__n)
 793       { _M_default_initialize(); }
 794
 795       /**
 796        *  @brief  Creates a %deque with copies of an exemplar element.
 797        *  @param  n  The number of elements to initially create.
 798        *  @param  value  An element to copy.
 799        *  @param  a  An allocator.
 800        *
 801        *  This constructor fills the %deque with @a n copies of @a value.
 802        */
 803       deque(size_type __n, const value_type& __value,
 804             const allocator_type& __a = allocator_type())
 805       : _Base(__a, __n)
 806       { _M_fill_initialize(__value); }
 807 #else
 808       /**
 809        *  @brief  Creates a %deque with copies of an exemplar element.
 810        *  @param  n  The number of elements to initially create.
 811        *  @param  value  An element to copy.
 812        *  @param  a  An allocator.
 813        *
 814        *  This constructor fills the %deque with @a n copies of @a value.
 815        */
 816       explicit
 817       deque(size_type __n, const value_type& __value = value_type(),
 818             const allocator_type& __a = allocator_type())
 819       : _Base(__a, __n)
 820       { _M_fill_initialize(__value); }
 821 #endif
 822
 823       /**
 824        *  @brief  %Deque copy constructor.
 825        *  @param  x  A %deque of identical element and allocator types.
 826        *
 827        *  The newly-created %deque uses a copy of the allocation object used
 828        *  by @a x.
 829        */
 830       deque(const deque& __x)
 831       : _Base(__x._M_get_Tp_allocator(), __x.size())
 832       { std::__uninitialized_copy_a(__x.begin(), __x.end(),
 833                                     this->_M_impl._M_start,
 834                                     _M_get_Tp_allocator()); }
 835
 836 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 837       /**
 838        *  @brief  %Deque move constructor.
 839        *  @param  x  A %deque of identical element and allocator types.
 840        *
 841        *  The newly-created %deque contains the exact contents of @a x.
 842        *  The contents of @a x are a valid, but unspecified %deque.
 843        */
 844       deque(deque&& __x)
 845       : _Base(std::move(__x)) { }
 846
 847       /**
 848        *  @brief  Builds a %deque from an initializer list.
 849        *  @param  l  An initializer_list.
 850        *  @param  a  An allocator object.
 851        *
 852        *  Create a %deque consisting of copies of the elements in the
 853        *  initializer_list @a l.
 854        *
 855        *  This will call the element type's copy constructor N times
 856        *  (where N is l.size()) and do no memory reallocation.
 857        */
 858       deque(initializer_list<value_type> __l,
 859             const allocator_type& __a = allocator_type())
 860       : _Base(__a)
 861       {
 862         _M_range_initialize(__l.begin(), __l.end(),
 863                             random_access_iterator_tag());
 864       }
 865 #endif
 866
 867       /**
 868        *  @brief  Builds a %deque from a range.
 869        *  @param  first  An input iterator.
 870        *  @param  last  An input iterator.
 871        *  @param  a  An allocator object.
 872        *
 873        *  Create a %deque consisting of copies of the elements from [first,
 874        *  last).
 875        *
 876        *  If the iterators are forward, bidirectional, or random-access, then
 877        *  this will call the elements' copy constructor N times (where N is
 878        *  distance(first,last)) and do no memory reallocation.  But if only
 879        *  input iterators are used, then this will do at most 2N calls to the
 880        *  copy constructor, and logN memory reallocations.
 881        */
 882       template<typename _InputIterator>
 883         deque(_InputIterator __first, _InputIterator __last,
 884               const allocator_type& __a = allocator_type())
 885         : _Base(__a)
 886         {
 887           // Check whether it's an integral type.  If so, it's not an iterator.
 888           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 889           _M_initialize_dispatch(__first, __last, _Integral());
 890         }
 891
 892       /**
 893        *  The dtor only erases the elements, and note that if the elements
 894        *  themselves are pointers, the pointed-to memory is not touched in any
 895        *  way.  Managing the pointer is the user's responsibility.
 896        */
 897       ~deque()
 898       { _M_destroy_data(begin(), end(), _M_get_Tp_allocator()); }
 899
 900       /**
 901        *  @brief  %Deque assignment operator.
 902        *  @param  x  A %deque of identical element and allocator types.
 903        *
 904        *  All the elements of @a x are copied, but unlike the copy constructor,
 905        *  the allocator object is not copied.
 906        */
 907       deque&
 908       operator=(const deque& __x);
 909
 910 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 911       /**
 912        *  @brief  %Deque move assignment operator.
 913        *  @param  x  A %deque of identical element and allocator types.
 914        *
 915        *  The contents of @a x are moved into this deque (without copying).
 916        *  @a x is a valid, but unspecified %deque.
 917        */
 918       deque&
 919       operator=(deque&& __x)
 920       {
 921         // NB: DR 1204.
 922         // NB: DR 675.
 923         this->clear();
 924         this->swap(__x);
 925         return *this;
 926       }
 927
 928       /**
 929        *  @brief  Assigns an initializer list to a %deque.
 930        *  @param  l  An initializer_list.
 931        *
 932        *  This function fills a %deque with copies of the elements in the
 933        *  initializer_list @a l.
 934        *
 935        *  Note that the assignment completely changes the %deque and that the
 936        *  resulting %deque's size is the same as the number of elements
 937        *  assigned.  Old data may be lost.
 938        */
 939       deque&
 940       operator=(initializer_list<value_type> __l)
 941       {
 942         this->assign(__l.begin(), __l.end());
 943         return *this;
 944       }
 945 #endif
 946
 947       /**
 948        *  @brief  Assigns a given value to a %deque.
 949        *  @param  n  Number of elements to be assigned.
 950        *  @param  val  Value to be assigned.
 951        *
 952        *  This function fills a %deque with @a n copies of the given
 953        *  value.  Note that the assignment completely changes the
 954        *  %deque and that the resulting %deque's size is the same as
 955        *  the number of elements assigned.  Old data may be lost.
 956        */
 957       void
 958       assign(size_type __n, const value_type& __val)
 959       { _M_fill_assign(__n, __val); }
 960
 961       /**
 962        *  @brief  Assigns a range to a %deque.
 963        *  @param  first  An input iterator.
 964        *  @param  last   An input iterator.
 965        *
 966        *  This function fills a %deque with copies of the elements in the
 967        *  range [first,last).
 968        *
 969        *  Note that the assignment completely changes the %deque and that the
 970        *  resulting %deque's size is the same as the number of elements
 971        *  assigned.  Old data may be lost.
 972        */
 973       template<typename _InputIterator>
 974         void
 975         assign(_InputIterator __first, _InputIterator __last)
 976         {
 977           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 978           _M_assign_dispatch(__first, __last, _Integral());
 979         }
 980
 981 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 982       /**
 983        *  @brief  Assigns an initializer list to a %deque.
 984        *  @param  l  An initializer_list.
 985        *
 986        *  This function fills a %deque with copies of the elements in the
 987        *  initializer_list @a l.
 988        *
 989        *  Note that the assignment completely changes the %deque and that the
 990        *  resulting %deque's size is the same as the number of elements
 991        *  assigned.  Old data may be lost.
 992        */
 993       void
 994       assign(initializer_list<value_type> __l)
 995       { this->assign(__l.begin(), __l.end()); }
 996 #endif
 997
 998       /// Get a copy of the memory allocation object.
 999       allocator_type
1000       get_allocator() const
1001       { return _Base::get_allocator(); }
1002
1003       // iterators
1004       /**
1005        *  Returns a read/write iterator that points to the first element in the
1006        *  %deque.  Iteration is done in ordinary element order.
1007        */
1008       iterator
1009       begin()
1010       { return this->_M_impl._M_start; }
1011
1012       /**
1013        *  Returns a read-only (constant) iterator that points to the first
1014        *  element in the %deque.  Iteration is done in ordinary element order.
1015        */
1016       const_iterator
1017       begin() const
1018       { return this->_M_impl._M_start; }
1019
1020       /**
1021        *  Returns a read/write iterator that points one past the last
1022        *  element in the %deque.  Iteration is done in ordinary
1023        *  element order.
1024        */
1025       iterator
1026       end()
1027       { return this->_M_impl._M_finish; }
1028
1029       /**
1030        *  Returns a read-only (constant) iterator that points one past
1031        *  the last element in the %deque.  Iteration is done in
1032        *  ordinary element order.
1033        */
1034       const_iterator
1035       end() const
1036       { return this->_M_impl._M_finish; }
1037
1038       /**
1039        *  Returns a read/write reverse iterator that points to the
1040        *  last element in the %deque.  Iteration is done in reverse
1041        *  element order.
1042        */
1043       reverse_iterator
1044       rbegin()
1045       { return reverse_iterator(this->_M_impl._M_finish); }
1046
1047       /**
1048        *  Returns a read-only (constant) reverse iterator that points
1049        *  to the last element in the %deque.  Iteration is done in
1050        *  reverse element order.
1051        */
1052       const_reverse_iterator
1053       rbegin() const
1054       { return const_reverse_iterator(this->_M_impl._M_finish); }
1055
1056       /**
1057        *  Returns a read/write reverse iterator that points to one
1058        *  before the first element in the %deque.  Iteration is done
1059        *  in reverse element order.
1060        */
1061       reverse_iterator
1062       rend()
1063       { return reverse_iterator(this->_M_impl._M_start); }
1064
1065       /**
1066        *  Returns a read-only (constant) reverse iterator that points
1067        *  to one before the first element in the %deque.  Iteration is
1068        *  done in reverse element order.
1069        */
1070       const_reverse_iterator
1071       rend() const
1072       { return const_reverse_iterator(this->_M_impl._M_start); }
1073
1074 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1075       /**
1076        *  Returns a read-only (constant) iterator that points to the first
1077        *  element in the %deque.  Iteration is done in ordinary element order.
1078        */
1079       const_iterator
1080       cbegin() const
1081       { return this->_M_impl._M_start; }
1082
1083       /**
1084        *  Returns a read-only (constant) iterator that points one past
1085        *  the last element in the %deque.  Iteration is done in
1086        *  ordinary element order.
1087        */
1088       const_iterator
1089       cend() const
1090       { return this->_M_impl._M_finish; }
1091
1092       /**
1093        *  Returns a read-only (constant) reverse iterator that points
1094        *  to the last element in the %deque.  Iteration is done in
1095        *  reverse element order.
1096        */
1097       const_reverse_iterator
1098       crbegin() const
1099       { return const_reverse_iterator(this->_M_impl._M_finish); }
1100
1101       /**
1102        *  Returns a read-only (constant) reverse iterator that points
1103        *  to one before the first element in the %deque.  Iteration is
1104        *  done in reverse element order.
1105        */
1106       const_reverse_iterator
1107       crend() const
1108       { return const_reverse_iterator(this->_M_impl._M_start); }
1109 #endif
1110
1111       // [23.2.1.2] capacity
1112       /**  Returns the number of elements in the %deque.  */
1113       size_type
1114       size() const
1115       { return this->_M_impl._M_finish - this->_M_impl._M_start; }
1116
1117       /**  Returns the size() of the largest possible %deque.  */
1118       size_type
1119       max_size() const
1120       { return _M_get_Tp_allocator().max_size(); }
1121
1122 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1123       /**
1124        *  @brief  Resizes the %deque to the specified number of elements.
1125        *  @param  new_size  Number of elements the %deque should contain.
1126        *
1127        *  This function will %resize the %deque to the specified
1128        *  number of elements.  If the number is smaller than the
1129        *  %deque's current size the %deque is truncated, otherwise
1130        *  default constructed elements are appended.
1131        */
1132       void
1133       resize(size_type __new_size)
1134       {
1135         const size_type __len = size();
1136         if (__new_size > __len)
1137           _M_default_append(__new_size - __len);
1138         else if (__new_size < __len)
1139           _M_erase_at_end(this->_M_impl._M_start
1140                           + difference_type(__new_size));
1141       }
1142
1143       /**
1144        *  @brief  Resizes the %deque to the specified number of elements.
1145        *  @param  new_size  Number of elements the %deque should contain.
1146        *  @param  x  Data with which new elements should be populated.
1147        *
1148        *  This function will %resize the %deque to the specified
1149        *  number of elements.  If the number is smaller than the
1150        *  %deque's current size the %deque is truncated, otherwise the
1151        *  %deque is extended and new elements are populated with given
1152        *  data.
1153        */
1154       void
1155       resize(size_type __new_size, const value_type& __x)
1156       {
1157         const size_type __len = size();
1158         if (__new_size > __len)
1159           insert(this->_M_impl._M_finish, __new_size - __len, __x);
1160         else if (__new_size < __len)
1161           _M_erase_at_end(this->_M_impl._M_start
1162                           + difference_type(__new_size));
1163       }
1164 #else
1165       /**
1166        *  @brief  Resizes the %deque to the specified number of elements.
1167        *  @param  new_size  Number of elements the %deque should contain.
1168        *  @param  x  Data with which new elements should be populated.
1169        *
1170        *  This function will %resize the %deque to the specified
1171        *  number of elements.  If the number is smaller than the
1172        *  %deque's current size the %deque is truncated, otherwise the
1173        *  %deque is extended and new elements are populated with given
1174        *  data.
1175        */
1176       void
1177       resize(size_type __new_size, value_type __x = value_type())
1178       {
1179         const size_type __len = size();
1180         if (__new_size > __len)
1181           insert(this->_M_impl._M_finish, __new_size - __len, __x);
1182         else if (__new_size < __len)
1183           _M_erase_at_end(this->_M_impl._M_start
1184                           + difference_type(__new_size));
1185       }
1186 #endif
1187
1188 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1189       /**  A non-binding request to reduce memory use.  */
1190       void
1191       shrink_to_fit()
1192       { std::__shrink_to_fit<deque>::_S_do_it(*this); }
1193 #endif
1194
1195       /**
1196        *  Returns true if the %deque is empty.  (Thus begin() would
1197        *  equal end().)
1198        */
1199       bool
1200       empty() const
1201       { return this->_M_impl._M_finish == this->_M_impl._M_start; }
1202
1203       // element access
1204       /**
1205        *  @brief Subscript access to the data contained in the %deque.
1206        *  @param n The index of the element for which data should be
1207        *  accessed.
1208        *  @return  Read/write reference to data.
1209        *
1210        *  This operator allows for easy, array-style, data access.
1211        *  Note that data access with this operator is unchecked and
1212        *  out_of_range lookups are not defined. (For checked lookups
1213        *  see at().)
1214        */
1215       reference
1216       operator[](size_type __n)
1217       { return this->_M_impl._M_start[difference_type(__n)]; }
1218
1219       /**
1220        *  @brief Subscript access to the data contained in the %deque.
1221        *  @param n The index of the element for which data should be
1222        *  accessed.
1223        *  @return  Read-only (constant) reference to data.
1224        *
1225        *  This operator allows for easy, array-style, data access.
1226        *  Note that data access with this operator is unchecked and
1227        *  out_of_range lookups are not defined. (For checked lookups
1228        *  see at().)
1229        */
1230       const_reference
1231       operator[](size_type __n) const
1232       { return this->_M_impl._M_start[difference_type(__n)]; }
1233
1234     protected:
1235       /// Safety check used only from at().
1236       void
1237       _M_range_check(size_type __n) const
1238       {
1239         if (__n >= this->size())
1240           __throw_out_of_range(__N("deque::_M_range_check"));
1241       }
1242
1243     public:
1244       /**
1245        *  @brief  Provides access to the data contained in the %deque.
1246        *  @param n The index of the element for which data should be
1247        *  accessed.
1248        *  @return  Read/write reference to data.
1249        *  @throw  std::out_of_range  If @a n is an invalid index.
1250        *
1251        *  This function provides for safer data access.  The parameter
1252        *  is first checked that it is in the range of the deque.  The
1253        *  function throws out_of_range if the check fails.
1254        */
1255       reference
1256       at(size_type __n)
1257       {
1258         _M_range_check(__n);
1259         return (*this)[__n];
1260       }
1261
1262       /**
1263        *  @brief  Provides access to the data contained in the %deque.
1264        *  @param n The index of the element for which data should be
1265        *  accessed.
1266        *  @return  Read-only (constant) reference to data.
1267        *  @throw  std::out_of_range  If @a n is an invalid index.
1268        *
1269        *  This function provides for safer data access.  The parameter is first
1270        *  checked that it is in the range of the deque.  The function throws
1271        *  out_of_range if the check fails.
1272        */
1273       const_reference
1274       at(size_type __n) const
1275       {
1276         _M_range_check(__n);
1277         return (*this)[__n];
1278       }
1279
1280       /**
1281        *  Returns a read/write reference to the data at the first
1282        *  element of the %deque.
1283        */
1284       reference
1285       front()
1286       { return *begin(); }
1287
1288       /**
1289        *  Returns a read-only (constant) reference to the data at the first
1290        *  element of the %deque.
1291        */
1292       const_reference
1293       front() const
1294       { return *begin(); }
1295
1296       /**
1297        *  Returns a read/write reference to the data at the last element of the
1298        *  %deque.
1299        */
1300       reference
1301       back()
1302       {
1303         iterator __tmp = end();
1304         --__tmp;
1305         return *__tmp;
1306       }
1307
1308       /**
1309        *  Returns a read-only (constant) reference to the data at the last
1310        *  element of the %deque.
1311        */
1312       const_reference
1313       back() const
1314       {
1315         const_iterator __tmp = end();
1316         --__tmp;
1317         return *__tmp;
1318       }
1319
1320       // [23.2.1.2] modifiers
1321       /**
1322        *  @brief  Add data to the front of the %deque.
1323        *  @param  x  Data to be added.
1324        *
1325        *  This is a typical stack operation.  The function creates an
1326        *  element at the front of the %deque and assigns the given
1327        *  data to it.  Due to the nature of a %deque this operation
1328        *  can be done in constant time.
1329        */
1330       void
1331       push_front(const value_type& __x)
1332       {
1333         if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
1334           {
1335             this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1, __x);
1336             --this->_M_impl._M_start._M_cur;
1337           }
1338         else
1339           _M_push_front_aux(__x);
1340       }
1341
1342 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1343       void
1344       push_front(value_type&& __x)
1345       { emplace_front(std::move(__x)); }
1346
1347       template<typename... _Args>
1348         void
1349         emplace_front(_Args&&... __args);
1350 #endif
1351
1352       /**
1353        *  @brief  Add data to the end of the %deque.
1354        *  @param  x  Data to be added.
1355        *
1356        *  This is a typical stack operation.  The function creates an
1357        *  element at the end of the %deque and assigns the given data
1358        *  to it.  Due to the nature of a %deque this operation can be
1359        *  done in constant time.
1360        */
1361       void
1362       push_back(const value_type& __x)
1363       {
1364         if (this->_M_impl._M_finish._M_cur
1365             != this->_M_impl._M_finish._M_last - 1)
1366           {
1367             this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __x);
1368             ++this->_M_impl._M_finish._M_cur;
1369           }
1370         else
1371           _M_push_back_aux(__x);
1372       }
1373
1374 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1375       void
1376       push_back(value_type&& __x)
1377       { emplace_back(std::move(__x)); }
1378
1379       template<typename... _Args>
1380         void
1381         emplace_back(_Args&&... __args);
1382 #endif
1383
1384       /**
1385        *  @brief  Removes first element.
1386        *
1387        *  This is a typical stack operation.  It shrinks the %deque by one.
1388        *
1389        *  Note that no data is returned, and if the first element's data is
1390        *  needed, it should be retrieved before pop_front() is called.
1391        */
1392       void
1393       pop_front()
1394       {
1395         if (this->_M_impl._M_start._M_cur
1396             != this->_M_impl._M_start._M_last - 1)
1397           {
1398             this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
1399             ++this->_M_impl._M_start._M_cur;
1400           }
1401         else
1402           _M_pop_front_aux();
1403       }
1404
1405       /**
1406        *  @brief  Removes last element.
1407        *
1408        *  This is a typical stack operation.  It shrinks the %deque by one.
1409        *
1410        *  Note that no data is returned, and if the last element's data is
1411        *  needed, it should be retrieved before pop_back() is called.
1412        */
1413       void
1414       pop_back()
1415       {
1416         if (this->_M_impl._M_finish._M_cur
1417             != this->_M_impl._M_finish._M_first)
1418           {
1419             --this->_M_impl._M_finish._M_cur;
1420             this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
1421           }
1422         else
1423           _M_pop_back_aux();
1424       }
1425
1426 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1427       /**
1428        *  @brief  Inserts an object in %deque before specified iterator.
1429        *  @param  position  An iterator into the %deque.
1430        *  @param  args  Arguments.
1431        *  @return  An iterator that points to the inserted data.
1432        *
1433        *  This function will insert an object of type T constructed
1434        *  with T(std::forward<Args>(args)...) before the specified location.
1435        */
1436       template<typename... _Args>
1437         iterator
1438         emplace(iterator __position, _Args&&... __args);
1439 #endif
1440
1441       /**
1442        *  @brief  Inserts given value into %deque before specified iterator.
1443        *  @param  position  An iterator into the %deque.
1444        *  @param  x  Data to be inserted.
1445        *  @return  An iterator that points to the inserted data.
1446        *
1447        *  This function will insert a copy of the given value before the
1448        *  specified location.
1449        */
1450       iterator
1451       insert(iterator __position, const value_type& __x);
1452
1453 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1454       /**
1455        *  @brief  Inserts given rvalue into %deque before specified iterator.
1456        *  @param  position  An iterator into the %deque.
1457        *  @param  x  Data to be inserted.
1458        *  @return  An iterator that points to the inserted data.
1459        *
1460        *  This function will insert a copy of the given rvalue before the
1461        *  specified location.
1462        */
1463       iterator
1464       insert(iterator __position, value_type&& __x)
1465       { return emplace(__position, std::move(__x)); }
1466
1467       /**
1468        *  @brief  Inserts an initializer list into the %deque.
1469        *  @param  p  An iterator into the %deque.
1470        *  @param  l  An initializer_list.
1471        *
1472        *  This function will insert copies of the data in the
1473        *  initializer_list @a l into the %deque before the location
1474        *  specified by @a p.  This is known as <em>list insert</em>.
1475        */
1476       void
1477       insert(iterator __p, initializer_list<value_type> __l)
1478       { this->insert(__p, __l.begin(), __l.end()); }
1479 #endif
1480
1481       /**
1482        *  @brief  Inserts a number of copies of given data into the %deque.
1483        *  @param  position  An iterator into the %deque.
1484        *  @param  n  Number of elements to be inserted.
1485        *  @param  x  Data to be inserted.
1486        *
1487        *  This function will insert a specified number of copies of the given
1488        *  data before the location specified by @a position.
1489        */
1490       void
1491       insert(iterator __position, size_type __n, const value_type& __x)
1492       { _M_fill_insert(__position, __n, __x); }
1493
1494       /**
1495        *  @brief  Inserts a range into the %deque.
1496        *  @param  position  An iterator into the %deque.
1497        *  @param  first  An input iterator.
1498        *  @param  last   An input iterator.
1499        *
1500        *  This function will insert copies of the data in the range
1501        *  [first,last) into the %deque before the location specified
1502        *  by @a pos.  This is known as <em>range insert</em>.
1503        */
1504       template<typename _InputIterator>
1505         void
1506         insert(iterator __position, _InputIterator __first,
1507                _InputIterator __last)
1508         {
1509           // Check whether it's an integral type.  If so, it's not an iterator.
1510           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1511           _M_insert_dispatch(__position, __first, __last, _Integral());
1512         }
1513
1514       /**
1515        *  @brief  Remove element at given position.
1516        *  @param  position  Iterator pointing to element to be erased.
1517        *  @return  An iterator pointing to the next element (or end()).
1518        *
1519        *  This function will erase the element at the given position and thus
1520        *  shorten the %deque by one.
1521        *
1522        *  The user is cautioned that
1523        *  this function only erases the element, and that if the element is
1524        *  itself a pointer, the pointed-to memory is not touched in any way.
1525        *  Managing the pointer is the user's responsibility.
1526        */
1527       iterator
1528       erase(iterator __position);
1529
1530       /**
1531        *  @brief  Remove a range of elements.
1532        *  @param  first  Iterator pointing to the first element to be erased.
1533        *  @param  last  Iterator pointing to one past the last element to be
1534        *                erased.
1535        *  @return  An iterator pointing to the element pointed to by @a last
1536        *           prior to erasing (or end()).
1537        *
1538        *  This function will erase the elements in the range [first,last) and
1539        *  shorten the %deque accordingly.
1540        *
1541        *  The user is cautioned that
1542        *  this function only erases the elements, and that if the elements
1543        *  themselves are pointers, the pointed-to memory is not touched in any
1544        *  way.  Managing the pointer is the user's responsibility.
1545        */
1546       iterator
1547       erase(iterator __first, iterator __last);
1548
1549       /**
1550        *  @brief  Swaps data with another %deque.
1551        *  @param  x  A %deque of the same element and allocator types.
1552        *
1553        *  This exchanges the elements between two deques in constant time.
1554        *  (Four pointers, so it should be quite fast.)
1555        *  Note that the global std::swap() function is specialized such that
1556        *  std::swap(d1,d2) will feed to this function.
1557        */
1558       void
1559       swap(deque& __x)
1560       {
1561         std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
1562         std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
1563         std::swap(this->_M_impl._M_map, __x._M_impl._M_map);
1564         std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size);
1565
1566         // _GLIBCXX_RESOLVE_LIB_DEFECTS
1567         // 431. Swapping containers with unequal allocators.
1568         std::__alloc_swap<_Tp_alloc_type>::_S_do_it(_M_get_Tp_allocator(),
1569                                                     __x._M_get_Tp_allocator());
1570       }
1571
1572       /**
1573        *  Erases all the elements.  Note that this function only erases the
1574        *  elements, and that if the elements themselves are pointers, the
1575        *  pointed-to memory is not touched in any way.  Managing the pointer is
1576        *  the user's responsibility.
1577        */
1578       void
1579       clear()
1580       { _M_erase_at_end(begin()); }
1581
1582     protected:
1583       // Internal constructor functions follow.
1584
1585       // called by the range constructor to implement [23.1.1]/9
1586
1587       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1588       // 438. Ambiguity in the "do the right thing" clause
1589       template<typename _Integer>
1590         void
1591         _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1592         {
1593           _M_initialize_map(static_cast<size_type>(__n));
1594           _M_fill_initialize(__x);
1595         }
1596
1597       // called by the range constructor to implement [23.1.1]/9
1598       template<typename _InputIterator>
1599         void
1600         _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1601                                __false_type)
1602         {
1603           typedef typename std::iterator_traits<_InputIterator>::
1604             iterator_category _IterCategory;
1605           _M_range_initialize(__first, __last, _IterCategory());
1606         }
1607
1608       // called by the second initialize_dispatch above
1609       //@{
1610       /**
1611        *  @brief Fills the deque with whatever is in [first,last).
1612        *  @param  first  An input iterator.
1613        *  @param  last  An input iterator.
1614        *  @return   Nothing.
1615        *
1616        *  If the iterators are actually forward iterators (or better), then the
1617        *  memory layout can be done all at once.  Else we move forward using
1618        *  push_back on each value from the iterator.
1619        */
1620       template<typename _InputIterator>
1621         void
1622         _M_range_initialize(_InputIterator __first, _InputIterator __last,
1623                             std::input_iterator_tag);
1624
1625       // called by the second initialize_dispatch above
1626       template<typename _ForwardIterator>
1627         void
1628         _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
1629                             std::forward_iterator_tag);
1630       //@}
1631
1632       /**
1633        *  @brief Fills the %deque with copies of value.
1634        *  @param  value  Initial value.
1635        *  @return   Nothing.
1636        *  @pre _M_start and _M_finish have already been initialized,
1637        *  but none of the %deque's elements have yet been constructed.
1638        *
1639        *  This function is called only when the user provides an explicit size
1640        *  (with or without an explicit exemplar value).
1641        */
1642       void
1643       _M_fill_initialize(const value_type& __value);
1644
1645 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1646       // called by deque(n).
1647       void
1648       _M_default_initialize();
1649 #endif
1650
1651       // Internal assign functions follow.  The *_aux functions do the actual
1652       // assignment work for the range versions.
1653
1654       // called by the range assign to implement [23.1.1]/9
1655
1656       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1657       // 438. Ambiguity in the "do the right thing" clause
1658       template<typename _Integer>
1659         void
1660         _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1661         { _M_fill_assign(__n, __val); }
1662
1663       // called by the range assign to implement [23.1.1]/9
1664       template<typename _InputIterator>
1665         void
1666         _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1667                            __false_type)
1668         {
1669           typedef typename std::iterator_traits<_InputIterator>::
1670             iterator_category _IterCategory;
1671           _M_assign_aux(__first, __last, _IterCategory());
1672         }
1673
1674       // called by the second assign_dispatch above
1675       template<typename _InputIterator>
1676         void
1677         _M_assign_aux(_InputIterator __first, _InputIterator __last,
1678                       std::input_iterator_tag);
1679
1680       // called by the second assign_dispatch above
1681       template<typename _ForwardIterator>
1682         void
1683         _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1684                       std::forward_iterator_tag)
1685         {
1686           const size_type __len = std::distance(__first, __last);
1687           if (__len > size())
1688             {
1689               _ForwardIterator __mid = __first;
1690               std::advance(__mid, size());
1691               std::copy(__first, __mid, begin());
1692               insert(end(), __mid, __last);
1693             }
1694           else
1695             _M_erase_at_end(std::copy(__first, __last, begin()));
1696         }
1697
1698       // Called by assign(n,t), and the range assign when it turns out
1699       // to be the same thing.
1700       void
1701       _M_fill_assign(size_type __n, const value_type& __val)
1702       {
1703         if (__n > size())
1704           {
1705             std::fill(begin(), end(), __val);
1706             insert(end(), __n - size(), __val);
1707           }
1708         else
1709           {
1710             _M_erase_at_end(begin() + difference_type(__n));
1711             std::fill(begin(), end(), __val);
1712           }
1713       }
1714
1715       //@{
1716       /// Helper functions for push_* and pop_*.
1717 #ifndef __GXX_EXPERIMENTAL_CXX0X__
1718       void _M_push_back_aux(const value_type&);
1719
1720       void _M_push_front_aux(const value_type&);
1721 #else
1722       template<typename... _Args>
1723         void _M_push_back_aux(_Args&&... __args);
1724
1725       template<typename... _Args>
1726         void _M_push_front_aux(_Args&&... __args);
1727 #endif
1728
1729       void _M_pop_back_aux();
1730
1731       void _M_pop_front_aux();
1732       //@}
1733
1734       // Internal insert functions follow.  The *_aux functions do the actual
1735       // insertion work when all shortcuts fail.
1736
1737       // called by the range insert to implement [23.1.1]/9
1738
1739       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1740       // 438. Ambiguity in the "do the right thing" clause
1741       template<typename _Integer>
1742         void
1743         _M_insert_dispatch(iterator __pos,
1744                            _Integer __n, _Integer __x, __true_type)
1745         { _M_fill_insert(__pos, __n, __x); }
1746
1747       // called by the range insert to implement [23.1.1]/9
1748       template<typename _InputIterator>
1749         void
1750         _M_insert_dispatch(iterator __pos,
1751                            _InputIterator __first, _InputIterator __last,
1752                            __false_type)
1753         {
1754           typedef typename std::iterator_traits<_InputIterator>::
1755             iterator_category _IterCategory;
1756           _M_range_insert_aux(__pos, __first, __last, _IterCategory());
1757         }
1758
1759       // called by the second insert_dispatch above
1760       template<typename _InputIterator>
1761         void
1762         _M_range_insert_aux(iterator __pos, _InputIterator __first,
1763                             _InputIterator __last, std::input_iterator_tag);
1764
1765       // called by the second insert_dispatch above
1766       template<typename _ForwardIterator>
1767         void
1768         _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
1769                             _ForwardIterator __last, std::forward_iterator_tag);
1770
1771       // Called by insert(p,n,x), and the range insert when it turns out to be
1772       // the same thing.  Can use fill functions in optimal situations,
1773       // otherwise passes off to insert_aux(p,n,x).
1774       void
1775       _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
1776
1777       // called by insert(p,x)
1778 #ifndef __GXX_EXPERIMENTAL_CXX0X__
1779       iterator
1780       _M_insert_aux(iterator __pos, const value_type& __x);
1781 #else
1782       template<typename... _Args>
1783         iterator
1784         _M_insert_aux(iterator __pos, _Args&&... __args);
1785 #endif
1786
1787       // called by insert(p,n,x) via fill_insert
1788       void
1789       _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
1790
1791       // called by range_insert_aux for forward iterators
1792       template<typename _ForwardIterator>
1793         void
1794         _M_insert_aux(iterator __pos,
1795                       _ForwardIterator __first, _ForwardIterator __last,
1796                       size_type __n);
1797
1798
1799       // Internal erase functions follow.
1800
1801       void
1802       _M_destroy_data_aux(iterator __first, iterator __last);
1803
1804       // Called by ~deque().
1805       // NB: Doesn't deallocate the nodes.
1806       template<typename _Alloc1>
1807         void
1808         _M_destroy_data(iterator __first, iterator __last, const _Alloc1&)
1809         { _M_destroy_data_aux(__first, __last); }
1810
1811       void
1812       _M_destroy_data(iterator __first, iterator __last,
1813                       const std::allocator<_Tp>&)
1814       {
1815         if (!__has_trivial_destructor(value_type))
1816           _M_destroy_data_aux(__first, __last);
1817       }
1818
1819       // Called by erase(q1, q2).
1820       void
1821       _M_erase_at_begin(iterator __pos)
1822       {
1823         _M_destroy_data(begin(), __pos, _M_get_Tp_allocator());
1824         _M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node);
1825         this->_M_impl._M_start = __pos;
1826       }
1827
1828       // Called by erase(q1, q2), resize(), clear(), _M_assign_aux,
1829       // _M_fill_assign, operator=.
1830       void
1831       _M_erase_at_end(iterator __pos)
1832       {
1833         _M_destroy_data(__pos, end(), _M_get_Tp_allocator());
1834         _M_destroy_nodes(__pos._M_node + 1,
1835                          this->_M_impl._M_finish._M_node + 1);
1836         this->_M_impl._M_finish = __pos;
1837       }
1838
1839 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1840       // Called by resize(sz).
1841       void
1842       _M_default_append(size_type __n);
1843 #endif
1844
1845       //@{
1846       /// Memory-handling helpers for the previous internal insert functions.
1847       iterator
1848       _M_reserve_elements_at_front(size_type __n)
1849       {
1850         const size_type __vacancies = this->_M_impl._M_start._M_cur
1851                                       - this->_M_impl._M_start._M_first;
1852         if (__n > __vacancies)
1853           _M_new_elements_at_front(__n - __vacancies);
1854         return this->_M_impl._M_start - difference_type(__n);
1855       }
1856
1857       iterator
1858       _M_reserve_elements_at_back(size_type __n)
1859       {
1860         const size_type __vacancies = (this->_M_impl._M_finish._M_last
1861                                        - this->_M_impl._M_finish._M_cur) - 1;
1862         if (__n > __vacancies)
1863           _M_new_elements_at_back(__n - __vacancies);
1864         return this->_M_impl._M_finish + difference_type(__n);
1865       }
1866
1867       void
1868       _M_new_elements_at_front(size_type __new_elements);
1869
1870       void
1871       _M_new_elements_at_back(size_type __new_elements);
1872       //@}
1873
1874
1875       //@{
1876       /**
1877        *  @brief Memory-handling helpers for the major %map.
1878        *
1879        *  Makes sure the _M_map has space for new nodes.  Does not
1880        *  actually add the nodes.  Can invalidate _M_map pointers.
1881        *  (And consequently, %deque iterators.)
1882        */
1883       void
1884       _M_reserve_map_at_back(size_type __nodes_to_add = 1)
1885       {
1886         if (__nodes_to_add + 1 > this->_M_impl._M_map_size
1887             - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
1888           _M_reallocate_map(__nodes_to_add, false);
1889       }
1890
1891       void
1892       _M_reserve_map_at_front(size_type __nodes_to_add = 1)
1893       {
1894         if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
1895                                        - this->_M_impl._M_map))
1896           _M_reallocate_map(__nodes_to_add, true);
1897       }
1898
1899       void
1900       _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
1901       //@}
1902     };
1903
1904
1905   /**
1906    *  @brief  Deque equality comparison.
1907    *  @param  x  A %deque.
1908    *  @param  y  A %deque of the same type as @a x.
1909    *  @return  True iff the size and elements of the deques are equal.
1910    *
1911    *  This is an equivalence relation.  It is linear in the size of the
1912    *  deques.  Deques are considered equivalent if their sizes are equal,
1913    *  and if corresponding elements compare equal.
1914   */
1915   template<typename _Tp, typename _Alloc>
1916     inline bool
1917     operator==(const deque<_Tp, _Alloc>& __x,
1918                          const deque<_Tp, _Alloc>& __y)
1919     { return __x.size() == __y.size()
1920              && std::equal(__x.begin(), __x.end(), __y.begin()); }
1921
1922   /**
1923    *  @brief  Deque ordering relation.
1924    *  @param  x  A %deque.
1925    *  @param  y  A %deque of the same type as @a x.
1926    *  @return  True iff @a x is lexicographically less than @a y.
1927    *
1928    *  This is a total ordering relation.  It is linear in the size of the
1929    *  deques.  The elements must be comparable with @c <.
1930    *
1931    *  See std::lexicographical_compare() for how the determination is made.
1932   */
1933   template<typename _Tp, typename _Alloc>
1934     inline bool
1935     operator<(const deque<_Tp, _Alloc>& __x,
1936               const deque<_Tp, _Alloc>& __y)
1937     { return std::lexicographical_compare(__x.begin(), __x.end(),
1938                                           __y.begin(), __y.end()); }
1939
1940   /// Based on operator==
1941   template<typename _Tp, typename _Alloc>
1942     inline bool
1943     operator!=(const deque<_Tp, _Alloc>& __x,
1944                const deque<_Tp, _Alloc>& __y)
1945     { return !(__x == __y); }
1946
1947   /// Based on operator<
1948   template<typename _Tp, typename _Alloc>
1949     inline bool
1950     operator>(const deque<_Tp, _Alloc>& __x,
1951               const deque<_Tp, _Alloc>& __y)
1952     { return __y < __x; }
1953
1954   /// Based on operator<
1955   template<typename _Tp, typename _Alloc>
1956     inline bool
1957     operator<=(const deque<_Tp, _Alloc>& __x,
1958                const deque<_Tp, _Alloc>& __y)
1959     { return !(__y < __x); }
1960
1961   /// Based on operator<
1962   template<typename _Tp, typename _Alloc>
1963     inline bool
1964     operator>=(const deque<_Tp, _Alloc>& __x,
1965                const deque<_Tp, _Alloc>& __y)
1966     { return !(__x < __y); }
1967
1968   /// See std::deque::swap().
1969   template<typename _Tp, typename _Alloc>
1970     inline void
1971     swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y)
1972     { __x.swap(__y); }
1973
1974 #undef _GLIBCXX_DEQUE_BUF_SIZE
1975
1976 _GLIBCXX_END_NAMESPACE_CONTAINER
1977 } // namespace std
1978
1979 #endif /* _STL_DEQUE_H */