Subversion Repositories scarts

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

// Copyright (C) 2001, 2002, 2003, 2004, 2005 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 2, 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.

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

// with this library; see the file COPYING.  If not, write to the Free

// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,

// USA.

// As a special exception, you may use this file as part of a free software

// library without restriction.  Specifically, if other files instantiate

// templates or use macros or inline functions from this file, or you compile

// this file and link it with other files to produce an executable, this

// file does not by itself cause the resulting executable to be covered by

// the GNU General Public License.  This exception does not however

// invalidate any other reasons why the executable file might be covered by

// the GNU General Public License.

/*

 *

 * 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 stl_deque.h

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

 *  You should not attempt to use it directly.

 */

#ifndef _DEQUE_H

#define _DEQUE_H 1

#include <bits/concept_check.h>

#include <bits/stl_iterator_base_types.h>

#include <bits/stl_iterator_base_funcs.h>

namespace _GLIBCXX_STD

{

  /**

   *  @if maint

   *  @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 '512' is

   *  tuneable (and no other code needs to change), but no investigation has

   *  been done since inheriting the SGI code.

   *  @endif

  */

  inline size_t

  __deque_buf_size(size_t __size)

  { return __size < 512 ? size_t(512 / __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.

   *

   *  @if maint

   *  All the functions are op overloads except for _M_set_node.

   *  @endif

  */

  template<typename _Tp, typename _Ref, typename _Ptr>

    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); }

      /** @if maint

       *  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.

       *  @endif

       */

      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<typename _Tp, typename _Ref, typename _Ptr>

    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 _Tp, typename _RefL, typename _PtrL,

           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<typename _Tp, typename _Ref, typename _Ptr>

    inline bool

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

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

    { return !(__x == __y); }

  template<typename _Tp, typename _RefL, typename _PtrL,

           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<typename _Tp, typename _Ref, typename _Ptr>

    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 _Tp, typename _RefL, typename _PtrL,

           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<typename _Tp, typename _Ref, typename _Ptr>

    inline bool

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

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

    { return __y < __x; }

  template<typename _Tp, typename _RefL, typename _PtrL,

           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<typename _Tp, typename _Ref, typename _Ptr>

    inline bool

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

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

    { return !(__y < __x); }

  template<typename _Tp, typename _RefL, typename _PtrL,

           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<typename _Tp, typename _Ref, typename _Ptr>

    inline bool

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

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

    { return !(__x < __y); }

  template<typename _Tp, typename _RefL, typename _PtrL,

           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<typename _Tp, typename _RefL, typename _PtrL,

           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<typename _Tp, typename _Ref, typename _Ptr>

    inline _Deque_iterator<_Tp, _Ref, _Ptr>

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

    { return __x + __n; }

  /**

   *  @if maint

   *  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.

   *  @endif

  */

  template<typename _Tp, typename _Alloc>

    class _Deque_base

    {

    public:

      typedef _Alloc                  allocator_type;

      allocator_type

      get_allocator() const

      { return _M_get_Tp_allocator(); }

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

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

      _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)

      { }

      ~_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(const _Tp_alloc_type& __a)

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

          _M_start(), _M_finish()

        { }

      };

      _Tp_alloc_type&

      _M_get_Tp_allocator()

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

      const _Tp_alloc_type&

      _M_get_Tp_allocator() const

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

      _Map_alloc_type

      _M_get_map_allocator() const

      { return _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<typename _Tp, typename _Alloc>

    _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);

        }

    }

  /**

   *  @if maint

   *  @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...

   *  @endif

  */

  template<typename _Tp, typename _Alloc>

    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<typename _Tp, typename _Alloc>

    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<typename _Tp, typename _Alloc>

    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 Containers

   *  @ingroup Sequences

   *

   *  Meets the requirements of a <a href="tables.html#65">container</a>, a

   *  <a href="tables.html#66">reversible container</a>, and a

   *  <a href="tables.html#67">sequence</a>, including the

   *  <a href="tables.html#68">optional sequence requirements</a>.

   *

   *  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.

   *

   *  @if maint

   *  Here's how a deque<Tp> 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-"nodes".  (The name %map has nothing to do with the

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

   *  std::list's usage of "node".)

   *

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

   *  to as "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

   *  "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 "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 <N

   * 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 "aware" of the discontiguous

   *  storage!

   *

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

   *  class is entirely responsible for "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.

   *  @endif

  */

  template<typename _Tp, typename _Alloc = std::allocator<_Tp> >

    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_iterator>      const_reverse_iterator;

      typedef std::reverse_iterator<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;

      /** @if maint

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

       *  May be accessed via _M_impl.*

       *  @endif

       */

      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.

       */

      explicit

      deque(const allocator_type& __a = allocator_type())

      : _Base(__a, 0) {}

      /**

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

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

       *  @param  value  An element to copy.

       *

       *  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); }

      /**

       *  @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.get_allocator(), __x.size())

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

                                    this->_M_impl._M_start,

                                    _M_get_Tp_allocator()); }

      /**

       *  @brief  Builds a %deque from a range.

       *  @param  first  An input iterator.

       *  @param  last  An input iterator.

       *

       *  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.

       */

      template<typename _InputIterator>

        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());

        }

      /**

       *  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 responsibilty.

       */

      ~deque()

      { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,