stl list源码学习札记

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。 1 楼 巴巴米 2012-08-30   看了半天才发现是c++，我说我怎么没见过unique这个函数 2 楼 xinyiwust 2012-08-30   巴巴米 写道看了半天才发现是c++，我说我怎么没见过unique这个函数
哈哈，java中还没听说过stl呢。。。 3 楼 sdujq 2012-08-30   巴巴米 写道看了半天才发现是c++，我说我怎么没见过unique这个函数
+1 4 楼 巴巴米 2012-08-30   xinyiwust 写道巴巴米 写道看了半天才发现是c++，我说我怎么没见过unique这个函数
哈哈，java中还没听说过stl呢。。。
是啊，我就是被stl吸引进来的

查看更多 下一篇