C++ 在迭代同一个向量时擦除向量中的元素
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/9927163/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Erase element in vector while iterating the same vector
提问by miqbal
Possible Duplicate:
Erasing from a std::vector while doing a for each?
I'm trying to implement vertice coloring according to this algorithm;
我正在尝试根据此算法实现顶点着色；
/*
Given G=(V,E):
Compute Degree(v) for all v in V.
Set uncolored = V sorted in decreasing order of Degree(v).
set currentColor = 0.
while there are uncolored nodes:
set A=first element of uncolored
remove A from uncolored
set Color(A) = currentColor
set coloredWithCurrent = {A}
for each v in uncolored:
if v is not adjacent to anything in coloredWithCurrent:
set Color(v)=currentColor.
add v to currentColor.
remove v from uncolored.
end if
end for
currentColor = currentColor + 1.
end while
*/
I don't understand "add v to currentColor." line but I supposed, it means assing currentColor to v. Therefore what is the "set"? Anyway the problem is erasing element in vector while iterating it. This is the code.
我不明白“将 v 添加到 currentColor”。行，但我想，这意味着将 currentColor 分配给 v。因此，“设置”是什么？无论如何，问题是在迭代时擦除向量中的元素。这是代码。
vector<struct Uncolored> uc;
vector<struct Colored> c;
int currentColor = 0;
struct Colored A;
struct Colored B;
vector<struct Uncolored>::iterator it;
vector<struct Uncolored>::iterator it2;
vector<struct Colored>::iterator it3;
for(it=uc.begin();it<uc.end();it++){
A.id = (*it).id;
uc.erase(uc.begin());
A.color = currentColor;
c.push_back(A);
for(it2=uc.begin();it2<uc.end();it2++) {
it3=c.begin();
while(it3 != c.end()) {
if( adjacencyMatris[(*it2).id][(*it3).id] == 0 ) {
B.id = (*it2).id;
it2 = uc.erase(it2);
B.color = currentColor;
c.push_back(B);
}
it3++;
}
}
currentColor = currentColor + 1;
}
I think it2 = uc.erase(it2);line is already general use but It gives run time error.
我认为it2 = uc.erase(it2);line 已经是通用的，但它会出现运行时错误。
回答by Bojan Komazec
In the line:
在行中：
it2 = uc.erase(it2);
an element pointed by iterator it2is removed from the vector, elements are shifted in memory in order to fill that gap which invalidates it2. it2gets a new value and now points to the first element after the the removed one or the end of the vector (if removed element was the last one). This means that after erasing an element you should not advance it2. An alternative to proposed remove-erase idiomis a simple trick:
迭代器指向的元素it2从向量中删除，元素在内存中移动以填补无效的空白it2。it2获得一个新值，现在指向被移除元素之后的第一个元素或向量的结尾（如果移除的元素是最后一个元素）。这意味着在擦除元素后您不应该前进it2。建议的替代方案remove-erase idiom是一个简单的技巧：
for(it2 = uc.begin(); it2 != uc.end();)
{
...
if(...)
{
it2 = uc.erase(it2);
}
else
{
++it2;
}
...
}
You can read more about this here.
您可以在此处阅读更多相关信息。
Edit:Regarding your comment, you can use a flag to pass the information whether an element has been erased or not, and you can check it when you get out from the inner loop:
编辑：关于你的评论，你可以使用一个标志来传递一个元素是否被擦除的信息，当你从内循环中出来时你可以检查它：
for(it2=uc.begin(); it2 != uc.end();)
{
bool bErased = false;
for(it3 = c.begin(); it3 != c.end(); ++it3)
{
if(adjacencyMatris[(*it2).id][(*it3).id] == 0 )
{
B.id = (*it2).id;
it2 = uc.erase(it2);
bErased = true;
B.color = currentColor;
c.push_back(B);
break;
}
}
if(!bErased)
++it2;
}
After you've erased an element from ucyou need to break from the inner loop. In the next iteration of the outer loop you'll be able to access the next element in the ucthrough a valid iterator.
从uc您删除元素后，您需要中断内部循环。在外循环的下一次迭代中，您将能够uc通过有效的迭代器访问 中的下一个元素。
回答by StilesCrisis
Instead of working with iteratortypes, store an index into the vector. When you need an iterator--perhaps for passing into erase--you can say begin() + myIndexto generate an iterator.
不要使用iterator类型，而是将索引存储到vector. 当你需要一个迭代器——也许是为了传入——erase你可以说begin() + myIndex生成一个迭代器。
This also makes the loop look more familiar, e.g.
这也使循环看起来更熟悉，例如
for(ind=0; ind < uc.size(); ind++) {
回答by Attila
vector::erase()can invalidate iteratorspointing to the vector.
This invalidates all iterator and references to position (or first) and its subsequent elements.
这将使所有迭代器和对位置（或第一个）及其后续元素的引用无效。
You need to add the result of eraseto the iterator (it will point to the element just after the one erased) and use that consequently. Note that in
您需要将 的结果添加erase到迭代器中（它将指向擦除后的元素）并因此使用它。请注意，在
for(it=uc.begin();it<uc.end();++it){
A.id = (*it).id;
uc.erase(uc.begin());
...
}
The iterator itis not valid after uc.erase, so subsequent ++ and use might result in runtime error.
迭代器it在 之后无效uc.erase，因此后续 ++ 和使用可能会导致运行时错误。
Similarly, even though you assign the result of erase to it2, the call can invalidate it, which is not changed.
同样，即使您将 erase 的结果分配给it2，调用也会使 无效it，这不会改变。
Your best bet is either to re-start your algorithm from the beginning after each erase(), or if you can alter it so that it can continue from the iterator returned by erase, do that to gain some efficiency.
您最好的选择是在 each 之后从头开始重新启动您的算法erase()，或者如果您可以更改它以便它可以从 返回的迭代器继续erase，那么这样做以获得一些效率。
回答by asclepix
You've got the runtime error because it2 = uc.erase(it2);returns the iterator following the last removed element, so the it2++in for(it2=uc.begin();it2<uc.end();it2++)goes beyond the last element.
您有运行时错误，因为it2 = uc.erase(it2);在最后一个删除的元素之后返回迭代器，因此it2++infor(it2=uc.begin();it2<uc.end();it2++)超出了最后一个元素。
Try changing your if in:
尝试更改您的 if ：
if( adjacencyMatris[(*it2).id][(*it3).id] == 0 ) {
B.id = (*it2).id;
uc.erase(it2);
B.color = currentColor;
c.push_back(B);
break;
}
