在向量中删除元素，同时迭代相同的向量 [英] Erase element in vector while iterating the same vector

问题描述

可能重复：

从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

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

关于此此处。

编辑：
关于您的评论，您可以使用标记传递信息，无论元素是否已被擦除，您可以在你从内循环中走出：

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.

这篇关于在向量中删除元素，同时迭代相同的向量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！