Subversion Repositories Kolibri OS

// Deque implementation -*- C++ -*-

// Copyright (C) 2001-2013 Free Software Foundation, Inc.

//

// This file is part of the GNU ISO C++ Library.  This library is free

// software; you can redistribute it and/or modify it under the

// terms of the GNU General Public License as published by the

// Free Software Foundation; either version 3, or (at your option)

// any later version.

// This library is distributed in the hope that it will be useful,

// but WITHOUT ANY WARRANTY; without even the implied warranty of

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional

// permissions described in the GCC Runtime Library Exception, version

// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and

// a copy of the GCC Runtime Library Exception along with this program;

// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see

// .

/*

 *

 * Copyright (c) 1994

 * Hewlett-Packard Company

 *

 * Permission to use, copy, modify, distribute and sell this software

 * and its documentation for any purpose is hereby granted without fee,

 * provided that the above copyright notice appear in all copies and

 * that both that copyright notice and this permission notice appear

 * in supporting documentation.  Hewlett-Packard Company makes no

 * representations about the suitability of this software for any

 * purpose.  It is provided "as is" without express or implied warranty.

 *

 *

 * Copyright (c) 1997

 * Silicon Graphics Computer Systems, Inc.

 *

 * Permission to use, copy, modify, distribute and sell this software

 * and its documentation for any purpose is hereby granted without fee,

 * provided that the above copyright notice appear in all copies and

 * that both that copyright notice and this permission notice appear

 * in supporting documentation.  Silicon Graphics makes no

 * representations about the suitability of this software for any

 * purpose.  It is provided "as is" without express or implied warranty.

 */

/** @file bits/stl_deque.h

 *  This is an internal header file, included by other library headers.

 *  Do not attempt to use it directly. @headername{deque}

 */

#ifndef _STL_DEQUE_H

#define _STL_DEQUE_H 1

#include 

#include 

#include 

#if __cplusplus >= 201103L

#include 

#endif

namespace std _GLIBCXX_VISIBILITY(default)

{

_GLIBCXX_BEGIN_NAMESPACE_CONTAINER

  /**

   *  @brief This function controls the size of memory nodes.

   *  @param  __size  The size of an element.

   *  @return   The number (not byte size) of elements per node.

   *

   *  This function started off as a compiler kludge from SGI, but

   *  seems to be a useful wrapper around a repeated constant

   *  expression.  The @b 512 is tunable (and no other code needs to

   *  change), but no investigation has been done since inheriting the

   *  SGI code.  Touch _GLIBCXX_DEQUE_BUF_SIZE only if you know what

   *  you are doing, however: changing it breaks the binary

   *  compatibility!!

  */

#ifndef _GLIBCXX_DEQUE_BUF_SIZE

#define _GLIBCXX_DEQUE_BUF_SIZE 512

#endif

  inline size_t

  __deque_buf_size(size_t __size)

