Kreaturen Liste erstellen

[starcow]

Hallo Zusammen.

Ich stelle grad etwas erstaunt fest, dass sich eine std:list anscheinen ja doch ohne Probleme mit Instanzen einer Klasse füllen lässt.

Code: Alles auswählen

std::list<Kreatur> kreaturenListe; // Die Kreaturen-Liste
Kreatur kreatur; // Eine Kreatur-Instanz
kreaturenListe.push_back(kreatur);

Bislang dachte ich immer, man könne in einem vector oder list keine tatsächlichen Klassen-Objekte speichern, sondern müsse den Weg über den Heap mittels Pointer gehen.

Code: Alles auswählen

std::list<Kreatur*> kreaturZeigerListe; // Die Kreaturen-Liste
Kreatur* kreaturZeiger = new Kreatur; // Eine neue Kreatur-Instanz auf dem Heap
kreaturZeigerListe.push_back(kreaturZeiger);

Jetzt frage ich mich - da ja beides zu funktionieren scheint - weshalb ich den Weg mittels Zeiger gehen sollte, wenn ich die Kreaturen auch direkt in die Liste speichern kann.
In den Anfängen von C und C++ lernt man doch, dass es unumgänglich ist, mit new oder malloc zu arbeiten, wenn man Objekte zur Laufzeit erzeugen will.
Ganz offensichtlich lassen sich ja aber mit beiden Methoden zur Laufzeit neue Kreatur-Instanzen erzeugen - quasi dank der stl.

Übersehe ich da grad etwas entscheidendes? Zur welchen Methode würdet ihr mir raten? Stimmt denn die Überlegung, dass ich das Risiko eines Memory-Leaks ausschliessen kann, sofern ich kein "new" oder "malloc" einsetze und stattdessen die Instanzen direkt in einem vector oder einer list speichere?

Gruss starcow

[xq]

Hey starcow!

Übersehe ich da grad etwas entscheidendes?

Ja, dass die STL-Container das new/malloc für dich übernehmen. Die Container können jeden Typen aufnehmen, den du als "T" übergibst. vector<T> garantiert dir Speicherreihenfolge, das heißt, dein erstes ([1]) Element liegt immer direkt hinter nullten ([0]) Element und so weiter. Eine list<T>[/list] garantiert dir nur, dass die Elemente in der Reihenfolge gespeichert sind, hat dafür aber andere Komplexitäten/Laufzeiten als ein Vektor.

Zur welchen Methode würdet ihr mir raten?

Falls nur keine Polymorphie brauchst: vector oder list, ansonsten würde ich einen vector<unique_ptr<T>> nutzen, da dieser das Verhalten von einem vector<T> hat, aber trotzdem mit polymorphen Klassen umgehen kann (also mit Vererbung).

Stimmt denn die Überlegung, dass ich das Risiko eines Memory-Leaks ausschliessen kann, sofern ich kein "new" oder "malloc" einsetze und stattdessen die Instanzen direkt in einem vector oder einer list speichere?

Du kannst natürlich immer noch ein Memory Leak haben, aber: Die Containertypen garantieren dir, dass wenn der Container gelöscht wird, alle gespeicherten Objekte gelöscht werden. Hier gilt aber: Wenn du einen Pointer in einem Container speicherst, wird nur der Pointer (also das Objekt, dass die Adresse speichert) gelöscht, nicht aber das Objekt, auf das dieser Pointer zeigt.

Was hier gilt: Wenn du eigene Objekte in Containern speicherst, müssen diese im Destruktor natürlich auch all ihren Speicher freigeben, sonst hast du ebenfalls ein Memory Leak.

Aber grundlegend programmiere ich mittlerweile C++ mit dem Stil new-free programming, nutze also immer sowas wie std::make_unique oder std::make_shared und erzeuge keine Objekte mehr via new/malloc. Da bleibt einem einfach sehr viel Stress erspart

[joeydee]

