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

Meine Idee ist es, Folgendes zu verwenden std::set y Boost.interval also IdManager enthält eine Reihe von sich nicht überschneidenden Intervallen freier IDs. AllocateId() ist sehr einfach und schnell und gibt nur die linke Begrenzung des ersten freien Intervalls zurück. Die beiden anderen Methoden sind etwas schwieriger, da es notwendig sein kann, ein bestehendes Intervall zu teilen oder zwei benachbarte Intervalle zu verschmelzen. Sie sind jedoch auch recht schnell.

Dies ist also eine Veranschaulichung der Idee der Verwendung von Intervallen:

IdManager mgr;    // Now there is one interval of free IDs:  [1..MAX_INT]
mgr.MarkAsUsed(3);// Now there are two interval of free IDs: [1..2], [4..MAX_INT]
mgr.AllocateId(); // two intervals:                          [2..2], [4..MAX_INT]
mgr.AllocateId(); // Now there is one interval:              [4..MAX_INT]
mgr.AllocateId(); // Now there is one interval:              [5..MAX_INT]

Dies ist der Code selbst:

#include <boost/numeric/interval.hpp>
#include <limits>
#include <set>
#include <iostream>

class id_interval 
{
public:
    id_interval(int ll, int uu) : value_(ll,uu)  {}
    bool operator < (const id_interval& ) const;
    int left() const { return value_.lower(); }
    int right() const {  return value_.upper(); }
private:
    boost::numeric::interval<int> value_;
};

class IdManager {
public:
    IdManager();
    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. 
private: 
    typedef std::set<id_interval> id_intervals_t;
    id_intervals_t free_;
};

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

int IdManager::AllocateId()
{
    id_interval first = *(free_.begin());
    int free_id = first.left();
    free_.erase(free_.begin());
    if (first.left() + 1 <= first.right()) {
        free_.insert(id_interval(first.left() + 1 , first.right()));
    }
    return free_id;
}

bool IdManager::MarkAsUsed(int id)
{
    id_intervals_t::iterator it = free_.find(id_interval(id,id));
    if (it == free_.end()) {
        return false;
    } else {
        id_interval free_interval = *(it);
        free_.erase (it);
        if (free_interval.left() < id) {
            free_.insert(id_interval(free_interval.left(), id-1));
        }
        if (id +1 <= free_interval.right() ) {
            free_.insert(id_interval(id+1, free_interval.right()));
        }
        return true;
    }
}

void IdManager::FreeId(int id)
{
    id_intervals_t::iterator it = free_.find(id_interval(id,id));
    if (it != free_.end()  && it->left() <= id && it->right() > id) {
        return ;
    }
    it = free_.upper_bound(id_interval(id,id));
    if (it == free_.end()) {
        return ;
    } else {
        id_interval free_interval = *(it);

        if (id + 1 != free_interval.left()) {
            free_.insert(id_interval(id, id));
        } else {
            if (it != free_.begin()) {
                id_intervals_t::iterator it_2 = it;
                --it_2;
                if (it_2->right() + 1 == id ) {
                    id_interval free_interval_2 = *(it_2);
                    free_.erase(it);
                    free_.erase(it_2);
                    free_.insert(
                        id_interval(free_interval_2.left(), 
                                    free_interval.right()));
                } else {
                    free_.erase(it);
                    free_.insert(id_interval(id, free_interval.right()));
                }
            } else {
                    free_.erase(it);
                    free_.insert(id_interval(id, free_interval.right()));
            }
        }
    }
}

bool id_interval::operator < (const id_interval& s) const
{
    return 
      (value_.lower() < s.value_.lower()) && 
      (value_.upper() < s.value_.lower());
}

int main()
{
    IdManager mgr;

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

    return 0;
}

Answer 2

Es wäre gut zu wissen, wie viele IDs man im Auge behalten soll. Wenn es nur hundert oder so sind, kann eine einfache set tun würde, mit linearem Traversal, um eine neue ID zu erhalten. Wenn es mehr wie ein paar Tausend ist, dann natürlich die lineare Traversal wird ein Performance-Killer, vor allem in Anbetracht der Cache Unfreundlichkeit des Satzes.

Ich persönlich würde mich für Folgendes entscheiden:

• set das hilft, den Überblick über die Kennungen zu behalten O(log N)
• die neue ID als das aktuelle Maximum + 1 vorschlagen... O(1)

Wenn Sie (während der Lebensdauer der Anwendung) nicht mehr zuweisen als max<int>() ids, sollte es in Ordnung sein, andernfalls... verwenden Sie einen größeren Typ (machen Sie ihn unsigned, verwenden Sie eine long o long long ), mit dem man am einfachsten beginnen kann.

Und wenn das nicht ausreicht, hinterlasst mir einen Kommentar, und ich werde es überarbeiten und nach komplizierteren Lösungen suchen. Aber je komplizierter die Buchführung ist, desto länger dauert es, sie in der Praxis auszuführen, und desto größer ist die Wahrscheinlichkeit, dass man einen Fehler macht.

Answer 3

Aber ich glaube nicht, dass Sie garantieren müssen, dass die ID bei 1 beginnt. Sie können einfach sicherstellen, dass die verfügbare ID größer als alle zugewiesenen IDs ist.

Wenn z. B. die 3 zuerst registriert wird, kann die nächste verfügbare ID einfach die 4 sein. Ich denke nicht, dass es notwendig ist, die 1 zu verwenden.

Answer 4

Ich nehme an, dass Sie in der Lage sein wollen, alle verfügbaren Werte für den Id-Typ zu verwenden und dass Sie freigegebene Ids wiederverwenden wollen? Ich gehe auch davon aus, dass Sie die Sammlung sperren, wenn Sie sie von mehr als einem Thread aus verwenden...

Ich würde eine Klasse mit einem Set erstellen, um die zugewiesenen IDs zu speichern, eine Liste, um die freien IDs zu speichern und einen maximalen zugewiesenen Wert, um zu verhindern, dass ich die Liste der freien IDs mit jeder verfügbaren ID vorladen muss.

Sie beginnen also mit einem leeren Satz von zugewiesenen ids und einer leeren Liste von freien ids und dem zugewiesenen max als 0. Sie weisen zu, nehmen den Kopf der freien Liste, wenn es einen gibt, sonst nehmen Sie max, überprüfen Sie, dass es nicht in Ihrem Satz von zugewiesenen ids ist, da es sein könnte, wenn jemand es reserviert hat, wenn es ist, erhöhen Sie max und versuchen Sie es erneut, wenn nicht, fügen Sie es dem Satz hinzu und geben Sie es zurück.

Wenn du eine ID freigibst, überprüfst du einfach, ob sie in deinem Set enthalten ist, und wenn ja, schiebst du sie auf deine Freie-Liste.

Um einen Ausweis zu reservieren, überprüfen Sie einfach das Set und fügen es hinzu, wenn es nicht vorhanden ist.

Dadurch werden IDs schnell wiederverwendet, was gut oder schlecht für Sie sein kann, d.h. allocate(), free(), allocate() gibt Ihnen die gleiche ID zurück, wenn keine anderen Threads auf die Sammlung zugreifen.

Answer 5

Komprimierter Vektor. Aber ich glaube nicht, dass ein Container einen spürbaren Unterschied machen würde.