Elemente aus einem Vektor löschen

101

Ich möchte ein Element mit der Löschmethode aus einem Vektor löschen. Das Problem hierbei ist jedoch, dass das Element nicht garantiert nur einmal im Vektor vorkommt. Es kann mehrmals vorhanden sein und ich muss alle löschen. Mein Code ist ungefähr so:

void erase(std::vector<int>& myNumbers_in, int number_in)
{
    std::vector<int>::iterator iter = myNumbers_in.begin();
    std::vector<int>::iterator endIter = myNumbers_in.end();
    for(; iter != endIter; ++iter)
    {
        if(*iter == number_in)
        {
            myNumbers_in.erase(iter);
        }
    }
}

int main(int argc, char* argv[])
{
    std::vector<int> myNmbers;
    for(int i = 0; i < 2; ++i)
    {
        myNmbers.push_back(i);
        myNmbers.push_back(i);
    }

    erase(myNmbers, 1);

    return 0;
}

Dieser Code stürzt offensichtlich ab, weil ich das Ende des Vektors ändere, während ich ihn durchlaufe. Was ist der beste Weg, um dies zu erreichen? Dh gibt es eine Möglichkeit, dies zu tun, ohne den Vektor mehrmals zu durchlaufen oder eine weitere Kopie des Vektors zu erstellen?

Naveen
quelle

Antworten:

166

Verwenden Sie die Redewendung Entfernen / Löschen :

std::vector<int>& vec = myNumbers; // use shorter name
vec.erase(std::remove(vec.begin(), vec.end(), number_in), vec.end());

Was passiert, ist, dass removedie Elemente komprimiert werden, die sich von dem zu entfernenden Wert ( number_in) am Anfang von unterscheiden, vectorund der Iterator zum ersten Element nach diesem Bereich zurückkehrt. Dann eraseentfernt diese Elemente (dessen Wert nicht spezifiziert).

Motti
quelle
2
std::remove()Verschiebt Elemente so, dass die zu entfernenden Elemente überschrieben werden. Der Algorithmus ändert die Größe des Containers nicht. Wenn nElemente entfernt werden, ist nicht definiert, welche nElemente die letzten sind.
Wilhelmtell
20
Das Löschen-Entfernen-Idiom wird in Punkt 32 des Buches "Effektive STL: 50 spezifische Möglichkeiten zur Verbesserung der Verwendung der Standardvorlagenbibliothek" von Scott Meyers beschrieben.
Alessandro Jacopson
1
@Benjin Es ist kein Update erforderlich. Es ruft die Destruktoren der Objekte auf, falls vorhanden.
Motti
53
Solche STL-Redewendungen lassen mich Python für kleine Projekte verwenden.
Johannes Overmann
1
@ LouisDionne, die sich auf die Überladung mit einem Iterator bezieht, verwende ich die Überladung mit zwei Iteratoren
Motti
53

Wenn Sie erase aufrufen, werden Iteratoren ungültig. Sie können Folgendes verwenden:

void erase(std::vector<int>& myNumbers_in, int number_in)
{
    std::vector<int>::iterator iter = myNumbers_in.begin();
    while (iter != myNumbers_in.end())
    {
        if (*iter == number_in)
        {
            iter = myNumbers_in.erase(iter);
        }
        else
        {
           ++iter;
        }
    }

}

Oder Sie können std :: remove_if zusammen mit einem Funktor und std :: vector :: erase verwenden:

struct Eraser
{
    Eraser(int number_in) : number_in(number_in) {}
    int number_in;
    bool operator()(int i) const
    {
        return i == number_in;
    }
};

std::vector<int> myNumbers;
myNumbers.erase(std::remove_if(myNumbers.begin(), myNumbers.end(), Eraser(number_in)), myNumbers.end());

Anstatt in diesem Fall Ihren eigenen Funktor zu schreiben, können Sie std :: remove verwenden :

std::vector<int> myNumbers;
myNumbers.erase(std::remove(myNumbers.begin(), myNumbers.end(), number_in), myNumbers.end());

