c++.de :: Zwei Elemente an Iteratorposition von Vector entfernen

pyhax Mitglied 16:39:33 02.05.2012 Titel:

Hallo,

ich möchte von einem std::vector jeweils das größte und das kleinste Element entfernen. Dazu habe ich mit std::minmax_element(C++11) das größte und kleinste Element gesucht, da ich die Werte der Elemente noch weiter verwenden möchte. Um jetzt die beiden Elemente von dem Vektor zu entfernen, müsste ich zweimal vector::erase aufrufen. Das funktioniert aber nicht, da dann der zweite Iterator ungültig wird. Wie kann man das verhindern bzw. gibt es eine andere Möglichkeit zwei Elemente von einem Vektor zu entfernen?

SeppJ Moderator 16:52:55 02.05.2012 Titel:

Ist die Reihenfolge wichtig? Falls nein, dann kopier doch das hinterste Element an die Stelle und verkleiner den vector um 1. Oder du löscht zuerst den hinteren der beiden Werte, denn erase macht nur Iteratoren ungültig, die auf den gelöschten Wert folgen.

Werner Salomon Mitglied 16:56:00 02.05.2012 Titel:

Hallo pyhax,

Du musst Dir eben für das Löschen des zweiten Elements den Index merken. Damit sich dieser nicht verändert, muss das Element mit dem größeren Index zuerst gelöscht werden. Weiter muss noch der Fall, dass beide Iteratoren gleich sind bedacht werden. Eine Skizze:

C++:
1 2 3 4 5 6 7 8 9 10	vector< int > v; // v = ... std::pair< vector< int >::iterator, vector< int >::iterator > res = minmax_element( v.begin(), v.end() ); if( res.second < res.first ) swap( res.first, res.second ); const bool min_equal_max = res.first == res.second; // auch vor erase merken, ob Iteratoren gleich sind const vector< int >::size_type idx1 = res.first - v.begin(); v.erase( res.second ); // nach diesem Aufruf kann man mit res nichts mehr anfangen if( !min_equal_max ) v.erase( v.begin() + idx1 );

Gruß
Werner

pyhax Mitglied 16:57:14 02.05.2012 Titel:

Ok, danke SeppJ, dass erase nur die Iteratoren ungültig macht, die auf den gelöschten Wert folgen wusste ich nicht. Dann lösche ich als erstes den hinteren.

Edit:

@Werner: Das beide Iteratoren gleich sind kann bei mir nicht passieren, da der Vektor immer mindestens 3 Werte enthält (wird durch eine andere Funktion sichergestellt).

Edit2:

@Werner: Eigentlich müsste idx1 ja vom Typ vector::difference_type sein, oder?

Werner Salomon Mitglied 17:10:12 02.05.2012 Titel:

pyhax schrieb:

Ok, danke SeppJ, dass erase nur die Iteratoren ungültig macht, die auf den gelöschten Wert folgen wusste ich nicht. Dann lösche ich als erstes den hinteren.

funktioniert wahrscheinlich mit 100% aller vector-Implementierungen, aber ich glaube nicht, dass der Standard das garantiert. Müsste man mal nachlesen

pyhax schrieb:

@Werner: Das beide Iteratoren gleich sind kann bei mir nicht passieren, da der Vektor immer mindestens 3 Werte enthält (wird durch eine andere Funktion sichergestellt).

.. und wenn die drei Werte gleich sind?

pyhax schrieb:

@Werner: Eigentlich müsste idx1 ja vom Typ vector::difference_type sein, oder?

stimmt difference_type ist richtig

Mir fällt gerade ein, dass ein remove-Mechanismus wesentlich performanter wäre, als ein doppelter erase. Muss ich noch mal drüber nachdenken. Wie groß sind die Vektoren in etwa?

Gruß
Werner

pyhax Mitglied 17:22:20 02.05.2012 Titel:

Werner Salomon schrieb:

pyhax schrieb:

@Werner: Das beide Iteratoren gleich sind kann bei mir nicht passieren, da der Vektor immer mindestens 3 Werte enthält (wird durch eine andere Funktion sichergestellt).

.. und wenn die drei Werte gleich sind?

pyhax schrieb:

@Werner: Eigentlich müsste idx1 ja vom Typ vector::difference_type sein, oder?

stimmt difference_type ist richtig

Mir fällt gerade ein, dass ein remove-Mechanismus wesentlich performanter wäre, als ein doppelter erase. Muss ich noch mal drüber nachdenken. Wie groß sind die Vektoren in etwa?

Gruß
Werner

1) Dann ist der Vektor auch ungültig. In dem Vektor werden Punkte eines Polygons gespeichert, die sollte nicht alle 3 gleich sein

2) Nicht so groß. Ist mir eigentlich egal, bis jetzt stört mich Performace weniger.

SeppJ Moderator 17:40:07 02.05.2012 Titel:

Werner Salomon schrieb:

pyhax schrieb:

Ok, danke SeppJ, dass erase nur die Iteratoren ungültig macht, die auf den gelöschten Wert folgen wusste ich nicht. Dann lösche ich als erstes den hinteren.

funktioniert wahrscheinlich mit 100% aller vector-Implementierungen, aber ich glaube nicht, dass der Standard das garantiert. Müsste man mal nachlesen

Das ist garantiertes Verhalten:

C++ 23.3.6.6,3 schrieb:

Effects: Invalidates iterators and references at or after the point of the erase.

pumuckl Moderator 19:10:01 02.05.2012 Titel:

Mal ne Frage, bei der ich mich wundere, warum sie noch keiner gestellt hat: Was machst du sonst noch mit dem vetor? Wenn das "remove_minmax" die Hauptaufgabe ist, würde sich für einfaches Handling ein std::(multi)set anbieten. Sonst würde ichs vermutlich wie folgt lösen:

C++:
1 2 3 4 5 6 7 8 9	template <class T> void remove_minmax(std::vector<T>& v) { auto size = v.size(); auto minmax = std::minmax_element(std::begin(v), std::end(v)); std::swap((minmax.first), v[size-1]); std::swap((minmax.second), v[size-2]); v.resize(size-2); };

Ich habs mir jetzt nicht komplett durchgedacht, aber vermutlich würds auch reichen, an Stelle des swap move-Zuweisungen zu nehmen, weil man die beiden letzten Stellen ja eh wegwirft:

C++:
1 2 3 4 5 6 7 8 9	template <class T> void remove_minmax(std::vector<T>& v) { auto size = v.size(); auto minmax = std::minmax_element(std::begin(v), std::end(v)); (minmax.first) = std::move(v[size-1]); (minmax.second) = std::move(v[size-2]); v.resize(size-2); };