Элемент стирания в векторе при повторении одного и того же вектора

Возможный дубликат:
Удаление из 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); уже используется, но дает ошибку времени выполнения.

Ответы

Ответ 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;
   }
   ...
}

Вы можете прочитать об этом здесь.

Edit: Что касается вашего комментария, вы можете использовать флаг для передачи информации о стирании элемента или нет, и вы можете проверить его, когда вы выходите из внутреннего цикла:

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 через действительный итератор.

Ответ 2

Вместо работы с типами iterator сохраните индекс в vector. Когда вам нужен итератор - возможно, для перехода в erase - вы можете сказать begin() + myIndex, чтобы сгенерировать итератор.

Это также делает цикл более знакомым, например

for(ind=0; ind < uc.size(); ind++) {

Ответ 3

vector::erase() может аннулировать итераторы, указывая на вектор.

Это делает недействительным весь итератор и ссылки на позицию (или первое) и его последующие элементы.

Вам нужно добавить результат erase к итератору (он будет указывать на элемент сразу после его удаления) и использовать его поэтому. Заметим, что в

for(it=uc.begin();it<uc.end();++it){ 
  A.id = (*it).id;         
  uc.erase(uc.begin()); 
  ...
}

Итератор it недействителен после uc.erase, поэтому последующий ++ и использование могут привести к ошибке выполнения.

Аналогично, хотя вы назначаете результат стирания на it2, вызов может аннулировать it, который не изменяется.

Лучше всего либо перезапустить свой алгоритм с самого начала после каждого erase(), либо если вы можете его изменить, чтобы он мог продолжить работу с итератора, возвращаемого erase, сделайте это, чтобы получить некоторую эффективность.

Ответ 4

У вас есть ошибка времени выполнения, потому что it2 = uc.erase(it2); возвращает итератор после последнего удаленного элемента, поэтому it2++ in for(it2=uc.begin();it2<uc.end();it2++) выходит за пределы последнего элемента.

Попробуйте изменить его, если:

if( adjacencyMatris[(*it2).id][(*it3).id] == 0 ) {
    B.id = (*it2).id;       
    uc.erase(it2);
    B.color = currentColor;
    c.push_back(B);
    break;
}