Disponible la nueva versión "donationware" 7.3 de OrganiZATOR
Descubre un nuevo concepto en el manejo de la información.
La mejor ayuda para sobrevivir en la moderna jungla de datos la tienes aquí.

Curso C++

[Home]  [Inicio]  [Índice]


5.1.1a Seleccionar un contenedor

§1 Sinopsis

Como se ha señalado ( 5.1), el binomio contendor-iterador conforma una herramienta que se adapta a circunstancias muy variadas. De hecho, es posible que un determinado problema pueda ser abordado de varias formas. En estos casos la selección de la forma de contenedor más adecuado depende de las circunstancias. En ciertas ocasiones puede resultar bastante obvia; en otras puede no estar tan claro cual es la mejor opción, pues "a priori", pueden adaptarse varias formas al caso concreto. Naturalmente puede utilizarse el sistema de prueba y comparación. Por ejemplo, cronometrando los resultados obtenidos en un modo u otro. También será de gran ayuda la experiencia, pero como una guía o criterio general puede utilizarse el principio de selección que se indica a continuación.

Como se accederá a los datos? Si es importante un acceso aleatorio, pueden utilizarse un vector o un deque. Si basta con un acceso secuencial cualquiera de los dos puede ser el elegido.
Es importante el orden en que serán mantenidos los valores dentro de la colección de datos? Existen muchas formas de secuenciar los valores. Si es importante un orden estricto a lo largo de toda la vida del contenedor, la elección obvia es un set, dado que las inserciones en una de estas estructuras se realiza automáticamente en orden.

Si este orden es importante solo en algún momento, por ejemplo al final de una serie de inserciones, puede ser más sencillo colocar los valores en un list o vector para ordenar más tarde el resultado en el momento necesario.

Si el orden en que se almacenan los valores en la estructura está relacionado con el orden de su inserción, entonces un stack, un queue o un list pueden ser la mejor elección.

Puede variar mucho el tamaño de la estructura de datos durante el curso de la ejecución del programa? Si es así, entonces puede ser que la mejor opción sean un list o un set. Un vector o un deque pueden conducir a mantener un gran almacenamiento intermedio (buffer); incluso después que los elementos hayan sido eliminados de la colección de datos. Estos dos contenedores no son adecuados para cambios de tamaño, aunque vector dispone de un mecanismo de inserción al final eficiente.

Recíprocamente: si el tamaño de la colección se mantiene relativamente estable, entonces un vector o un deque pueden utilizar menos memoria que un list o un set que almacenen el mismo número de elementos.

Es posible determinar el tamaño de la colección? La estructura de datos vector proporciona un medio para pre-seleccionar un bloque de memoria de un tamaño específico con la función miembro reserve(), posibilidad que no existe en otros contenedores.
Es frecuente tener que comprobar si un valor cualquiera está incluido en la colección? En este caso, un contenedor set o map pueden ser buena elección. En estos casos comprobar si un determinado valor está incluido puede ser realizado con un pequeño número de pasos (logarítmicos con el tamaño del contenedor). Mientras que la misma verificación en cualquiera de los otros tipos puede requerir comparar el valor con cada elemento almacenado en el contenedor.
Está indexada la colección de datos?

Si es así, puede ser vista la colección como una serie de pares clave/valor?

Si las claves son enteros entre 0 y un límite superior, pueden utilizarse un vector o un deque.

Si la clave es algún otro valor, como cadenas de caracteres o tipos definidos por el usuario, puede utilizarse un contenedor map.

Pueden los valores estar relacionados unos con otros? Todos los valores almacenados en cualquier contenedor de la STL debe ser capaz de comprobar la igualdad con cualquier otro valor similar, pero recuerde que no todos son capaces de reconocer el operador de relación menor-que; sin embargo, si los valores no pueden ser ordenados utilizando el operador menor-que, no pueden ser almacenados en un set o en un map.
Es una operación frecuente tener que encontrar y eliminar el valor mayor de la colección? En caso afirmativo, la estructura de datos más idónea es el priority queue.
En que posiciones son insertados o eliminados los elementos de la estructura? Si los valores son añadidos o eliminados en la zona interior, entonces la mejor opción es un list.

Si los valores son insertados solo al comienzo, un deque o un list pueden ser lo más adecuado.

Si los valores son insertados y eliminados solo al final, un stack o un queue pueden ser elecciones lógicas.

Es frecuente tener que refundir dos o más secuencias en una sola? En caso afirmativo, puede considerarse que las mejores opciones son un set o un list, dependiendo que la colección deba o no ser mantenida en orden.

Refundir dos set es una operación muy eficiente.  Si la colección de datos no está ordenada, pero puede utilizarse la función miembro splice() de las list (que es muy eficiente), entonces es preferible este último tipo de contenedor, dado que esta operación no está contemplada en las demás formas.

§2 Tipos no incluidos

Como se ha indicado repetidamente, la Librería Estándar C++ incluye contenedores adecuados para la mayoría de los casos prácticos, aunque quizás existen una serie de estructuras de datos clásicas que no han sido incluidas ( 1.8). En la mayoría de los casos, la causa es que los contenedores proporcionados pueden ser fácilmente adaptados para suplir los usos facilitados por los tipos omitidos.

La tabla adjunta relaciona los tipos clásicos no incluidos y la sustitución más fácil.


Contenedor omitido Sustitución utilizando elementos de STL
tree El modo set está implementado internamente como un árbol de búsqueda binaria.

Para la mayoría de los casos prácticos que pueden ser resueltos utilizando árboles este modo es un sustituto adecuado.

matrices multidimensionales Puesto que los vectores pueden almacenar elementos que sean otros vectores, estas estructuras pueden ser construidas fácilmente.
graph La representación de un gráfico puede ser fácilmente construida como un map que contiene otros map. Un map cuyos elementos son a su vez maps, es la representación natural de un gráfico directo. Por ejemplo, supongamos que utilizamos cadenas de caracteres para codificar nombres de ciudades, y que deseamos construir un map donde el valor asociado con un borde es la distancia entre dos ciudades conectadas.

Se puede crear uno de estos gráficos como se muestra en el ejemplo ( xxx)

sparse array Una novedosa sustitución es la representación de un gráfico ( xxx).
hash table Las tablas hash [1] proporcionan un tiempo de acceso constante, así como inserción y borrado de elementos, convirtiendo estas operaciones en operaciones de índice.

Una tabla hash puede ser construida fácilmente como un vector (o deque) cuyos elementos son lists (o incluso sets).  En el ejemplo de la ordenación raíz ( xxx) se describe una de estas estructuras (un vector de deques), aunque en este ejemplo no incluye invocación la función hash para convertir un valor en un índice.

Funcionalidad set En la STL, los tipos set están específicamente ordenados, y sus operaciones (como la unión intersección, etc.) no pueden ser realizadas sobre colecciones de valores no ordenados (por ejemplo un conjunto de números complejos).

Una list puede ser utilizada como sustituto, aunque es necesario escribir funciones de operación especiales, dado que los algoritmos genéricos no pueden ser utilizados con listas.

  Inicio.


[1] Las tablas hash, también denominadas matrices matrices asociativas ("Associative arrays") o simplemente hashes, son listas de varias columnas en las que existe una correspondencia entre los elementos de una y los elementos de la otra. El ejemplo típico es un listin telefónico en el que corresponde un número de una lista numérica con una posición de una lista de nombres.