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

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

Definietly неправильный способ сделать это, вы никогда не настроить i вниз, как вы удаляете ..

Работы с итераторами, и эта проблема уходит!

например.

for(auto it = photons.begin(); it != photons.end();) 
{ 
    if (useless) 
    it = photons.erase(it); 
    else 
    ++it; 
} 

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

Answer 2

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

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

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

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 5

Вы должны работать с СТЛ :: список в этом дело. Цитирование STL документы:

Lists have the important property that insertion and splicing do not invalidate iterators to list elements, and that even removal invalidates only the iterators that point to the elements that are removed.

Так что это будет идти по линии:

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