https://blog.csdn.net/y1196645376/article/details/52938474
在使用STL各类容器的时候，有时会出现迭代器失效，引用(指针)失效等情况的而发生，即使看似你的操作都是合法的情况下；
首先我们把以上的问题分成两类：
容器的迭代器为什么会失效？容器元素的引用(指针)为什么会失效？
问题： 容器的迭代器为什么会失效？即容器的元素在容器内部搬家了；
我们可以把容器看做是一个小镇，有一个个的房子;而元素就是相当于住在房子里面的人;现在，假如小镇又搬进来一户人家。小镇自然需要为这户人家安排一户房子： 假如是空房子还好(只需要住进去就行)；如果新来的这户人家看中了已经居住的某户人家的房子，那么肯定需要之前那户人家搬出来，然后才能进去住; 而某些容器中为了保证数据的顺序一致性，就会出现下面的情况： 很显然，如果出现了以上图片所示的情况，那么就相当于容器的元素在容器内部搬家了，因为或多或少的造成了其他元素搬家;而迭代器相当于什么呢？恩，我们可以在这里把它当做是房子的门牌号(每个房子的门牌号都不一样);以前我们知道通过一户人家的门牌号就可以很容易找到这户人家。但是，如果该户人家搬家了呢? 对，正是这样的”搬家”导致容器的迭代器失效;各类容器发生迭代器失效的情况：
可以看出来非线性表的适应性是最好的，因为不需要内存地址连续;而线性表中，不适宜的插入删除位置会使得迭代器失效。(使得迭代器失效还有一种情况：容器存储空间的重新分配)删除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双端队列的元素地址; 如果当容器中进行了内存重新分配,那么元素的物理存储地址必然改变，所以这就是导致引用和指针失效的原因；各类容器发生引用(指针)失效的情况：
后记：值得注意的是,不同的编译器对于stl内存管理策略可能略有差别;
我们知道 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中插入很多记录，比如说100000条，为了避免在插入过程中移动内存，咱实现向系统预订一段足够的连续的空间：a.reserve(100000);
