Mehrere Element in std::vector löschen



  • Hallo,
    ich habe hier ein etwas schwieriges Problem:
    Ich möchte mehrere Elemente aus einem Vektor löschen. Allerdings scheint meine Idee irgendwie nicht zu funktionieren.

    Meine Idee war:
    *Zuerst alle Indexe der Elemente, die gelöscht werden in einem std::set abspeicheren (->ship_indexes)
    *dann das erste Element löschen: Problem, die vorher abgespeicherten Indexe werden ungültig, da sich die Position der Element durch das Löschen verschiebt.
    Also aus einem Vektor mit
    vec[0]=0
    vec[1]=1
    vec[2]=2
    vec[3]=3
    wird nach dem löschen von vec[2]
    vec[0]=0
    vec[1]=1
    vec[2]=3

    Also muss ich abspeichern, wie viele Elemente ich gespeichert habe, und die Anzahl der gelöschten Elemente von dem abgespeicherten Index in ship_indexes abziehen. Das funktioniert natürlich nur, wenn ich die Elemente von oben nach unten lösche (also zuerst Index 0 dann 3 dann 5).
    Da std::set eh seine Elemente standardmäßig so sortiert ist das kein Problem.

    So, trotz allem scheint diese Idee nicht zu funktionieren.
    Ich bekomme einen Fehler, weil ich anscheinend ein Element 2x mit delete lösche.
    Ich weiß nicht mehr weiter, nach den Logs, die mein Programm ausgibt, scheint mein Algorithmus zu funktionieren, aber das Programm stürzt jedesmal beim Aufruf von delete ab.

    Hier der Code:

    while(index_iter!=ship_indexes.end())//clear all ships at the indexes in ShipVector
    	{
    		if(count_deletes>0)
    			_DPRINTL("count_deletes>0");
    		//save the size of the ship
    		shipsize_buffer_vector.push_back(ShipVector.at(*index_iter-count_deletes)->GetSize());
    		//clear ship from ShipVector
    		_DPRINTL("delete ship [%p]: *index_iter: %d, count_deletes: %d",ShipVector.at(*index_iter-count_deletes),*index_iter,count_deletes);
    		delete ShipVector.at((*index_iter-count_deletes)); //[crashes here] delete the Ship, because it was created with new
    		_DPRINTL("deleted ship [%p]!",ShipVector.at(*index_iter-count_deletes));
    		ShipVector.erase(ShipVector.begin() + (*index_iter-count_deletes)); //don't remove the brackets, or the iterator will jump for one moment over his bounds, that leads in VS to an assertion failed!
    
    		//with the erase all vector elements from (*index_iter-count_deletes) on moved one left
    		//so we will have to subtract one more than before, to erase the element meant by ship_indexes 
    		count_deletes++; 
    
    		_DPRINTL("DUMP: ShipVector after %d. delete",count_deletes);
    		DumpShipVector();
    		_DPRINTL("END DUMP: ShipVector after %d. delete",count_deletes);
    
    		index_iter++;
    	}
    

    Das ganze Projekt findet ihr auf:
    http://mitglied.lycos.de/xcooperation23/simulator/fight_simulator.html
    ([offtopic]falls ihr euch wundert wofür das ist: http://openspacegame.sourceforge.net/board/index.php
    [/offtopic])

    Hier ist noch ein "kleiner" Ausschnitt aus meinem Debug-Log:

    [debug 0]: DUMP: ship_indexes
    [debug 0]: 2
    [debug 0]: 5
    [debug 0]: 9
    [debug 0]: 12
    [debug 0]: END DUMP: ship_indexes
    [debug 0]: DUMP: ShipVector before
    [debug 0]: ShipVector[0]: 003569D0 -> Delete: 0 Healthpoints: 4500
    [debug 0]: ShipVector[1]: 00356CD8 -> Delete: 0 Healthpoints: 1500
    [debug 0]: ShipVector[2]: 00356DD0 -> Delete: 0 Healthpoints: 0
    [debug 0]: ShipVector[3]: 00356F78 -> Delete: 0 Healthpoints: 4500
    [debug 0]: ShipVector[4]: 00357028 -> Delete: 0 Healthpoints: 1500
    [debug 0]: ShipVector[5]: 003570D0 -> Delete: 0 Healthpoints: 0
    [debug 0]: ShipVector[6]: 00357178 -> Delete: 0 Healthpoints: 500
    [debug 0]: ShipVector[7]: 00357290 -> Delete: 0 Healthpoints: 7000
    [debug 0]: ShipVector[8]: 003573E0 -> Delete: 0 Healthpoints: 8000
    [debug 0]: ShipVector[9]: 00357660 -> Delete: 0 Healthpoints: 0
    [debug 0]: ShipVector[10]: 00357708 -> Delete: 0 Healthpoints: 5000
    [debug 0]: ShipVector[11]: 00357858 -> Delete: 0 Healthpoints: 5000
    [debug 0]: ShipVector[12]: 00357900 -> Delete: 0 Healthpoints: 0
    [debug 0]: END DUMP: ShipVector before
    [debug 0]: delete ship [00356DD0]: *index_iter: 2, count_deletes: 0
    [debug 0]: deleted ship [00356DD0]!
    [debug 0]: DUMP: ShipVector after 1. delete
    [debug 0]: ShipVector[0]: 003569D0 -> Delete: 0 Healthpoints: 4500
    [debug 0]: ShipVector[1]: 00356CD8 -> Delete: 0 Healthpoints: 1500
    [debug 0]: ShipVector[2]: 00356F78 -> Delete: 0 Healthpoints: 4500
    [debug 0]: ShipVector[3]: 00357028 -> Delete: 0 Healthpoints: 1500
    [debug 0]: ShipVector[4]: 003570D0 -> Delete: 0 Healthpoints: 0
    [debug 0]: ShipVector[5]: 00357178 -> Delete: 0 Healthpoints: 500
    [debug 0]: ShipVector[6]: 00357290 -> Delete: 0 Healthpoints: 7000
    [debug 0]: ShipVector[7]: 003573E0 -> Delete: 0 Healthpoints: 8000
    [debug 0]: ShipVector[8]: 00357660 -> Delete: 0 Healthpoints: 0
    [debug 0]: ShipVector[9]: 00357708 -> Delete: 0 Healthpoints: 5000
    [debug 0]: ShipVector[10]: 00357858 -> Delete: 0 Healthpoints: 5000
    [debug 0]: ShipVector[11]: 00357900 -> Delete: 0 Healthpoints: 0
    [debug 0]: END DUMP: ShipVector after 1. delete
    [debug 0]: count_deletes>0
    [debug 0]: delete ship [003570D0]: *index_iter: 5, count_deletes: 1
    [debug 0]: deleted ship [003570D0]!
    [debug 0]: DUMP: ShipVector after 2. delete
    [debug 0]: ShipVector[0]: 003569D0 -> Delete: 0 Healthpoints: 4500
    [debug 0]: ShipVector[1]: 00356CD8 -> Delete: 0 Healthpoints: 1500
    [debug 0]: ShipVector[2]: 00356F78 -> Delete: 0 Healthpoints: 4500
    [debug 0]: ShipVector[3]: 00357028 -> Delete: 0 Healthpoints: 1500
    [debug 0]: ShipVector[4]: 00357178 -> Delete: 0 Healthpoints: 500
    [debug 0]: ShipVector[5]: 00357290 -> Delete: 0 Healthpoints: 7000
    [debug 0]: ShipVector[6]: 003573E0 -> Delete: 0 Healthpoints: 8000
    [debug 0]: ShipVector[7]: 00357660 -> Delete: 0 Healthpoints: 0
    [debug 0]: ShipVector[8]: 00357708 -> Delete: 0 Healthpoints: 5000
    [debug 0]: ShipVector[9]: 00357858 -> Delete: 0 Healthpoints: 5000
    [debug 0]: ShipVector[10]: 00357900 -> Delete: 0 Healthpoints: 0
    [debug 0]: END DUMP: ShipVector after 2. delete
    [debug 0]: count_deletes>0
    [debug 0]: delete ship [00357660]: *index_iter: 9, count_deletes: 2
    

    so und nach dem delete gibts nen Crash.
    Wobei ich nicht weiß wieso, nirgendwo im Log wurde ein Schiff mit der Adresse 00357660 gelöscht.



  • Eine Frage: du speicherst die Indexe aller zu löschenden Schiffe, wieso deletest du sie nicht gleich beim Suchen danach?



  • Generell isses vielleicht laufzeitmäßig nicht so geschickt die Indices vorher irgendwo abzulegen. Dann lieber irgendwas mit std::remove konstruieren. Dein Problem kannste aber ganz einfach umgehen, indem Du die Elemente von hinten nach vorne löschst. Dadurch verschieben sich die vorderen Elemente nicht. 😉



  • Warum gehst du nicht einfach rückwärts durch dein set?



  • Damit Jesters Vorschlag nicht untergeht:

    #include <algorithm>
    
    struct MyPred
    {
        bool operator() (const ShipVectorContent& elem)
        {
            // wenn elem deleted werden soll -> return true
            return false;
        }
    };
    
    vector<ShipVectorContent>::iterator new_end = std::remove(ShipVector.begin(), ShipVector.end(), MyPred());
    
    ShipVector.erase(new_end, ShipVector.end());
    

    MfG SideWinder



  • std::erase( std::remove( ShipVectr.begin(), ShipVector.end(), MyPred() );
    

    so! 🙂

    Edit: Ups, zu spät...



  • Dass ich die Indexe abspeichere hat schon einen Grund:

    Das Problem ist folgendes:
    Das ganze ist ein Kampfsimulator, der einen Kampf zwischen zwei Raumschiffflotten berechnen soll.
    Wird ein Schiff zerstört habe ich es (wie ihr vorgeschlagen habt) in meiner ersten Version gleich gelöscht.
    Das Problem das ich dabei hatte war folgendes: Jedes Schiff hat eine bestimmte Wahrscheinlichkeit getroffen zu werden, abhängig von seiner Größe.
    Entferne ich das Schiff sofort, muss ich jedesmal wenn ein Schiff zerstört wird die Trefferwahrscheinlichkeit aller Schiffe neu berechnen.
    Meine Idee war also, die zerstörten Schiffe bis zum Ende einer Runde noch da zu lassen. (Dann können sie zwar immer noch getroffen werden, etwas unrealistisch, aber wenn ich genügend Geschwindigkeit dabei raushole geht das in Ordnung).
    Wird ein Schiff zerstört, speichere ich also seinen Index ab (dann weiß ich ja, welches Schiff kaputt ist, und muss nicht wieder den ganzen Array nach kaputten Schiffen durchsuchen).

    Und am Ende der Runde lösche ich die kaputten Schiffe aus der Flotte Das ist das was mein Code oben machen sollte).
    Dabei muss ich dann die Trefferwahrscheinlichkeit nur EINMAL berechnen

    Aber ich werd jetzt mal die Schiffe von hinten löschen, das sollte gehen.



  • Ok, ich hab jetzt euren Vorschlag umgesetzt und die Schiff von hinten her gelöscht.
    Ergebnis: gleiches Problem wie vorher :(.

    Code:

    INDEX_SET::reverse_iterator index_reviter;
    	index_reviter=ship_indexes.rbegin();
    
    	while(index_reviter!=ship_indexes.rend())//clear all ships at the indexes in ShipVector
    	{
    		if(count_deletes>0)
    			_DPRINTL("count_deletes>0");
    		//save the size of the ship
    		shipsize_buffer_vector.push_back(ShipVector.at(*index_reviter)->GetSize());
    		//clear ship from ShipVector
    		_DPRINTL("delete ship [%p]: *index_reviter: %d",ShipVector.at(*index_reviter),*index_reviter);
    		delete ShipVector.at(*index_reviter); //delete the Ship, because it was created with new
    		_DPRINTL("deleted ship [%p]!",ShipVector.at(*index_reviter));
    		ShipVector.erase(ShipVector.begin() + *index_reviter); //don't remove the brackets, or the iterator will jump for one moment over his bounds, that leads in VS to an assertion failed!
    
    		count_deletes++;
    
    		_DPRINTL("DUMP: ShipVector after %d. delete",count_deletes);
    		DumpShipVector();
    		_DPRINTL("END DUMP: ShipVector after %d. delete",count_deletes);
    
    		index_reviter++;
    	}
    

    Mir ist allerdings was aufgefallen:
    Schaut euch dieses Bild hier an: http://666kb.com/i/anhp4ws10z83hogy2.png

    Seht ihr auf was index_reviter zeigt?
    Genau auf eine negative Zahl. Das kann doch nicht sein?????
    Ich meine ich weiß ja nicht, es ist ja alles richtig programmiert soweit ich das sehe.
    Und was am aller seltsamsten ist:
    Gehe ich weiter, und schaue was ShipVector.at(size_t pos) macht, dann ist pos nicht der (falsche negative) Wert von index_reviter, sondern der richtige, auf den index_reviter auch zeigen sollte 😮 .
    Was soll das? Ein Bug in Visual Studio oder ein Fehler von mir???
    Bugs äußern sich ja manchmal in der schrägsten Dingen 😃
    Langsam hab ich das Gefühl, das mein Fehler irgendwo anderst liegt 😞
    Aber wo, das hier ist die einzige Stelle an der ich delete benütze...



  • Frage fürs eigene Verständnis: wieso dererenzierst du den iterator beim delete (also beim aufruf von at, genauer gesagt)



  • Also, ship_indexes speichert die Indexe der Elemente ab, die aus ShipVector gelöscht werden sollen.
    index_reviter ist ein Iterator, der auf ein Element in ship_indexes zeigt
    ShipVector enthält die Zeiger auf alle Schiffe in der Flotte.
    Da ich alle Schiffe mit new erstellt habe, muss ich sie, wenn ich sie aus der Flotte mit erase lösche, mit delete wieder löschen. (Sonst werden sie ja nie gelöscht -> Memory Leak)

    Deswegen mach ich

    delete ShipVector.at(*index_reviter); //delete the Ship, because it was created with new
    

    Heißt nix anderes als "Lösche jetzt das Schiff, das zerstört worden ist"
    Und *index_reviter sollte ja der Index des Schiffes sein das gelöscht wird

    Das war doch deine Frage oder?? 😃



  • Hmm, wenn man einen index dereferenziert erhält man das Element auf das er zeigt soweit ich bisher dachte.

    quasi:

    std::vector<int> v;
    v.push_back(5);
    std::iterator it=v.begin();
    assert((*it)=5);
    

    Von daher würde ich einfach

    delete *it;
    

    schreiben.



  • naja, aber da verwechselst du was:

    index_iter zeigt auf ship_indexes, der die Indexe der Schiffe enthält die gelöscht werden sollen.
    ShipVector enthält dann die Zeiger auf die Schiffe.

    Deswegen

    delete ShipVector.at(*index_reviter); //delete the Ship, because it was created with new
    


  • Achsoooo, *Klick*
    Sorry, hatte glatt vergessen, dass das ja nicht der vector ist auf den der iterator zeigt.

    Entschuldige dann.


Log in to reply