stl_deque.h

俄罗斯高人Mamaich的Pocket gcc编译器（运行在PocketPC上）的全部源代码。

  protected:
    typedef typename _Alloc_traits<_Tp,_Alloc>::_Alloc_type  _Node_alloc_type;
    typedef typename _Alloc_traits<_Tp*,_Alloc>::_Alloc_type _Map_alloc_type;
  
    _Tp*
    _M_allocate_node()
    {
      return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp)));
    }
  
    void
    _M_deallocate_node(_Tp* __p)
    {
      _Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp)));
    }
  
    _Tp**
    _M_allocate_map(size_t __n) 
      { return _Map_alloc_type::allocate(__n); }
  
    void
    _M_deallocate_map(_Tp** __p, size_t __n) 
      { _Map_alloc_type::deallocate(__p, __n); }
  
    _Tp**   _M_map;
    size_t  _M_map_size;
  };
  
  
  /**
   *  @if maint
   *  Deque base class.  Using _Alloc_traits in the instantiation of the parent
   *  class provides the compile-time dispatching mentioned in the parent's
   *  docs.  This class provides the unified face for %deque's allocation.
   *
   *  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 _Deque_alloc_base<_Tp,_Alloc,
                                _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
  {
  public:
    typedef _Deque_alloc_base<_Tp,_Alloc,
                               _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
            _Base;
    typedef typename _Base::allocator_type             allocator_type;
    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)
      : _Base(__a), _M_start(), _M_finish()
      { _M_initialize_map(__num_elements); }
    _Deque_base(const allocator_type& __a) 
      : _Base(__a), _M_start(), _M_finish() {}
    ~_Deque_base();    
  
  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 };
  
    iterator _M_start;
    iterator _M_finish;
  };
  
  
  template <typename _Tp, typename _Alloc>
  _Deque_base<_Tp,_Alloc>::~_Deque_base()
  {
    if (_M_map)
    {
      _M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1);
      _M_deallocate_map(_M_map, _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;
  
    _M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2);
    _M_map = _M_allocate_map(_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 = _M_map + (_M_map_size - __num_nodes) / 2;
    _Tp** __nfinish = __nstart + __num_nodes;
      
    try 
      { _M_create_nodes(__nstart, __nfinish); }
    catch(...)
      {
        _M_deallocate_map(_M_map, _M_map_size);
        _M_map = 0;
        _M_map_size = 0;
        __throw_exception_again;
      }
    
    _M_start._M_set_node(__nstart);
    _M_finish._M_set_node(__nfinish - 1);
    _M_start._M_cur = _M_start._M_first;
    _M_finish._M_cur = _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 = _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
    __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
  
    typedef _Deque_base<_Tp, _Alloc>           _Base;
  
  public:
    typedef _Tp                                value_type;
    typedef value_type*                        pointer;
    typedef const value_type*                  const_pointer;
    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 value_type&                        reference;
    typedef const value_type&                  const_reference;
    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.  If the
     *  _Alloc type requires separate instances, then two of them will also be
     *  included in each deque.
     *  @endif
    */
    using _Base::_M_map;
    using _Base::_M_map_size;
    using _Base::_M_start;
    using _Base::_M_finish;
  
  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()) 
      { uninitialized_copy(__x.begin(), __x.end(), _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() { _Destroy(_M_start, _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(); }