Bin mir nicht mehr sicher, aber was genau passiert wenn ich einen Vector zur Laufzeit dynamisch erweitere?
Wenn die Speicherreihenfolge garantiert bleiben soll kann es ja passieren, dass der komplette Vector intern umkopiert werden muss? Würde bedeuten, falls man sich irgendwo einen Pointer auf Element X geholt hat, dieser irgendwann nicht mehr gültig sein könnte, ist das richtig?

[xq]

Bin mir nicht mehr sicher, aber was genau passiert wenn ich einen Vector zur Laufzeit dynamisch erweitere? Wenn die Speicherreihenfolge garantiert bleiben soll kann es ja passieren, dass der komplette Vector intern umkopiert werden muss? Würde bedeuten, falls man sich irgendwo einen Pointer auf Element X geholt hat, dieser irgendwann nicht mehr gültig sein könnte, ist das richtig?

Ja, genau das. Ein Vektor hat eine Kapazität und eine Größe. Wenn der Vektor über die Kapazität hinaus wächst, wird intern ein neuer Speicher allokiert und die Objekte vom alten Speicher in den neuen Speicher gemoved. Damit verändern sie ihren Pointer.

[starcow]

Vielen Dank Master! :)

vector<T> garantiert dir Speicherreihenfolge, das heißt, dein erstes ([1]) Element liegt immer direkt hinter nullten ([0]) Element und so weiter. Eine list<T>[/list] garantiert dir nur, dass die Elemente in der Reihenfolge gespeichert sind, hat dafür aber andere Komplexitäten/Laufzeiten als ein Vektor.

Heisst das, dass es mir erlaubt ist, einen vector folgendermassen zu durchlaufen?

Code: Alles auswählen

std:vector<int> elemente;
elemente.push_back(35);
elemente.push_back(45);
elemente.push_back(98);

for (unsigned int i = 0; i < elemente.size(); ++i) {
std::cout "Inhalt: " << elemente.at(i) << std::endl;
}

Bei einer Liste habe ich es so gelernt:

Code: Alles auswählen

for (std::list<int>::iterator iCurrent = LISTcreatur.begin(); iCurrent != LISTcreatur.end(); ++iCurrent) {
}

Das würde aber eigentlich auch voraussetzen, dass die Elemente in der Liste im Speicher direkt hintereinander abgebildet sind.
Wäre dem nicht so, müsste ja der Zeiger durch die iteration (++iCurrent) in der Konsequenz auf einen unzulässigen Speicherbereich verweisen.

Mir ist jetzt aber doch noch eine Situation in den Sinn gekommen, in der es grosse Vorteile mit sich bringt, wenn man anstatt des Objektes, nur deren Zeiger in einer Liste speichert.
Da das Objekt auf dem Heap mittels "new" erstellt wurde, ist damit garantiert, dass sich die Speicheradresse des Objektes nicht ändert - bis man es löscht.
Somit habe ich auch gleich einen "Identifikator".
Wenn das Objekt z. B eine Axt ist, kann ich dem Player die Speicheradresse dieser Axt mitteilen, und dieser kann dann über den Zeiger auf die Attribute der Axt zugreifen.
Liegt das Objekt hingegen in einer Liste, darf ich an dieser Stelle nicht mit Pointern arbeiten, da nicht garantiert ist, dass die Speicheradresse konstant bleibt.
Ich müsste also dem Objekt resp. der Axt intern eine ID mitgeben und jedesmal die Liste druchlaufen, bis ich auf die ID stosse, nur um einen Wert abzufragen oder zu verändern.
Da scheint mir die Lösung mit den Pointern, die sich in einer Liste befinden, wesentlich eleganter und schneller.

Gruss starcow

[RustySpoon]

Das würde aber eigentlich auch voraussetzen, dass die Elemente in der Liste im Speicher direkt hintereinander abgebildet sind.
Wäre dem nicht so, müsste ja der Zeiger durch die iteration (++iCurrent) in der Konsequenz auf einen unzulässigen Speicherbereich verweisen.