  { return (__size < _GLIBCXX_DEQUE_BUF_SIZE

	    ? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) : size_t(1)); }

  /**

   *  @brief A deque::iterator.

   *

   *  Quite a bit of intelligence here.  Much of the functionality of

   *  deque is actually passed off to this class.  A deque holds two

   *  of these internally, marking its valid range.  Access to

   *  elements is done as offsets of either of those two, relying on

   *  operator overloading in this class.

   *

   *  All the functions are op overloads except for _M_set_node.

  */

  template

    struct _Deque_iterator

    {

      typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;

      typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;

      static size_t _S_buffer_size()

      { return __deque_buf_size(sizeof(_Tp)); }

      typedef std::random_access_iterator_tag iterator_category;

      typedef _Tp                             value_type;

      typedef _Ptr                            pointer;

      typedef _Ref                            reference;

      typedef size_t                          size_type;

      typedef ptrdiff_t                       difference_type;

      typedef _Tp**                           _Map_pointer;

      typedef _Deque_iterator                 _Self;

      _Tp* _M_cur;

      _Tp* _M_first;

      _Tp* _M_last;

      _Map_pointer _M_node;

      _Deque_iterator(_Tp* __x, _Map_pointer __y)

      : _M_cur(__x), _M_first(*__y),

        _M_last(*__y + _S_buffer_size()), _M_node(__y) { }

      _Deque_iterator()

      : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) { }

      _Deque_iterator(const iterator& __x)

      : _M_cur(__x._M_cur), _M_first(__x._M_first),

        _M_last(__x._M_last), _M_node(__x._M_node) { }

      reference

      operator*() const

      { return *_M_cur; }

      pointer

      operator->() const

      { return _M_cur; }

      _Self&

      operator++()

      {

	++_M_cur;

	if (_M_cur == _M_last)

	  {

	    _M_set_node(_M_node + 1);

	    _M_cur = _M_first;

	  }

	return *this;

      }

      _Self

      operator++(int)

      {

	_Self __tmp = *this;

	++*this;

	return __tmp;

      }

      _Self&

      operator--()

      {

	if (_M_cur == _M_first)

	  {

	    _M_set_node(_M_node - 1);

	    _M_cur = _M_last;

	  }

	--_M_cur;

	return *this;

      }

      _Self

      operator--(int)

      {

	_Self __tmp = *this;

	--*this;

	return __tmp;

      }

      _Self&

      operator+=(difference_type __n)

      {

	const difference_type __offset = __n + (_M_cur - _M_first);

	if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))

	  _M_cur += __n;

	else

	  {

	    const difference_type __node_offset =

	      __offset > 0 ? __offset / difference_type(_S_buffer_size())

	                   : -difference_type((-__offset - 1)

					      / _S_buffer_size()) - 1;

	    _M_set_node(_M_node + __node_offset);

	    _M_cur = _M_first + (__offset - __node_offset

				 * difference_type(_S_buffer_size()));

	  }

	return *this;

      }

      _Self

      operator+(difference_type __n) const

      {

	_Self __tmp = *this;

	return __tmp += __n;

      }

      _Self&

      operator-=(difference_type __n)

      { return *this += -__n; }

      _Self

      operator-(difference_type __n) const

      {

	_Self __tmp = *this;

	return __tmp -= __n;

      }

      reference

      operator[](difference_type __n) const

      { return *(*this + __n); }

      /**

       *  Prepares to traverse new_node.  Sets everything except

       *  _M_cur, which should therefore be set by the caller

       *  immediately afterwards, based on _M_first and _M_last.

       */

      void

      _M_set_node(_Map_pointer __new_node)

      {

	_M_node = __new_node;

	_M_first = *__new_node;

	_M_last = _M_first + difference_type(_S_buffer_size());

      }

    };

  // Note: we also provide overloads whose operands are of the same type in

  // order to avoid ambiguous overload resolution when std::rel_ops operators

  // are in scope (for additional details, see libstdc++/3628)

  template

    inline bool

    operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,

	       const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)

    { return __x._M_cur == __y._M_cur; }

  template

	   typename _RefR, typename _PtrR>

    inline bool

    operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,

	       const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)

    { return __x._M_cur == __y._M_cur; }

  template

    inline bool

    operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,

	       const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)

    { return !(__x == __y); }

  template

	   typename _RefR, typename _PtrR>

    inline bool

    operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,

	       const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)

    { return !(__x == __y); }

  template

    inline bool

    operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,

	      const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)

    { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)

                                          : (__x._M_node < __y._M_node); }

  template

	   typename _RefR, typename _PtrR>

    inline bool

    operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,

	      const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)

    { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)

	                                  : (__x._M_node < __y._M_node); }

  template

    inline bool

    operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,

	      const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)

    { return __y < __x; }

  template

	   typename _RefR, typename _PtrR>

    inline bool

    operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,

	      const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)

    { return __y < __x; }

  template

    inline bool

    operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,

	       const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)

    { return !(__y < __x); }

  template

	   typename _RefR, typename _PtrR>

    inline bool

    operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,

	       const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)

    { return !(__y < __x); }

  template

    inline bool

    operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,

	       const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)

    { return !(__x < __y); }

  template

	   typename _RefR, typename _PtrR>

    inline bool

    operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,

	       const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)

    { return !(__x < __y); }

  // _GLIBCXX_RESOLVE_LIB_DEFECTS

  // According to the resolution of DR179 not only the various comparison

  // operators but also operator- must accept mixed iterator/const_iterator

  // parameters.

  template

    inline typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type

    operator-(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,

	      const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)

    {

      return typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type

	(_Deque_iterator<_Tp, _Ref, _Ptr>::_S_buffer_size())

	* (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)

	+ (__y._M_last - __y._M_cur);

    }

  template

	   typename _RefR, typename _PtrR>

    inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type

    operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,

	      const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)

    {

      return typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type

	(_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size())

	* (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)

	+ (__y._M_last - __y._M_cur);

    }

  template

    inline _Deque_iterator<_Tp, _Ref, _Ptr>

    operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)

    { return __x + __n; }

  template

    void

    fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>&,

	 const _Deque_iterator<_Tp, _Tp&, _Tp*>&, const _Tp&);

  template

    _Deque_iterator<_Tp, _Tp&, _Tp*>

    copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,

	 _Deque_iterator<_Tp, const _Tp&, const _Tp*>,

	 _Deque_iterator<_Tp, _Tp&, _Tp*>);

  template

    inline _Deque_iterator<_Tp, _Tp&, _Tp*>

    copy(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,

	 _Deque_iterator<_Tp, _Tp&, _Tp*> __last,

	 _Deque_iterator<_Tp, _Tp&, _Tp*> __result)

    { return std::copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),

		       _Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),

		       __result); }

  template

    _Deque_iterator<_Tp, _Tp&, _Tp*>

    copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,

		  _Deque_iterator<_Tp, const _Tp&, const _Tp*>,

		  _Deque_iterator<_Tp, _Tp&, _Tp*>);

  template

    inline _Deque_iterator<_Tp, _Tp&, _Tp*>

    copy_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,

		  _Deque_iterator<_Tp, _Tp&, _Tp*> __last,

		  _Deque_iterator<_Tp, _Tp&, _Tp*> __result)

    { return std::copy_backward(_Deque_iterator<_Tp,

				const _Tp&, const _Tp*>(__first),

				_Deque_iterator<_Tp,

				const _Tp&, const _Tp*>(__last),

				__result); }

