Wie lösche ich ein Element aus std :: vector <> nach Index?

508

Ich habe einen std :: vector <int> und möchte das n-te Element löschen. Wie mache ich das?

std::vector<int> vec;

vec.push_back(6);
vec.push_back(-17);
vec.push_back(12);

vec.erase(???);
dau_man
quelle
4
Verwenden Sie eine std :: deque, die das Einfügen und Löschen an beiden Enden ermöglicht.
Dario
40
Nein, denken Sie nicht daran, deque zu verwenden, nur weil Sie möglicherweise ein Element löschen möchten. Das ist ein wirklich schlechter Rat. Es gibt eine ganze Reihe von Gründen, warum Sie deque oder vector verwenden möchten. Das Löschen eines Elements aus einem Vektor kann zwar kostspielig sein, insbesondere wenn der Vektor groß ist, aber es gibt keinen Grund zu der Annahme, dass eine Deque besser wäre als ein Vektor aus dem gerade veröffentlichten Codebeispiel.
Eule
6
Wenn Sie beispielsweise eine grafische Anwendung haben, in der Sie eine "Liste" von Dingen anzeigen, in die Sie Dinge interaktiv einfügen / entfernen, sollten Sie die Liste 50 bis 100 Mal pro Sekunde durchlaufen, um sie anzuzeigen, und einige Dinge hinzufügen / entfernen mal jede Minute. Die Implementierung der "Liste" als Vektor ist daher im Hinblick auf die Gesamteffizienz wahrscheinlich eine bessere Option.
Michel Billaud

Antworten:

705

Um ein einzelnes Element zu löschen, haben Sie folgende Möglichkeiten:

std::vector<int> vec;

vec.push_back(6);
vec.push_back(-17);
vec.push_back(12);

// Deletes the second element (vec[1])
vec.erase(vec.begin() + 1);

Oder um mehrere Elemente gleichzeitig zu löschen:

// Deletes the second through third elements (vec[1], vec[2])
vec.erase(vec.begin() + 1, vec.begin() + 3);
mmmmmmmm
quelle
50
Beachten Sie auch , binär operator+ist nicht unbedingt für Iteratoren auf andere Behältertypen definiert, wie list<T>::iterator(Sie nicht tun können list.begin() + 2auf ein std::list, den Sie verwenden müssen std::advancefür diese)
bobobobo
Geben Sie an, dass "+1" das erste Element myVector [0] ist oder die tatsächliche Position myVector [1]
K - Die Toxizität in SO wächst.
2
Mit Voraus müssen Sie den Iterator in einer Variablen speichern. Wenn Sie std :: next verwenden, können Sie dies in einer Zeile tun: vec.erase (next (begin (vec), 123));
Dani
8
Vielen Dank an alle, die geantwortet haben. Was halten wir von einem Klassendesign, wenn eine so einfache Operation wie das Löschen eines Elements erfordert, dass man zu StackOverflow kommt?
Pierre
5
@Pierre Da der numerische Index eines bestimmten Elements nicht das primäre Zugriffsmodell ist, ist dies der Iterator . Alle Funktionen, die Elemente eines Containers betrachten, verwenden die Iteratoren dieses Containers. ZBstd::find_if
Caleth
212

Die Löschmethode für std :: vector ist überladen, daher ist der Aufruf wahrscheinlich klarer

vec.erase(vec.begin() + index);

wenn Sie nur ein einzelnes Element löschen möchten.

CodeBuddy
quelle
3
Dieses Problem tritt jedoch auf, egal wie viele Elemente Sie haben.
Zyx 2000
15
Wenn es nur ein Element gibt, ist der Index 0, und Sie erhalten, vec.begin()welches gültig ist.
Anne Quinn
28
Ich wünschte, jemand hätte erwähnt, dass vec.erase(0)dies nicht funktioniert, aber vec.erase(vec.begin()+0)(oder ohne +0). Ansonsten bekomme ich keinen passenden Funktionsaufruf, weshalb ich hierher
gekommen
@qrtLs vec.erase(0)kann tatsächlich kompiliert werden, wenn es 0zufällig als Nullzeigerkonstante interpretiert wird ...
LF
57
template <typename T>
void remove(std::vector<T>& vec, size_t pos)
{
    std::vector<T>::iterator it = vec.begin();
    std::advance(it, pos);
    vec.erase(it);
}
Max
quelle
2
Max, was macht diese Funktion besser als: template <typename T> void remove(std::vector<T>& vec, size_t pos) { vec.erase(vec.begin + pos); }Ich sage auch nicht, dass es besser ist, nur aus persönlichem Interesse zu fragen und das beste Ergebnis zu erzielen, das diese Frage erzielen könnte.
13
@JoeyvG: Da a vector<T>::iteratorein Iterator mit wahlfreiem Zugriff ist, ist Ihre Version in Ordnung und möglicherweise etwas klarer. Aber die Version, die Max gepostet hat, sollte gut funktionieren, wenn Sie den Container in einen anderen ändern, der keine Iteratoren mit wahlfreiem Zugriff unterstützt
Lily Ballard
2
Dies ist imo die bessere Antwort, da es auch für andere Containerformate gilt. Sie können auch std :: next () verwenden.
Bim
Viel besserer Ansatz, da er nicht auf den Einbauten des Containers beruht.
BartoszKP
std :: advanced wird nur benötigt, wenn Sie glauben, dass dies kein Vektor ist, dh keine Liste. Aber wie Sie hier angegeben haben, wäre Operator + nicht einfacher? Laut diesem stackoverflow.com/questions/1668088/… gibt es einen möglichen Leistungsgewinn bei Operator +
Neil McGill vor
14