In C ++ 11 können Sie ein Lambda anstelle eines Funktors verwenden:

std::vector<int> myNumbers;
myNumbers.erase(std::remove_if(myNumbers.begin(), myNumbers.end(), [number_in](int number){ return number == number_in; }), myNumbers.end());

In C ++ 17 sind auch std :: experiment :: erase und std :: experiment :: erase_if verfügbar, in C ++ 20 werden diese (endgültig) in std :: erase und std :: erase_if umbenannt :

std::vector<int> myNumbers;
std::erase_if(myNumbers, Eraser(number_in)); // or use lambda

oder:

std::vector<int> myNumbers;
std::erase(myNumbers, number_in);
dalle
quelle
2
Warum sollten Sie Ihren eigenen Funktor verwenden, wenn Sie gleich_zu verwenden können? :-P sgi.com/tech/stl/equal_to.html
Chris Jester-Young
3
Übrigens ist das Anrufen erasemit removeder kanonische Weg, dies zu tun.
Konrad Rudolph
1
Ich denke, er macht genau das. aber er sollte remove_if verwenden, wenn er einen eigenen functor iirc verwendet. oder verwenden Sie einfach entfernen ohne den Funktor
Johannes Schaub - litb
3
+1 Der buchstabierte Code hat mir gerade bei einem Programmierwettbewerb geholfen, während "nur die Redewendung zum Entfernen und Löschen verwenden" dies nicht tat.
13
  1. Sie können mit dem Indexzugriff iterieren.

  2. Um die Komplexität von O (n ^ 2) zu vermeiden, können Sie zwei Indizes verwenden: i - aktueller Testindex, j - Index zum Speichern des nächsten Elements und am Ende des Zyklus neue Größe des Vektors.

Code:

void erase(std::vector<int>& v, int num)
{
  size_t j = 0;
  for (size_t i = 0; i < v.size(); ++i) {
    if (v[i] != num) v[j++] = v[i];
  }
  // trim vector to new size
  v.resize(j);
}

In diesem Fall haben Sie keine Ungültigmachung von Iteratoren, die Komplexität ist O (n) und der Code ist sehr präzise und Sie müssen einige Hilfsklassen nicht schreiben, obwohl in einigen Fällen die Verwendung von Hilfsklassen in flexiblerem Code von Vorteil sein kann.

Dieser Code wird nicht verwendet erase Methode, sondern löst Ihre Aufgabe.

Mit pure stl können Sie dies folgendermaßen tun (dies ähnelt der Antwort von Motti):

#include <algorithm>

void erase(std::vector<int>& v, int num) {
    vector<int>::iterator it = remove(v.begin(), v.end(), num);
    v.erase(it, v.end());
}
sergtk
quelle
4

Abhängig davon, warum Sie dies tun, verwenden Sie ein std :: set möglicherweise eine bessere Idee als std :: vector.

Jedes Element kann nur einmal vorkommen. Wenn Sie es mehrmals hinzufügen, muss ohnehin nur eine Instanz gelöscht werden. Dies macht den Löschvorgang trivial. Die Löschoperation hat auch eine geringere zeitliche Komplexität als auf dem Vektor, jedoch ist das Hinzufügen von Elementen auf der Menge langsamer, so dass dies möglicherweise kein großer Vorteil ist.

Dies funktioniert natürlich nicht, wenn Sie daran interessiert sind, wie oft ein Element zu Ihrem Vektor hinzugefügt wurde oder in welcher Reihenfolge die Elemente hinzugefügt wurden.

Laserallan
quelle
-1

Um das erste Element zu löschen, können Sie Folgendes verwenden:

vector<int> mV{ 1, 2, 3, 4, 5 }; 
vector<int>::iterator it; 

it = mV.begin(); 
mV.erase(it); 
Amit Vujic
quelle
Das war nicht die Frage. Ihre Antwort nach 11 Jahren scheint nicht relevant zu sein, Amit!
Asteroiden mit Flügeln