Naja, das ist ja der Witz an einem Iterator. Der ermöglicht dir sequentiellen Zugriff (und imitiert das Verhalten eines Pointers), kann intern aber sonstwas treiben. Es wird ja keine Aussage darüber getätigt wie ++iCurrent überhaupt implementiert ist.

[NytroX]

Noch ein paar Tipps:

Statt einem Iterator, würde ich einfach ein foreach benutzen, das ist weniger kompliziert und man muss nicht mit der Länge/size rumhantieren.

Du kannst statt einem Pointer einfach den Index speichern. Selbst wenn der vector dann reallokiert wird, bleibt der index ja gleich. Und der erlaubt auch sofortigen Zugriff.
Das einzige Problem daran ist, dass es passieren kann, dass der Index nicht mehr gültig ist, wenn du die Kreatur aus dem vector löschst.

Am besten immer mit "kreaturen.at(index)" auf den vector zugreifen, nie direkt mit "kreaturen[index]", das erspart viele schlimme Dinge.

Wenn Kreaturen auf andere zeigen, könnte man das auch mit einer shared_ptr/weak_ptr Kombination lösen, dann kann man frei löschen, was man will; aber dann wirds komplizierter :-)

Beispiele:

Code: Alles auswählen

#include <vector>
#include <string>
#include <optional>
#include <algorithm>

struct Kreatur
{
	std::string name = "";
	int leben = 0;
	std::optional<size_t> reitet_auf = {}; //optional, vielleicht reitet er garnicht
};

void start_game() {
	//vector erstellen
	auto kreaturen = std::vector<Kreatur>{};

	//neue kreaturen
	kreaturen.push_back(Kreatur{ "Drache", 100, {} });
	kreaturen.push_back(Kreatur{ "Pferd", 100, {} });
	kreaturen.push_back(Kreatur{ "Mensch", 20, {} });

	//iterieren über kreaturen mit foreach
	for (auto& kreatur : kreaturen) {
		kreatur.leben += 10;
	}

	//setz den mensch aufs pferd

	//such das pferd
	auto pferd = std::find_if(kreaturen.begin(), kreaturen.end(), [](const auto& kreatur) {return kreatur.name == "Pferd";  });
	if (pferd != kreaturen.end()) {
		//gefunden - jetzt index merken
		auto pferd_index = std::distance(kreaturen.begin(), pferd);
		//such den mensch
		auto mensch = std::find_if(kreaturen.begin(), kreaturen.end(), [](const auto& kreatur) {return kreatur.name == "Mensch";  });
		if (mensch != kreaturen.end()) {
			//gefunden - und losreiten!
			mensch->reitet_auf = pferd_index;

			//reitet der mensch?
			if (mensch->reitet_auf.has_value()) {
				//ah gut, er reitet gerade - jetz gib mir das reittier, ohne zu suchen
				auto reittier_index = mensch->reitet_auf.value();
				auto& reittier = kreaturen.at(reittier_index);
				reittier.leben -= 20; // pferd ist k.o. :-)
			}
		}
	}
}

[Krishty]

Am besten immer mit "kreaturen.at(index)" auf den vector zugreifen, nie direkt mit "kreaturen[index]", das erspart viele schlimme Dinge.

Am besten immer sicherstellen, dass man seine Indizes gültig hält. Das ist vielleicht kniffliger, aber falsche Array-Indizes verschlucken ist er der Anfang von richtig schlimmen Dingen.

[starcow]

Danke für den Tipp bezüglich foreach, NytroX :)

Ich vermute die Idee mit gespeicherten Index wird wohl eher aufwändiger und fehleranfälliger als der Ansatz über die Pointer.
Die Kreaturen werden halt immer wieder aus der Liste gelöscht, sobald sie der Tod ereilt - und das dürfte bei einem Spiel mit Hack & Slay Charakter ziemlich oft der Fall sein ^^. Man müsste dann ja die Index-Nummern jedes mal umsortieren, sofern ich deine Idee jetzt richtig verstanden habe.