stl list源码学习笔记

1.list中有一个unique函数，这个函数容易给人造成一种错觉：直接调用它就可以移除list中的重复元素。其实不然，unique函数实现如下：

template <class T, class Alloc>  
void list<T, 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;  
  }  
}  

由代码可知，unique函数只能移除相邻的重复结点，故若要移除list中重复的节点，应该先排序（sort），然后再调用unique。

2.list的size()函数的时间复杂度是o(n)，这一点要尤其注意，判断list是否为空的时候应该使用empty()而不是0 == size()。empty(）的代码如下：

bool empty() const { return node->next == node; }  

size()的代码如下：

  size_type size() const  
    {  
        size_type result = 0;  
        distance(begin(), end(), result);  
        return result;  
    } 

其中的distance的源码如下：

template <class _InputIterator, class _Distance>
inline void __distance
(_InputIterator __first,
   _InputIterator __last,
   _Distance& __n,
   input_iterator_tag)
{
   while (__first != __last) { ++__first; ++__n; }
}

template <class _RandomAccessIterator, class _Distance>
inline void __distance
(_RandomAccessIterator __first,
   _RandomAccessIterator __last,
   _Distance& __n,
   random_access_iterator_tag)
{
   __n += __last - __first;
}
template <class _InputIterator, class _Distance>
inline void distance
(_InputIterator __first,
   _InputIterator __last,
   _Distance& __n)
{
   __distance(__first, __last, __n, iterator_category(__first));
}

从

 while (__first != __last) { ++__first; ++__n; }

中可以看出，其时间复杂度确实是o(n)。至于size()为什么要这样写，请参考：http://hi.baidu.com/acojvbqaknbgmud/item/c4c1d0c55d5b7629ef466525.

3.要注意list的成员函数remove_if和stl提供的泛型算法remove_if的区别，具体请参考http://blog.csdn.net/steven_wang787/article/details/4513121。

评论

4 楼 巴巴米 2012-08-30  

xinyiwust 写道

巴巴米 写道

看了半天才发现是c++，我说我怎么没见过unique这个函数

哈哈，java中还没听说过stl呢。。。

是啊，我就是被stl吸引进来的

3 楼 sdujq 2012-08-30  

巴巴米 写道

看了半天才发现是c++，我说我怎么没见过unique这个函数

+1

2 楼 xinyiwust 2012-08-30  

巴巴米 写道

看了半天才发现是c++，我说我怎么没见过unique这个函数

哈哈，java中还没听说过stl呢。。。

1 楼 巴巴米 2012-08-30  

看了半天才发现是c++，我说我怎么没见过unique这个函数