在迭代相同的向量时删除向量中的元素

Question

可能重复:
在为每个执行a时从std :: vector中删除？

我正在尝试根据这个算法实现顶点着色;

/*
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协调.因此什么是"set"？无论如何,问题是在迭代它时在向量中擦除元素.这是代码.

    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);line已经是普遍使用但它给出了运行时错误.

Answer 1

在线:

it2 = uc.erase(it2);

迭代器指向的元素it2从向量中移除,元素在内存中移位以填充无效的间隙it2.it2获取一个新值,现在指向移除的向量之后的第一个元素或向量的末尾(如果删除的元素是最后一个元素).这意味着在擦除元素后,您不应该前进it2.提议的替代方案remove-erase idiom是一个简单的技巧:

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

你可以在这里阅读更多相关信息.

编辑: 关于你的评论,你可以使用一个标志来传递一个元素是否被删除的信息,你可以从内循环中检查它:

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通过有效迭代器访问下一个元素.