stl_list.h

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

      iterator __tmp = end();
      this->erase(--__tmp);
    }
  
    /**
     *  @brief  Inserts given value into %list before specified iterator.
     *  @param  position  An iterator into the %list.
     *  @param  x  Data to be inserted.
     *  @return  An iterator that points to the inserted data.
     *
     *  This function will insert a copy of the given value before the specified
     *  location.
     *  Due to the nature of a %list this operation can be done in constant
     *  time, and does not invalidate iterators and references.
    */
    iterator
    insert(iterator __position, const value_type& __x);
  
  #ifdef _GLIBCPP_DEPRECATED
    /**
     *  @brief  Inserts an element into the %list.
     *  @param  position  An iterator into the %list.
     *  @return  An iterator that points to the inserted element.
     *
     *  This function will insert a default-constructed element before the
     *  specified location.  You should consider using
     *  insert(position,value_type()) instead.
     *  Due to the nature of a %list this operation can be done in constant
     *  time, and does not invalidate iterators and references.
     *
     *  @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.
    */
    iterator
    insert(iterator __position) { return insert(__position, value_type()); }
  #endif
  
    /**
     *  @brief  Inserts a number of copies of given data into the %list.
     *  @param  position  An iterator into the %list.
     *  @param  n  Number of elements to be inserted.
     *  @param  x  Data to be inserted.
     *
     *  This function will insert a specified number of copies of the given data
     *  before the location specified by @a position.
     *
     *  Due to the nature of a %list this operation can be done in constant
     *  time, and does not invalidate iterators and references.
    */
    void
    insert(iterator __pos, size_type __n, const value_type& __x)
    { _M_fill_insert(__pos, __n, __x); }
  
    /**
     *  @brief  Inserts a range into the %list.
     *  @param  pos  An iterator into the %list.
     *  @param  first  An input iterator.
     *  @param  last   An input iterator.
     *
     *  This function will insert copies of the data in the range [first,last)
     *  into the %list before the location specified by @a pos.
     *
     *  Due to the nature of a %list this operation can be done in constant
     *  time, and does not invalidate iterators and references.
    */
    template<typename _InputIterator>
      void
      insert(iterator __pos, _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_insert_dispatch(__pos, __first, __last, _Integral());
      }
  
    /**
     *  @brief  Remove element at given position.
     *  @param  position  Iterator pointing to element to be erased.
     *  @return  An iterator pointing to the next element (or end()).
     *
     *  This function will erase the element at the given position and thus
     *  shorten 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.
     *  The user is also cautioned that
     *  this function only erases the element, and that if the element is itself
     *  a pointer, the pointed-to memory is not touched in any way.  Managing
     *  the pointer is the user's responsibilty.
    */
    iterator
    erase(iterator __position);
  
    /**
     *  @brief  Remove a range of elements.
     *  @param  first  Iterator pointing to the first element to be erased.
     *  @param  last  Iterator pointing to one past the last element to be
     *                erased.
     *  @return  An iterator pointing to the element pointed to by @a last
     *           prior to erasing (or end()).
     *
     *  This function will erase the elements in the range [first,last) and
     *  shorten the %list accordingly.
     *
     *  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.
     *  The user is also cautioned that
     *  this function only erases the elements, and 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.
    */
    iterator
    erase(iterator __first, iterator __last)
    {
      while (__first != __last)
        erase(__first++);
      return __last;
    }
  
    /**
     *  @brief  Swaps data with another %list.
     *  @param  x  A %list of the same element and allocator types.
     *
     *  This exchanges the elements between two lists in constant time.
     *  (It is only swapping a single pointer, so it should be quite fast.)
     *  Note that the global std::swap() function is specialized such that
     *  std::swap(l1,l2) will feed to this function.
    */
    void
    swap(list& __x) { std::swap(_M_node, __x._M_node); }
  
    /**
     *  Erases all the elements.  Note that this function only erases the
     *  elements, and 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.
    */
    void
    clear() { _Base::__clear(); }
  
    // [23.2.2.4] list operations
    /**
     *  @doctodo
    */
    void
    splice(iterator __position, list& __x)
    {
      if (!__x.empty())
        this->_M_transfer(__position, __x.begin(), __x.end());
    }
  
    /**
     *  @doctodo
    */
    void
    splice(iterator __position, list&, iterator __i)
    {
      iterator __j = __i;
      ++__j;
      if (__position == __i || __position == __j) return;
      this->_M_transfer(__position, __i, __j);
    }
  
    /**
     *  @doctodo
    */
    void
    splice(iterator __position, list&, iterator __first, iterator __last)
    {
      if (__first != __last)
        this->_M_transfer(__position, __first, __last);
    }
  
    /**
     *  @doctodo
    */
    void
    remove(const _Tp& __value);
  
    /**
     *  @doctodo
    */
    template<typename _Predicate>
      void
      remove_if(_Predicate);
  
    /**
     *  @doctodo
    */
    void
    unique();
  
    /**
     *  @doctodo
    */
    template<typename _BinaryPredicate>
      void
      unique(_BinaryPredicate);
  
    /**
     *  @doctodo
    */
    void
    merge(list& __x);
  
    /**
     *  @doctodo
    */
    template<typename _StrictWeakOrdering>
      void
      merge(list&, _StrictWeakOrdering);
  
    /**
     *  @doctodo
    */
    void
    reverse() { __List_base_reverse(this->_M_node); }
  
    /**
     *  @doctodo
    */
    void
    sort();
  
    /**
     *  @doctodo
    */
    template<typename _StrictWeakOrdering>
      void
      sort(_StrictWeakOrdering);
  
  protected:
    // Internal assign functions follow.
  
    // called by the range assign to implement [23.1.1]/9
    template<typename _Integer>
      void
      _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
      {
        _M_fill_assign(static_cast<size_type>(__n),
                       static_cast<value_type>(__val));
      }
  
    // called by the range assign to implement [23.1.1]/9
    template<typename _InputIter>
      void
      _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type);
  
    // Called by assign(n,t), and the range assign when it turns out to be the
    // same thing.
    void
    _M_fill_assign(size_type __n, const value_type& __val);
  
  
    // Internal insert functions follow.
  
    // called by the range insert to implement [23.1.1]/9
    template<typename _Integer>
      void
      _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
                         __true_type)
      {
        _M_fill_insert(__pos, static_cast<size_type>(__n),
                       static_cast<value_type>(__x));
      }
  
    // called by the range insert to implement [23.1.1]/9
    template<typename _InputIterator>
      void
      _M_insert_dispatch(iterator __pos,
                         _InputIterator __first, _InputIterator __last,
                         __false_type)
      {
        for ( ; __first != __last; ++__first)
          insert(__pos, *__first);
      }
  
    // Called by insert(p,n,x), and the range insert when it turns out to be
    // the same thing.
    void
    _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
    {
      for ( ; __n > 0; --__n)
        insert(__pos, __x);
    }
  
  
    // Moves the elements from [first,last) before position.
    void
    _M_transfer(iterator __position, iterator __first, iterator __last)
    {
      if (__position != __last) {
        // Remove [first, last) from its old position.
        __last._M_node->_M_prev->_M_next     = __position._M_node;
        __first._M_node->_M_prev->_M_next    = __last._M_node;
        __position._M_node->_M_prev->_M_next = __first._M_node;
  
        // Splice [first, last) into its new position.
        _List_node_base* __tmp      = __position._M_node->_M_prev;
        __position._M_node->_M_prev = __last._M_node->_M_prev;
        __last._M_node->_M_prev     = __first._M_node->_M_prev;
        __first._M_node->_M_prev    = __tmp;
      }
    }
  };
  
  
  /**
   *  @brief  List equality comparison.
   *  @param  x  A %list.
   *  @param  y  A %list of the same type as @a x.
   *  @return  True iff the size and elements of the lists are equal.
   *
   *  This is an equivalence relation.  It is linear in the size of the
   *  lists.  Lists are considered equivalent if their sizes are equal,
   *  and if corresponding elements compare equal.
  */
  template<typename _Tp, typename _Alloc>
  inline bool
    operator==(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
    {
      typedef typename list<_Tp,_Alloc>::const_iterator const_iterator;
      const_iterator __end1 = __x.end();
      const_iterator __end2 = __y.end();
  
      const_iterator __i1 = __x.begin();
      const_iterator __i2 = __y.begin();
      while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) {
        ++__i1;
        ++__i2;
      }
      return __i1 == __end1 && __i2 == __end2;
    }
  
  /**
   *  @brief  List ordering relation.
   *  @param  x  A %list.
   *  @param  y  A %list of the same type as @a x.
   *  @return  True iff @a x is lexographically less than @a y.
   *
   *  This is a total ordering relation.  It is linear in the size of the
   *  lists.  The elements must be comparable with @c <.
   *
   *  See std::lexographical_compare() for how the determination is made.
  */
  template<typename _Tp, typename _Alloc>
    inline bool
    operator<(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
    {
      return lexicographical_compare(__x.begin(), __x.end(),
                                     __y.begin(), __y.end());
    }
  
  /// Based on operator==
  template<typename _Tp, typename _Alloc>
    inline bool
    operator!=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
    { return !(__x == __y); }
  
  /// Based on operator<
  template<typename _Tp, typename _Alloc>
    inline bool
    operator>(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
    { return __y < __x; }
  
  /// Based on operator<
  template<typename _Tp, typename _Alloc>
    inline bool
    operator<=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
    { return !(__y < __x); }
  
  /// Based on operator<
  template<typename _Tp, typename _Alloc>
    inline bool
    operator>=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
    { return !(__x < __y); }
  
  /// See std::list::swap().
  template<typename _Tp, typename _Alloc>
    inline void
    swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
    { __x.swap(__y); }
} // namespace std

#endif /* __GLIBCPP_INTERNAL_LIST_H */