Razón Artificial

La ciencia y el arte de crear videojuegos

Una introducción a la STL I – Introducción a los contenedores

Escrito por adrigm el 14 de marzo de 2012 en Programación | 1 Comentario.

Vamos a dedicar una serie de artículos a hablar de la Biblioteca de plantillas estándar (STL) de C++. Esta poderosa herramienta usada por casi todo los programadores de C++ de la que hay muy poca documentación disponible en nuestro idioma.

La STL es una colección de estructuras de datos y algoritmos de uso común. Esta basada en plantillas utilizando programación genérica. Está diseñada para ser eficiente, evita el uso de funciones virtuales en favor de las plantillas evitando operaciones en tiempo de ejecución.

La STL se podría dividir en tres grandes partes: Contenedores (plantillas de estructuras de datos populares), iteradores y algoritmos.

Introducción a los contenedores

Los contenedores de la STL son estructuras de datos capaces de contener casi cualquier tipo de objeto (hay algunas restricciones). Existen 3 tipos de clases contenedoras: contenedores de primera clase, adaptadores y casi-contenedores.

También podemos catalogar a los contenedores por el tipo. Existen 3 tipos de contenedores: Contenedores de secuencia, Contenedores asociativos y Adaptadores de contenedores. Vamos a ver una tabla con los tipos de contenedores que hay.

Clase Contenedora Descripción
Contenedores de secuencia (primera clase)
vector Inserción y eliminación rápida en la parte final. Acceso directo a cualquier elemento.
deque Incersiones y eliminaciones rápidas en la parte inicial o final. Acceso aleatorio a cualquier elemento.
list Lista con enlace doble, incersión y eliminación rápida en cualquier parte.
Contenedores asociativos (primera clase)
set Búsqueda rápida, no se permiten duplicados.
multiset Búsqueda rápida, se permiten duplicados
map Asociasión de uno a uno, no se permiten duplicados, búsqueda rápida basada en claves.
multimap Asociasión de uno a uno, se permiten duplicados, búsqueda rápida basada en claves.
Adaptadores de contenedores
stack Último en entrar primero en salir (UEPS).
queue Primero en entrar, primero en salir (PEPS).
priority_queue El elemento de mayor prioridad siempre es el primero en salir.

Las contenedores de secuencia representan estructuras de datos lineales tales come vectores y listas enlazadas. Los contenedores asociativos representan estructuras de datos no lineales que por lo general pueden localizar elementos almacenados en ellos rápidamente. Dichos elementos pueden almacenar conjuntos de valores, o pares clave/valor. Los contenedores de secuencia y los contenedores asociativos son los contenedores de primera clase. Las pilas (stack), las colas (queue) y las colas priorizadas (priority queue) son en realidad versiones restringidas de los contenedores de secuencia. Por esta razón la STL los implementa como adaptadores de contenedores que permiten a un programa ver un contenedor de secuencia de manera restringida.

Existen otro tipo de contenedores los conocidos como casi-contenedores que son los arreglos basados en punteros tipo C,  los contenedores bitset para mantener conjuntos de valores de bandera y contenedores valarray para llevar a cabo operaciones vectoriales matemáticas de alta velocidad (esta última clase esta optimizada para un buen rendimiento del compilador y no es tan flexible como los contenedores de primera clase). Se les consideran casi-contenedores porque guardan similitud con los contenedores, pero no soportan todas sus capacidades. El tipo string de la STL, por ejemplo, soporta la misma funcionalidad que un contenedor de secuencia, pero sólo almacena datos de tipo carácter.

Funciones comunes de los contenedores

La mayoría de contenedores de la STL proporcionan una funcionalidad similar. Hay muchas operaciones genéricas, como el método size, que se aplica a todos los contenedores. La siguiente tabla muestra los métodos comunes en todos los contenedores

Aviso Los operadores sobrecargados operator<, operator<=, operator>, operator>=, operator== y operator!= no se proporcionan para contenedores priority_queue.
Funciones miembros comunes Descripción
constructor predeterminado Un constructor para crear un contenedor vacío. Por lo general, cada contenedor cuenta con varios constructores que proporcionan distintos métodos de inicialización.
constructor de copia Un constructor que inicializa al contenedor para que sea una copia de un contenedor existente del mismo tipo.
destructor La función destructora para encargarse de la limpieza, una vez que el contenedor ya no sea necesario.
empty Devuelve true si no hay elementos en el contenedor, en caso contrario devuelve false.
insert Inserta un elemento en el contenedor.
size Devuelve el número de elementos que hay actualmente en el contenedor.
operator= Asigna un contenedor a otro.
operator< Devuelve true si el primer contenedor es menor que el segundo, en caso contrario devuelve false.
operator<= Devuelve true si el primer contenedor es menor o igual que el segundo, en caso contrario devuelve false.
operator> Devuelve true si el primer contenedor es mayor que el segundo, en caso contrario devuelve false.
operator>= Devuelve true si el primer contenedor es mayor o igual que el segundo, en caso contrario devuelve false.
operator== Devuelve true si el primer contenedor es igual que el segundo, en caso contrario devuelve false.
operator!= Devuelve true si el primer contenedor es distinto que el segundo, en caso contrario devuelve false.
swap Intercambia los elementos de dos contenedores.
Funciones que solo se enecuentran en contenedores de primera clase
max_size Devuelve el número máximo de elementos para un contenedor.
begin Las dos versiones de esta función devuelven ya sea un iterator o un const_iterator que hace referencia al primer elemento del contenedor.
end Las dos versiones de esta función devuelven ya sea un iterator o un const_iterator que hace referencia a la siguiente posición después del final del contenedor.
rbegin Las dos versiones de esta función devuelven ya sea un reverse_iterator o un const_revese_iterator que hace referencia al último elemento del contenedor.
rend Las dos versiones de esta función devuelven ya sea un reverse_iterator o un const_revese_iterator que hace referencia a la posición que está antes del primer elemento del contenedor.
erase Elimina uno o más elementos del contenedor.
clear Elimina todos los elementos del contenedor.