#if __cplusplus >= 201103L

  template

    _Deque_iterator<_Tp, _Tp&, _Tp*>

    move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,

	 _Deque_iterator<_Tp, const _Tp&, const _Tp*>,

	 _Deque_iterator<_Tp, _Tp&, _Tp*>);

  template

    inline _Deque_iterator<_Tp, _Tp&, _Tp*>

    move(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,

	 _Deque_iterator<_Tp, _Tp&, _Tp*> __last,

	 _Deque_iterator<_Tp, _Tp&, _Tp*> __result)

    { return std::move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),

		       _Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),

		       __result); }

  template

    _Deque_iterator<_Tp, _Tp&, _Tp*>

    move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,

		  _Deque_iterator<_Tp, const _Tp&, const _Tp*>,

		  _Deque_iterator<_Tp, _Tp&, _Tp*>);

  template

    inline _Deque_iterator<_Tp, _Tp&, _Tp*>

    move_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,

		  _Deque_iterator<_Tp, _Tp&, _Tp*> __last,

		  _Deque_iterator<_Tp, _Tp&, _Tp*> __result)

    { return std::move_backward(_Deque_iterator<_Tp,

				const _Tp&, const _Tp*>(__first),

				_Deque_iterator<_Tp,

				const _Tp&, const _Tp*>(__last),

				__result); }

#endif

  /**

   *  Deque base class.  This class provides the unified face for %deque's

   *  allocation.  This class's constructor and destructor allocate and

   *  deallocate (but do not initialize) storage.  This makes %exception

   *  safety easier.

   *

   *  Nothing in this class ever constructs or destroys an actual Tp element.

   *  (Deque handles that itself.)  Only/All memory management is performed

   *  here.

  */

  template

    class _Deque_base

    {

    public:

      typedef _Alloc                  allocator_type;

      allocator_type

      get_allocator() const _GLIBCXX_NOEXCEPT

      { return allocator_type(_M_get_Tp_allocator()); }

      typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;

      typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;

      _Deque_base()

      : _M_impl()

      { _M_initialize_map(0); }

      _Deque_base(size_t __num_elements)

      : _M_impl()

      { _M_initialize_map(__num_elements); }

      _Deque_base(const allocator_type& __a, size_t __num_elements)

      : _M_impl(__a)

      { _M_initialize_map(__num_elements); }

      _Deque_base(const allocator_type& __a)

      : _M_impl(__a)

      { }

#if __cplusplus >= 201103L

      _Deque_base(_Deque_base&& __x)

      : _M_impl(std::move(__x._M_get_Tp_allocator()))

      {

	_M_initialize_map(0);

	if (__x._M_impl._M_map)

	  {

	    std::swap(this->_M_impl._M_start, __x._M_impl._M_start);

	    std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);

	    std::swap(this->_M_impl._M_map, __x._M_impl._M_map);

	    std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size);

	  }

      }

