Crear contenedores multidimensionales en C++

Array bidimensional

La Standard Template Library (STL) se llama a veces biblioteca estándar de C++ para distinguirla de la biblioteca estándar de C. Una de las herramientas que la biblioteca STL ofrece son contenedores. Un contenedor es un objeto que contiene un número variable de otros objetos. Todos estos objetos tienen el mismo tipo. Por ejemplo, un contenedor de enteros podría tener el tipo std::vector<int>. En lugar de int se podría poner cualquier otro tipo.

En particular, se podría usar otro contenedor como tipo de elemento. Un objeto de tipo std::vector<std::vector> > sería algo como un array bidimensional. Sin embargo, no sería lo mismo que un array de tipo int[x][y]. Esta última versión crea un array rectangular, es decir una matriz. La versión de std::vector crearía una array dinámico de arrays dinámicos, en que cada línea podría tener un número diferente de columnas – por lo cual se parece a los arrays multidimensionales del lenguaje de programación Java.

Iteradores

Desgraciadamente no hay un contenedor multidimensional en la STL. Una razón es probablemente la iteración sobre todos los elementos. Una tarea de programación común es hacer algo con cada elemento de un contenedor. Esto se hace típicamente en un bucle for del primer al último elemento. La STL ofrece clases especiales llamados iterator. Iteradores son objetos que se comportan como punteros y tienen, como estos, algunas de las siguientes propiedades.

• Pueden delimitar un rango de valores apuntando al primer y al último elemento. (Más correctamente detrás del último elemento.) Los iteradores se inicializan típicamente con los métodos begin() y end() del contenedor.
• Pueden acceder al elemento a que apuntan – típicamente con los operadores * y ->.
• Pueden apuntar al elemento previo o siguiente – típicamente con los operadores -- y ++ de pre-fijo o post-fijo.

Estas operaciones están bien definidas para contenedores lineales, es decir contenedores en que los elementos están ordenados de una forma específica. Esto no quiere decir que estén ordenados lógicamente, por ejemplo números pequeños primero, sino que se puede diferenciar claramente un predecesor y un sucesor de cada elemento. Pero ¿cómo podemos establecer este orden en un array multidimensional? ¿Avanzar al próximo elemento es moverse una columna o una fila más allá?

Iterar sobre una colección multidimensional

Matemáticamente no hay un orden estricto en un espacio multidimensional. No obstante, para resolver nuestro problema de iteración sólo necesitamos cumplir lo siguiente: Una iteración completa pasa por todos los elementos exactamente una vez.

¿Qué quiere decir esto? Quiere decir que no importa si vamos fila por fila o columna por columna (o por cualquier otra forma) cuando un bucle de forma

for (iterator p = container.begin();
     p != container.end();
     ++p)
{
    // Do something with *p or p->
}

pasaría por todos los elemento del array. (Aquí igual te interesa por qué el incremento prefijo es más rápido que postfijo.)

Hay otro problema con los arrays multidimensionales en C++. Habitualmente nos gusta escribir algo como punto[x][y] para referirnos a un elemento en concreto del array punto. No obstante, no hay una método operator[][] que podríamos sobre cargar y el método operator[] sólo permite un parámetro.

Hay varias formas para afrontar este problema.

• El método operator[] de un contenedor bidimensional podría exportar una referencia a un contenedor unidimensional que igualmente sobrecarga el método operator[]. Es una buena solución pero restringe la libertad de como implementar el contenedor multidimensional.
• El método operator() permite un número arbitrario de parámetros. En lugar de punto[x][y] escribiríamos punto(x, y). Este sistema es una buena solución para contenedores de un número fijo de dimensiones.
• Finalmente podríamos sobrecarga el método operator[] usando un índice multidimensional. En lugar de punto[x][y] o punto(x, y) escribiríamos algo como punto[array_index(x, y)]. No es una solución demasiado práctica pero la única aceptable para contenedores con un número de dimensiones variable. Aunque el índice multidimensional sería otra clase que deberíamos crear para este propósito, es probable que ya lo hayamos hecho a la hora de crear las clases de los iteradores para el array multidimensional.

Conclusión

Hemos repasado unos puntos a tener en cuenta a la hora de crear contenedores multidimensionales al estilo con la STL. Como puede llegar a ser laborioso conviene buscarse implementaciones ya hechas como el componente MultiArray de la biblioteca Boost.

Referencias

• Pre-fix más rápido que post-fix
• MultiArray en la biblioteca Boost.
• Ampliar std::map
• Comparación entre vector y deque