Archivos de encabezado de la STL

En la siguiente tabla se muestran los archivos de encabezado necesarios para los distintos contenedores. Todo el contenido de estos archivos de encabezado está dentro del namespace std

Archivos de encabezado de la STL
<vector>
 <list>
 <deque>
 <queue> Contiene tanto a queue como a priority_queue.
 <stack>
 <map> Contiene tanto a map como a multimap.
 <set> Contiene tanto a set como a multiset
 <valarray>
 <bitset>

Definiciones typedef comunes de los contenedores de primera clase

En la siguiente tabla se muestran los elementos typedef (para crear sinónimos o alias de tipos extensos) comunes que se encuentran en los contenedores de primera clase. Estos elementos typedef se utilizan en declaraciones genéricas de variables, parámetros a funciones y valores de retorno de las funciones. Por ejemplo, value_type en contenedor es siempre un typedef que representa el tipo de valor almacenado en el contenedor.

typedef Descripción
allocator_type El tipo de objeto utilizado para aasignar la memoria del contenedor.
value_type El tipo de elemento almacenado en el contenedor.
reference Una referencia al tipo de elemento almacenado en el contenedor.
const_reference Una referencia constante al tipo de elemento almacenado en el contenedor. Dicha referencia sólo puede ser utilizada para leer elementos y colocarlos en el contenedor, y para realizar operaciones const.
pointer Un puntero al tipo de elemento almacenado en el contenedor.
const_pointer Un puntero al tipo de elemento constante almacenado en el contenedor.
iterator Un iterador que apunta al tipo de elemento almacenado en el contenedor.
const_iterator Un iterador constante que apunta al tipo de elemento almacenado en el contenedor y que solo puede utilizarse para leer elementos.
reverse_iterator Un iterador inverso que apunta al tipo de elemento almacenado en el contenedor. Este tipo de iterador es para iterar a través de un contenedor en sentido inverso.
const_reverse_iterator Un iterador inverso constante que apunta al tipo de elemento almacenado en el contenedor y que solo puede utilizarse para leer elementos. Esti tipo de iterador es para iterar a través del contenedor en sentido inverso.
difference_type El tipo del resultado obtenido al restar dos iteradores que hacen referencia al mismo contenedor (operator- no está definido para iteradores de contenedores list ni contenedores asociativos).
size_type El tipo utilizado para contar elementos en un contenedor e indizar a través de un contenedor de secuencia (no se puede indizar a través de un contenedor list).

Al utilizar contenedores de la STL, es importante asegurar que el tipo de elemento que vaya a almacenarse en el contenedor soporte un conjunto mínimo de funcionalidad. Al insertar un elemento en un contenedor, se crea una copia de ese elemento. Por esta razón el tipo de elemento debe proporcionar su propio constructor copia y operador de asignación (esto solo se requiere si la copia y la asignación predeterminada a nivel de miembro no se realizan operaciones apropiadas de copia y asignación para el tipo de elemento). Además, los contenedores asociativos y muchos algoritmos requieren de la comparación de elementos. Por esta razón, el tipo del elemento debe proporcionar un operador de igualdad == y un operador menor que <.

Técnicamente, los contenedores de la STL no requieren comparar sus elementos con los operadores de igualdad y menor que, a menos que un programa utilice una método del contenedor que deba comparar elementos (por ejemplo, la función sort en la clase list). Por desgracia, algunos compiladores de C++ previos al estándar no son capaces de ignorar la parte de la plantilla que no se utiliza en un programa específico. En los compiladores con este problema, tal vez deba sobrecargar los operadores == y < de los objetos que vayas a insertar en un contenedor de la STL.

Hemos visto una introducción a los contenedores los tipos que hay las funciones miembros comunes a ellos, sus archivos de encabezado y los typedef comunes. En el siguiente artículo haremos una introducción a los iteradores y en los sucesivos empezaremos a ver específicamente cada contenedor y usarlos en la práctica.

Un Comentario en "Una introducción a la STL I – Introducción a los contenedores"

  1. Engage dice:

    Eh, Adri, a ver si hablamos que no te veo desde que planeamos lo del diseño del robot del juego 2D.
    Un saludo.

    Engage

Deja un comentario