vector

vector是一个顺序容器，在内存中是一块连续的内存。引起内存重新分配的插入运算使所有迭代器失效，插入也使得插入位置及其后位置的迭代器失效，删除运算使得删除位置及其后位置的迭代器失效.

迭代器失效

  1. push_back操作:end操作返回的迭代器肯定失效，一旦引发内存重分配，所有迭代器都会失效；判断是否发生内存分配可以比较capacity的返回值。

  2. insert操作 插入点之后的所有迭代器失效；但一旦引发内存重分配，所有迭代器都会失效；

  3. erase操作 插入点之后的所有迭代器失效；

  4. reserve操作 所有迭代器失效（因为它导致内存重分配）；

删除某迭代器的正确方法

erase迭代器不仅使所指向被删元素的迭代器失效，而且使被删元素之后的所有迭代器失效，所以不能使用erase(iter++)的方式，但是erase的返回值为下一个有效的迭代器。

所以正确方法为::

for( iter = c.begin(); iter != c.end(); )
      iter = c.erase(iter);

deque

deque由一段一段的定量连续空间构成，采用一个表（map）来记录每个连续空间的首址，map是一小块连续的空间，目的是便于迭代器的寻址（map+1即可跳转到下一个连续空间的首址）。map中的每一个元素（node）都是指针，指向另一端（较大的）连续线性空间，称为缓冲区，缓冲区才是deque的储存空间主体。可动态增加或减少元素，内存管理自动完成，不提供用于内存管理的成员函数。

其中，对迭代器it的解引用得到的是cur位置处对应的元素。

deque要求map中前后各预留一个node节点，以便扩充时可用。

迭代器失效

下面讨论插入删除操作，deque中的迭代器、引用失效问题。

查看deque源码可知，在push_front/push_back中，由于要满足以上预留一个节点的要求，若当前map所管理的节点个数不足以扩充时，map需要重分配。如下图所示：

当前deque中含有23个元素，此时push_back（23），会导致node节点不足，于是引起map的重分配。

原来的迭代器的node指向的map节点被释放，也就无法找到对应的元素，故原迭代器失效。而由于这个过程中内存并未发生改变，故其他元素的引用、指针仍然有效。push_front同理。

pop_front，pop_back只是简单的析构元素，必要时（第一个缓冲区、最后一个缓冲区只有一个元素）释放该缓冲区、调整start、finish迭代器的状态，所以指向其他元素的迭代器有效。

除了头尾两端，在任何地方插入和删除元素都将导致内存重新分配，导致指向deque元素的任何迭代器失效。

总结：

  1. 插入头尾，一般指向其他元素的迭代器不失效，也可能会失效，取决于是否进行内存重新分配；插入其他位置。指向其他元素的迭代器、指针、引用失效

  2. 删除头尾，指向其他元素的迭代器有效；删除其他位置，指向其他元素的迭代器失效。

map和set

map和set是关联容器，以红黑树组织数据，虽然删除了一个元素，整棵树也会调整，以符合红黑树或者二叉树的规范，但是单个节点在内存中的地址没有变化，变化的是各节点之间的指向关系。插入、删除一个迭代器不会对其他迭代器造成影响

删除某迭代器的正确方法

C++11之前的做法

erase迭代器只是被删元素的迭代器失效，但是返回值为void，所以要采用erase(iter++)的方式删除迭代器，

所以正确方法为::

for( iter = c.begin(); iter != c.end(); )
c.erase(iter++);
unordered_set和unordered_map

它里面的元素不一定是按键值排序的，而是按照所用的hash函数分派的，它能提供更快的搜索速度（当前和hash函数有关）。

###C++11之后的做法

(1)

iterator  erase (const_iterator position);

(2)

size_type erase (const value_type& val);

(3)

iterator  erase (const_iterator first, const_iterator last);

C++11已经将map,set和vector,deque的erase函数的返回值统一,所以不需要使用上述方法了

1
2

for( auto iter = c.begin(); iter != c.end(); )
      iter = c.erase(iter);

list

内部数据结构为双向环状链表。不能随机访问一个元素。可双向遍历。可动态增加或减少元素，内存管理自动完成。

迭代器失效

插入：增加任何元素都不会使迭代器失效。

删除：删除元素时，除了指向当前被删除元素的迭代器外，其它迭代器都不会失效。

对于list型的数据结构，使用了不连续分配的内存，删除运算使指向删除位置的迭代器失效，但是不会失效其他迭代器.解决办法两种，erase(*iter)会返回下一个有效迭代器的值，或者erase(iter++).

slist

内部数据结构：单向链表。

不可双向遍历，只能从前到后地遍历。

其它的特性同list相似。

建议：

  1. 尽量不要使用slist的insert，erase，previous等操作。因为这些操作需要向前遍历，但是slist不能直接向前遍历，所以它会从头开始向后搜索，所需时间与位于当前元素之前的元素个数成正比。

  2. slist专门提供了insert_after，erase_after等函数进行优化。 但若经常需要向前遍历，建议选用list。

Stack

适配器，它可以将任意类型的序列容器转换为一个堆栈，一般使用deque作为支持的序列容器。

元素只能后进先出（LIFO）。

不能遍历整个stack。

queue

适配器，它可以将任意类型的序列容器转换为一个队列，一般使用deque作为支持的序列容器。

元素只能先进先出（FIFO）。

不能遍历整个queue。

priority_queue

适配器，它可以将任意类型的序列容器转换为一个优先级队列，一般使用vector作为底层存储方式。

只能访问第一个元素，不能遍历整个priority_queue。

第一个元素始终是优先级最高的一个元素。

转载：http://blog.csdn.net/hackbuteer1/article/details/7734382