stl_deque.h

mingw32.rar

      //standard container and at the same time makes use of the EBO
      //for empty allocators.
      struct _Deque_impl
	: public _Alloc {
	_Tp** _M_map;
	size_t _M_map_size;
	iterator _M_start;
	iterator _M_finish;

	_Deque_impl(const _Alloc& __a)
	  : _Alloc(__a), _M_map(0), _M_map_size(0), _M_start(), _M_finish()
	{ }
      };

      typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type;
      _Map_alloc_type _M_get_map_allocator() const
      { return _Map_alloc_type(this->get_allocator()); }

      _Tp*
      _M_allocate_node()
      { return _M_impl._Alloc::allocate(__deque_buf_size(sizeof(_Tp))); }

      void
      _M_deallocate_node(_Tp* __p)
      { _M_impl._Alloc::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)
    {
      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,
				   __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.
   *
   *  **** As I write this, the nodes are /not/ allocated using the high-speed
   *  memory pool.  There are 20 hours left in the year; perhaps I can fix
   *  this before 2002.
   *
   *  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 = allocator<_Tp> >
    class deque : protected _Deque_base<_Tp, _Alloc>
    {
      // concept requirements
      __glibcxx_class_requires(_Tp, _SGIAssignableConcept)

      typedef _Deque_base<_Tp, _Alloc>           _Base;

    public:
      typedef _Tp                                value_type;
      typedef typename _Alloc::pointer           pointer;
      typedef typename _Alloc::const_pointer     const_pointer;
      typedef typename _Alloc::reference         reference;
      typedef typename _Alloc::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 typename _Base::allocator_type     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;

      /** @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.
       */
      deque(size_type __n, const value_type& __value,
	    const allocator_type& __a = allocator_type())
      : _Base(__a, __n)
      { _M_fill_initialize(__value); }

      /**
       *  @brief  Create a %deque with default elements.
       *  @param  n  The number of elements to initially create.
       *
       *  This constructor fills the %deque with @a n copies of a
       *  default-constructed element.
       */
      explicit
      deque(size_type __n)
      : _Base(allocator_type(), __n)
      { _M_fill_initialize(value_type()); }

      /**
       *  @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(__x.begin(), __x.end(), this->_M_impl._M_start); }

      /**
       *  @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 _Is_integer<_InputIterator>::_Integral _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); }

      /**
       *  @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);

      /**
       *  @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.
       */
      template<typename _InputIterator>
        void
        assign(_InputIterator __first, _InputIterator __last)
        {
	  typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
	  _M_assign_dispatch(__first, __last, _Integral());
	}

      /// Get a copy of the memory allocation object.
      allocator_type
      get_allocator() const
      { return _Base::get_allocator(); }