Die eraseMethode wird auf zwei Arten verwendet:

  1. Einzelelement löschen:

    vector.erase( vector.begin() + 3 ); // Deleting the fourth element
  2. Löschen einer Reihe von Elementen:

    vector.erase( vector.begin() + 3, vector.begin() + 5 ); // Deleting from fourth element to sixth element
Eswaran Pandi
quelle
7
Dies ist eine doppelte Antwort fast 7 Jahre nach der akzeptierten Antwort. Bitte tu das nicht.
AlastairG
10

Tatsächlich erasefunktioniert die Funktion für zwei Profile:

  • Ein einzelnes Element entfernen

    iterator erase (iterator position);
  • Eine Reihe von Elementen entfernen

    iterator erase (iterator first, iterator last);

Da std :: vec.begin () den Beginn des Containers markiert und wir das i-te Element in unserem Vektor löschen möchten, können wir Folgendes verwenden:

vec.erase(vec.begin() + index);

Wenn Sie genau hinschauen, ist vec.begin () nur ein Zeiger auf die Startposition unseres Vektors. Wenn Sie den Wert von i hinzufügen, wird der Zeiger auf die Position i erhöht, sodass wir stattdessen auf den Zeiger auf das i-te Element zugreifen können, indem:

&vec[i]

So können wir schreiben:

vec.erase(&vec[i]); // To delete the ith element
Varun Garg
quelle
6
-1 Die letzte Zeile wird nicht kompiliert (zumindest in VS2017). Der Code geht davon aus, dass vector :: iterator implizit aus einem Rohzeiger konstruierbar ist, was vom Standard nicht verlangt wird.
CuriousGeorge
1
Dies gilt insbesondere für Debug-Iteratoren
Nishant Singh
9

Wenn Sie einen ungeordneten Vektor haben, können Sie die Tatsache nutzen, dass er ungeordnet ist, und etwas verwenden, das ich von Dan Higgins bei CPPCON gesehen habe

template< typename TContainer >
static bool EraseFromUnorderedByIndex( TContainer& inContainer, size_t inIndex )
{
    if ( inIndex < inContainer.size() )
    {
        if ( inIndex != inContainer.size() - 1 )
            inContainer[inIndex] = inContainer.back();
        inContainer.pop_back();
        return true;
    }
    return false;
}

Da die Listenreihenfolge keine Rolle spielt, nehmen Sie einfach das letzte Element in der Liste und kopieren Sie es über das Element, das Sie entfernen möchten. Fügen Sie dann das letzte Element hinzu und löschen Sie es.

Ton J.
quelle
Ich denke, dies ist die beste Antwort, wenn der Vektor ungeordnet ist. Es iterator + indexbasiert nicht auf der Annahme, dass Sie tatsächlich die Iteratorposition an diesem Index zurückgeben, was nicht für alle iterierbaren Container gilt. Es ist auch eine konstante Komplexität anstelle einer linearen, indem der Rückzeiger ausgenutzt wird.
Theferrit32
1
Dies muss unbedingt zur Standardbibliothek hinzugefügt werden, da unordered_removeund unordered_remove_if… es sei denn, es wurde und ich habe es verpasst, was heutzutage immer häufiger vorkommt :)
Will Crawford
Wenn würde vorschlagen, Verschiebungszuweisung oder Tausch anstelle einer Kopierzuweisung zu verwenden.
Carsten S
std::removeOrdnet den Container so an, dass alle zu entfernenden Elemente am Ende sind. Wenn Sie C ++ 17 verwenden, müssen Sie dies nicht manuell tun.
Keith
@keith wie std::removehilft das? cppreference behauptet, dass selbst in C ++ 17 alle removeÜberladungen ein Prädikat erfordern und keine einen Index annehmen.
Paul Du Bois
4

Wenn Sie mit großen Vektoren (Größe> 100.000) arbeiten und viele Elemente löschen möchten, würde ich Folgendes empfehlen:

