bestimmtes Element in std::vector löschen
-
Braunstein schrieb:
Nun ja. AFAIK wird end() und size() aber nicht neu gesetzt und das könnte bei der Weiterverwendung Probleme gegeben.
Ja, das gehört zu den Möglichkeiten, die Zugriff auf die Datenstruktur benötigen - und diesen Zugriff hat der Algorithmus nicht (schließlich soll er auch mit Arrays und eigenen Klassen arbeiten können - zumindest erstere haben kein size(), was man korrigieren könnte). Darum liefert es auch einen Iterator auf die neue Endposition zurück - mit der kannst du auch weiterarbeiten.
Ich habe auch nirgendwo gefunden, dass nach remove der Zugriff auf Elemente hinter dem neuen Ende undefiniertes Verhalten erzeugt.
Ich glaube, das war auch "nur" implementation defined - aber da müsste ich nachsehen.
-
Ok, das ist logisch.
Zum Löschen von Elementen aus einem Container gehört für mich einfach die Anpassung von size() etc. dazu.
-
CStoll schrieb:
vector::erase() macht auch nichts anderes als die Lücken durch nachfolgende Elemente aufzufüllen - es merkt sich nur, welcher Bereich seiner Daten gültige Elemente enthält).
das hoffe ich mal nicht. denn aufgrund der C-Syntax bei MPI versende ich std::vector-en immer via MPI::Send(&vec[0], 10,...). und auch sonst arbeite ich oftmals direkt mit den adressen. und bis data hatte ich hier weder mit dem gcc/Intel compiler/minGW oder cl probleme
spräche auch gegen die hohe performance von vectoren. für löschen innerhalb von containern soll man eh besser listen/maps der ähnliches verwenden.
ein nicht representativer test bestätigt zumindest meine aussage:
int main() { int main() { std::vector<int> vec; for(int i=0; i<8; i++) vec.push_back(i); for(int i=0; i<8; i++) std::cout<< (&vec[0])[i]<<" "; std::cout<<std::endl; vec.erase(vec.begin()+2); vec.push_back(9); for(int i=0; i<8; i++) std::cout<< (&vec[0])[i]<<" "; return 0; }ausgabe:
0 1 2 3 4 5 6 7
0 1 3 4 5 6 7 9bei wem dies nicht so rauskommt, der sage mir bitte bescheid.
-
Ich hab mal kurz in vector::erase in meiner dinkumware reingeschaut.
Dort wird folgendes gemacht.
- Die Daten von hinten über den zu löschenden Wert kopiert.
- destroy für das letzte Element aufgerufen
- end angepasst.
Die Daten bleiben also hintereinander.
-
ja, ich hab auch bei der STL-Implementierung für den cl von VS8 nachgeschaut. und im "C++ STL - verstehen, anwenden, erweitern" von gallileo steht es auch so. aber das mus snicht heissen, dass der standard das explizit so fordert... wäre nur interessant zu wissen.
-
Der Standard scheint das nicht zu fordern. Jedenfalls nicht in der Version die ich habe (2003 23.2.4.3).
-
Braunstein schrieb:
Der Standard scheint das nicht zu fordern. Jedenfalls nicht in der Version die ich habe (2003 23.2.4.3).
dacht mir sowas... schade...
-
Der Standard fordert seit der 2003er zumindest, dass &vec[0] gültig ist und ein Zeiger auf den Anfang der gesamten Sequenz ist. Ich hab jetzt keine Lust die Stelle rauszusuchen, das Thema kam in letzter Zeit aber häufiger. In einem der entsprechenden Beiträge gibts auch den Standardauszug.
-
Ich raff net so ganz, was ihr hier diskutiert, aber bei mir funktioniert das mit erase wunderbar. Alle nachfolgenden Daten werden wunderbar beibehalten und es läuft auch wunderschön schnell.
Danke nochmal, wegen dem Hinweis auf erase.
MfG Apo
-
LordJaxom schrieb:
Der Standard fordert seit der 2003er zumindest, dass &vec[0] gültig ist und ein Zeiger auf den Anfang der gesamten Sequenz ist. Ich hab jetzt keine Lust die Stelle rauszusuchen, das Thema kam in letzter Zeit aber häufiger. In einem der entsprechenden Beiträge gibts auch den Standardauszug.
hört sich doch schonmal ut an. aber der index operator muss auch bei allen anderen elementen korrekt funktionieren. und das meine ich, dass der sinn eines vectors flöten geht, wenn man bei vec[8] intern die "8" verbiegen muss, da man mal was gelöscht hat und die interne reihenfolge nicht mehr der "externen" entspricht. verkompliziert die interne sache einfach und kostet performance.
-
Meint ihr das aus 23.2.4 1
... Storage management is handled automatically, though hints can be given to improve efficiency. The elements of a vector are stored contiguously, meaning that if v is a vector<T, Allocator> where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().
-
Braunstein schrieb:
Meint ihr das aus 23.2.4 1
... Storage management is handled automatically, though hints can be given to improve efficiency. The elements of a vector are stored contiguously, meaning that if v is a vector<T, Allocator> where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().
Exakt. Das heisst auch muffmolchs Indexoperator funktioniert hinreichend korrekt
-
Wenn man das mit 23.2.4.3 zusammenbringt steht eigentlich fest, dass den Bibliotheksherstellern gar nichts anderes übrig bleibt, als nach erase zu kopieren und dann end und size anzupassen. Evtl. vorher erzeugte Iteratoren gelten dann natürlich nicht mehr für den Bereich ab dem gelöschten Element.
-
Mal zum remove:
Wenn die Funktionalität von remove "implementation defined" ist, dann würde das doch bedeuten, dass man damit rechnen muss, dass die Objekte einfach mit 0 überschrieben werden, oder? Wenn das Objekt aber kein POD ist, sondern selbst speicher verwaltet, dann würde der Zeiger darauf doch durch das Überschreiben verloren gehen?Noch schlimmer: wenn man danach vector::erase aurufen würde, würde nachträglich auf diesen kaputten Objekten der dtor aufgerufen(ist schätzungsweise wohl auch implementation defined, hab grad den standard net da).
Ist es unter diesen voraussetzungen überhaupt sinnvoll, remove zu verwenden?
-
Beim reinen remove sehe ich auch keinen Grund. Bei remove_if aber schon und das würde ich dann auch nur im Zusammenhang mit einem erase nutzen.
remove hat aber eben den Vorteil?!, dass es auch auf normale Arrays angewandt werden kann. Wenn das ein Vorteil ist.
-
@otze:
Dem Problem begegnet man, wie immer innerhalb der STL, wo ja häufiger Elemente umgelagert werden (man denke an das Einfügen mitten in einen vector), durch korrekte Kopiersemantik. Ein Objekt mit 0 überschreiben zu können, setzt ausserdem voraus, dass 0 für diesen Typ ein gültiger Wert ist
-
LordJaxom schrieb:
Braunstein schrieb:
Meint ihr das aus 23.2.4 1
... Storage management is handled automatically, though hints can be given to improve efficiency. The elements of a vector are stored contiguously, meaning that if v is a vector<T, Allocator> where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().
Exakt. Das heisst auch muffmolchs Indexoperator funktioniert hinreichend korrekt
puh... ihr bringt mich hier ins schwitzen... da hab ich ja nochmal glück gehabt
-
otze schrieb:
Mal zum remove:
Wenn die Funktionalität von remove "implementation defined" ist, dann würde das doch bedeuten, dass man damit rechnen muss, dass die Objekte einfach mit 0 überschrieben werden, oder? Wenn das Objekt aber kein POD ist, sondern selbst speicher verwaltet, dann würde der Zeiger darauf doch durch das Überschreiben verloren gehen?Wenn du 'p=remove(b,e,v);' aufrufst, ist garantiert, daß der zu löschende Wert nicht mehr im Bereich [b,p[ vorkommt und daß alle anderen Elemente in der ursprünglichen Reihenfolge bleiben - was im Bereich [p,e[ zurückbleibt, ist afaik nicht spezifiziert (allerdings sind die Objekte dort noch technisch intakt).