Handle zu Objekt in Vektor

[Yamahari]

Hallo Forum,
Ich habe den Vektor

std::vector<Entity> entities

und möchte bestimmte Entity Instanzen in diesem Vektor verfolgen.
Dies ist alles kein Problem solange der Vektor nicht neu geordnet wird oder das Datenfeld eine neue Speicheradresse erhält, z.B. beim Überschreiten der reservierten Kapazität.

Der Vektor wird momentan durch die folgende Funktion von "toten" Entities gesäubert :

entities.erase(std::remove_if(entities.begin(), entities.end(),
	[](Entity& entity)
{
	return !entity.isAlive();
}), entities.end());

Was wäre eine elegante Methode Entity Handles zu implementieren ?
Meine Ansätze wären dabei entweder den Index ins Datenfeld oder einen Zeiger direkt zur Speicheradresse des Entities zu verwenden. Allerdings werden diese aufgrund der oben genannten Anhaltspunkte ungültig. Also bräuchte ich einen cleveren Weg den Index oder Zeiger zu aktualisieren.
Wäre dankbar für Ansätze oder Lösungen

[Mechanics]

Muss das ein Vektor sein? Es wäre einfacher, eine andere Datenstruktur zu verwenden, wie map oder unordered_map mit dem Key als Handle.

[wob]

Du könntest z.B. einen std::vector<std::unique_ptr<Entity>> verwenden - wenn sich das Vector-Layout ändert, bleibt die Entity trotzdem an derselben Stelle, nur der Zeiger steht anderswo im Speicher. Aber du musst natürlich dennoch beim erase beachten, dass du dann nicht mehr den gespeicherten Pointer nutzen kannst.

Du könntest auch std::shared_ptr<Entity> in deinen vector tun und als Observerklasse einen std::weak_ptr nehmen, dann stellt dieser mittels lock() fest, ob es den shared_ptr noch gibt oder nicht.

Könnte aber sein, dass diese Ansätze nicht zu deinem Problem passen. Wie groß ist denn sizeof(Entity) ? Je größer Entity ist, desto eher bieten sich diese std::vector<Pointertyp> -Lösungen an.

[dot]

wob schrieb:

Du könntest z.B. einen std::vector<std::unique_ptr<Entity>> verwenden - wenn sich das Vector-Layout ändert, bleibt die Entity trotzdem an derselben Stelle, nur der Zeiger steht anderswo im Speicher.

Oder einfach std::list...

[Finnegan]

dot schrieb:

wob schrieb:

Du könntest z.B. einen std::vector<std::unique_ptr<Entity>> verwenden - wenn sich das Vector-Layout ändert, bleibt die Entity trotzdem an derselben Stelle, nur der Zeiger steht anderswo im Speicher.

Oder einfach std::list...

Ich will auch mal nochwas einwerfen: boost::stable_vector - wenns denn unbedingt etwas array-artiges sein soll und man nicht möchte dass einem Referenzen unterm Arsch weggezogen werden.

[Yamahari]

Mechanics schrieb:

Muss das ein Vektor sein? Es wäre einfacher, eine andere Datenstruktur zu verwenden, wie map oder unordered_map mit dem Key als Handle.

Der Vorteil eines Vektors bestehend darin, dass die Elemente kontinuierlich im Speicher untergebracht sind. Das beschleunigt das Iterieren enorm; besonders wenn jedes System eben dies 60 Mal in der Sekunde macht.

wob schrieb:

Du könntest z.B. einen std::vector<std::unique_ptr<Entity>> verwenden - wenn sich das Vector-Layout ändert, bleibt die Entity trotzdem an derselben Stelle, nur der Zeiger steht anderswo im Speicher. Aber du musst natürlich dennoch beim erase beachten, dass du dann nicht mehr den gespeicherten Pointer nutzen kannst.

Du könntest auch std::shared_ptr<Entity> in deinen vector tun und als Observerklasse einen std::weak_ptr nehmen, dann stellt dieser mittels lock() fest, ob es den shared_ptr noch gibt oder nicht.

Könnte aber sein, dass diese Ansätze nicht zu deinem Problem passen. Wie groß ist denn sizeof(Entity) ? Je größer Entity ist, desto eher bieten sich diese std::vector<Pointertyp> -Lösungen an.

Der Hintergedanke beim Vektor besteht eben darin, wie oben schon erwähnt, dass die Entities alle nebeneinander im Speicher liegen. Das erhöht die Performance bei häufigem Iterieren deutlich. Einen Zeiger zu verwenden würde dem ursprünglichen Gedanken eher entgegenwirken. Momentan sehen meine Entities wie folgt aus:

template < typename T >
struct Entity
{
	bool alive;
	typename T::Signature signature;
	std::map<std::size_t, std::size_t> componentDataIndices;
};

Vielleicht muss ich auch noch einmal mein Layout überdenken, so brauch ich im Endeffekt vielleicht sogar gar keine Handles mehr.

[dot]

Yamahari schrieb:

Mechanics schrieb:

Muss das ein Vektor sein? Es wäre einfacher, eine andere Datenstruktur zu verwenden, wie map oder unordered_map mit dem Key als Handle.

