Effizienter Container für EntityIds

Yamahari

Hallo,
ich habe folgende Klasse für das Erstellen und Entfernen von Ids.
Meine erste Frage: Ist die Art und Weise auf diejenige die Klasse funktioniert effizient und bzw. oder gibt es noch effizientere Methoden dies zu erreichen ?

Da ich C++/ Programmieren nur nebenbei, als vorläufiges Hobby, lerne, habe ich auch noch andere Fragen, die im Code zu finden sind.

Im Voraus schon einmal Danke

#include <iostream>
#include <utility>
#include <vector>

using namespace std;

class Ids
{
public:
	Ids(size_t maxIds, size_t maxfreeIds){ ids_.reserve(maxIds); freeIds_.reserve(maxfreeIds); }

	size_t add()
	{
		if (freeIds_.empty())
		{
			ids_.push_back(createUniqueId()); // <- wird das Ergebnis von createUniqueId kopiert oder verschoben(?) ? 
		}
		else
		{
			ids_.push_back(freeIds_.back()); 
			freeIds_.pop_back();
		}

		return ids_.back();
	}

	void remove(size_t id)
	{
		swap(ids_[id], ids_.back()); // vector::at : vector::operator[] ?  

		freeIds_.push_back(ids_.back());
		ids_.pop_back();
	}

	void test() // wie der Name suggeriert, nur zum testen 
	{
		cout << "Size of ids_: "     << ids_.size()     << " Capacity of ids_: "     << ids_.capacity()     << " MaxSize of ids_: "     << ids_.max_size() << endl;
		cout << "Size of freeIds_: " << freeIds_.size() << " Capacity of freeIds_: " << freeIds_.capacity() << " MaxSize of freeIds_: " << freeIds_.max_size() << endl;
	}

	void printIds()
	{
		for (auto& i : ids_){ cout << i << endl; }
	}

private:
	inline size_t createUniqueId() const
	{
		static size_t lastId{ 0u };
		return lastId++;
	}

	vector<size_t> ids_;
	vector<size_t> freeIds_;
};

Finnegan

Auf den ersten flüchtigen Blick würde ich sagen, dass man auf den Vektor ids_ verzichten kann. Die IDs in diesem kann man indirekt ermitteln,
da es sich dabei um alle Zahlen ≤ lastId handelt, die sich nicht in freeIds_ befinden.

Ebenso lässt sich Speicher sparen, wenn man in freeIds_ nur diejenigen freien IDs speichert, die ≤ lastId sind. Dann ist freeIds_ zu Anfang leer,
und wird nur dann gefüllt, wenn eine ID freigegeben wird. Die freien IDs sind dann alle Zahlen > lastId_ und <= maxIds plus diejenigen, die sich in freeIds_ befinden.

Wenn man es so handhabt, darf maxIds auch größer als der Arbeitspeicher sein und es können dabei sogar fast alle IDs vergeben sein, falls sich nicht zu viele davon in der
freeIds_ -Liste befinden (eventuell kann man auch lastId wieder reduzieren, wenn die hinteren IDs alle frei sind).

Noch effizienter könnte eine einfache fortlaufende Nummer sein ohne dass die frei gewordenen IDs erneut vergeben werden. Bei 64 Bit Breite kann das je nach Anwendungsfall durchaus für ein paar
hundert Jahre Laufzeit ausreichen (wenn ich ich nicht verrechnet habe kann man damit etwa 580 Millionen Jahre lang 1000 IDs pro Sekunde vergeben).

Die effizienteste Lösung ist natürlich wenn man überhaupt keine IDs benötigt. Schliesslich lässt sich jedes Objekt im Speicher auch eindeutig durch seine Adresse identifizieren.
Das hängt aber stark davon ab was für ein Problem du damit lösen willst.

Finnegan

hustbaer

Deine remove Funktion ist fehlerhaft.
Die bekommt eine ID übergeben, verwendet diese dann aber als Index in ids_ .

Was die Effizienz angeht kann ich mich dem anschliessen was Finnegan schon geschrieben hat. Ob es effizient ist was du da machst kann man nicht sagen, ohne zu wissen welches Problem du damit eigentlich lösen willst.