STL在遍历过程中操作地址的改变

2023-08-26 09:57:22

start writing 2023.8.26 9:18

又遇到奇怪错误了，其实在打模拟赛（wzOI 2023.8.24 T1）的时候就发现有这个问题了，赛后来研究一下。

以下代码：

//check是一个返回值为 bool 类型的判断函数,S是一个unordered_set<int>
for(int i=1;i<=n;i++){
    int x=i,maxx=0,ans;
    for(int y:S){
        if(!check(x,y))continue;
        S.erase(y);
        x=merge(x,y);
    }
}

看上去是不是很正常，但是如果你用这样的代码跑一遍样例，如果发生了删除操作，那么 \(y\) 就会变成一个很奇怪的值。

原因跟之前差不多，上面的代码经过我的测试基本上可以等效为：

for(int i=1;i<=n;i++){
    int x=i,maxx=0,ans;
    for(auto it=S.begin();it!=S.end();it++){
        int y=*it;
        if(!check(x,y))continue;
        S.erase(y);
        x=merge(x,y);
    }
}

然后在调试的过程中就会出现以下错误：

很清晰的，S.begin() 的地址发生了变化，那么它原来指向的迭代器的地址也就错误了，所以继续迭代就也会返回一个错误值。

经过不是非常严谨的实验，map,unordered_map,set,unordered_set 中用这样的方法遍历并在中途删除元素，.begin() 的地址均可能会发生改变并报错，但边遍历边增加元素似乎并没有发生地址的变化。

实验代码：

//map<int,int> or unordered_map<int,int> S;
for(int i=1;i<=n;i++){
    int x=i,maxx=0,ans;
    for(auto it=S.begin();it!=S.end();it++){
        int y=(*it).first;
        //(or) int y=it->first;
        if(!check(x,y))continue;
        S.erase(y);
        x=merge(x,y);
    }
}

解决方案：

可以先把要删除的元素存起来，遍历完再删除。

queue<int>Q;
for(int i=1;i<=n;i++){
    int x=i,maxx=0,ans;
    for(int y:S){
        if(!check(x,y))continue;
        Q.push(y);
        x=merge(x,y);
    }
    while(!Q.empty())S.erase(Q.front()),Q.pop();
}

end writing 9:56