在迭代同一个向量时擦除向量中的元素

2021-12-21 00:00:00 vector c++

可能的重复:
从 std::vector 中擦除，同时为每个做一个?

我正在尝试根据此算法实现顶点着色；

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
*/

我不明白将 v 添加到 currentColor".行，但我想，这意味着将 currentColor 分配给 v.因此，设置"是什么?无论如何，问题是在迭代时擦除向量中的元素.这是代码.

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.

    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;
    }

我认为 it2 = uc.erase(it2); 行已经是通用的，但它给出了运行时错误.

I think it2 = uc.erase(it2); line is already general use but It gives run time error.

推荐答案

在行:

it2 = uc.erase(it2);

迭代器 it2 指向的元素从向量中删除，元素在内存中移动以填补使 it2 无效的空白.it2 获得一个新值，现在指向被移除元素之后的第一个元素或向量的结尾(如果移除的元素是最后一个元素).这意味着在擦除一个元素后你不应该推进 it2.建议的 remove-erase idiom 的替代方法是一个简单的技巧:

an element pointed by iterator it2 is removed from the vector, elements are shifted in memory in order to fill that gap which invalidates it2. it2 gets 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 idiom is a simple trick: 

for(it2 = uc.begin(); it2 != uc.end();)
{
   ...   
   if(...)
   {
      it2 = uc.erase(it2); 
   }
   else
   {
      ++it2;
   }
   ...
}

您可以阅读有关此内容的更多信息这里.

You can read more about this here.

关于你的评论，你可以使用一个标志来传递一个元素是否被擦除的信息，当你从内循环中出来时你可以检查一下:

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;
}

从 uc 中删除一个元素后，您需要中断内部循环.在外循环的下一次迭代中，您将能够通过有效的迭代器访问 uc 中的下一个元素.

After you've erased an element from uc you 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 uc through a valid iterator.

相关文章