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. Está 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.
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.