#endif

      ~_Deque_base();

    protected:

      //This struct encapsulates the implementation of the std::deque

      //standard container and at the same time makes use of the EBO

      //for empty allocators.

      typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type;

      typedef typename _Alloc::template rebind<_Tp>::other  _Tp_alloc_type;

      struct _Deque_impl

      : public _Tp_alloc_type

      {

	_Tp** _M_map;

	size_t _M_map_size;

	iterator _M_start;

	iterator _M_finish;

	_Deque_impl()

	: _Tp_alloc_type(), _M_map(0), _M_map_size(0),

	  _M_start(), _M_finish()

	{ }

	_Deque_impl(const _Tp_alloc_type& __a)

	: _Tp_alloc_type(__a), _M_map(0), _M_map_size(0),

	  _M_start(), _M_finish()

	{ }

#if __cplusplus >= 201103L

	_Deque_impl(_Tp_alloc_type&& __a)

	: _Tp_alloc_type(std::move(__a)), _M_map(0), _M_map_size(0),

	  _M_start(), _M_finish()

	{ }

#endif

      };

      _Tp_alloc_type&

      _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT

      { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }

      const _Tp_alloc_type&

      _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT

      { return *static_cast(&this->_M_impl); }

      _Map_alloc_type

      _M_get_map_allocator() const _GLIBCXX_NOEXCEPT

      { return _Map_alloc_type(_M_get_Tp_allocator()); }

      _Tp*

      _M_allocate_node()

      {

	return _M_impl._Tp_alloc_type::allocate(__deque_buf_size(sizeof(_Tp)));

      }

      void

      _M_deallocate_node(_Tp* __p)

      {

	_M_impl._Tp_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp)));

      }

      _Tp**

      _M_allocate_map(size_t __n)

      { return _M_get_map_allocator().allocate(__n); }

      void

      _M_deallocate_map(_Tp** __p, size_t __n)

      { _M_get_map_allocator().deallocate(__p, __n); }

    protected:

      void _M_initialize_map(size_t);

      void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);

      void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);

      enum { _S_initial_map_size = 8 };

      _Deque_impl _M_impl;

    };

  template

    _Deque_base<_Tp, _Alloc>::

    ~_Deque_base()

    {

      if (this->_M_impl._M_map)

	{

	  _M_destroy_nodes(this->_M_impl._M_start._M_node,

			   this->_M_impl._M_finish._M_node + 1);

	  _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);

	}

    }

  /**

   *  @brief Layout storage.

   *  @param  __num_elements  The count of T's for which to allocate space

   *                        at first.

   *  @return   Nothing.

   *

   *  The initial underlying memory layout is a bit complicated...

  */

  template

    void

    _Deque_base<_Tp, _Alloc>::

    _M_initialize_map(size_t __num_elements)

    {

      const size_t __num_nodes = (__num_elements/ __deque_buf_size(sizeof(_Tp))

				  + 1);

      this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,

					   size_t(__num_nodes + 2));

      this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);

      // For "small" maps (needing less than _M_map_size nodes), allocation

      // starts in the middle elements and grows outwards.  So nstart may be

      // the beginning of _M_map, but for small maps it may be as far in as

      // _M_map+3.

      _Tp** __nstart = (this->_M_impl._M_map

			+ (this->_M_impl._M_map_size - __num_nodes) / 2);

      _Tp** __nfinish = __nstart + __num_nodes;

      __try

	{ _M_create_nodes(__nstart, __nfinish); }

      __catch(...)

	{

	  _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);

	  this->_M_impl._M_map = 0;

	  this->_M_impl._M_map_size = 0;

	  __throw_exception_again;

	}

      this->_M_impl._M_start._M_set_node(__nstart);

      this->_M_impl._M_finish._M_set_node(__nfinish - 1);

      this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;

      this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first

					+ __num_elements

					% __deque_buf_size(sizeof(_Tp)));

    }

  template

    void

    _Deque_base<_Tp, _Alloc>::

    _M_create_nodes(_Tp** __nstart, _Tp** __nfinish)

    {

      _Tp** __cur;

      __try

	{

	  for (__cur = __nstart; __cur < __nfinish; ++__cur)

	    *__cur = this->_M_allocate_node();

	}

      __catch(...)

	{

	  _M_destroy_nodes(__nstart, __cur);

	  __throw_exception_again;

	}

    }

  template

    void

    _Deque_base<_Tp, _Alloc>::

    _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish)

    {

      for (_Tp** __n = __nstart; __n < __nfinish; ++__n)

	_M_deallocate_node(*__n);

    }

  /**

   *  @brief  A standard container using fixed-size memory allocation and

   *  constant-time manipulation of elements at either end.

   *

   *  @ingroup sequences

   *

   *  @tparam _Tp  Type of element.

   *  @tparam _Alloc  Allocator type, defaults to allocator<_Tp>.

   *

   *  Meets the requirements of a container, a

   *  reversible container, and a

   *  sequence, including the

   *  optional sequence requirements.

   *

   *  In previous HP/SGI versions of deque, there was an extra template

   *  parameter so users could control the node size.  This extension turned

   *  out to violate the C++ standard (it can be detected using template

   *  template parameters), and it was removed.

   *

   *  Here's how a deque manages memory.  Each deque has 4 members:

   *

   *  - Tp**        _M_map

   *  - size_t      _M_map_size

   *  - iterator    _M_start, _M_finish

   *

   *  map_size is at least 8.  %map is an array of map_size

   *  pointers-to-@a nodes.  (The name %map has nothing to do with the

   *  std::map class, and @b nodes should not be confused with

   *  std::list's usage of @a node.)

   *

   *  A @a node has no specific type name as such, but it is referred

   *  to as @a node in this file.  It is a simple array-of-Tp.  If Tp

   *  is very large, there will be one Tp element per node (i.e., an

   *  @a array of one).  For non-huge Tp's, node size is inversely

   *  related to Tp size: the larger the Tp, the fewer Tp's will fit

   *  in a node.  The goal here is to keep the total size of a node

   *  relatively small and constant over different Tp's, to improve

   *  allocator efficiency.

   *

   *  Not every pointer in the %map array will point to a node.  If

   *  the initial number of elements in the deque is small, the

   *  /middle/ %map pointers will be valid, and the ones at the edges

   *  will be unused.  This same situation will arise as the %map

   *  grows: available %map pointers, if any, will be on the ends.  As

   *  new nodes are created, only a subset of the %map's pointers need

   *  to be copied @a outward.

   *

   *  Class invariants:

   * - For any nonsingular iterator i:

   *    - i.node points to a member of the %map array.  (Yes, you read that

   *      correctly:  i.node does not actually point to a node.)  The member of

   *      the %map array is what actually points to the node.

   *    - i.first == *(i.node)    (This points to the node (first Tp element).)

   *    - i.last  == i.first + node_size

   *    - i.cur is a pointer in the range [i.first, i.last).  NOTE:

   *      the implication of this is that i.cur is always a dereferenceable

   *      pointer, even if i is a past-the-end iterator.

   * - Start and Finish are always nonsingular iterators.  NOTE: this

   * means that an empty deque must have one node, a deque with 

   * elements (where N is the node buffer size) must have one node, a

   * deque with N through (2N-1) elements must have two nodes, etc.

   * - For every node other than start.node and finish.node, every

   * element in the node is an initialized object.  If start.node ==

   * finish.node, then [start.cur, finish.cur) are initialized

   * objects, and the elements outside that range are uninitialized

   * storage.  Otherwise, [start.cur, start.last) and [finish.first,

   * finish.cur) are initialized objects, and [start.first, start.cur)

   * and [finish.cur, finish.last) are uninitialized storage.

   * - [%map, %map + map_size) is a valid, non-empty range.

   * - [start.node, finish.node] is a valid range contained within

   *   [%map, %map + map_size).

   * - A pointer in the range [%map, %map + map_size) points to an allocated

   *   node if and only if the pointer is in the range

   *   [start.node, finish.node].

   *

   *  Here's the magic:  nothing in deque is @b aware of the discontiguous

   *  storage!

   *

   *  The memory setup and layout occurs in the parent, _Base, and the iterator

   *  class is entirely responsible for @a leaping from one node to the next.

   *  All the implementation routines for deque itself work only through the

   *  start and finish iterators.  This keeps the routines simple and sane,

   *  and we can use other standard algorithms as well.

  */

  template >

    class deque : protected _Deque_base<_Tp, _Alloc>

    {

      // concept requirements

      typedef typename _Alloc::value_type        _Alloc_value_type;

      __glibcxx_class_requires(_Tp, _SGIAssignableConcept)

      __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)

      typedef _Deque_base<_Tp, _Alloc>           _Base;

      typedef typename _Base::_Tp_alloc_type	 _Tp_alloc_type;

    public:

      typedef _Tp                                        value_type;

      typedef typename _Tp_alloc_type::pointer           pointer;

      typedef typename _Tp_alloc_type::const_pointer     const_pointer;

      typedef typename _Tp_alloc_type::reference         reference;

      typedef typename _Tp_alloc_type::const_reference   const_reference;

      typedef typename _Base::iterator                   iterator;

      typedef typename _Base::const_iterator             const_iterator;

      typedef std::reverse_iterator      const_reverse_iterator;

      typedef std::reverse_iterator            reverse_iterator;

      typedef size_t                             size_type;

      typedef ptrdiff_t                          difference_type;

      typedef _Alloc                             allocator_type;

    protected:

      typedef pointer*                           _Map_pointer;

      static size_t _S_buffer_size()

      { return __deque_buf_size(sizeof(_Tp)); }

      // Functions controlling memory layout, and nothing else.

      using _Base::_M_initialize_map;

      using _Base::_M_create_nodes;

      using _Base::_M_destroy_nodes;

      using _Base::_M_allocate_node;

      using _Base::_M_deallocate_node;

      using _Base::_M_allocate_map;

      using _Base::_M_deallocate_map;

      using _Base::_M_get_Tp_allocator;

      /**

       *  A total of four data members accumulated down the hierarchy.

       *  May be accessed via _M_impl.*

       */

      using _Base::_M_impl;

    public:

      // [23.2.1.1] construct/copy/destroy

      // (assign() and get_allocator() are also listed in this section)

      /**

       *  @brief  Default constructor creates no elements.

       */

      deque()

      : _Base() { }

      /**

       *  @brief  Creates a %deque with no elements.

       *  @param  __a  An allocator object.

       */

      explicit

      deque(const allocator_type& __a)

      : _Base(__a, 0) { }

