STL容器的迭代器失效的原因

c++ STL容器的内存分配

一.前言
在使用STL各类容器的时候，有时会出现迭代器失效，引用(指针)失效等情况的而发生，即使看似你的操作都是合法的情况下。

要了解问题的原因，我们就要了解C++中stl容器的内存分配策略。我们才知道在哪些操作下可能导致迭代器失效，引用(指针)失效。

二.问题分类
首先我们把以上的问题分成两类：

容器的迭代器为什么会失效？
容器元素的引用(指针)为什么会失效？
因为从内存角度上来讲，如果引用是失效了那么指针也就是失效了，也就是容器的该元素从这个内存地址搬家了！

三.第一类问题分析
问题： 容器的迭代器为什么会失效？

对于上面的问题我们可以换个说法：容器的元素在容器内部搬家了。

我们可以把容器看做是一个小镇，有一个个的房子(无论是list,vector还是其他的,只是房子之间的联系关系不同。不过这不在我们目前考虑范围)；
而元素就是相当于住在房子里面的人。
现在，假如小镇又搬进来一户人家。小镇自然需要为这户人家安排一户房子：

假如是空房子还好(只需要住进去就行)；
如果新来的这户人家看中了已经居住的某户人家的房子，那么肯定需要之前那户人家搬出来，然后才能进去住。而某些容器中为了保证数据的顺序一致性，就会出现下面的情况：

很显然，如果出现了以上图片所示的情况，那么就相当于容器的元素在容器内部搬家了，因为或多或少的造成了其他元素搬家。
而迭代器相当于什么呢？恩，我们可以在这里把它当做是房子的门牌号(每个房子的门牌号都不一样)。
以前我们知道通过一户人家的门牌号就可以很容易找到这户人家。但是，如果该户人家搬家了呢？
对，正是这样的”搬家”导致容器的迭代器失效。

问题原因找出来了，我们下面就来总结一下，各类容器发生迭代器失效的情况：

可以看出来非线性表的适应性是最好的，因为不需要内存地址连续。
而线性表中，不适宜的插入删除位置会使得迭代器失效。(使得迭代器失效还有一种情况：容器存储空间的重新分配,我们后面来讲)

下面我来举个例子：
给定一个容器 vector< int >vi，删除容器中所有为3的元素。

下面是两个版本的代码：

代码1：

for(auto it = vi.begin();it != vi.end();)
{
    if(*it == 3) it = vi.erase(it);
    else it ++;
}

代码2：

auto end = vi.end();
for(auto it = vi.begin();it != end;)
{
    if(*it == 3) it = vi.erase(it);
    else it ++;
}

可能代码2的作者是考虑到每次循环都需要调用vi.end()的开销，于是就在循环外记录了尾后迭代器。
然而在上面的代码中。由于在循环内部可能会调用erase的函数；也就是说一旦发生删除，那么尾后迭代器就会失效。所以代码2是错误的！！
不过还有个地方值得注意：删除erase的时候会使得it迭代器失效，所以需要用it来接受erase函数的返回值。

四.第二类问题分析
问题： 容器元素的引用或指针为什么会失效？

这个问题就是涉及到了不同容器中如何去管理内存的。以下用 vector(string) 和 deque 来举例。

• vector(string 可看做vector< char >)

为了支持快速随机访问，vector只能将元素连续存储——每个元素紧挨着前一个元素存储。然而当我们向vector 或者string添加元素的时候；如果没有空间容纳新元素，容器不可能简单地把它添加在内存的其他位置——因为元素必须连续存储。容器就必须重新分配新的内存空间来保存已有的元素和新元素，将旧元素移动到新空间，然后添加新的元素。

• deque

deque看似和vector很相似，但是 deque 能高效的在首位进行元素的插入删除；并且 deque 也支持随机访问；说明 deque 的内部内存实现要比vector复杂得多。事实上 deque 采用的是动态内存块的策略，块的内部是一段连续的内存，但是块与块之间物理内存不一定连续。

deque的元素数据采用分块的线性结构进行存储，如图所示。deque分成若干线性存储块，称为deque块。块的大小一般为512个字节，元素的数据类型所占用的字节数，决定了每个deque块可容纳的元素个数。

所有的deque块使用一个Map块进行管理，每个Map数据项记录各个deque块的首地址。Map是deque的中心部件，将先于deque块，依照deque元素的个数计算出deque块数，作为Map块的数据项数，创建出Map块。以后，每创建一个deque块，都将deque块的首地址存入Map的相应数据项中。

在Map和deque块的结构之下，deque使用了两个迭代器M_start和M_finish，对首个deque块和末deque块进行控制访问。迭代器iterator共有4个变量域，包括M_first、M_last、M_cur和M_node。M_node存放当前deque块的Map数据项地址，M_first和M_last分别存放该deque块的首尾元素的地址（M_last实际存放的是deque块的末尾字节的地址），M_cur则存放当前访问的deque双端队列的元素地址。

简单介绍了 vector 和 deque 的内存管理策略之后；我们知道，如果当容器中进行了内存重新分配。那么元素的物理存储地址必然改变，所以这就是导致引用和指针失效的原因！！

我们下面就来总结一下，各类容器发生引用(指针)失效的情况：

五.后话
值得注意的是，不同的编译器对于stl内存管理策略可能略有差别。下面拿 vector 举例：

我们知道 vector 的内存管理策略是：当push_back的时候发现容量不够存储新的元素就需要去开辟一个更大的内存，然后将旧元素复制过去，然后再加入新元素。

那么有个问题是：当容量不够的时候需要开辟一个多大的内存呢？这个实现机制在不同的编译器中就可能有不同。

目前我见过有三个版本的：

• VS2013自带G++编译器 ： 每次开辟新内存比原来多一个元素内存。
• VS2010自带G++编译器： 每次开闭新内存比原来容量多一半。(*150%)
• CodeBlocks自带GCC编译器： 每次开辟新内存为原来容量的一倍。(*200%)

不管开辟内存的策略如何，总需要满足一个定则：
在一个初始化为空的 vector 上调用n次push_back来创建一个n个元素的vector，所花费时间不能超过n的常数倍。

还有一个值得注意的地方就是：
对于vector的 pop_back 或者 erase ,clear 只会减小容器的元素个数，并不会减少容器的容量。resize也是一样，如果小于size。只会使得容器元素个数减小，容器的容量不会减小。

换句话来说，一个vector容器对象容量是只增不减的。只会在析构函数的时候对占用内存进行释放。

当然以上问题也不是不可以解决的：

使用swap函数可以使得两个vector对象内部元素甚至所占内存空间都互换。
比如想释放vector< int > vt 占用的内存：

• 清空所有元素，释放所有容量

vector<int>().swap(vt);

• 元素不改变，释放多余的容量

vector<int>(vt).swap(vt);

从第二段代码我们也可以得知，vector 的拷贝构造函数只是会将元素拷贝过来，而容量也只是会初始化为和元素个数一样。

还值得注意的一个地方是：

如果会需要向一个vector中插入很多记录，比如说100000条，为了避免在插入过程中移动内存，咱实现向系统预订一段足够的连续的空间，例如：

a.reserve(100000);