5.1.1 Contenedores

§1 Presentación

En sentido C++ estricto, un contenedor de la STL es una clase genérica (plantilla 4.12.2) que puede instanciarse para representar diversos tipos de objetos. Esta clase incluye ciertas operaciones (muy básicas) sobre los objetos de su tipo; naturalmente estas operaciones están representadas por funciones-miembro, incluyendo constructores y funciones-operador, que son a su vez funciones genéricas (plantillas 4.12.1). Al mismo tiempo, desde el punto de vista de las teorías de la información, podemos considerarlos estructuras de datos ( 1.8) más o menos adecuadas (según el caso) para aplicarles ciertos algoritmos ( 5.1.3).

De su propio nombre ("Containers") podemos deducir que su misión principal, y razón de su existencia, es su función como estructuras de datos, y en este sentido podemos adelantar que entre sus funcionalidades más destacadas se encuentran la gestión del espacio de almacenamiento necesario. Como veremos al tratar de los asignadores de memoria (allocators 5.1.5) y en las explicaciones más detalladas al respecto ( 5.1.1b), una de las primerísimas ventajas de la utilización de contenedores es que el programador no tiene que enredarse con las cuestiones siempre espinosas de asignar o liberar memoria para los objetos creados, de forma que queda liberado de los operadores new y delete ( 4.9.20).

§2 Filosofía de uso

Presentaremos una primera pincelada sobre la filosofía de uso de los contenedores mediante un sencillo ejemplo: si tenemos que manejar un conjunto de enteros, puede utilizarse una matriz de enteros, pero ya hemos señalado ( 4.3) que esta estructura nos obliga a conocer de antemano la cantidad de datos a almacenar (el tamaño de la matriz). En consecuencia, si el número de datos puede variar, esta opción no es muy adecuada. Además, si es importante mantener los datos ordenados, la utilización de una matriz nos obligaría a ingeniar por nuestra cuenta la forma de hacerlo; seguramente mediante complicadas rutinas de "sort" hechas manualmente.

Una alternativa es utilizar como "contenedor" para nuestros enteros una clase genérica de la STL denominada vector. En este caso, serían posibles expresiones como las siguientes:

vector<int> v(3);         // L1:
v[0] = 7;                 // L2:
v[1] = v[0] + 1;          // L3:
v[2] = v[0] + v[1];       // L4:

Al encontrar la primera sentencia, el compilador crea una instancia (especialidad) anónima de la plantilla vector para alojar enteros; a continuación una instancia de ella para alojar tres enteros, a la que denominamos v.

Una primera inspección de las sentencias L2 a L3, nos muestra que la clase ofrece la posibilidad de utilizar con sus miembros el operador subíndice de matriz [ ] ( 4.9.16). Deducimos por tanto, que dispone de una versión sobrecargada de este operador para los miembros de la clase ( 4.9.18d), lo que nos permite utilizar el objeto v como una matriz, aunque con algunas funcionalidades no incluidas en aquellas.

Después de L4 los valores finales para los miembros de nuestra "matriz" serian:

v[0] == 7, v[1] == 8, v[2] == 15

Supongamos ahora que deseamos invertir el orden de los elementos de nuestra matriz. Para ello utilizamos una función especial:

reverse(v.begin(), v.end());

después de lo cual, el orden de miembros sería:

v[0] == 15, v[1] == 8, v[2] == 7

La primera observación es que la función reverse utiliza dos argumentos, que son a su vez el valor devuelto por sendos métodos de clase (los aplicamos sobre nuestro objeto v).  El valor devuelto por estos métodos es lo que se conoce como un iterador; una especie de puntero que señalan al interior de la estructura de datos representada por el contenedor v. En este caso, el primer iterador señala al primer miembro y el segundo a una posición después del último; de esta forma se indican los miembros inicial y final entre los que se realizará la operación de inversión efectuada por reverse.

