stl_list.h

gcc3.2.1源代码

      }

      iterator
      erase(iterator __first, iterator __last);

      void
      clear()
      { _Base::clear(); }

      void
      resize(size_type __new_size, const _Tp& __x);
      
      void
      resize(size_type __new_size)
      { this->resize(__new_size, _Tp()); }

      void
      pop_front()
      { erase(begin()); }

      void
      pop_back()
      { 
        iterator __tmp = end();
        erase(--__tmp);
      }

      list(size_type __n, const _Tp& __value,
           const allocator_type& __a = allocator_type())
      : _Base(__a)
      { insert(begin(), __n, __value); }

      explicit
      list(size_type __n)
      : _Base(allocator_type())
      { insert(begin(), __n, _Tp()); }

      // We don't need any dispatching tricks here, because insert does all of
      // that anyway.  
      template<typename _InputIterator>
      list(_InputIterator __first, _InputIterator __last,
           const allocator_type& __a = allocator_type())
      : _Base(__a)
      { insert(begin(), __first, __last); }

      list(const list<_Tp, _Alloc>& __x)
      : _Base(__x.get_allocator())
      { insert(begin(), __x.begin(), __x.end()); }

      ~list()
      { }

      list<_Tp, _Alloc>&
      operator=(const list<_Tp, _Alloc>& __x);

    public:
      // assign(), a generalized assignment member function.  Two
      // versions: one that takes a count, and one that takes a range.
      // The range version is a member template, so we dispatch on whether
      // or not the type is an integer.

      void
      assign(size_type __n, const _Tp& __val)
      { _M_fill_assign(__n, __val); }

      void
      _M_fill_assign(size_type __n, const _Tp& __val);

      template<typename _InputIterator>
        void
        assign(_InputIterator __first, _InputIterator __last)
        {
          typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
          _M_assign_dispatch(__first, __last, _Integral());
        }

      template<typename _Integer>
        void
        _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
        { _M_fill_assign((size_type) __n, (_Tp) __val); }

      template<typename _InputIterator>
        void
        _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
                           __false_type);

    protected:
      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;
        }
      }

    public:
      void
      splice(iterator __position, list& __x)
      {
        if (!__x.empty()) 
          this->_M_transfer(__position, __x.begin(), __x.end());
      }

      void
      splice(iterator __position, list&, iterator __i)
      {
        iterator __j = __i;
        ++__j;
        if (__position == __i || __position == __j) return;
        this->_M_transfer(__position, __i, __j);
      }

      void
      splice(iterator __position, list&, iterator __first, iterator __last)
      {
        if (__first != __last) 
          this->_M_transfer(__position, __first, __last);
      }

      void
      remove(const _Tp& __value);

      void
      unique();

      void
      merge(list& __x);

      void
      reverse();

      void
      sort();

      template<typename _Predicate>
        void
        remove_if(_Predicate);

      template<typename _BinaryPredicate>
        void
        unique(_BinaryPredicate);

      template<typename _StrictWeakOrdering>
        void
        merge(list&, _StrictWeakOrdering);

      template<typename _StrictWeakOrdering>
        void
        sort(_StrictWeakOrdering);
    };

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

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

  template<typename _Tp, typename _Alloc>
    inline bool
    operator!=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
    { return !(__x == __y); }

  template<typename _Tp, typename _Alloc>
    inline bool
    operator>(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
    { return __y < __x; }

  template<typename _Tp, typename _Alloc>
    inline bool
    operator<=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
    { return !(__y < __x); }

  template<typename _Tp, typename _Alloc>
    inline bool
    operator>=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
    { return !(__x < __y); }

  template<typename _Tp, typename _Alloc>
    inline void 
    swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
    { __x.swap(__y); }

  // move these to stl_list.tcc

  template<typename _Tp, typename _Alloc>
    void _List_base<_Tp,_Alloc>::
    clear() 
    {
      _List_node<_Tp>* __cur = static_cast<_List_node<_Tp>*>(_M_node->_M_next);
      while (__cur != _M_node) {
        _List_node<_Tp>* __tmp = __cur;
        __cur = static_cast<_List_node<_Tp>*>(__cur->_M_next);
        _Destroy(&__tmp->_M_data);
        _M_put_node(__tmp);
      }
      _M_node->_M_next = _M_node;
      _M_node->_M_prev = _M_node;
    }

  template<typename _Tp, typename _Alloc>
    template <typename _InputIter>
      void list<_Tp, _Alloc>::
      _M_insert_dispatch(iterator __position, _InputIter __first, _InputIter __last,
                                            __false_type)
      {
        for ( ; __first != __last; ++__first)
          insert(__position, *__first);
      
      }

  template<typename _Tp, typename _Alloc>
    void list<_Tp, _Alloc>::
    _M_fill_insert(iterator __position, size_type __n, const _Tp& __x)
    {
      for ( ; __n > 0; --__n)
        insert(__position, __x);
    }

  template<typename _Tp, typename _Alloc>
    typename list<_Tp,_Alloc>::iterator list<_Tp, _Alloc>::
    erase(iterator __first, iterator __last)
    {
      while (__first != __last)
        erase(__first++);
      return __last;
    }

  template<typename _Tp, typename _Alloc>
    void list<_Tp, _Alloc>::
    resize(size_type __new_size, const _Tp& __x)
    {
      iterator __i = begin();
      size_type __len = 0;
      for ( ; __i != end() && __len < __new_size; ++__i, ++__len)
        ;
      if (__len == __new_size)
        erase(__i, end());
      else                          // __i == end()
        insert(end(), __new_size - __len, __x);
    }

  template<typename _Tp, typename _Alloc>
    list<_Tp, _Alloc>& list<_Tp, _Alloc>::
    operator=(const list<_Tp, _Alloc>& __x)
    {
      if (this != &__x) {
        iterator __first1 = begin();
        iterator __last1 = end();
        const_iterator __first2 = __x.begin();
        const_iterator __last2 = __x.end();
        while (__first1 != __last1 && __first2 != __last2) 
          *__first1++ = *__first2++;
        if (__first2 == __last2)
          erase(__first1, __last1);
        else
          insert(__last1, __first2, __last2);
      }
      return *this;
    }

  template<typename _Tp, typename _Alloc>
    void list<_Tp, _Alloc>::
    _M_fill_assign(size_type __n, const _Tp& __val) {
      iterator __i = begin();
      for ( ; __i != end() && __n > 0; ++__i, --__n)
        *__i = __val;
      if (__n > 0)
        insert(end(), __n, __val);
      else
        erase(__i, end());
    }

  template<typename _Tp, typename _Alloc>
    template <typename _InputIter>
      void list<_Tp, _Alloc>::
      _M_assign_dispatch(_InputIter __first2, _InputIter __last2, __false_type)
      {
        iterator __first1 = begin();
        iterator __last1 = end();
        for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
          *__first1 = *__first2;
        if (__first2 == __last2)
          erase(__first1, __last1);
        else
          insert(__last1, __first2, __last2);
      }

  template<typename _Tp, typename _Alloc>
    void list<_Tp, _Alloc>::
    remove(const _Tp& __value)
    {
      iterator __first = begin();
      iterator __last = end();
      while (__first != __last) {
        iterator __next = __first;
        ++__next;
        if (*__first == __value) erase(__first);
        __first = __next;
      }
    }

  template<typename _Tp, typename _Alloc>
    void list<_Tp, _Alloc>::
    unique()
    {
      iterator __first = begin();
      iterator __last = end();
      if (__first == __last) return;
      iterator __next = __first;
      while (++__next != __last) {
        if (*__first == *__next)
          erase(__next);
        else
          __first = __next;
        __next = __first;
      }
    }

  template<typename _Tp, typename _Alloc>
    void list<_Tp, _Alloc>::
    merge(list<_Tp, _Alloc>& __x)
    {
      iterator __first1 = begin();
      iterator __last1 = end();
      iterator __first2 = __x.begin();
      iterator __last2 = __x.end();
      while (__first1 != __last1 && __first2 != __last2)
        if (*__first2 < *__first1) {
          iterator __next = __first2;
          _M_transfer(__first1, __first2, ++__next);
          __first2 = __next;
        }
        else
          ++__first1;
      if (__first2 != __last2) _M_transfer(__last1, __first2, __last2);
    }

  inline void
  __List_base_reverse(_List_node_base* __p)
  {
    _List_node_base* __tmp = __p;
    do {
      std::swap(__tmp->_M_next, __tmp->_M_prev);
      __tmp = __tmp->_M_prev;     // Old next node is now prev.
    } while (__tmp != __p);
  }

  template<typename _Tp, typename _Alloc>
  inline void list<_Tp, _Alloc>::
  reverse() 
  { __List_base_reverse(this->_M_node); }    

  template<typename _Tp, typename _Alloc>
    void list<_Tp, _Alloc>::
    sort()
    {
      // Do nothing if the list has length 0 or 1.
      if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
        list<_Tp, _Alloc> __carry;
        list<_Tp, _Alloc> __counter[64];
        int __fill = 0;
        while (!empty()) {
          __carry.splice(__carry.begin(), *this, begin());
          int __i = 0;
          while(__i < __fill && !__counter[__i].empty()) {
            __counter[__i].merge(__carry);
            __carry.swap(__counter[__i++]);
          }
          __carry.swap(__counter[__i]);         
          if (__i == __fill) ++__fill;
        } 

        for (int __i = 1; __i < __fill; ++__i)
          __counter[__i].merge(__counter[__i-1]);
        swap(__counter[__fill-1]);
      }
    }

  template<typename _Tp, typename _Alloc>
    template <typename _Predicate>
      void list<_Tp, _Alloc>::
      remove_if(_Predicate __pred)
      {
        iterator __first = begin();
        iterator __last = end();
        while (__first != __last) {
          iterator __next = __first;
          ++__next;
          if (__pred(*__first)) erase(__first);
          __first = __next;
        }
      }

  template<typename _Tp, typename _Alloc>
    template <typename _BinaryPredicate>
      void list<_Tp, _Alloc>::
      unique(_BinaryPredicate __binary_pred)
      {
        iterator __first = begin();
        iterator __last = end();
        if (__first == __last) return;
        iterator __next = __first;
        while (++__next != __last) {
          if (__binary_pred(*__first, *__next))
            erase(__next);
          else
            __first = __next;
          __next = __first;
        }
      }

  template<typename _Tp, typename _Alloc>
    template <typename _StrictWeakOrdering>
      void list<_Tp, _Alloc>::
      merge(list<_Tp, _Alloc>& __x, _StrictWeakOrdering __comp)
      {
        iterator __first1 = begin();
        iterator __last1 = end();
        iterator __first2 = __x.begin();
        iterator __last2 = __x.end();
        while (__first1 != __last1 && __first2 != __last2)
          if (__comp(*__first2, *__first1)) {
            iterator __next = __first2;
            _M_transfer(__first1, __first2, ++__next);
            __first2 = __next;
          }
          else
            ++__first1;
        if (__first2 != __last2) _M_transfer(__last1, __first2, __last2);
      }

  template<typename _Tp, typename _Alloc>
    template <typename _StrictWeakOrdering>
    void list<_Tp, _Alloc>::
    sort(_StrictWeakOrdering __comp)
    {
      // Do nothing if the list has length 0 or 1.
      if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
        list<_Tp, _Alloc> __carry;
        list<_Tp, _Alloc> __counter[64];
        int __fill = 0;
        while (!empty()) {
          __carry.splice(__carry.begin(), *this, begin());
          int __i = 0;
          while(__i < __fill && !__counter[__i].empty()) {
            __counter[__i].merge(__carry, __comp);
            __carry.swap(__counter[__i++]);
          }
          __carry.swap(__counter[__i]);         
          if (__i == __fill) ++__fill;
        } 

        for (int __i = 1; __i < __fill; ++__i) 
          __counter[__i].merge(__counter[__i-1], __comp);
        swap(__counter[__fill-1]);
      }
    }

} // namespace std 

#endif /* __GLIBCPP_INTERNAL_LIST_H */

// vi:set ts=2 sw=2:
// Local Variables:
// mode:C++
// End: