vector容器的物理基础是线性表,底层是指针变量实现的。
在这里导致vector迭代器失效的原因会有两种-----插入失效,删除失效。
我们在一块vector空间插入pos(20)
但是这个空间只能存放五个数,要想插入数据,就要重新扩容2倍(一般扩容时,二倍是比较合理的)。
当释放小空间时,pos迭代器仍然指向他,所以释放后,pos就是野指针了,所以造成pos迭代器失效。
举个例子:我们在所有的偶数前面插入这个偶数的2 倍,由于我们写的迭代器可能存在误差,我们直接调用std库里的迭代器进行测试。
int main() { std::vector<int> v; //调用std中的vector v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); vector<int>::iterator it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) { v.insert(it, *it * 2); } ++it; } for (auto e : v) { cout << e << endl; } return 0; }
对于上面的代码我们直接给他扩容让他空间足够。
int main() { std::vector<int> v; //调用std中的vector v.reserve(10); v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); vector<int>::iterator it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) { v.insert(it, *it * 2); } ++it; } for (auto e : v) { cout << e << endl; } return 0; }编译直接报错,为啥空间足够,迭代器也会失效呢?
按我们所想的代码,打印的是1,4,2,3,8,4,5。。。但是这全部是2,而且还是在同一个地方,不是在偶数前面插入的4。
这个原因是啥?
我们加入数据2的下标是[1],当我们插入4后,我们想让下标进行移动到数据3处,但是这个下标现在在数据4的下标[1]处,然后下标++,到数据2的下标[2]处,诶我们发现,这个下标转转回回又到了数据2处,然后又在他前面插入。所以会一直插入4在2前面。
所以我们可以用一个指针去接收插入后的迭代器。
int main() { std::vector<int> v; //调用std中的vector v.reserve(10); v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); vector<int>::iterator it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) { it=v.insert(it, *it * 2); it += 2; } else { ++it; } } for (auto e : v) { cout << e << endl; } return 0; }如果按照第一种情况,扩容使迭代器失效,那我们不扩容看看加一个指针接收还会不会失效。
如果我们不用指针接收,单纯让it每次+2行吗?
不扩容的情况不行:
而扩用的可以,但是用指针接收也不费事,别用这两种代码。
接下来我们删除vector中的偶数,看看能不能正常运行。
int main() { std::vector<int> v; //调用std中的vector v.reserve(10); v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); vector<int>::iterator it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) { v.erase(it); } ++it; } for (auto e : v) { cout << e << endl; } return 0; }迭代器又一次失效了。
这个是因为当我们删除2后,pos指针的位置还在原来的位置,但是3却往前挪了,而pos指向3时编译器认为指针不在指向原来的数据发生改变,所以迭代器就会失效。
这个解决方法也是指针接收。
这里的it不用加两回了,因为删除本身就是一个加号。
评论区有一位大佬提出了一个很深刻的问题,就上面的那个例子,在删除数字2之后,那他后面的数据是不是往前移动呢?我测试一下:
void test2() { vector<int> v = { 1,2,3,4,5,6 }; auto it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) { v.erase(it); continue; } it++; } }接下来进行删除操作:
删除是之所以出现迭代器失效是因为指向变了。
比如1 2 3 4 5,删除it指向2,删除后,变成1 3 4 5,此时删除后本来就指向了3,但是你还++了就变成4了。
删除之后it还是指向当前位置但是你必须得用返回值接受,不然就会报错 这是编译器检查。
而且用返回值是为了防止缩容,因为缩容后就是到达一个新的地址了,而不是之前的地址,就和insert迭代器失效一样,就是为了避免这个,所以编译器直接做了检查。
相对于底层是顺序表的vector来说,list的底层是链表,这就使他在插入时不需要大量挪动数据。也就是说list在进行插入插入操作时不会迭代器失灵。
vector在插入时出现了野指针问题,但是在list中,插入时会创造一个新节点,指针仍旧指向原来那个结点,不会出现野指针。但是删除操作就会导致迭代器失效了。因为结点删除了但是指针还在,指针就是野指针了。
但是list容器在删除是也会导致迭代器失效问题,情况如下:
int main() { std::list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(4); lt.push_back(5); lt.push_back(8); lt.push_back(10); for (auto e : lt) { cout << e << " "; } cout << endl; auto pos = find(lt.begin(), lt.end(), 5); //在list范围找5 if (pos != lt.end()) { lt.erase(pos); pos++; } for (auto e : lt) { cout << e << " "; } return 0; }就比如我们要删除5,那么这个结点被删除之后而pos指针就变成野指针了。
也就是删除操作时会使迭代器失效。
这里把pos++代码去掉,就可以正常运行了。
总结:迭代器之所以失效最大的原因是成为野指针了。
总是感觉这篇博客有一点水,但是真没内容写了,就这吧!