Contenedor o algoritmo más rápido para identificadores únicos reutilizables en C++

Question

Necesito identificadores únicos reutilizables. El usuario puede elegir sus propios identificadores o puede solicitar uno gratis. El API es básicamente

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. 
}; 

Supongamos identificadores de pasar a empezar a 1 y el progreso, 2, 3, etc. Esto no es un requisito, sólo para ayudar a ilustrar.

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

imprimiría

1 
2 
4 

Debido Identificación 3 ya ha sido declarado utilizado.

¿Cuál es el mejor contenedor/algoritmo para recordar qué identificadores se utilizan Y encontrar una identificación gratuita?

Si desea conocer el un caso de uso específico, glGenTextures de OpenGL, glBindTexture y glDeleteTextures son equivalentes a AllocateId, MarkAsUsed y FreeId

Answer 1

Mi idea es utilizar std::set y Boost.interval para que IdManager contenga un conjunto de intervalos de identificación libre sin superposición. AllocateId() es muy simple y muy rápido y simplemente devuelve el límite izquierdo del primer intervalo libre. Otros dos métodos son un poco más difíciles porque podría ser necesario dividir un intervalo existente o fusionar dos intervalos adyacentes. Sin embargo, también son bastante rápidos.

Así que esta es una ilustración de la idea de utilizar intervalos:

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] 

Esto es propio código:

#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

pero no creo que hay que garantizar la identificación debe empieza con 1. Solo puede asegurarse de que el ID disponible sea mayor que todos los ID asignados.

Al igual que si el 3 se registra primero, luego el siguiente ID disponible puede ser sólo 4. No creo que es necesario utilizar 1.

Answer 3

Sería bueno saber cuántos identificadores de estás se supone que debe hacer un seguimiento de. Si solo hay un centenar o más, un simple set haría, con un recorrido lineal para obtener un nuevo ID. Si es más como unos pocos miles, entonces, por supuesto, el cruce lineal se convertirá en un asesino de rendimiento, especialmente teniendo en cuenta la falta de hostilidad del conjunto.

Personalmente, me gustaría ir a por el siguiente:

• set, lo que ayuda a mantener un registro de los identificadores fácilmente O(log N)
• proponer el nuevo ID que la corriente máxima + 1 ... O(1)

Si no asigna (en la vida útil de la aplicación) más de max<int>() ids, debería estar bien, de lo contrario ... use un tipo más grande (hágala sin firmar, use un long o long long) que es la más fácil para empezar.

Y si no es suficiente, déjame un comentario y voy a editar y buscar soluciones más complicadas. Pero cuanto más complicada es la contabilidad, más tiempo llevará ejecutarla en la práctica y mayores serán las posibilidades de cometer un error.

Answer 4

Supongo que quiere poder usar todos los valores disponibles para el tipo de Id y que desea reutilizar los Id liberados? También estoy asumiendo que bloquearás la colección si la estás utilizando desde más de un hilo ...

Crearía una clase con un conjunto para almacenar los identificadores asignados, una lista para almacenar el ID gratuitos y un valor máximo asignado para evitar tener que precargar la lista de identificación gratuita con cada identificación disponible.

Así que empiezas con un conjunto vacío de identificadores asignados y una lista vacía de identificadores gratuitos y el máximo asignado como 0.Asignas, tomas el encabezado de la lista libre si hay una, de lo contrario tomas max, verificas que no está en tu conjunto de identificadores asignados como podría ser si alguien lo reservara, si es, incrementa el máximo y vuelve a intentarlo, si no agrega al conjunto y devolverlo.

Cuando libera una identificación, simplemente verifique que esté en su conjunto y, de ser así, empújela en su lista gratuita.

Para reservar una identificación, simplemente verifique el conjunto y, si no está presente, agréguela.

Esto recicla los identificadores rápidamente, lo que puede o no ser bueno para usted, es decir, allocate(), free(), allocate() le devolverá la misma identificación si no hay otros hilos accediendo a la colección.

Answer 5

Vector comprimido. Pero no creo que ningún contenedor haga una diferencia notable.

Answer 6

Normalmente, me apegaré a una implementación simple hasta que tenga una idea de qué métodos se usan más. La afinación prematura podría ser incorrecta. Use la implementación simple y registre su uso, luego puede optimizar las funciones que más se usan. No sirve para optimizar la eliminación rápida o la asignación rápida si solo necesitas un par de cientos de identificadores y un vector simple sería suficiente.

Answer 7

similares a skwllsp, me gustaría un seguimiento de los rangos que no tienen sido asignado, pero mis métodos son ligeramente diferentes. El contenedor base sería un mapa, con la clave como el límite superior del rango y el valor como el límite inferior.

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 8

Así que un amigo señaló que en este caso un hash podría ser mejor. La mayoría de los programas de OpenGL no usan más de unos pocos miles de identificadores, por lo que casi se garantiza que un hash con 4096 slots tenga solo 1 o 2 entradas por ranura. Existe un caso degenerado en el que muchos identificadores pueden ir en 1 casilla, pero eso es muy poco probable. Usar un hash haría que AllocateID fuera mucho más lento, pero se podría usar un conjunto para eso. La asignación de ser más lento es menos importante que InUse siendo rápido para mi caso de uso.