Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Element aus Vector entfernen

Werbeanzeige

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

11

14.02.2015, 17:14

Der Nachteil so einer for-Konstruktion ist, dass man später gern übersieht, dass der Iterator manuell inkrementiert werden muss. Ein while macht das gleich von Anfang an klar.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

12

14.02.2015, 17:57

Es sollte auch noch gesagt werden, dass das Löschen aus einem std::vector ineffizient ist. Wenn du beispielsweise das erste Element löschst, müssen alle, die danach kommen, um eins nach vorne rücken (d. h. alle Elemente müssen kopiert werden - und da ist es je nach Größe der Elemente vorteilhaft, wenn du nur Zeiger speicherst).

Kommt das Löschen häufig vor, so empfiehlt sich ggf. eine std::list, die natürlich andere Nachteile hat ... Es kommt also auf deinen konkreten Anwendungsfall an.

Oder alternativ, falls die Reihenfolge der Elemente keine Rolle spielt, kannst du einen Trick anwenden: Lösche ein Element, indem du das letzte Element an seine Stelle kopierst und dann das letzte Element löschst, was schnell geht, da nichts aufrücken muss.
David Scherfgens Website | Konzentrationstest Polizei

Spiele Programmierer

Alter Hase

Beiträge: 1 223

Wohnort: Deutschland Bayern

Beruf: Schüler

  • Private Nachricht senden

13

14.02.2015, 18:10

Wenn du Performance sparen willst, möchte ich gerade noch anmerken, dass deine Konstruktion bei vielen Elemente ineffizient wird, wenn du mehrere Objekte aus dem Vektor löscht. Jeder einzelne Aufruf von "erase" verschiebt alle Elemente nach dem aktuellen Element. "erase" ist also eine O(n) Operation und die Schleife dann O(n*k), wobei k die Anzahl zu löschender Elemente angibt.

Ist das bei dir der Fall, wäre folgendes besser. Im Prinzip werden die Objekte alle zusammengeschoben und der Vector dann am Ende einmal verkleinert.
Das geht so...

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12

auto ReadIter = Field.begin();
auto WriteIter = Field.begin();
for (; ReadIter != Field.end(); ++ReadIter)
{
    if ((*ReadIter)->GetFieldValue() == 0) //Wenn nicht(!) entfernt, an neue Stelle schieben. -> Vergleich negiert
    {
        if (WriteIter != ReadIter) //Verschieben notwendig?
            *WriteIter = std::move(*ReadIter);
        ++WriteIter;
    }
}
Field.erase(WriteIter, Field.end()); //Alle unnütz gewordenen Objekte am Ende löschen...


Es gibt aber auch schon eine fertige Methode in der C++ STL, die das selbe macht aber bevorzugt werden sollte. (In "algorithm")

C-/C++-Quelltext

 
1
2
3
4

Field.erase(std::remove_if(Field.begin(), Field.end(), [](CField* const Field)
    {
        return Field->GetFieldValue() != 0;
    }), Field.end());


@David
Die std::list ist dafür beim Iterieren wesentlich ineffizienter, weil man eine fast unendliche Pointerkette quer durch den Speicher hat. Das ist auch sehr schlecht für den Cache. Da man in 99% der Fälle viel häufiger für die Einträge iteriert als Elemente entfernt, ist eine std::list in 99% der Fälle eine schlechte Wahl. Bis zu einer gewissen Zahl in 100en bis 10000en Objekten ist die "std::list" sogar dann noch langsamer, weil die Allokation und das Löschen der einzelnen Einträge auf dem Heap viel länger dauert. Eine Situation in der die std::list in der Praxis besser abscheidet kommt fast nicht vor.

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »Spiele Programmierer« (14.02.2015, 18:16)

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

14

15.02.2015, 09:40

Man sollte sich als erstes Mal fragen, warum aus seinem 9x9 Spielfeld irgendwo in der Mitte ein Feld geloescht werden muss. Idealerweise, legt man sich diese 81 Elemente am Anfang in einem Block einmal an (egal ob man da jetzt new, reserve oder resize nimmt) und fasst das dann nie weder an.
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

Helmut

5x Contest-Sieger

Beiträge: 692

Wohnort: Bielefeld

  • Private Nachricht senden

15

15.02.2015, 11:38

@Spiele Programmierer
Schöne Antwort!
Hier ist ein interessanter Vortrag für die, die das genauer interessiert.
Sei stets geduldig gegenüber Leuten, die nicht mit dir übereinstimmen. Sie haben ein Recht auf ihren Standpunkt - trotz ihrer lächerlichen Meinung. (F. Hollaender)

Spiele Programmierer

Alter Hase

Beiträge: 1 223

Wohnort: Deutschland Bayern

Beruf: Schüler

  • Private Nachricht senden

16

15.02.2015, 13:10

Dieses Video kann ich auch empfehlen - und habe ich auch schon selbst ab und zu zu solchen Themen verlinkt. ^^
Die Frage nach den Lists tritt ja häufiger auf.

Urprimat

Treue Seele

  • »Urprimat« ist der Autor dieses Themas

Beiträge: 91

  • Private Nachricht senden

17

20.02.2015, 13:02

Vielen Dank für die vielen antworten.
ich werde wohl einiges ändern müssen.


EDIT:
@TGGC
Der Vektor um den es geht beschreibt den Weg den das Programm durch die 9*9 Felder zu gehen hat.
Jedes Feld bekommt unter einigen bedingungen einen Wert zugewisen und wird dann aus dem "Weg" Vector gelöscht.
Wenn es die bedingungen NICHT erfüllt bleibt es im Weg Vector drin, da es vielleicht in der nächten runde die bedingungen erfüllt.

Ich spare dadurch extrem viel Zeit. Bevor ich diesen "Weg" Vector benutzt hatte brauchtes das programm ca 17 sek. nun sind es 1,4 sek.



Liebe Grüße Urprimat
Most good programmers do programming not because they expect to get paid or get adulation by the public, but because it is fun to program.

Linus Torvalds

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »Urprimat« (20.02.2015, 13:10)

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

18

20.02.2015, 14:34

Wenn du immer nur ein Flag setzen wuerdest "wird nicht mehr benutzt" waers vielleicht trotzdem schneller. Eine andere Methode ist es einen zweiten Vektor aufzubauen, in dem du die Indizes der Felder speicherst, die du nicht rausloeschen wolltest. Allgemein kann man aber schwer sagen, was besser ist. Das Loeschen ist es aber selten.
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

19

21.02.2015, 16:02

Alternativ nicht benötigte Objekte ans Ende des Vectors schieben und selbst merken wo Ende der aktiven Objekte ist. So ähnlich hast du es ja am Anfang auch vorgeschlagen TGGC.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

20

21.02.2015, 23:20

Auch eine gute Strategie, vor allem wenn die Reihenfolge keine Rolle spielt!
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

Werbeanzeige

Ähnliche Themen