Question

c++ STL 迭代器失效问题

请教大家一个问题 在对容器元素进行添加和删除时，iterator会部分或全部的失效。下面一个例子
vector<int>::iterator first=v.begin(),last=v.end();
while(first!=last){
//do some processing
//insert new value and reassign first,which otherwise would be invalid
first=v.insert(first,42);
++first;
}
上述代码的行为未定义，原因是循环体中实现了元素的添加运算，添加元素使得存储在last中的迭代器失效。该迭代器既没有指向容器的v元素，也不再指向v的超出末端的下一个位置。
问题1：为什么“该迭代器既没有指向容器的v元素，也不再指向v的超出末端的下一个位置”。迭代器不是一个指针吗？虽然删除了他指向的元素，但在他所指向的地址又添加了其他元素，为什么会不指向容器中的元素呢？
问题2：对于vector类型的容器，当在其中（非末端下一个位置）插入元素时，是不是插入点以后的所有元素都向后移动？

Answer 1

迭代器失效,有两个层面的意思，
1) 无法通过迭代器++,--操作遍历整个stl容器。记作: 第一层失效。
2) 无法通过迭代器存取迭代器所指向的内存。 记作: 第二层失效。
关于这个问题, 不同的容器对应的结果是不同的。
vector
vector是个连续内存存储的容器，如果vector容器的中间某个元素被删除或从中间插入一个元素， 有可能导致内存空间不够用而重新分配一块大的内存。
这个动作将导致先前获取的迭代器,，第一层和第二层均失效。
map
map内部是红黑树结构，当map中新插入或删除元素后，树的结构会相应的调整。
但是，通过先前的迭代器，仍然可以通过++可以遍历map。 能遍历到值>当前迭代器的节点。 (没有看具体stl内部实现,初步代码验证正确)
迭代器指向的用户数据内存始终有效。
list
同理map, 通过++只能遍历链表右侧的节点，迭代器指向的用户数据内存也始终有效。

Answer 2

你可以把迭代器理解为，用对象封装的指针（实际上并不是一定这样，但是你可以这么去理解）。

迭代器失效是因为，某一些容器在进行一些操作的时候，会因为各种原因（比如之前分配的内存不够啊等等）申请新的内存地址，并把数据转移过去，老的内存有可能会被释放。

迭代器就好比门牌号一样，你现在在一栋楼里，挨个门访问。

突然，楼里面的居民全部搬家了，这时候你还去访问以前的那个门牌号，那肯定你是找不到人的。

这个时候，你需要想办法拿到新的地址，这样你可以接着访问。

调用任何vector的non const函数都有可能使之前获得的迭代器失效。例如push back，insert，erase等等。

至于在容量足够的情况下，添加元素必然会使从添加位置起的所有迭代器失效（因为数据被移动了）。

要处理这种情况也很简单，就是在每一次有可能使迭代器失效的操作进行之后，重新取迭代器。

也就是，在insert后面加一行 last = v。end（）

while (first != last) {
    //do some processing
    //insert new value and reassign first,which otherwise would be invalid
    first = v.insert(first, 42);
    ++first;
    ++first;
    last = v.end();
}

Answer 3

问题一：先看一段话
在创建一个vector 后，它会自动在内存中分配一块连续的内存空间进行数据存储，初始的空间大小可以预先指定也可以由vector 默认指定，这个大小即capacity （）函数的返回值。当存储的数据超过分配的空间时vector 会重新分配一块内存块，但这样的分配是很耗时的，在重新分配空间时它会做这样的动作：
首先，vector 会申请一块更大的内存块；
然后，将原来的数据拷贝到新的内存块中；
其次，销毁掉原内存块中的对象（调用对象的析构函数）；
最后，将原来的内存空间释放掉。

可以发现，如果你插入的值使得vector的预先分配容量不够用时，vector将会重新申请一块内存，那么原来的内存就无效了，虽然存在原来的地址还在使用并且添加了其他元素，但是这是不安全的，因为你不知道什么时候重新申请了新内存。所以vector不允许这样做。

问题2：
是的，因为vector是连续存储，这也是问题一的原因

追问

如果添加一个元素时内存够用，不需要重新分配 ,将元素向后移 迭代器原先所指向的地址不是又添加了其他元素
这时迭代器为什么也会失效呢

追答

当不需要重新分配时，迭代器原先所指向的地址确实变成了其他元素，这个我已经验证过了。说它失效是因为我们不知道什么时候vector会重新申请内存，我们不能做没有把握的事。即使vector没有重新分配内存，迭代器所指向的内容也不是我们所需要的了，对它做操作没有意义。你也不要纠结于“失效”这两个字，当迭代器的行为不可预知时，我们就认为它是失效的。

Answer 4

你这个是一个死循环。