stl_list.h

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

  
    /** @if maint
     *  One data member plus two memory-handling functions.  If the _Alloc
     *  type requires separate instances, then one of those will also be
     *  included, accumulated from the topmost parent.
     *  @endif
    */
    using _Base::_M_node;
    using _Base::_M_put_node;
    using _Base::_M_get_node;
  
    /**
     *  @if maint
     *  @param  x  An instance of user data.
     *
     *  Allocates space for a new node and constructs a copy of @a x in it.
     *  @endif
    */
    _Node*
    _M_create_node(const value_type& __x)
    {
      _Node* __p = _M_get_node();
      try {
        _Construct(&__p->_M_data, __x);
      }
      catch(...)
      {
        _M_put_node(__p);
        __throw_exception_again;
      }
      return __p;
    }
  
    /**
     *  @if maint
     *  Allocates space for a new node and default-constructs a new instance
     *  of @c value_type in it.
     *  @endif
    */
    _Node*
    _M_create_node()
    {
      _Node* __p = _M_get_node();
      try {
        _Construct(&__p->_M_data);
      }
      catch(...)
      {
        _M_put_node(__p);
        __throw_exception_again;
      }
      return __p;
    }
  
  public:
    // [23.2.2.1] construct/copy/destroy
    // (assign() and get_allocator() are also listed in this section)
    /**
     *  @brief  Default constructor creates no elements.
    */
    explicit
    list(const allocator_type& __a = allocator_type())
    : _Base(__a) { }
  
    /**
     *  @brief  Create a %list 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 %list with @a n copies of @a value.
    */
    list(size_type __n, const value_type& __value,
         const allocator_type& __a = allocator_type())
      : _Base(__a)
      { this->insert(begin(), __n, __value); }
  
    /**
     *  @brief  Create a %list with default elements.
     *  @param  n  The number of elements to initially create.
     * 
     *  This constructor fills the %list with @a n copies of a
     *  default-constructed element.
    */
    explicit
    list(size_type __n)
      : _Base(allocator_type())
      { this->insert(begin(), __n, value_type()); }
  
    /**
     *  @brief  %List copy constructor.
     *  @param  x  A %list of identical element and allocator types.
     * 
     *  The newly-created %list uses a copy of the allocation object used
     *  by @a x.
    */
    list(const list& __x)
      : _Base(__x.get_allocator())
      { this->insert(begin(), __x.begin(), __x.end()); }
  
    /**
     *  @brief  Builds a %list from a range.
     *  @param  first  An input iterator.
     *  @param  last  An input iterator.
     * 
     *  Create a %list consisting of copies of the elements from [first,last).
     *  This is linear in N (where N is distance(first,last)).
     *
     *  @if maint
     *  We don't need any dispatching tricks here, because insert does all of
     *  that anyway.
     *  @endif
    */
    template<typename _InputIterator>
      list(_InputIterator __first, _InputIterator __last,
           const allocator_type& __a = allocator_type())
      : _Base(__a)
      { this->insert(begin(), __first, __last); }
  
    /**
     *  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.
    */
    ~list() { }
  
    /**
     *  @brief  %List assignment operator.
     *  @param  x  A %list 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.
    */
    list&
    operator=(const list& __x);
  
    /**
     *  @brief  Assigns a given value to a %list.
     *  @param  n  Number of elements to be assigned.
     *  @param  val  Value to be assigned.
     *
     *  This function fills a %list with @a n copies of the given value.
     *  Note that the assignment completely changes the %list and that the
     *  resulting %list'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 %list.
     *  @param  first  An input iterator.
     *  @param  last   An input iterator.
     *
     *  This function fills a %list with copies of the elements in the
     *  range [first,last).
     *
     *  Note that the assignment completely changes the %list and that the
     *  resulting %list'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)
      {
        // Check whether it's an integral type.  If so, it's not an iterator.
        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(); }
  
    // iterators
    /**
     *  Returns a read/write iterator that points to the first element in the
     *  %list.  Iteration is done in ordinary element order.
    */
    iterator
    begin() { return static_cast<_Node*>(_M_node->_M_next); }
  
    /**
     *  Returns a read-only (constant) iterator that points to the first element
     *  in the %list.  Iteration is done in ordinary element order.
    */
    const_iterator
    begin() const { return static_cast<_Node*>(_M_node->_M_next); }
  
    /**
     *  Returns a read/write iterator that points one past the last element in
     *  the %list.  Iteration is done in ordinary element order.
    */
    iterator
    end() { return _M_node; }
  
    /**
     *  Returns a read-only (constant) iterator that points one past the last
     *  element in the %list.  Iteration is done in ordinary element order.
    */
    const_iterator
    end() const { return _M_node; }
  
    /**
     *  Returns a read/write reverse iterator that points to the last element in
     *  the %list.  Iteration is done in reverse element order.
    */
    reverse_iterator
    rbegin() { return reverse_iterator(end()); }
  
    /**
     *  Returns a read-only (constant) reverse iterator that points to the last
     *  element in the %list.  Iteration is done in reverse element order.
    */
    const_reverse_iterator
    rbegin() const { return const_reverse_iterator(end()); }
  
    /**
     *  Returns a read/write reverse iterator that points to one before the
     *  first element in the %list.  Iteration is done in reverse element
     *  order.
    */
    reverse_iterator
    rend() { return reverse_iterator(begin()); }
  
    /**
     *  Returns a read-only (constant) reverse iterator that points to one
     *  before the first element in the %list.  Iteration is done in reverse
     *  element order.
    */
    const_reverse_iterator
    rend() const
    { return const_reverse_iterator(begin()); }
  
    // [23.2.2.2] capacity
    /**
     *  Returns true if the %list is empty.  (Thus begin() would equal end().)
    */
    bool
    empty() const { return _M_node->_M_next == _M_node; }
  
    /**  Returns the number of elements in the %list.  */
    size_type
    size() const { return distance(begin(), end()); }
  
    /**  Returns the size() of the largest possible %list.  */
    size_type
    max_size() const { return size_type(-1); }
  
    /**
     *  @brief  Resizes the %list to the specified number of elements.
     *  @param  new_size  Number of elements the %list should contain.
     *  @param  x  Data with which new elements should be populated.
     *
     *  This function will %resize the %list to the specified number of
     *  elements.  If the number is smaller than the %list's current size the
     *  %list is truncated, otherwise the %list is extended and new elements
     *  are populated with given data.
    */
    void
    resize(size_type __new_size, const value_type& __x);
  
    /**
     *  @brief  Resizes the %list to the specified number of elements.
     *  @param  new_size  Number of elements the %list should contain.
     *
     *  This function will resize the %list to the specified number of
     *  elements.  If the number is smaller than the %list's current size the
     *  %list is truncated, otherwise the %list is extended and new elements
     *  are default-constructed.
    */
    void
    resize(size_type __new_size) { this->resize(__new_size, value_type()); }
  
    // element access
    /**
     *  Returns a read/write reference to the data at the first element of the
     *  %list.
    */
    reference
    front() { return *begin(); }
  
    /**
     *  Returns a read-only (constant) reference to the data at the first
     *  element of the %list.
    */
    const_reference
    front() const { return *begin(); }
  
    /**
     *  Returns a read/write reference to the data at the last element of the
     *  %list.
    */
    reference
    back() { return *(--end()); }
  
    /**
     *  Returns a read-only (constant) reference to the data at the last
     *  element of the %list.
    */
    const_reference
    back() const { return *(--end()); }
  
    // [23.2.2.3] modifiers
    /**
     *  @brief  Add data to the front of the %list.
     *  @param  x  Data to be added.
     *
     *  This is a typical stack operation.  The function creates an element at
     *  the front of the %list and assigns the given data to it.  Due to the
     *  nature of a %list this operation can be done in constant time, and
     *  does not invalidate iterators and references.
    */
    void
    push_front(const value_type& __x) { this->insert(begin(), __x); }
  
  #ifdef _GLIBCPP_DEPRECATED
    /**
     *  @brief  Add data to the front of the %list.
     *
     *  This is a typical stack operation.  The function creates a
     *  default-constructed element at the front of the %list.  Due to the
     *  nature of a %list this operation can be done in constant time.  You
     *  should consider using push_front(value_type()) instead.
     *
     *  @note This was deprecated in 3.2 and will be removed in 3.4.  You must
     *        define @c _GLIBCPP_DEPRECATED to make this visible in 3.2; see
     *        c++config.h.
    */
    void
    push_front() { this->insert(begin(), value_type()); }
  #endif
  
    /**
     *  @brief  Removes first element.
     *
     *  This is a typical stack operation.  It shrinks the %list by one.
     *  Due to the nature of a %list this operation can be done in constant
     *  time, and only invalidates iterators/references to the element being
     *  removed.
     *
     *  Note that no data is returned, and if the first element's data is
     *  needed, it should be retrieved before pop_front() is called.
    */
    void
    pop_front() { this->erase(begin()); }
  
    /**
     *  @brief  Add data to the end of the %list.
     *  @param  x  Data to be added.
     *
     *  This is a typical stack operation.  The function creates an element at
     *  the end of the %list and assigns the given data to it.  Due to the
     *  nature of a %list this operation can be done in constant time, and
     *  does not invalidate iterators and references.
    */
    void
    push_back(const value_type& __x) { this->insert(end(), __x); }
  
  #ifdef _GLIBCPP_DEPRECATED
    /**
     *  @brief  Add data to the end of the %list.
     *
     *  This is a typical stack operation.  The function creates a
     *  default-constructed element at the end of the %list.  Due to the nature
     *  of a %list this operation can be done in constant time.  You should
     *  consider using push_back(value_type()) instead.
     *
     *  @note This was deprecated in 3.2 and will be removed in 3.4.  You must
     *        define @c _GLIBCPP_DEPRECATED to make this visible in 3.2; see
     *        c++config.h.
    */
    void
    push_back() { this->insert(end(), value_type()); }
  #endif
  
    /**
     *  @brief  Removes last element.
     *
     *  This is a typical stack operation.  It shrinks the %list by one.
     *  Due to the nature of a %list this operation can be done in constant
     *  time, and only invalidates iterators/references to the element being
     *  removed.
     *
     *  Note that no data is returned, and if the last element's data is
     *  needed, it should be retrieved before pop_back() is called.
    */
    void
    pop_back()
    {