¿Pensamientos sobre cómo implementar?

Question

Estoy portando un código c muy antiguo en C++ y me he encontrado con una lista vinculada implementada dentro de una matriz. El elemento es una estructura simple:

struct element 
{ 
    void *m_ptrData; 
    short m_nextEntry; 
    short m_prevEntry; 
}; 

Como matriz, hay acceso rápido a los datos, si conoce el índice. El aspecto de la lista enlazada permite mover los elementos y "eliminarlos" de la lista. Los elementos se pueden mover en la lista, según la frecuencia de uso (hasta MRU y abajo por LRU).

Me gusta encontrar una forma mejor de implementar esto que usar otra matriz. Me gustaría utilizar STL, pero no estoy seguro de qué contenedor es el mejor para usar.

¿Alguien tiene alguna idea?

Answer 1

Como se trata de una lista enlazada, probablemente debería utilizar std::list ...

La regla de oro es que se desea utilizar una lista enlazada cuando se necesita para insertar elementos en posiciones aleatorias en la lista, o eliminar elementos aleatorios de la lista. Si necesita agregar/eliminar elementos al final de la lista, debe usar std::vector. Si necesita agregar/eliminar elementos a/desde el principio o el final de la lista, entonces debe usar std::deque.

Tenga en cuenta que estamos hablando de probabilidades aquí. Si necesita insertar un elemento en el medio de std::vector una vez en una luna azul, eso probablemente sea correcto. Pero si necesita hacer esto todo el tiempo, tendrá un gran impacto en el rendimiento, ya que el vector necesitará mover constantemente sus elementos, y probablemente reasignar también su memoria.

Por otro lado, la ventaja de usar un vector es que sus elementos son contiguos en la memoria, lo que mejora enormemente el rendimiento si simplemente necesita recorrerlos en orden debido al almacenamiento en caché.

Answer 2

Ver aquí:

http://linuxsoftware.co.nz/cppcontainers.html

Hay un diagrama de flujo para ayudarle a elegir el contenedor a la derecha en la parte inferior.

Answer 3

Dado que los datos en esta lista son punteros, ¿para qué preocuparse con una lista vinculada? Para POD pequeños, std::vector suele ser la mejor primera apuesta, y debido a la mejor ubicación de sus datos que funcionan muy bien con los cachés de procesador a menudo supera una lista vinculada, incluso donde, en teoría, una lista vinculada debería ser mejor. Elegiría std::vector hasta que algunos perfiles muestren que hay un problema de rendimiento y std::list tiene un mejor rendimiento.