`
xinyiwust
  • 浏览: 13059 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

stl list源码学习笔记

    博客分类:
  • C++
阅读更多
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
0
6
分享到:
评论
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这个函数

相关推荐

Global site tag (gtag.js) - Google Analytics