[C++] vector && list 等容器的迭代器失效问题

水墨不写bug 2024-07-19 10:35:05 阅读 77

标题:[C++] 容器的迭代器失效问题

@水墨不写bug



正文开始:

什么是迭代器?

        迭代器是STL提供的六大组件之一,它允许我们访问容器(如vector、list、set等)中的元素,同时提供一个遍历容器的方法。然而,在使用迭代器时,我们必须注意所谓的“迭代器失效”问题。

一、插入/删除元素

(1)erase导致删除位置之后的迭代器失效

        当我们在使用vector时,接收到了一组数据。然而这组数据的奇数具有实际意义,偶数需要被删除,这时候我们可能会写出这样的代码:

<code>//删除偶数

vector<int> v1 = { 1,2,3,4,5,6,7,8,9,10,22,1};

for (vector<int>::iterator it = v1.begin();it!= v1.end();)

{

if (*it % 2 == 0)

{

v1.erase(it);

}

else

{

it++;

}

}

        乍一看,这段代码看似没有问题,并且在gcc上可以跑过,但是实际上这段代码是不符合C++标准的。

1.换一个编译器,比如VS2022,发现问题了:

 报错翻译过来就是迭代器不兼容。其实VS2022是通过对vector的迭代器进行封装来达到这一功能的。

2.在gcc上可以跑过,本质上只是一个巧合。


 迭代器失效本质

        在STL标准中,vector的erase会返回一个修正后的迭代器,而这样的修正就是为了避免迭代器失效。

        vector中的一组数据,{1,2,3,4,5,6,7,8,9};假设有一个迭代器指向元素5:

         在删除元素“5”后,由于会发生数据拷贝移动,于是这个迭代器就“顺势”指向了下一个元素“6”:

         这一行为是未定义的!如果我们使用的容器不是连续线性的,比如链表,那么结果将不堪设想,会产生野指针!

<code>void test7()

{

list<int> v1 = { 1,2,3,4,5,6,7,8,9,10,22,1 };

for (list<int>::iterator it = v1.begin(); it != v1.end();)

{

if (*it % 2 == 0)

{

v1.erase(it);

}

else

{

it++;

}

}

cout << v1;

}

int main()

{

//test1();

//test2();

//test3();

//test4();

//test5();

//test6();

test7();

return 0;

}

 


 vector的erase()原型:

iterator erase (const_iterator position);

iterator erase (const_iterator first, const_iterator last);

        STl的vector返回一个迭代器,指向被函数调用删除的最后一个元素后面元素的新位置。如果操作删除序列中的最后一个元素,则这是容器的末端。

        所以标准的写法是:

<code>

vector<int> v1 = { 1,2,3,4,5,6,7,8,9,10,22,1};

for (vector<int>::iterator it = v1.begin();it!= v1.end();)

{

if (*it % 2 == 0)

{

it = v1.erase(it);

}

else

{

it++;

}

}

cout << v1;

这样就实时更新了迭代器。 


(2)insert导致的迭代器失效

i,插入元素之后位置的迭代器失效

        与删除元素之后位置的迭代器失效的问题本质上是一致的:

vector<int> v1 = { 1,2,3,4,5,6,7,8,9,10 };

vector<int>::iterator it = v1.begin() + 5;

cout << *it << endl;

v1.insert(v1.begin(), 4);

cout << *it << endl;

 在运行时报错:

 由于无法保留原来的迭代器,所以直接更新为指向插入元素的迭代器:

<code>vector<int> v1 = { 1,2,3,4,5,6,7,8,9,10 };

vector<int>::iterator it = v1.begin() + 5;

cout << *it << endl;

it = v1.insert(v1.begin(), 0);

cout << *it << endl;

 

ii,扩容移动导致的迭代器失效

        我们看一段insert()的原型:

<code>//在pos位置插入对象

iterator insert(iterator pos, const T& t)

//由于可能需要扩容,会发生迭代器失效,对内部而言

//迭代器pos在扩容前后指向的对象不再相同,对外部也是同样的会发生

{

if (size() == capacity())

//需要扩容

{

int len = pos - _start;

int Newcapacity = capacity() == 0 ? 4 : capacity() * 2;

reserve(Newcapacity);

//改变capacity,不改变size

//记录len,解决迭代器失效的问题

pos = _start + len;

}

        通过分析,我们发现:在insert之前,会有一个是否需要扩容的检验,如果需要扩容,则释放旧空间,开辟新空间,然后拷贝数据。

        在这个过程中,如果需要扩容那么原来指向原旧空间的迭代器就失效了,如果访问失效的迭代器,会出现意想不到的结果。

        这个就解释了VS2022封装为什么迭代器。也许VS将迭代器封装为一个类,并且有这个类内部有一个判断迭代器是否失效的方法,如果我们访问了失效的迭代器就会报错。

二、容器重新分配内存

        其实,只要是导致容器的重新开辟这一动作时,就伴随着迭代器失效。

比如:

(1)std::vector 插入元素导致的重新分配

#include <iostream>

#include <vector>

int main() {

std::vector<int> v{1, 2, 3};

auto it = v.begin(); // 假设 it 指向第一个元素 1

// 插入元素,如果导致重新分配内存,it 将失效

v.push_back(4); // 如果 v 的容量不足以容纳新元素,它将重新分配内存

// 下面的代码在重新分配后可能会导致未定义行为

// *it = 0; // 如果 it 已失效,这是未定义行为

// 更好的做法是重新获取迭代器

it = v.begin(); // 现在 it 指向新的第一个元素(可能是原来的 1,也可能是新内存位置上的 1)

std::cout << *it << std::endl; // 输出:1

return 0;

}

(2)std::vector resize 导致的重新分配

#include <iostream>

#include <vector>

int main() {

std::vector<int> v{1, 2, 3};

auto it = v.begin(); // 假设 it 指向第一个元素 1

// resize 到一个更大的大小,如果导致重新分配内存,it 将失效

v.resize(10); // 如果 v 的容量不足以容纳 10 个元素,它将重新分配内存

// 下面的代码在重新分配后会导致未定义行为

// *it = 0; // 如果 it 已失效,这是未定义行为

// 更好的做法是重新获取迭代器

it = v.begin(); // 现在 it 指向新的第一个元素(原来的 1 或新内存位置上的元素)

std::cout << *it << std::endl; // 输出:1

return 0;

}

        这两个操作都导致了容器的重新开辟也就是 释放旧空间,开辟新空间进行容量调整的过程,所以造成迭代器失效。


三、避免迭代器失效 

        在实际应用中,我们要避免迭代器失效,就需要理解常见的错误及原理,养成良好的变成习惯,形成风格,这样才能在最大程度上减少错误!


目录

一、插入/删除元素:

(1)erase导致删除位置之后的迭代器失效

 vector的erase()原型:

(2)insert导致的迭代器失效

i,插入元素之后位置的迭代器失效

ii,扩容移动导致的迭代器失效

二、容器重新分配内存

(1)std::vector 插入元素导致的重新分配

(2)std::vector resize 导致的重新分配

三、避免迭代器失效 


完~

未经作者同意禁止转载



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。