Der Vorteil eines Vektors bestehend darin, dass die Elemente kontinuierlich im Speicher untergebracht sind.

Damit die Element aber immer kontinuierlich im Speicher untergebracht sein können, müssen bei Änderungen am Vektor dessen Elemente im Speicher verschoben werden, womit wie beim Ausgangsproblem sind. Gleichbleibende Adresse der Elemente und zusammenhängende Speicherung einer dynamisch veränderlichen Sequenz an Elementen schließen sich also rein prinzipiell gegenseitig aus...

[Mechanics]

Yamahari schrieb:

Der Vorteil eines Vektors bestehend darin, dass die Elemente kontinuierlich im Speicher untergebracht sind. Das beschleunigt das Iterieren enorm; besonders wenn jedes System eben dies 60 Mal in der Sekunde macht.

Ja, das hat schon was, ich verwende auch gern Vektoren, auch sowas wie boost::flat_map. Du musst aber schauen, ob sich das wirklich lohnt und ob du dir dadurch nicht unnötige Nachteile einhandelst. 60 mal pro Sekunde hört sich jetzt nicht nach so viel an (du wirst wahrscheinlich mehr Probleme mit dem Scheduling des Betriebssystems haben) und so wahnsinnig groß wird der Vorteil beim Iterieren auch nicht sein. Da musst du abwägen (und messen), was mehr ins Gewicht fällt.

[Yamahari]

Mechanics schrieb:

Yamahari schrieb:

Der Vorteil eines Vektors bestehend darin, dass die Elemente kontinuierlich im Speicher untergebracht sind. Das beschleunigt das Iterieren enorm; besonders wenn jedes System eben dies 60 Mal in der Sekunde macht.

Ja, das hat schon was, ich verwende auch gern Vektoren, auch sowas wie boost::flat_map. Du musst aber schauen, ob sich das wirklich lohnt und ob du dir dadurch nicht unnötige Nachteile einhandelst. 60 mal pro Sekunde hört sich jetzt nicht nach so viel an (du wirst wahrscheinlich mehr Probleme mit dem Scheduling des Betriebssystems haben) und so wahnsinnig groß wird der Vorteil beim Iterieren auch nicht sein. Da musst du abwägen (und messen), was mehr ins Gewicht fällt.

60 mal pro Sekunde * die Anzahl der Systeme, um genau zu sein.
Achja meine Entity Klasse sieht jetzt übrigens wie folgt aus, falls es jemanden interessiert:

template < typename TSettings >
class Entity
{
public:
	Entity()
		: alive_{ true }
	{}

	~Entity() = default;

	Entity(const Entity& entity) = default;
	Entity(Entity&& entity) = default;

public:
	Entity& operator=(const Entity& entity) = default;
	Entity& operator=(Entity&& entity) = default;

public:
	template < typename T, typename = std::enable_if_t<TSettings::template IsComponent<T>::value> >
	void addComponentDataIndex(typename TSettings::DataIndex index) noexcept
	{
		componentDataIndices_.emplace(TSettings::template ComponentId<T>::value, index);
	}

	template < typename T, typename = std::enable_if_t<TSettings::template IsTag<T>::value> >
	void attachTag() noexcept
	{
		signature_[TSettings::ComponentCount::value + TSettings::template TagId<T>::value] = true;
	}

	template < typename T, typename = std::enable_if_t<TSettings::template IsTag<T>::value> >
	void detachTag() noexcept
	{
		signature_[TSettings::ComponentCount::value + TSettings::template TagId<T>::value] = false;
	}

	template < typename T, typename = std::enable_if_t<TSettings::template IsComponent<T>::value> >
	void removeComponentDataIndex() noexcept
	{
		componentDataIndices_.erase(TSettings::template ComponentId<T>::value);
	}

	template < typename T, typename = std::enable_if_t<TSettings::template IsComponent<T>::value> >
	void setComponentSignatureBit(bool value) noexcept
	{
		signature_[TSettings::template ComponentId<T>::value] = value;
	}

	template < typename T, typename = std::enable_if_t<TSettings::template IsTag<T>::value> >
	bool hasTag() const noexcept
	{
		return signature_[TSettings::ComponentCount::value + TSettings::template TagId<T>::value];
	}

	template < typename T, typename = std::enable_if_t<TSettings::template IsComponent<T>::value> >
	auto getComponentDataIndex() const noexcept
	{
		return componentDataIndices_[TSettings::template ComponentId<T>::value];
	}

public:
	void kill() noexcept
	{
		alive_ = false;
	}

	bool isAlive() const noexcept
	{
		return alive_;
	}

	const auto& getComponentDataIndices() const noexcept
	{
		return componentDataIndices_;
	}

	const auto& getSignature() const noexcept
	{
		return signature_;
	}

private:
	bool alive_;
	std::map<typename TSettings::ComponentIndex, typename TSettings::DataIndex> componentDataIndices_;
	typename TSettings::Signature signature_;
};

Das Problem mit den Handles besteht auch noch, kümmere ich mich aber später drum