La Standard Template Library (STL) de C++ ofrece varios tipos de contenedores como vectores, listas y mapas. Sin embargo, no ofrece algunos contenedores que podrían resultar muy útiles para situaciones determinadas, sobre todo para simulaciones numéricas. Por su utilidad puede ser viable que uno mismo crea estos contenedores en lugar de crear clases particulares para cada tipo de elemento. En la biblioteca libre Boost ya se han incluido algunos de estos contenedores propuestos aquí.

Array multidimensional

Un array de un número de dimensiones variable puede ser útil para calcular tensores matemáticos o combinar datos de varias tablas en una base de datos. El índice en un array multidimensional sería un vector, es decir un array unidimensional, cuya longitud sería la dimensión N.

Una iteración sobre todos los elementos se podría hacer incrementando el primero componente del vector de índice hasta que llegara al número máximo permitido para la dimensión que representa. A continuación se incrementaría el segundo componente, reseteando el primero a cero. Al final el último componente (para la dimensión N) se pasaría por el número máximo permitido y la iteración se terminaría cuando el índice multidimensional sería el vector (0, 0, 0, … N).

Arrays bi- y tridimensionales

Estos arrays podrían ser una particularización de una array multidimensional. Teniendo en cuenta que tienen un uso bastante más frecuente para representar tablas (dos dimensiones) o funciones definidas en el espacio (tres dimensiones), implementaciones particulares podrían optimizar la velocidad.

Árboles

Aunque cada implementación del contenedor std::map usa internamente un árbol, no existe un contenedor árbol. Un árbol genérico permitiría un número variable de hijos en cada nodo. Esto quiere decir que cada nodo tendría un contenedor lineal (array o lista) de referencias a otros nodos.

Un árbol tan genérico podría ser limitado a un árbol binario si el contenedor de nodos hijos podría hacer referencia a dos nodos como máximo. Se podría implementar un árbol binario usando un árbol genérico, pero una implementación particular podría mejorar la velocidad de ejecución. Para el caso de un árbol binario podría valer la pena buscar el código de un std::map, ya que este contenedor implementa un árbol binario.

Un árbol unario, es decir, donde cada nodo sólo puede tener un hijo, sería una lista. Una lista ya existe en la STL como std::list.

Redes

La manera más genérica de entrelazar nodos es mediante un grafo representando una red. Cada nodo puede estar conectado con cualquier otro nodo – incluido él mismo. Como no hay manera de establecer un orden lineal en esta configuración, la única forma es usar otro contenedor como std::list que contiene los nodos y que permite iterar fácilmente sobre todos.

Cada nodo contendría un contenedor con referencias a otros nodos similar a un árbol genérico. Para quitar un nodo del conjunto, podrías usar dos estrategias:

  1. Iterar sobre todos los nodos y eliminar todas las referencias al nodo a eliminar. Esto sería lento porque requiere doble bucle anidado. Uno sobre todos los nodos (excluyendo el nodo a eliminar) y otro sobre todas las referencias en cada nodo.
  2. Guardar en cada nodo, qué otros nodos guardan una referencia a él – similar a una lista doblemente enlazada. Esto complica el modelo el nodo, pero es una estrategia mejor para redes grandes.

Contenedor de acceso aleatorio para una gran cantidad de datos

¿Qué tipo de contenedor usarías si quieres insertar un carácter en medio de un texto de un millón de caracteres? La clase std::string (array) me obligaría a copiar mucho texto para cada tecla que pulso. Una lista haría la inserción rápida pero copiar el texto entero eterno.

Una solución podría ser un contenedor cuyo modelo interior es un std::list<std::deque<> >. Insertar cualquier tamaño de datos causaría en dividir una deque existente en dos e insertar los datos nuevos como una nueva deque en medio. Como habría que dividir la deque existente en dos, se podría hacer una de las dos los suficientemente grande para albergar los datos nuevos y una parte de la vieja dividida. La otra parte sería acortada haciendo los elementos sobrantes inválidos – reduciendo el tamaño con size().

La parte más complicada sería la implementación del iterador de acceso aleatorio, ya que debería empezar a contar al principio de la lista, contando el número de elementos válidos en cada deque hasta llegar a la deque que contiene el índice requerido.

Métodos útiles para este contenedor sería compactar el contenido entero a una deque única o dividir el contenido en deques con un tamaño máximo.

Referencias