#if __cplusplus >= 201103L

      /**

       *  @brief  Creates a %deque with default constructed elements.

       *  @param  __n  The number of elements to initially create.

       *

       *  This constructor fills the %deque with @a n default

       *  constructed elements.

       */

      explicit

      deque(size_type __n)

      : _Base(__n)

      { _M_default_initialize(); }

      /**

       *  @brief  Creates a %deque with copies of an exemplar element.

       *  @param  __n  The number of elements to initially create.

       *  @param  __value  An element to copy.

       *  @param  __a  An allocator.

       *

       *  This constructor fills the %deque with @a __n copies of @a __value.

       */

      deque(size_type __n, const value_type& __value,

	    const allocator_type& __a = allocator_type())

      : _Base(__a, __n)

      { _M_fill_initialize(__value); }

#else

      /**

       *  @brief  Creates a %deque with copies of an exemplar element.

       *  @param  __n  The number of elements to initially create.

       *  @param  __value  An element to copy.

       *  @param  __a  An allocator.

       *

       *  This constructor fills the %deque with @a __n copies of @a __value.

       */

      explicit

      deque(size_type __n, const value_type& __value = value_type(),

	    const allocator_type& __a = allocator_type())

      : _Base(__a, __n)

      { _M_fill_initialize(__value); }

