Удаление элементов из вектора

Question

Следующий код C ++ заполняет вектор несколькими объектами, а затем удаляет некоторые из этих объектов, но, похоже, удаляет неправильные:

vector<Photon>  photons;

photons = source->emitPhotons();    // fills vector with 300 Photon objects

for (int i=0; i<photons.size();  i++) {
    bool useless = false;

    // process photon, set useless to true for some

    // remove useless photons
    if (useless) {
        photons.erase(photons.begin()+i);
    }
}

Я делаю это правильно?Я думаю, что линия photons.erase(photons.begin()+i); может быть проблемой?

Answer 1

Определенно неправильный способ сделать это, вы никогда не уменьшите i при удалении ..

Работа с итераторами, и эта проблема исчезнет!1007 *

Существуют и другие способы использования алгоритмов (например, remove_if, erase и т. Д.), Но приведенное выше является наиболее понятным ...

Answer 2

элегантный способ будет:

std::vector<Photon> photons = source->emitPhotons();
photons.erase(
      std::remove_if(photons.begin(), photons.end(), isUseless),
      photons.end());

и

bool isUseless(const Photon& photon) { /* whatever */ }

Answer 3

Правильная версия будет выглядеть так:

for (vector<Photon>::iterator i=photons.begin(); i!=photons.end(); /*note, how the advance of i is made below*/) {
   bool useless = false;

   // process photon, set useless to true for some

   // remove useless photons
   if (useless) {
     i = photons.erase(i);
   } else {
     ++i;
   }
}

Answer 4

В этом случае вы должны работать с stl :: list. Цитирование документов STL:

Списки имеют важное свойство, заключающееся в том, что вставка и объединение не делают недействительными итераторы для элементов списка, и что даже удаление делает недействительными только итераторы, которые указывают на удаляемые элементы.

Так что это будет выглядеть так:

std::list<Photon> photons;
photons = source->emitPhotons();
std::list<Photon>::iterator i;
for(i=photons.begin();i!=photons.end();++i)
{
    bool useless=false;
    if(useless)
        photons.erase(i);
}

Answer 5

Стирание элементов в середине вектора очень неэффективно ... остальные элементы необходимо «сдвинуть» назад на один слот, чтобы заполнить «пустой» слот в векторе, созданном вызовомerase.Если вам нужно стереть элементы в середине структуры данных типа списка, не подвергаясь такому штрафу, и вам не нужно O (1) время произвольного доступа (т. Е. Вы просто пытаетесь сохранить свои элементы всписок, который вы будете копировать или использовать в другом месте позже, и вы всегда будете перебирать список, а не случайным образом обращаться к нему), вам следует заглянуть в std::list, который использует базовый связанный список для его реализации, давая ему O (1)сложность для внесения изменений в список, таких как вставка / удаление.