C++-deque的插入和删除操作会使迭代器失效么

Question

STL容器deque，向其中一个位置插入一个元素和删除一个位置上的元素底层是怎么实现的？操作后会使得其他位置上的迭代器失效吗？

Answer 1

deque 的存储方式是“分块双向链表”的结构，块内是连续的线性表，块间是双向链表。
在一个位置插入和删除一个元素，有可能使那个元素所在的块发生重新分配内存之类的情况，类似 vector 的实现方式，而迭代器是针对整个 deque 的。
在任何位置插入和删除元素，根据 deque 的存储特性，通常来说，只会是那个元素所在的块的迭代器失效（这个失效的原因与 vector 类似），但是我们没办法那些块有多大，也就没办法判断到底哪些迭代器失效了，所以必须重新获取。

Answer 2

关于迭代器失效，可以从另外的角度分为2种：逻辑失效和物理失效：
（1） 物理失效：因为对迭代器的插入（insert,push_back,push_front都有可能）工作使得迭代器重新分配内存，这种情况下容器的所有迭代器会物理失效，即他们所指向的已经不是该容器的元素而是未知指。
（2） 逻辑失效：即迭代器仍然指向该容器元素，但是它的值已经不是期望的值。如果对迭代器的操作没有使之重新分配内存，则对所有的顺序迭代器（vector,deque,list）push_back 一定使end逻辑失效，同理，对于（deque和list）push_fornt回使begin逻辑实效，对于vector和deque insert（）回使insert位置之后的所有迭代器实效。

vector迭代器的几种失效的情况：
1.当插入（push_back）一个元素后，end操作返回的迭代器肯定失效。
2.当插入(push_back)一个元素后，capacity返回值与没有插入元素之前相比有改变，则需要重新加载整个容器，此时first和end操作返回的迭代器都会失效。
3.当进行删除操作（erase，pop_back）后，指向删除点的迭代器全部失效；指向删除点后面的元素的迭代器也将全部失效。

deque迭代器的失效情况： ，在C++Primer一书中是这样限定的，
1.在deque容器首部或者尾部插入元素不会使得任何迭代器失效。
2.在其首部或尾部删除元素则只会使指向被删除元素的迭代器失效。
3.在deque容器的任何其他位置的插入和删除操作将使指向该容器元素的所有迭代器失效。

只有list的迭代器好像很少情况下会失效。也许就只是在删除的时候，指向被删除节点的迭代器会失效吧，其他的还没有发现。

Answer 3

会失效的。
根据《STL源码剖析》一书的介绍，deque是由一段一段的定量连续空间构成的。
浏览一下deque成员函数insert的源码，你会发现，如果对deque的插入点既不是最前端，也不是最尾端的话，插入操作会引起插入点之前或者之后的元素进行移动(调用copy函数)，这个操作势必会使相应的迭代器失效。
详情参考《STL源码剖析》一书。

Answer 4

一定会, deque在插入删除操作是迭代器需要重新获取, 一般stl中类似array的vector,deque,string这种插入和删除都会使迭代器失效
参考这里, 随时查查: http://www.cplusplus.com/reference/stl/

Answer 5

会的，任何的插入和删除操作都会是deque的迭代器失效。必须重新获取才可以是用的
----------------------对于说不失效的解答--------------------

#include <iostream>
#include <deque>
int main(int argc, char *argv[])
{
deque<int> iDeque;
deque<int>::iterator iter;
int i = 0;
while (i < 10)
{
iDeque.push_back(i);
++i;
}

iter = iDeque.begin();
iDeque.push_front(20);
std::cout<<*iter;//崩溃掉

system("PAUSE");
return 0;
}

认为插入或者删除不会导致迭代器失效的同学。可以运行这段代码，在我注释的那段会崩溃掉。无论是STL源码剖析4.4节说了什么，但是确实崩了，也就是说，迭代器失效了。

崩溃信息里面说的比较明确
expression:deque iterator not dereferencable
deque的迭代器不可引用