#endif

      /**

       *  @brief  %Deque copy constructor.

       *  @param  __x  A %deque of identical element and allocator types.

       *

       *  The newly-created %deque uses a copy of the allocation object used

       *  by @a __x.

       */

      deque(const deque& __x)

      : _Base(__x._M_get_Tp_allocator(), __x.size())

      { std::__uninitialized_copy_a(__x.begin(), __x.end(),

				    this->_M_impl._M_start,

				    _M_get_Tp_allocator()); }

#if __cplusplus >= 201103L

      /**

       *  @brief  %Deque move constructor.

       *  @param  __x  A %deque of identical element and allocator types.

       *

       *  The newly-created %deque contains the exact contents of @a __x.

       *  The contents of @a __x are a valid, but unspecified %deque.

       */

      deque(deque&& __x)

      : _Base(std::move(__x)) { }

      /**

       *  @brief  Builds a %deque from an initializer list.

       *  @param  __l  An initializer_list.

       *  @param  __a  An allocator object.

       *

       *  Create a %deque consisting of copies of the elements in the

       *  initializer_list @a __l.

       *

       *  This will call the element type's copy constructor N times

       *  (where N is __l.size()) and do no memory reallocation.

       */

      deque(initializer_list __l,

	    const allocator_type& __a = allocator_type())

      : _Base(__a)

      {

	_M_range_initialize(__l.begin(), __l.end(),

			    random_access_iterator_tag());

      }

