Löschen von Elementen aus einem Vektor

Question

Ich möchte ein Element mithilfe der Löschmethode aus einem Vektor löschen. Das Problem hierbei ist jedoch, dass das Element nicht nur einmal im Vektor auftritt. Es kann mehrere Male vorkommen und ich muss alle löschen. Mein Code ist so etwas wie diese:

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 offensichtlich abstürzt, weil ich das Ende des Vektors am ändert, während durchlaufen. Was ist der beste Weg, dies zu erreichen? I.e. Gibt es eine Möglichkeit, dies zu tun, ohne mehrmals durch den Vektor zu iterieren oder eine weitere Kopie des Vektors zu erstellen?

Answer 1

Verwenden der remove/erase idiom:

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

Was geschieht, ist, dass remove Preßlinge die Elemente, die von dem Wert unterscheiden (number_in) entfernt werden, in dem Anfang des vector und gibt die Iterator zum ersten Element nach diesem Bereich. Dann entfernt erase diese Elemente (wer Wert ist nicht angegeben).

Answer 2

Sie können am Ende beginnen oder das Ende aktualisieren, wenn ein Element gelöscht wird.

Es würde wie folgt aussehen:

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); 
         endIter = myNumbers_in.end(); 
       } 
     } 

    } 

Answer 3

Aufruf gelöscht werden Iteratoren ungültig machen, könnten Sie 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önnten std::remove_if zusammen mit einem Funktor und std :: vector verwenden: : löschen:

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 Ihren eigenen funktor in diesem Fall schreiben Sie co ULD verwenden std::remove:

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

Answer 4

Je nachdem, warum Sie dies tun, könnte die Verwendung einer std::set eine bessere Idee als std :: vector sein.

Es ermöglicht jedes Element nur einmal auftreten. Wenn Sie es mehrmals hinzufügen, wird immer nur eine Instanz gelöscht. Dies macht die Löschoperation trivial. Die Löschoperation hat auch eine geringere Zeitkomplexität als auf dem Vektor, jedoch ist das Hinzufügen von Elementen auf dem Gerät langsamer, so dass es möglicherweise nicht sehr vorteilhaft 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.

Answer 5

1. Sie iterieren können den Index Zugang,

2. Um O zu vermeiden (n^2) Komplexität können Sie zwei Indizes verwenden, i - Stromprüfung Index, j - Index store nächster Punkt 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 einem solchen Fall, dass Sie keine Ungültigkeits von Iteratoren haben, die Komplexität O (n) ist, und der Code ist sehr präzise und Sie brauchen nicht einige Hilfsklassen zu schreiben, obwohl in einigen Fällen die Verwendung von Hilfsklassen von flexibleren Code profitieren kann. Dieser Code verwendet nicht erase Methode, aber löst Ihre Aufgabe.

Verwendung von reinem stl Sie können auf folgende Art und Weise dies tun (das ist ähnlich wie die Antwort des 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()); 
}