stl list源码学习笔记

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

C++代码  

1. template <class T, class Alloc>    
2. void list<T, Alloc>::unique()    
3. {    
4.   iterator first = begin();    
5.   iterator last = end();    
6.   if (first == last) return;    
7.   iterator next = first;    
8.   while (++next != last)    
9.   {    
10.     if (*first == *next)    
11.       erase(next);    
12.     else    
13.       first = next;    
14.     next = first;    
15.   }    
16. }    

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

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

C++代码  

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

size()的代码如下：

C++代码  

1. size_type size() const    
2.   {    
3.       size_type result = 0;    
4.       distance(begin(), end(), result);    
5.       return result;    
6.   }   

其中的distance的源码如下：

C++代码  

1. template <class _InputIterator, class _Distance>  
2. inline void __distance  
3. (_InputIterator __first,  
4.    _InputIterator __last,  
5.    _Distance& __n,  
6.    input_iterator_tag)  
7. {  
8.    while (__first != __last) { ++__first; ++__n; }  
9. }  
10.   
11. template <class _RandomAccessIterator, class _Distance>  
12. inline void __distance  
13. (_RandomAccessIterator __first,  
14.    _RandomAccessIterator __last,  
15.    _Distance& __n,  
16.    random_access_iterator_tag)  
17. {  
18.    __n += __last - __first;  
19. }  
20. template <class _InputIterator, class _Distance>  
21. inline void distance  
22. (_InputIterator __first,  
23.    _InputIterator __last,  
24.    _Distance& __n)  
25. {  
26.    __distance(__first, __last, __n, iterator_category(__first));  
27. }  

从

C++代码  

1. 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。

http://xinyiwust.iteye.com/blog/1667892