Wie würden Sie Elemente eines std :: vector basierend auf einer Eigenschaft der Elemente entfernen?

Question

Wenn Sie zum Beispiel eine std::vector<MyClass> haben, wobei MyClass eine öffentliche Methode hat: bool isTiredOfLife(), wie entfernen Sie die Elemente, die wahr zurückgeben?

Answer 1

Ich ziehe remove_if

v.erase(remove_if(v.begin(), v.end(), 
       mem_fun_ref(&MyClass::isTiredOfLife)), 
     v.end()); 

remove_if einen Iterator zeigt nach dem letzten Element zurückgibt, die noch in der Sequenz ist. erase löscht alles vom ersten bis zum letzten Argument (beide Iteratoren).

Answer 2

Verwenden Sie remove_if ist die "richtige" Möglichkeit, dies zu tun. Achten Sie darauf, KEINEN Iterator zum Durchlaufen und Löschen zu verwenden, da das Entfernen von Elementen den Iterator ungültig macht. In der Tat ist jedes Beispiel, das lies() als primäre Methode verwendet, eine schlechte Idee auf Vektoren, weil das Löschen O (n) ist, was Ihren Algorithmus zu O (n^2) macht. Dies sollte ein O (n) -Algorithmus sein.

Die Methode, die ich unten gebe, ist wahrscheinlich schneller als remove_if, behält aber im Gegensatz zu remove_if NICHT die relative Reihenfolge der Elemente bei. Wenn Sie die Reihenfolge beibehalten möchten (d. H. Ihr Vektor ist sortiert), verwenden Sie remove_if, wie in der obigen Antwort. Wenn Sie nicht über Auftrag ist es egal, und wenn die Anzahl der Elemente als ein Viertel des Vektors gelöscht ist in der Regel weniger werden, ist diese Methode wahrscheinlich schneller sein:

for(size_t i = 0; i < vec.size();) 
    if(vec[i].isTiredOfLife()) 
    { 
     vec[i] = vec.back(); 
     vec.pop_back(); 
    } 
    else 
     ++i;