Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

迭代器失效的幾種情况

森明幫大於黑虎幫 2021-09-27 12:28:42 阅读数:24 评论数:0 点赞数:0 收藏数:0

引言:

最近自己寫代碼用到了删除鏈錶中某個節點操作,因為迭代器使用不規範,造成了程序崩潰。
例如,對某個迭代器解引用所獲得的值並不是執行erase()前這個迭代器指向的值,還有可能對未指向任何元素的迭代器的解引用賦值而引發程序crash。類似的問題代碼像這樣:

LeetCode第283題的一種常規解法:

class Solution {

public:
void moveZeroes(vector<int>& nums) {

int num = 0;
auto iter = nums.begin();
while(iter != nums.end()) {

if (*iter == 0) {

nums.erase(iter);
num++;
}
iter++;
}
nums.insert(nums.end(), num, 0);
}
};

nums.erase(iter)之後,iter及其後面的迭代器已經失效,不應該再使用這些迭代器。再執行iter++,其行為是未定義的。

迭代器失效的幾種情况總結:

  1. 對於序列式容器(如vector,deque),序列式容器就是數組式容器,删除當前的iterator會使後面所有元素的iterator都失效。這是因為vetor,deque使用了連續分配的內存,删除一個元素導致後面所有的元素會向前移動一個比特置。所以不能使用erase(iter++)的方式,還好erase方法可以返回下一個有效的iterator。

vector是一個順序容器,在內存中是一塊連續的內存,當删除一個元素後,內存中的數據會發生移動,以保證數據的緊凑。所以删除一個數據後,其他數據的地址發生了變化,之前獲取的迭代器根據原有的信息就訪問不到正確的數據。

所以為了防止vector迭代器失效,常用如下方法:

void vectorTest()
{

vector<int> container;
for (int i = 0; i < 10; i++)
{

container.push_back(i);
}
vector<int>::iterator iter;
for (iter = container.begin(); iter != container.end(); )
{

if (*iter > 3){

iter = container.erase(iter);//erase的返回值是删除元素下一個元素的迭代器
}
else{

iter++;
}
}
}
  1. 對於關聯容器(如map, set,multimap,multiset),删除當前的iterator,僅僅會使當前的iterator失效,只要在erase時,遞增當前iterator即可。這是因為map之類的容器,使用了紅黑樹來實現,插入、删除一個結點不會對其他結點造成影響。erase迭代器只是被删元素的迭代器失效,但是返回值為void,所以要采用erase(iter++)的方式删除迭代器。

解析:dataMap.erase(iter)之後,iter就已經失效了,所以iter無法自增,即iter++就會出bug.解决方案,就是在iter失效之前,先自增。

總結:

迭代器失效分三種情况考慮,也是非三種數據結構考慮,分別為數組型,鏈錶型,樹型數據結構。

  • 數組型數據結構:該數據結構的元素是分配在連續的內存中,insert和erase操作,都會使得删除點和插入點之後的元素挪比特置,所以,插入點和删除掉之後的迭代器全部失效,也就是說insert( * iter)(或erase( * iter)),然後在iter++,是沒有意義的。解决方法:erase( * iter)的返回值是下一個有效迭代器的值。 iter =cont.erase(iter)。

  • 鏈錶型數據結構:對於list型的數據結構,使用了不連續分配的內存,删除運算使指向删除比特置的迭代器失效,但是不會失效其他迭代器.解决辦法兩種,erase( * iter)會返回下一個有效迭代器的值,或者erase(iter++)。

  • 樹形數據結構: 使用紅黑樹來存儲數據,插入不會使得任何迭代器失效;删除運算使指向删除比特置的迭代器失效,但是不會失效其他迭代器.erase迭代器只是被删元素的迭代器失效,但是返回值為void,所以要采用erase(iter++)的方式删除迭代器。

版权声明
本文为[森明幫大於黑虎幫]所创,转载请带上原文链接,感谢

编程之旅,人生之路,不止于编程,还有诗和远方。
阅代码原理,看框架知识,学企业实践;
赏诗词,读日记,踏人生之路,观世界之行;

支付宝红包,每日可领