39 vector深入理解 · 迭代器失效深度浅拷贝
目录
一、迭代器失效
（一）外部迭代器失效
1、扩容引起的野指针问题
2、删除引起的逻辑问题
二、深度浅拷贝
一、迭代器失效
迭代器可以理解为像指针一样的类对象，但不要一味地认为迭代器就是指针，指针可以实现迭代器，但迭代器也可能是自定义类型，可以通过以下函数调用查看具体类型：
typeid(类型或者对象).name()typeid(vector<int>::iterator).name()（一）外部迭代器失效
上一节的末尾介绍的是一种内部迭代器失效，也有外部迭代器失效：
1、扩容引起的野指针问题
如下代码演示：
void test_vector01()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto& e : v1){cout << e << " ";}// 打印 1 2 3 4cout << endl;int x;cin >> x;auto it = find(v1.begin(),v1.end(),x);if (it != v1.end()){v1.insert(it, 10 * x);cout << *it << endl;}
}以上代码的功能是在x位置前插入10*x这个数。但在最后的 cout << *it << endl 处会发生迭代器失效的问题：因为 insert函数 是用形参接收实参，形参的改变不影响实参，insert函数虽然修正了形参pos的位置，但实参 it 的位置没有改变，依旧指向被释放的旧空间，是野指针，解引用野指针就会出现报错。
将insert函数的迭代器参数修改为iterator& pos是不是就可以了？
答：不行。因为若【迭代器运算的结果】做实参，如：it+2 传过去，这个it+2的结果会保留在一个临时的变量中，而临时变量具有常性，即不可修改（被const修饰），iterator&的话就会造成权限放大的问题。所以不能这样访问，且迭代器只有扩容的情况下才会失效，但我们又不知道什么时候扩容，所以默认迭代器失效了就不能访问。
解决：insert的返回值为【更新后的pos位置】，需要 insert 的话要用 it 接收新的 it 位置。insert代码修改如下：
iterator insert(iterator pos, const T& x)
{assert(pos >= _start && pos <= _finish);if (_finish == _endofstorage)//扩容{size_t len = pos - _start;//扩容前计算相对位置reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;//扩容后得出新的pos的位置，这样就不会出现迭代器失效的问题}iterator i = _finish - 1;while (i >= pos){*(i + 1) = *i;i--;}*pos = x;_finish++;return pos;
}将演示代码中插入部分的代码修改为：
if (it != v1.end()){it = v1.insert(it, 10 * x);cout << *it << endl;} 即可正常访问 it 迭代器的数据。
总结：外部迭代器第一种失效的原因为扩容引起的野指针的问题。
2、删除引起的逻辑问题
演示代码一：简单删除指定位置数据
void test_vector01()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto& e : v1){cout << e << " ";}cout << endl;int x;cin >> x;auto it = find(v1.begin(),v1.end(),x);if (it != v1.end()){v1.erase(it);cout << *it << endl;}
}运行后vs进行强制检查后报错，迭代器失效后不让访问 *it。这就是删除数据后，导致数据挪动，it 已经不是指向原来的位置了，会导致逻辑问题。
下面演示代码更能体现：
void test_vector01()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto& e : v1){cout << e << " ";}cout << endl;//删除所有的偶数auto it = v1.begin();while(it != v1.end()){if(*it % 2 == 0)v1.erase(it); ++it; }for(auto& e : v1){cout << e << " "; }
}因为代码在vs中运行会报错，以下结果在g++中运行得出：
若数据为：1 2 3 4 5 ，删除后结果为1 3 5；
但数据为：1 2 2 3 4 5，删除后的结果为1 2 3 5，代码的逻辑就会出现问题；
若数据为：1 2 2 3 4 5 2，删除后出现段错误（程序崩溃）。
通过以上数据可以看出是在进行删除后迭代器进行移动而造成的逻辑错误，那么修为进行删除后不挪动迭代器，而不需要删除则进行++能否解决问题？代码如下：
while(it != v1.end())
{if(*it % 2 == 0)v1.erase(it); else++it;
}改进后的代码不能解决vs平台的问题，依旧报错，若有删除到一定有效元素个数后就进行缩容的功能，即异地缩容出现，也会失效。
所以要访问 it迭代器 指向的对象则必须更新 it 的指向，更新的指向为erase函数返回的删除位置。代码如下：
while(it != v1.end())
{if(*it % 2 == 0)it = v1.erase(it); else++it;
}总结：失效的迭代器任何场景下都不能访问位置，更新后的迭代器才能访问。
注意：erase函数若不更新返回值，指向当前元素的pos迭代器失效，后面元素会牵扯到移动数据，因此pos指向的需要删除的元素后面的迭代器也全部失效。
二、深度浅拷贝
区分深拷贝与浅拷贝的概念：在自定义类型中，默认的拷贝构造会完成值拷贝（浅拷贝 ）：地址与值完全相等地进行拷贝，那么析构原对象与拷贝对象的话就会对同一块空间析构两次，且修改原对象会影响拷贝对象的内容；此时就需要深拷贝，即原对象与拷贝对象的地址不同但值相等。
当push_back的参数为string类型且扩容的时候会出问题，问题的核心为深层次的深浅拷贝问题，push_back所涉及的代码如下：
void push_back(const T& x)
{insert(_finish, x);
}iterator insert(iterator pos, const T& x)
{assert(pos >= _start && pos <= _finish);if (_finish == _endofstorage)//扩容{size_t len = pos - _start;//扩容前计算相对位置reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;//扩容后得出新的pos的位置，这样就不会出现迭代器失效的问题}iterator i = _finish - 1;while (i >= pos)//向后挪数据，腾出空间进行插入{*(i + 1) = *i;i--;}*pos = x;_finish++;return pos;
}void reserve(size_t n)//扩容
{if (n > capacity()){size_t OldSize = size();T* tmp = new T[n];if (_start){memcpy(tmp, _start, sizeof(T) * OldSize);delete[] _start;}_start = tmp;_finish = _start + OldSize;_endofstorage = _start + n;}
}解析：
进行扩容的三部曲：
① 开辟一个目标容量大小的空间；
② 把旧空间的值拷贝给新空间；
③ 更新对象的属性。
在进行 ① 的内存图如下：
在 ② 中进行memcpy的时候，进行的是浅拷贝，会把string对象数组中string对象的指针都原封不动地拷贝过来，与旧空间的sting指针指向的同一堆中地址的空间，当旧空间被释放的时候，新空间的string指针依旧指向旧的被释放的空间，就是野指针问题，就会出现乱码。内存图如下：
改进：把memcpy改成for循环拷贝进行赋值，这样的话若是内置类型就会直接拷贝，若是自定义类型就会调用它本身的深拷贝，不需要过多考虑。改进后代码如下：
void reserve(size_t n)//扩容
{if (n > capacity()){size_t OldSize = size();//扩容三部曲：//① new出新空间T* tmp = new T[n];if (_start){//② 拷贝原空间的数据到新空间//memcpy(tmp, _start, sizeof(T) * OldSize);reserve string对象时会出错for (size_t i = 0; i < OldSize; i++){tmp[i] = _start[i];}//③ 释放旧空间并更改原空间的成员变量的值delete[] _start;}_start = tmp;_finish = _start + OldSize; _endofstorage = _start + n;}
}
以上内容仅供分享，若有错误，请多指正。