Schnellster Container oder Algorithmus für eindeutige wiederverwendbare Kennungen in C++

Question

Ich benötige eindeutige, wiederverwendbare Kennungen. Der Benutzer kann seine eigene Kennung wählen oder eine freie Kennung anfordern. Die API ist grundsätzlich

class IdManager {
public:
  int AllocateId();          // Allocates an id
  void FreeId(int id);       // Frees an id so it can be used again
  bool MarkAsUsed(int id);   // Let's the user register an id. 
                             // returns false if the id was already used.
  bool IsUsed(int id);       // Returns true if id is used.
};

Angenommen, die IDs beginnen bei 1 und gehen weiter zu 2, 3 usw. Dies ist keine Voraussetzung, sondern dient nur der Veranschaulichung.

IdManager mgr;
mgr.MarkAsUsed(3);
printf ("%d\n", mgr.AllocateId());
printf ("%d\n", mgr.AllocateId());
printf ("%d\n", mgr.AllocateId());

Würde drucken

1
2
4

Denn id 3 wurde bereits für benutzt erklärt.

Was ist der beste Container / Algorithmus, um sich zu merken, welche IDs verwendet werden UND eine freie ID zu finden?

Wenn Sie einen speziellen Anwendungsfall kennenlernen möchten, sind OpenGLs glGenTextures, glBindTexture und glDeleteTextures äquivalent zu AllocateId, MarkAsUsed und FreeId

Answer 1

Normalerweise würde ich sagen, bleiben Sie bei einer einfachen Implementierung, bis Sie eine Vorstellung davon haben, welche Methoden am häufigsten verwendet werden. Ein verfrühtes Tuning könnte sich als falsch erweisen. Verwenden Sie die einfache Implementierung und protokollieren Sie ihre Verwendung, dann können Sie die Funktionen optimieren, die am meisten verwendet werden. Es macht keinen Sinn, für schnelles Entfernen oder schnelle Zuweisung zu optimieren, wenn Sie nur ein paar hundert IDs benötigen und ein einfacher Vektor ausreichen würde.

Answer 2

Ähnlich wie skwllsp Ich würde die Bereiche verfolgen, die noch nicht zugewiesen wurden, aber meine Methoden sind etwas anders. Der Basiscontainer wäre eine Karte, wobei der Schlüssel die obere Grenze des Bereichs und der Wert die untere Grenze ist.

IdManager::IdManager()
{
    m_map.insert(std::make_pair(std::numeric_limits<int>::max(), 1);
}

int IdManager::AllocateId()
{
    assert(!m_map.empty());
    MyMap::iterator p = m_map.begin();
    int id = p->second;
    ++p->second;
    if (p->second > p->first)
        m_map.erase(p);
    return id;
}

void IdManager::FreeId(int id)
{
    // I'll fill this in later
}

bool IdManager::MarkAsUsed(int id)
{
    MyMap::iterator p = m_map.lower_bound(id);

    // return false if the ID is already allocated
    if (p == m_map.end() || id < p->second || id > p->first)))
        return false;

    // first thunderstorm of the season, I'll leave this for now before the power glitches
}

bool IdManager::IsUsed(int id)
{
    MyMap::iterator p = m_map.lower_bound(id);
    return (p != m_map.end() && id >= p->second && id <= p->first);
}

Answer 3

Ein Freund wies mich darauf hin, dass in diesem Fall eine Raute besser wäre. Die meisten OpenGL-Programme verwenden nicht mehr als ein paar tausend ids, so dass ein Hash mit sagen wir 4096 Slots fast garantiert nur 1 oder 2 Einträge pro Slot hat. Es gibt einen degenerierten Fall, in dem viele IDs in einen Slot passen könnten, aber das ist sehr unwahrscheinlich. Die Verwendung eines Hashes würde AllocateID viel langsamer machen, aber dafür könnte ein Set verwendet werden. Allocating langsamer ist weniger wichtig als InUse ist schnell für meinen Anwendungsfall.