La segunda observación es que la función reverse no es un método de clase, sino una función global; es lo que denominamos un algoritmo. Esta función tiene la peculiaridad de que puede ser aplicado sobre el contenedor vector (y algún otro); que opera sobre un rango de los elementos del contenedor, en nuestro caso sobre la totalidad (esta capacidad de operar sobre una parte de un contenedor es característica de los algoritmos). También que pueden operar sobre otros contenedores produciendo un efecto similar. Por ejemplo, el algoritmo reverse puede operar incluso sobre una simple matriz:

char Ch[5] = { 'A', 'E', 'I', 'O', 'U' };
reverse(Ch, Ch + 5);
for (int i = 0; i < 5; ++i) cout << "Ch[" << i << "] = " << Ch[i];

Salida:

Ch[0] = U Ch[1] = O Ch[2] = I Ch[3] = E Ch[4] = A

Es significativo que el objeto v es una estructura de datos que permite acceder individualmente a sus miembros "como si" fuesen elementos de una matriz. También que se pueden aplicar ciertas operaciones sobre la totalidad, o parte, de esta estructura considerada como una unidad.

§3 Clasificación

Existen dos tipos de contenedores: secuencias y asociativos; a su vez se subdividen según el tipo de iterador que soportan.

Las secuencias almacenan los elementos en orden secuencial (de ahí su nombre). El contenedor agrupa a todos sus miembros como una sucesión lineal, y en consecuencia son adecuadas para accesos directos y secuenciales. Un ejemplo de secuencia es una matriz. De hecho, los algoritmos que pueden aplicarse a las secuencias pueden aplicarse también a las matrices.

Las asociaciones almacenan sus miembros en forma de árbol indexado, por lo que son denominados también contenedores asociativos ordenados, y resultan adecuados para accesos aleatorios mediante claves.  La STL proporciona cinco tipo distintos.

La existencia de índices supone una ordenación según los valores de un conjunto de elementos (denominado "de claves") para el que debe existir un criterio de ordenación. Dicho en otras palabras, los objetos "de clave" deben ser de un tipo para el que estén definidos los operadores relacionales. El árbol es mantenido ordenado de forma automática por los algoritmos de inserción y borrado del contenedor.

Existen mecanismos para asociar un valor o dato de cualquier tipo con una clave; para encontrar el valor asociado a una clave y para recorrer el conjunto (ordenado) de los elementos.

La Librería Estándar C++ contiene diez formas de contenedores y tres adaptadores de contenedor (denominados simplemente adaptadores). En esta sección se expondrán brevemente cuales son estas formas; sus características, y cual es la más adecuada para cada tipo de problema específico. En secciones sucesivas se comentarán individualmente con mayor detalle.

A continuación incluimos una relación siguiendo la clasificación utilizada en el Estándar:

• Secuencias

  • deque

  • list

  • stack

  • vector

  • vector <bool>

• adaptadores

• queue

• priority_queue

• Contenedores asociativos

  • map

  • multimap

  • set

  • multiset

  • bitset

§4 Características

Las características más significativas de las diversas formas de contenedor son:

