Wenn es um einen Container von Spiel-Objekten geht habe ich der Regel mit 3 Vektoren gelöst:
1. Vektor: Speichert die eigentlichen Spielobjekte (bzw. Pointer).
Besonderheit: Wenn ein Objekt aus dem Vektore gelöscht wird, wird der jeweilige Eintrag auf null gesetzt. Damit bleiben die Indices für die Spielobjekte für die gesamte Lebenszeit erhalten. Ergo ID = Index in diesem Vektor.
2. Vektor: Speichert eine Liste von freien Indices vom 1. Vektor. Die Indicies werden beim entfernen drauf gepuscht und beim einfügen abgepopt (damn, wie schreibt man das auf Deutsch?). Damit wird sicher gestellt, dass der 1. Vektor beim wiederholten entfernen und einfügen nicht beliebig anwächst.
3. Vektor: Ein Vektor mit Indicies die die Renderreihenfolge der Objekte im 1. Vektor angibt. An der Stelle kannst du auch stattdessen eine KD-Tree oder eine beliebige andere Struktur aufbauen. Wichtig ist jedenfalls, dass die Struktur die Objekte selber nicht enthält sondern diese nur per Index im 1. Vektor referenziert.

So ein System habe ich schon in zwei Spielengines verwendet. Außerdem haben wir die Technik für einen Software-Raytracer verwendet bei uns an der Uni. Also das sollte so schon performant sein.
Ich denke mal wenn dir Performance wichtig ist solltest du versuchen Vektoren zu verwenden, einfach wegen dem lokalem Speicherzugriff.

Zugriff auf Spielobjekte sollte definitiv in O(1) laufen (per Id / Index), weil sowas bei der Kollisions-Engine und ähnlichen Berechnung massig verwendet wird.

Gruß

Felix