#endif

      /**

       *  @brief  Builds a %deque from a range.

       *  @param  __first  An input iterator.

       *  @param  __last  An input iterator.

       *  @param  __a  An allocator object.

       *

       *  Create a %deque consisting of copies of the elements from [__first,

       *  __last).

       *

       *  If the iterators are forward, bidirectional, or random-access, then

       *  this will call the elements' copy constructor N times (where N is

       *  distance(__first,__last)) and do no memory reallocation.  But if only

       *  input iterators are used, then this will do at most 2N calls to the

       *  copy constructor, and logN memory reallocations.

       */

#if __cplusplus >= 201103L

      template

	       typename = std::_RequireInputIter<_InputIterator>>

        deque(_InputIterator __first, _InputIterator __last,

	      const allocator_type& __a = allocator_type())

	: _Base(__a)

        { _M_initialize_dispatch(__first, __last, __false_type()); }

#else

      template

        deque(_InputIterator __first, _InputIterator __last,

	      const allocator_type& __a = allocator_type())

	: _Base(__a)

        {

	  // Check whether it's an integral type.  If so, it's not an iterator.

	  typedef typename std::__is_integer<_InputIterator>::__type _Integral;

	  _M_initialize_dispatch(__first, __last, _Integral());

	}

#endif

      /**

       *  The dtor only erases the elements, and note that if the elements

       *  themselves are pointers, the pointed-to memory is not touched in any

       *  way.  Managing the pointer is the user's responsibility.

       */

      ~deque() _GLIBCXX_NOEXCEPT

      { _M_destroy_data(begin(), end(), _M_get_Tp_allocator()); }

      /**

       *  @brief  %Deque assignment operator.

       *  @param  __x  A %deque of identical element and allocator types.

       *

       *  All the elements of @a x are copied, but unlike the copy constructor,

       *  the allocator object is not copied.

       */

      deque&

      operator=(const deque& __x);

#if __cplusplus >= 201103L

      /**

       *  @brief  %Deque move assignment operator.

       *  @param  __x  A %deque of identical element and allocator types.

       *

       *  The contents of @a __x are moved into this deque (without copying).

       *  @a __x is a valid, but unspecified %deque.

       */

      deque&

      operator=(deque&& __x)

      {

	// NB: DR 1204.

	// NB: DR 675.

	this->clear();

	this->swap(__x);

	return *this;

      }

      /**

       *  @brief  Assigns an initializer list to a %deque.

       *  @param  __l  An initializer_list.

       *

       *  This function fills a %deque with copies of the elements in the

       *  initializer_list @a __l.

       *

       *  Note that the assignment completely changes the %deque and that the

       *  resulting %deque's size is the same as the number of elements

       *  assigned.  Old data may be lost.

       */

      deque&

      operator=(initializer_list __l)

      {

	this->assign(__l.begin(), __l.end());

	return *this;

      }

#endif

      /**

       *  @brief  Assigns a given value to a %deque.

       *  @param  __n  Number of elements to be assigned.

       *  @param  __val  Value to be assigned.

       *

       *  This function fills a %deque with @a n copies of the given

       *  value.  Note that the assignment completely changes the

       *  %deque and that the resulting %deque's size is the same as

       *  the number of elements assigned.  Old data may be lost.

       */

      void

      assign(size_type __n, const value_type& __val)

      { _M_fill_assign(__n, __val); }

      /**

       *  @brief  Assigns a range to a %deque.

       *  @param  __first  An input iterator.

       *  @param  __last   An input iterator.

       *

       *  This function fills a %deque with copies of the elements in the

       *  range [__first,__last).

       *

       *  Note that the assignment completely changes the %deque and that the

       *  resulting %deque's size is the same as the number of elements

       *  assigned.  Old data may be lost.

       */