Contenedor	Características
Secuencias
vector	Este contenedor es una estructura de datos de tamaño fijo preferentemente. Aunque la STL proporciona herramientas para cambiar el tamaño de un vector de forma dinámica, esta operación es costosa y debe ser evitada dentro de lo posible (en este sentido el vector se comporta como una matriz ordinaria). Disponen de un buén mecanismo de acceso aleatorio a elementos y de un mecanismo de inserción al final muy eficiente ( 5.1.2g). Generalmente es preferible utilizar un vector que un deque o un list, a menos que sea frecuentemente necesario insertar datos al comienzo o al final, en cuyo caso es mejor utilizar un deque.  Si por el contrario es frecuente la inserción de elementos en el centro, entonces es preferible un list.
vector<bool>	Es una versión de la anterior especial para valores binarios (bits).
list	Este contenedor responde a la idéa intuitiva de "lista", el almacenamiento de objetos en una secuencia lineal que no está necesariamente ordenada (aunque sus miembros pueden ser ordenados fácilmente mediante la función-miembro sort() ). Estos contenedores suelen ser implementados como listas doblemente enlazadas ( 1.8). Dispone de mecanismos eficientes para insertar elementos al principio, al final o en cualquier posición (utilizando iteradores que denoten posición). Estas operaciones consumen un tiempo constante con independencia del número de elmentos albergados en el contenedor. Dado que son estructuras lineales, en general los elementos no pueden ser accedidos por subíndices como en un vector.  Es necesario realizar un recorrido lineal por todos los valores, por lo que en las operaciones de acceso se utilizan tiempos proporcionales al número de elementos.
stack	Contenedor de elementos tipo pila LIFO que permite inserciones y eliminaciones solo en la parte superior.
deque	Los deques o colas de doble terminación ("Double-ended queue") son un tipo de estructura de datos que comparte las características de las colas ("Queues") y las pilas ("Stacks"). Como en las colas ( 1.8), los elementos pueden ser empujados por un extremo al interior del contenedor, y el primer elemento introducido puede ser extraído por el extremo opuesto. Al mismo tiempo, el último elemento introducido por el principio puede ser extraído en ese mismo extremo como si fuese una pila ( 1.8). Estos contenedores suelen ser implementados bajo la forma de matrices bidimensionales. Las características de los deques implementados en la STL pueden resumirse en: Acceso aleatorio; mecanismo eficiente de inserción al principio o al final.
string	Contenedor de caracteres adaptado a operaciones con cadenas de caracteres.
Asociaciones
set	Como el resto de contenedores asociativos, esta forma de contenedor mantiene los elementos en orden. Dispone de mecanismos eficientes para inclusión, inserción y eliminación de elementos, y soporta claves únicas (solo puede existir un miembro con una clave determinada).
multiset	Versión del anterior que permite la existencia de claves duplicadas. Es decir, distintos elementos dentro del conjunto pueden responder a la misma clave.
bitset	Contenedor de bit más orientado al tamaño que hacia el tipo de contenido. Permite almacenar secuencias de bits de tamaño fijo. No existen iteradores para reccorrerlas, y sus elementos se acceden utilizando el operador subíndice [ ]. Se dispone de varias funciones para realizar con ellos operaciones de bits ( 4.9.3)
map	Como el resto de estructuras asociativas, el map mantiene sus elementos ordenados. Se caracteriza porque sus miembros son pares de valores que pueden ser de tipos distintos. Uno de ellos, el que actúa como clave para el índice ("Key-value"), puede ser de cualquier tipo, a condición de que sus elementos puedan ser ordenados según un criterio (por defecto se utiliza el operador <). Permite claves únicas. Es decir, que solo puede existir un miembro para cada clave. Dispone de mecanismos de inserción y borrado muy eficientes y no existe límite de tamaño. La estructura se encarga de crecer y disminuir en concordancia con las necesidades de sus miembros. Permite el operador [ ] subíndice para los elementos de la clave así como otras técnicas de acceso. Estas estructuras de datos recibe también los nombres de diccionarios, tablas y matrices asociativas, en referencia a que pueden considerarse como dos matrices del mismo número de elementos, en las que existe una relación entre cada miembro de una con otro miembro de la otra.  Una de las matrices (que actúa de índice) estaría ordenada según su contenido.
multimap	En todo igual que el anterior pero permitiendo además claves duplicadas. Es decir, que una misma clave pueda estar asociada a dos "valores" distintos.

 

Adaptador	Características
queue	Contenedor tipo cola FIFO que permite inserciones al final y eliminaciones al principio.
priority queue	Este contenedor dispone de mecanismos eficientes para acceso y eliminación de grandes valores.