int main(int argc, char** argv) {

    vector <int> vec;
    vector <int> vec2;

    for (int i = 0; i < 20000000; i++){
        vec.push_back(i);}

    for (int i = 0; i < vec.size(); i++)
    {
        if(vec.at(i) %3 != 0)
            vec2.push_back(i);
    }

    vec = vec2;
    cout << vec.size() << endl;
}

Der Code nimmt jede Zahl in vec, die nicht durch 3 geteilt werden kann, und kopiert sie in vec2. Danach kopiert es vec2 in vec. Es ist ziemlich schnell. Um 20.000.000 Elemente zu verarbeiten, benötigt dieser Algorithmus nur 0,8 Sekunden!

Ich habe das gleiche mit der Löschmethode gemacht, und es dauert sehr viel Zeit:

Erase-Version (10k elements)  : 0.04 sec
Erase-Version (100k elements) : 0.6  sec
Erase-Version (1000k elements): 56   sec
Erase-Version (10000k elements): ...still calculating (>30 min)
Fabian
quelle
6
Wie beantwortet dies die Frage?
Regis Portalez
4
Interessant, aber für die Frage nicht relevant!
Roddy
Wird ein In-Place-Algorithmus nicht schneller sein?
user202729
2
das ist std :: remove_if (+ löschen)
RiaD
3

Ich schlage vor, dies zu lesen, da ich glaube, dass Sie danach suchen. https://en.wikipedia.org/wiki/Erase%E2%80%93remove_idiom

Wenn Sie zum Beispiel verwenden

 vec.erase(vec.begin() + 1, vec.begin() + 3);

Sie löschen das n-te Element des Vektors, aber wenn Sie das zweite Element löschen, werden alle anderen Elemente des Vektors verschoben und die Vektorgröße beträgt -1. Dies kann problematisch sein, wenn Sie den Vektor durchlaufen, da die Vektorgröße () abnimmt. Wenn Sie ein Problem wie dieses haben, wird der Link empfohlen, den vorhandenen Algorithmus in der Standard-C ++ - Bibliothek zu verwenden. und "remove" oder "remove_if".

Hoffe das hat geholfen

Forscher
quelle
0

Die vorherigen Antworten setzen voraus, dass Sie immer einen signierten Index haben. Leider std::vectorAnwendungen size_typefür die Indizierung und difference_typefür Iterator Arithmetik, so dass sie arbeiten nicht zusammen , wenn Sie „-Wconversion“ haben und Freunde aktiviert. Dies ist eine weitere Möglichkeit, die Frage zu beantworten und gleichzeitig sowohl signierte als auch nicht signierte zu verarbeiten:

Zu entfernen:

template<class T, class I, class = typename std::enable_if<std::is_integral<I>::value>::type>
void remove(std::vector<T> &v, I index)
{
    const auto &iter = v.cbegin() + gsl::narrow_cast<typename std::vector<T>::difference_type>(index);
    v.erase(iter);
}

Nehmen:

template<class T, class I, class = typename std::enable_if<std::is_integral<I>::value>::type>
T take(std::vector<T> &v, I index)
{
    const auto &iter = v.cbegin() + gsl::narrow_cast<typename std::vector<T>::difference_type>(index);

    auto val = *iter;
    v.erase(iter);

    return val;
}
Rian Quinn
quelle
0

Hier ist eine weitere Möglichkeit, dies zu tun, wenn Sie ein Element löschen möchten, indem Sie dies mit seinem Wert im Vektor finden. Sie müssen dies nur für den Vektor tun.

vector<int> ar(n);
ar.erase(remove(ar.begin(), ar.end()), (place your value here from vector array));

es wird Ihren Wert von hier entfernen. Vielen Dank

meenachinmay
quelle
0

Wie wäre es damit?

void squeeze(vector<int> &v)
{
    int j = 0;
    for (int i = 1; i < v.size(); i++)
        if (v[i] != v[j] && ++j != i)
            v[j] = v[i];
    v.resize(j + 1);
}
def
quelle
-4

der schnellste Weg (zum Programmieren von Wettbewerben nach Zeitkomplexität () = konstant)

kann 100 Millionen Objekte in 1 Sekunde löschen;

    vector<int> it = (vector<int>::iterator) &vec[pos];
    vec.erase(it);

und am besten lesbarer Weg: vec.erase(vec.begin() + pos);

R.hatam
quelle
2
Dies ist sehr nicht tragbar; Es funktioniert mit libstdc ++, aber nicht mit libc ++ und nicht mit MSVC. vector<int>::iteratorist nicht unbedingt das gleiche wieint *
Marshall Clow
2
Es ist widerlich, ich denke, ich werde libstdc ++ ändern, damit es nicht funktioniert.
Jonathan Wakely