#if __cplusplus >= 201103L

      template

	       typename = std::_RequireInputIter<_InputIterator>>

        void

        assign(_InputIterator __first, _InputIterator __last)

        { _M_assign_dispatch(__first, __last, __false_type()); }

#else

      template

        void

        assign(_InputIterator __first, _InputIterator __last)

        {

	  typedef typename std::__is_integer<_InputIterator>::__type _Integral;

	  _M_assign_dispatch(__first, __last, _Integral());

	}

#endif

#if __cplusplus >= 201103L

      /**

       *  @brief  Assigns an initializer list to a %deque.

       *  @param  __l  An initializer_list.

       *

       *  This function fills a %deque with copies of the elements in the

       *  initializer_list @a __l.

       *

       *  Note that the assignment completely changes the %deque and that the

       *  resulting %deque's size is the same as the number of elements

       *  assigned.  Old data may be lost.

       */

      void

      assign(initializer_list __l)

      { this->assign(__l.begin(), __l.end()); }

#endif

      /// Get a copy of the memory allocation object.

      allocator_type

      get_allocator() const _GLIBCXX_NOEXCEPT

      { return _Base::get_allocator(); }

      // iterators

      /**

       *  Returns a read/write iterator that points to the first element in the

       *  %deque.  Iteration is done in ordinary element order.

       */

      iterator

      begin() _GLIBCXX_NOEXCEPT

      { return this->_M_impl._M_start; }

      /**

       *  Returns a read-only (constant) iterator that points to the first

       *  element in the %deque.  Iteration is done in ordinary element order.

       */

      const_iterator

      begin() const _GLIBCXX_NOEXCEPT

      { return this->_M_impl._M_start; }

      /**

       *  Returns a read/write iterator that points one past the last

       *  element in the %deque.  Iteration is done in ordinary

       *  element order.

       */

      iterator

      end() _GLIBCXX_NOEXCEPT

      { return this->_M_impl._M_finish; }

      /**

       *  Returns a read-only (constant) iterator that points one past

       *  the last element in the %deque.  Iteration is done in

       *  ordinary element order.

       */

      const_iterator

      end() const _GLIBCXX_NOEXCEPT

      { return this->_M_impl._M_finish; }

      /**

       *  Returns a read/write reverse iterator that points to the

       *  last element in the %deque.  Iteration is done in reverse

       *  element order.

       */

      reverse_iterator

      rbegin() _GLIBCXX_NOEXCEPT

      { return reverse_iterator(this->_M_impl._M_finish); }

      /**

       *  Returns a read-only (constant) reverse iterator that points

       *  to the last element in the %deque.  Iteration is done in

       *  reverse element order.

       */

      const_reverse_iterator

      rbegin() const _GLIBCXX_NOEXCEPT

      { return const_reverse_iterator(this->_M_impl._M_finish); }

      /**

       *  Returns a read/write reverse iterator that points to one

       *  before the first element in the %deque.  Iteration is done

       *  in reverse element order.

       */

      reverse_iterator

      rend() _GLIBCXX_NOEXCEPT

      { return reverse_iterator(this->_M_impl._M_start); }

      /**

       *  Returns a read-only (constant) reverse iterator that points

       *  to one before the first element in the %deque.  Iteration is

       *  done in reverse element order.

       */

      const_reverse_iterator

      rend() const _GLIBCXX_NOEXCEPT

      { return const_reverse_iterator(this->_M_impl._M_start); }

#if __cplusplus >= 201103L

      /**

       *  Returns a read-only (constant) iterator that points to the first

       *  element in the %deque.  Iteration is done in ordinary element order.

       */

      const_iterator

      cbegin() const noexcept

      { return this->_M_impl._M_start; }

      /**

       *  Returns a read-only (constant) iterator that points one past

       *  the last element in the %deque.  Iteration is done in

       *  ordinary element order.

       */

      const_iterator

      cend() const noexcept

      { return this->_M_impl._M_finish; }

      /**

       *  Returns a read-only (constant) reverse iterator that points

       *  to the last element in the %deque.  Iteration is done in