使用STL容器的一些常识

stl这种东西这几年确实用得不少了,大一暑假刚开始看c++primer的时候就知道有这么个东西,当时觉得非常神奇的样子。不过,我用stl最多的地方还是在做acm的一些题目的时候。很多时候为了方便,为了代码简洁性就用stl了。我还是比较喜欢stl这个东西的。

我只打算讲点简单的东西。比如大致的实现原理和使用的一些注意情况,另外讲下我对迭代器失效的理解。

vector是一个动态数组,既然是数组,那么在末尾增加和删除是很快的,复杂度是O(1)。但是,在其它位置增加和删除复杂度就跟位置有关系了,复杂度是O(n)。默认情况对vector的查找是不会应用二分的,所以你用stl里面的find查找复杂度也是O(n)。当vector的容量大小需要经常改变时候,你可以预估计容量的最大大小,然后调用reserve函数预分配一块大内存,这样就可以避免频繁的内存分配释放造成的性能损失了。

deque类似于vector。但是在头部增加和删除复杂度也是O(1),不过我没看过stl的实现,也不知道为什么。

list的内部实现大概是双向链表。那么在任意位置的插入和删除复制度都是O(1)。对于查找的话,虽然理论复杂度也是O(n)。不过,list的查找肯定会比vector慢的,因为多了一次取地址的间接操作。而且,数组因为地址是连续的,可以来个地址的缓存。

set和map内部是用红黑树实现的。红黑树也就是一棵平衡查找树吧,大家都学过二叉平衡树,红黑树大概类似这种东西。算法导论里面有对红黑树的详细介绍,不过看得让我很头晕,而且我也不想去实现一个红黑树,光是二叉平衡树的旋转已经很无语了。反正红黑树类似二叉平衡查找树就行了。那么,红黑树的插入删除都可能改变原有结点的位置之间的关系,意思是不仅仅是破坏或者增加一个结点的位置。但是原有结点的地址肯定是没有变化的。增删查改的复杂度都是log(n)。还有,对set和map的查找要应用容器内部的成员函数find,而不是全局的stl函数find。前者是二分查找,而后者是顺序查找。

下面我讲讲我对stl迭代器失效的理解。其实,大致知道了stl容器的实现,这个问题就很好理解了。

vector是动态数组,那么插入和删除元素都会改变该元素后面元素的地址,那么先前获取的指向后面位置元素的迭代器就会失效了。而且即使你插入在最后,也可能使所有的迭代器失效,因为可能这个时候刚好vector必须增加容量来容纳你新插入的元素了。你再访问这些迭代器的话,不是访问到错误的内容就是内存错误了。

list的话,由于结点是孤立的,是用指针把所有结点串起来的,那么原有结点的地址一直都不会改变。只要不对结点进行了删除,那么原来获取的迭代器就不会失效。但是,++和–的结果可能会和原来不一致的。

deque类似于vector吧。不过,我还是不是很清楚。

set和map的话,类似于list。它们的结点地址也一直不会变化,但是插入和删除会改变整棵树的布局,所以原来的迭代器++或者–之后可能就会指向乱七八糟的东西了。但是,你获取原来的元素还是可以的。

总之,对容器进行插入和删除之后一定要注意迭代器失效的情况,最好是从写法上避免这种可能性吧,而不是利用迭代器不失效的可能性。