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