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]
La STL proporciona un conjunto de clases comunes para C++, como contenedores y matrices asociativas , que se pueden utilizar 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.
La STL logra sus resultados mediante el uso de plantillas . Este enfoque proporciona polimorfismo en tiempo de compilación que suele ser más eficiente que el polimorfismo tradicional en tiempo de ejecución . Los compiladores de C++ modernos están ajustados para minimizar las penalizaciones por abstracción que surgen del uso intensivo de la STL.
La STL fue creada 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 .
La 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 una solicitud de Andrew Koenig para una propuesta formal a tiempo para la reunión de marzo de 1994. El comité tenía 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 significativa ( contenedores asociativos ) tenían que demostrarse que eran consistentes mediante su implementación completa, una tarea que Stepanov delegó a 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 de estándar ANSI/ISO C++ (1, partes de las cláusulas 17 a 27).
Las perspectivas de una rápida difusión generalizada del STL mejoraron considerablemente con la decisión de Hewlett-Packard de poner su implementación a disposición del público de forma gratuita 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 hoy los proveedores de compiladores y bibliotecas.
La STL contiene contenedores de secuencia y contenedores asociativos. Los contenedores son objetos que almacenan datos. Los contenedores de secuencia estándar incluyen vector, deque, y list. Los contenedores asociativos estándar son set, multiset, map, multimap, hash_set, y . También hay adaptadores de contenedor , , y , que son contenedores con hash_mapuna interfaz específica, que utilizan otros contenedores como implementación.hash_multisethash_multimap queuepriority_queuestack
La 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 de avance (que se pueden leer, escribir y mover hacia adelante), iteradores bidireccionales (que son como iteradores de avance, 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 utilizan rangos. [6]
Es posible que los iteradores bidireccionales actúen como iteradores de acceso aleatorio, de modo que avanzar diez pasos podría hacerse simplemente avanzando un paso a la vez un total de diez veces. Sin embargo, tener iteradores de acceso aleatorio distintos ofrece ventajas de eficiencia. Por ejemplo, un vector tendría un iterador de acceso aleatorio, pero una lista solo un iterador bidireccional.
Los iteradores son la característica principal que permite la generalidad de la STL. Por ejemplo, se puede implementar un algoritmo para invertir una secuencia utilizando iteradores bidireccionales, y luego se puede utilizar 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 la STL se pueden utilizar en el contenedor.
Esta generalidad también tiene un precio en ocasiones. 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 las funciones miembro que ofrece 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 la STL se proporciona una gran cantidad de algoritmos para realizar actividades como búsqueda y ordenación, cada uno implementado para requerir un cierto nivel de iterador (y por lo tanto funcionará en cualquier contenedor que proporcione una interfaz por iteradores). Los algoritmos de búsqueda como binary_searchy lower_boundutilizan la búsqueda binaria y algoritmos de ordenació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 ordenamiento débil estricto . Aparte de estos, se proporcionan algoritmos para hacer un montón a partir de un rango de elementos, generar permutaciones ordenadas lexicográficamente de un rango de elementos, fusionar rangos ordenados y realizar la unión , intersección y diferencia de rangos ordenados.
La STL incluye clases que sobrecargan el operador de llamada de función ( ). Las instancias de dichas clases se denominan funtores u objetos de función . Los funtores permiten parametrizar el comportamiento de la función asociada (por ejemplo, a través de argumentos pasados al constructor del funtor ) y se pueden utilizar para mantener la información de estado asociada por funtor junto con la función. Dado que tanto los funtores como los punteros de función se pueden invocar utilizando la sintaxis de una llamada de función, son intercambiables como argumentos para las plantillas cuando el parámetro correspondiente solo aparece en contextos de llamada de función.operator()
Un tipo de funtor 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, partial_sort, nth_element y todos los contenedores ordenados usan un predicado binario que debe proporcionar un ordenamiento débil estricto , es decir, debe comportarse como una prueba de pertenencia en una relación binaria transitiva, no reflexiva y asimétrica . Si no se proporciona ninguno, estos algoritmos y contenedores usan less de manera predeterminada, 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 fue omitido, [12] aunque fue agregado 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 comienzo 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 pero sin incluir el señalado por j. El rango [i, j) es válido si y solo si j es accesible desde i.