Interesante problema de Estructuras de Datos

En varios casos en ZinjaI tengo datos que necesito utilizar en dos contextos diferentes, requiriendo en uno el conjunto completo, y en otro solo una parte. Tomemos por ejemplo la lista de breakpoints de un proyecto. Mientras se edita un archivo fuente, la mayoría de las operaciones con breakpoints (agregar, quitar, definir propiedades, etc) se hará sobre los de ese fuente. Además, al guardar esta información en el proyecto, los breakpoints de un fuente se guardan asociados al mismo. Sin embargo, una lista de breakpoints por fuente no siempre es lo mejor porque muchas operaciones en el depurador (a nivel gdb) se harán sobre la lista completa. Por ejemplo, al inicializar la depuración, se deben setear todos los breakpoints en gdb antes de ejecutar, sin importar de dónde provengan. La misma idea aplica a varias otras cosas, como por ejemplo los archivos del proyecto (que están agrupados por categorías) o próximamente las inspecciones (que están asociadas a distintas ventanas/paneles de la interfaz).

Entonces, hace poco me armé un par de clases para representar dos contenedores que operen sobre los mismos elementos. Es decir, habrá un contenedor para el conjunto global, y otro para los subconjuntos parciales. A nivel algoritmos y estructuras de datos creo que es un ejercicio interesante, y por eso vengo a (documentarlo) comentarlo  en este post.

Resumiendo, quiero contendores para las sublistas locales, que son con los que voy a trabajar más frecuentemente (en el ejemplo de los breakpoits, uno por archivo); pero también quiero poder recorrer el conjunto total sin tener que ir a buscar cada uno de esos contenedores locales (porque es incómodo reunir las listas y lleva además a repetir código). Llamemos a partir de ahora Global al contendor que permitirá recorrer el conjunto total, y Local al que se utilizará para un subconjunto. Impongamos además la restricción de que Global es (casi) de solo-lectura; es decir, que agregamos y quitamos elementos en Local, mientras que en Global solo consultamos/modificamos elementos ya existentes. Para cada contenedor tengo que elegir una estructura de datos adecuada de entre las conocidas. Por simplicidad voy a evitar los árboles y eligir solo entre listas (enlazadas) y vectores.

 Así se organizan en memoria el vector y la lista, los dos tipos de contenedores más comunes.
(para simplificar el gráfico la lista solo muestra enlaces hacia "adelante", pero las
implementaciones reales usualmente requieren enlaces en ambas direcciones).

Repasando rápidamente, en una lista los datos son nodos sueltos con punteros que los enlazan (que dicen para cada nodo dónde está el que sigue o el anterior); mientras que en un vector los elementos están contiguos en memoria como en un arreglo tipo C. Usar una lista obliga a hacer news y deletes todo el tiempo (por cada nodo que se agrega o quita), y lleva entonces a fragmentar mucho la memoria (con la potencial pérdida de rendimiento por el mal uso de cache, además de lo caro que pueden ser new y delete), y a tener una sobrecarga en el espacio del mismo orden que la cantidad de elementos (punteros adicionales en cada nodo). Sin contar que además sólo permite acceso secuencial. El vector por su parte permite acceso aleatorio y tiene los datos de la forma más compacta posible y contiguos (cache-friendly), pero tiene dos problemas. Uno es que al trabajar sobre un bloque contiguo de memoria, hay que "administrar" el tamaño de ese bloque. Si es muy grande en comparación a la cantidad de elementos desperdiciamos memoria, pero si es muy chico nos quedamos sin espacio al insertar y nos vemos obligados a pedir uno nuevo más grande (y mover allí todos los datos previos). Sin contar que insertar y eliminar no es de tiempo constante como en la lista, a menos que lo hagamos siempre al final, y en este caso podría ser porque en un conjunto no interesa particularmente el orden.

Pero hay un defecto adicional en el vector culpa de este "pedir un bloque nuevo más grande", y es que si teníamos en algún lado fuera del vector punteros a sus elementos, todos los punteros dejarán de ser válidos cuando los elementos se muevan a ese bloque nuevo. En la lista no pasa esto porque los nodos nunca se mueven. Y aclaro esto porque si quiero que dos contenedores realmente compartan un mismo elemento (no que lo dupliquen, sino que usen la misma instancia), entonces habrá punteros involucrados, ya que el elemento no puede estar en ambos... ¿o si?. Mi idea entonces fue la siguiente: Local es un vector cuyos elementos son nodos de Global, que es una lista. Es decir, Global es una lista: tiene un puntero al primer nodo y de allí en más cada nodo lleva al siguiente; pero estos nodos no están en cualquier lado, sino que son elementos en los vectores. Entonces, un vector tiene de forma contigua  todos los nodos con elementos de su subconjunto, pero siguiendo los enlaces podemos recorrer la lista Global completa.

Así queda este par de estructuras extraña que combinan lista y vector para compartir datos.

Queda el problema de los punteros que dejan de ser válidos, y para solucionarlo en lugar de un nodo apuntar a otro nodo con un puntero común, apunta con un struct que tiene un puntero a la instancia de Local (el vector) y una posición para buscar dentro de esa instancia. Así, cuando ese Local reemplaza su bloque de memoria por otro más grande y mueve sus elementos no hace falta actualizar los enlaces en los nodos, porque éstos se manejan por posiciones del arreglo (relativas) y no por direcciones en memoria (absolutas, como lo haría una lista común), y el tiempo de acceso sigue siendo constante. Resumiendo con un poco de código, las clases necesarias y sus atributos quedarían como sigue:

    // "puntero" para usar en los nodos de la lista Global
    template<class T> struct NodePtr {
        Local<T> *m_local // vector que lo contienen
        int m_pos; // posición en el vector
    };

    // tipo de elemento para el vector local 
    // y a la vez nodo para la lista global
    template<class T> struct Node {
        T m_data; // El Dato
        NodePtr<T> m_next, m_prev; // enlaces para la lista global
    };

    // lista Global (para recorrer el conjunto completo)
    class Global {
        NodePtr<T> m_first, m_last; // enlaces a los extremos de la lista
    public:
        ...
    };

    // vector Local (para recorrer y manejar un subconjunto)
    class Local {
        Node<T> *m_datos; // elementos envueltos en nodos
        Global<T> *m_lista; // lista global para sus elementos
        int m_size,m_count; // espacio reservado y elems. validos
    public:
        ...
    };

Solo hay que tener en cuenta que al agregar o eliminar elementos de Local se deben "mantener" los enlaces de Global (por eso cada Local tiene un puntero a su Global entre sus atributos). Entonces, Local hace un doble trabajo en cada inserción/eliminación: trabajo de vector y de lista a la vez. Y en Global no se puede Eliminar ni Insertar, digamos que es una clase ficticia solo para poder "ver" a los subconjuntos como una sola gran y única bolsa de elementos. También hay que tener cuidado en cómo utilizar esos pseudo-punteros a la hora de mantener y recorrer la lista Global. Pero todos esos detalles quedan ocultos en las implementaciones de estas estructuras y en sus atributos privados, y podemos hacer un par de clases que actúen de iteradores para recorrerlas desde afuera sin preocuparnos ni notar estas particularidades.

Si a alguien le interesó este engendro, entre los fuentes de ZinjaI van a encontrar estas clases implementadas y documentadas (aunque con nombre algo diferentes, aquí simplificados para el ejemplo) en el archivo SingleList.h. Si alguien conoce algo mejor para este problema no dude en sugerirlo en los comentarios.