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。它们的结点地址也一直不会变化，但是插入和删除会改变整棵树的布局，所以原来的迭代器++或者—之后可能就会指向乱七八糟的东西了。但是，你获取原来的元素还是可以的。
总之，对容器进行插入和删除之后一定要注意迭代器失效的情况，最好是从写法上避免这种可能性吧，而不是利用迭代器不失效的可能性。