La biblioteca de plantillas estándar ( STL ) es una biblioteca de software diseñada originalmente por Alexander Stepanov para el lenguaje de programación C++ que influyó en muchas partes de la biblioteca estándar de C++ . Proporciona cuatro componentes llamados algoritmos , contenedores , funciones e iteradores . [1]
STL proporciona un conjunto de clases comunes para C++, como contenedores y matrices asociativas , que se pueden usar con cualquier tipo integrado y con cualquier tipo definido por el usuario que admita algunas operaciones elementales (como copia y asignación). Los algoritmos STL son independientes de los contenedores, lo que reduce significativamente la complejidad de la biblioteca.
El STL logra sus resultados mediante el uso de plantillas . Este enfoque proporciona polimorfismo en tiempo de compilación que a menudo es más eficiente que el polimorfismo en tiempo de ejecución tradicional . Los compiladores de C++ modernos están optimizados para minimizar las penalizaciones por abstracción que surgen del uso intensivo de STL.
El STL fue creado como la primera biblioteca de algoritmos genéricos y estructuras de datos para C++, con cuatro ideas en mente: programación genérica , abstracción sin pérdida de eficiencia, el modelo de cálculo de Von Neumann , [2] y semántica de valores .
STL y la biblioteca estándar de C++ son dos entidades distintas. [3]
En noviembre de 1993, Alexander Stepanov presentó una biblioteca basada en programación genérica al comité ANSI/ISO para la estandarización de C++. La respuesta del comité fue abrumadoramente favorable y condujo a que Andrew Koenig solicitara una propuesta formal a tiempo para la reunión de marzo de 1994. El comité recibió varias solicitudes de cambios y extensiones y los miembros del comité se reunieron con Stepanov y Meng Lee para ayudar a resolver los detalles. Los requisitos para la extensión más importante ( contenedores asociativos ) debían demostrarse consistentes implementándolos completamente, una tarea que Stepanov delegó en David Musser . Una propuesta recibió la aprobación final en la reunión del comité ANSI/ISO de julio de 1994. Posteriormente, el documento 17 de Stepanov y Lee se incorporó al borrador del estándar ANSI/ISO C++ (1, partes de las cláusulas 17 a 27).
Las perspectivas de una pronta difusión generalizada del STL mejoraron considerablemente con la decisión de Hewlett-Packard de hacer que su implementación estuviera disponible gratuitamente en Internet en agosto de 1994. Esta implementación, desarrollada por Stepanov, Lee y Musser durante el proceso de estandarización, se convirtió en la base de Muchas implementaciones que ofrecen los proveedores de compiladores y bibliotecas en la actualidad.
El STL contiene contenedores de secuencias y contenedores asociativos. Los contenedores son objetos que almacenan datos. Los contenedores de secuencia estándar incluyen vector, dequey list. Los contenedores asociativos estándar son set, multiset, map, multimap, hash_set, hash_mapy hash_multiset. hash_multimapTambién existen adaptadores de contenedores queue , priority_queuey stack, que son contenedores con una interfaz específica, que utilizan otros contenedores como implementación.
El STL implementa cinco tipos diferentes de iteradores . Estos son iteradores de entrada (que solo se pueden usar para leer una secuencia de valores), iteradores de salida (que solo se pueden usar para escribir una secuencia de valores), iteradores directos (que se pueden leer, escribir y avanzar), iteradores bidireccionales (que son como iteradores hacia adelante, pero también pueden moverse hacia atrás) yiteradores de acceso aleatorio (que pueden moverse libremente cualquier número de pasos en una operación).
Un concepto fundamental de STL es un rango que es un par de iteradores que designan el comienzo y el final del cálculo, y la mayoría de las plantillas algorítmicas de la biblioteca que operan en estructuras de datos tienen interfaces que usan rangos. [6]
Es posible hacer que los iteradores bidireccionales actúen como iteradores de acceso aleatorio, por lo que se podría avanzar diez pasos simplemente avanzando un paso a la vez un total de diez veces. Sin embargo, tener distintos iteradores de acceso aleatorio ofrece ventajas de eficiencia. Por ejemplo, un vector tendría un iterador de acceso aleatorio, pero una lista solo tendría un iterador bidireccional.
Los iteradores son la característica principal que permite la generalidad del STL. Por ejemplo, se puede implementar un algoritmo para invertir una secuencia usando iteradores bidireccionales, y luego se puede usar la misma implementación en listas, vectores y deques . Los contenedores creados por el usuario solo tienen que proporcionar un iterador que implemente una de las cinco interfaces de iterador estándar, y todos los algoritmos proporcionados en STL se pueden usar en el contenedor.
Esta generalidad a veces también tiene un precio. Por ejemplo, realizar una búsqueda en un contenedor asociativo, como un mapa o un conjunto, puede ser mucho más lento utilizando iteradores que llamando a funciones miembro ofrecidas por el propio contenedor. Esto se debe a que los métodos de un contenedor asociativo pueden aprovechar el conocimiento de la estructura interna, que es opaca para los algoritmos que utilizan iteradores.
En el STL se proporciona una gran cantidad de algoritmos para realizar actividades como búsqueda y clasificación, cada uno de los cuales se implementa para requerir un cierto nivel de iterador (y, por lo tanto, funcionará en cualquier contenedor que proporcione una interfaz mediante iteradores). Los algoritmos de búsqueda como binary_searchel lower_bounduso de búsqueda binaria y los algoritmos de clasificación similares requieren que el tipo de datos debe implementar un operador de comparación <o se debe especificar una función de comparación personalizada; dicho operador de comparación o función de comparación debe garantizar un orden débil estricto . Aparte de estos, se proporcionan algoritmos para crear un montón a partir de una variedad de elementos, generar permutaciones ordenadas lexicográficamente de una variedad de elementos, fusionar rangos ordenados y realizar unión , intersección y diferencia de rangos ordenados.
El STL incluye clases que sobrecargan el operador de llamada de función ( ). Las instancias de tales clases se denominan functores u objetos de función . Los functores permiten parametrizar el comportamiento de la función asociada (por ejemplo, a través de argumentos pasados al constructor del functor ) y pueden usarse para mantener información de estado asociada por functor junto con la función. Dado que tanto los functores como los punteros de función se pueden invocar utilizando la sintaxis de una llamada de función, son intercambiables como argumentos para plantillas cuando el parámetro correspondiente solo aparece en contextos de llamada de función.operator()
Un tipo de functor particularmente común es el predicado . Por ejemplo, algoritmos como find_iftoman un predicado unario que opera sobre los elementos de una secuencia. Algoritmos como sort, part_sort, nth_element y todos los contenedores ordenados utilizan un predicado binario que debe proporcionar un ordenamiento débil estricto , es decir, debe comportarse como una prueba de membresía en una relación binaria transitiva, no reflexiva y asimétrica . Si no se proporciona ninguno, estos algoritmos y contenedores usan less de forma predeterminada, lo que a su vez llama al operador menor que <.
La Calidad de Implementación (QoI) del compilador de C++ tiene un gran impacto en la usabilidad del STL (y del código con plantilla en general):
copy_ifalgoritmo se omitió, [12] aunque se agregó en C++11 . [13]El STL se compone de contenedores , iteradores , objetos de función y algoritmos.
La mayoría de las plantillas algorítmicas de la biblioteca que operan en estructuras de datos tienen interfaces que utilizan rangos. Un rango es un par de iteradores que designan el principio y el final del cálculo. [...] en general, un rango [i, j) se refiere a los elementos en la estructura de datos comenzando con el señalado por i y hasta el señalado por j, pero sin incluirlo. El rango [i, j) es válido si y sólo si j es accesible desde i.