Biblioteca de plantillas estándar - Standard Template Library

Para otros usos, consulte STL .

Biblioteca estándar de C ++
Contenedores
Biblioteca estándar de C

La biblioteca de plantillas estándar ( STL ) es una biblioteca de software 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 .

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 copiar y asignar). 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 modernos de C ++ están ajustados para minimizar las penalizaciones de abstracción que surgen del uso intensivo de STL.

El STL se creó 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, modelo de cálculo de Von Neumann y semántica de valores .

Historia

Artículo principal: Historia de la biblioteca de plantillas estándar

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 llevó a Andrew Koenig a solicitar una propuesta formal a tiempo para la reunión de marzo de 1994. El comité tuvo 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 demostrar ser consistentes implementándolos por completo, 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 difusión generalizada temprana de la STL mejoraron considerablemente con la decisión de Hewlett-Packard de hacer que su implementación esté 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 ofrecidas por los proveedores de bibliotecas y compiladores en la actualidad.

Composición

Contenedores

El STL contiene contenedores de secuencia y contenedores asociativos. Los contenedores son objetos que almacenan datos. Los estándar de contenedores de secuencias incluyen , , y . Los estándar de contenedores asociativos son , , , , , , y . También hay adaptadores de contenedores , y , que son recipientes con interfaz específica, utilizando otros recipientes como aplicación. vectordequelistsetmultisetmapmultimaphash_sethash_maphash_multisethash_multimap queuepriority_queuestack

Envase Descripción
Contenedores simples
par El contenedor de pares es un contenedor asociativo simple que consta de 2 tuplas de elementos de datos u objetos, llamados "primero" y "segundo", en ese orden fijo. El 'par' STL se puede asignar, copiar y comparar. La matriz de objetos asignados en un mapa o hash_map (descritos a continuación) son de tipo 'par' por defecto, donde todos los 'primeros' elementos actúan como claves únicas, cada una asociada con sus 'segundos' objetos de valor.
Secuencias (matrices / listas enlazadas ): colecciones ordenadas
vector una matriz dinámica , como la matriz C (es decir, con capacidad de acceso aleatorio ) con la capacidad de cambiar su tamaño automáticamente al insertar o borrar un objeto. Insertar un elemento en la parte posterior del vector al final lleva un tiempo constante amortizado . Eliminar el último elemento solo requiere un tiempo constante, porque no ocurre ningún cambio de tamaño. Insertar y borrar al principio o en el medio es lineal en el tiempo.

Existe una especialización para el tipo bool , que optimiza el espacio almacenando los valores bool como bits.

lista una lista doblemente enlazada ; los elementos no se almacenan en la memoria contigua. Rendimiento opuesto de un vector. Búsqueda y acceso lentos (tiempo lineal), pero una vez que se ha encontrado una posición, rápida inserción y eliminación (tiempo constante).
deslizamiento
 una lista enlazada individualmente ; los elementos no se almacenan en la memoria contigua. Rendimiento opuesto de un vector. Búsqueda y acceso lentos (tiempo lineal), pero una vez que se ha encontrado una posición, rápida inserción y eliminación (tiempo constante). Tiene una inserción y eliminación un poco más eficiente, y usa menos memoria que una lista doblemente vinculada, pero solo se puede iterar hacia adelante. Está implementado en la biblioteca estándar de C ++ como . forward_list
deque ( cola de dos extremos ) un vector con inserción / borrado al principio o al final en tiempo constante amortizado , sin embargo, carece de algunas garantías sobre la validez del iterador después de alterar la deque.
Adaptadores de contenedores
cola Proporciona una interfaz de cola FIFO en términos de / / / operaciones. pushpopfrontback

Las operaciones de apoyo de secuencias , , , y se pueden utilizar para cola instantiate (por ejemplo, y ). front()back()push_back()pop_front()listdeque
cola de prioridad Proporciona una interfaz de cola de prioridad en términos de operaciones (el elemento con la prioridad más alta está en la parte superior). push/pop/top

Cualquier de acceso aleatorio operaciones secuencia de apoyo , y se pueden utilizar para priority_queue instantiate (por ejemplo, y ). Se implementa mediante un

montón . front()push_back()pop_back()vectordeque

Los elementos también deben admitir la comparación (para determinar qué elemento tiene una prioridad más alta y debe aparecer primero).

apilar Proporciona una interfaz de pila LIFO en términos de operaciones (el último elemento insertado está en la parte superior). push/pop/top

Las operaciones de apoyo de secuencia , y se pueden utilizar para pila instantiate (por ejemplo , , y ). back()push_back()pop_back()vectorlistdeque
Contenedores asociativos : colecciones desordenadas
colocar un conjunto matemático ; insertar / borrar elementos en un conjunto no invalida los iteradores que apuntan al conjunto. Proporciona unión de operaciones , intersección , diferencia , diferencia simétrica y prueba de inclusión. 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 estrictamente débil ; de lo contrario, el comportamiento no está definido. Suele implementarse mediante un árbol de búsqueda binario autoequilibrado . <
multiset igual que un conjunto, pero permite elementos duplicados ( multiconjunto matemático ).
mapa una matriz asociativa ; permite el mapeo de un elemento de datos (una clave) a otro (un valor). El tipo de clave 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 estrictamente débil ; de lo contrario, el comportamiento no está definido. Suele implementarse mediante un árbol de búsqueda binario autoequilibrado. <
multimapa igual que un mapa, pero permite duplicar claves.
hash_set
hash_multiset
hash_map
hash_multimap 		similar a un conjunto, multi-conjunto, mapa o multi-mapa, respectivamente, pero implementado usando una tabla hash ; las claves no están ordenadas, pero debe existir una función hash para el tipo de clave. Estos tipos se dejaron fuera del estándar C ++; contenedores similares se estandarizaron en C ++ 11 , pero con diferentes nombres ( y ). unordered_setunordered_map
Otros tipos de contenedores
bitset almacena series de bits similares a un vector de bools de tamaño fijo. Implementa operaciones bit a bit y carece de iteradores. No es una secuencia. Proporciona acceso aleatorio.
Valarray Otro tipo de datos de matriz, destinado a uso numérico (especialmente para representar vectores y matrices ); el estándar C ++ permite optimizaciones específicas para este propósito. Según Josuttis, valarray fue mal diseñado por personas "que dejaron el comité [del estándar C ++] mucho tiempo antes de que se terminara el estándar", y se prefieren las bibliotecas de plantillas de expresión . Se rechazó una reescritura propuesta de la parte valarray del estándar en este sentido, convirtiéndose en un permiso para implementarlo utilizando una plantilla de expresión.

Iteradores

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 de avance (que se pueden leer, escribir y avanzar), iteradores bidireccionales (que son como iteradores hacia adelante, pero también pueden moverse hacia atrás) y acceso iterador aleatoria s(que se puede mover libremente a cualquier número de pasos en una sola operación).

Un concepto STL fundamental 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.

Es posible hacer que los iteradores bidireccionales actúen como iteradores de acceso aleatorio, por lo que avanzar diez pasos podría realizarse 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 el STL se pueden usar en el contenedor.

Esta generalidad también tiene un precio a veces. 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 a los algoritmos que utilizan iteradores.

Algoritmos

En el STL se proporciona una gran cantidad de algoritmos para realizar actividades como la búsqueda y la clasificació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 y utilizan la 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 estrictamente débil . 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 unión , intersección , diferencia de rangos ordenados. binary_searchlower_bound<

Funciones

El STL incluye clases que sobrecargan la función llamada operator ( ). 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 la 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 de 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 toman un predicado unario que opera sobre los elementos de una secuencia. Algoritmos como sort, parcial_sort, nth_element y todos los contenedores ordenados usan un predicado binario que debe proporcionar un orden 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 menos de forma predeterminada, lo que a su vez llama al operador menor que <. find_if

Criticas

Calidad de implementación de compiladores de C ++

La calidad de implementación (QoI) del compilador de C ++ tiene un gran impacto en la usabilidad de STL (y el código con plantilla en general):

  • Los mensajes de error que involucran plantillas tienden a ser muy largos y difíciles de descifrar. Este problema se ha considerado tan grave que se han escrito varias herramientas que simplifican e imprimen mensajes de error relacionados con STL para hacerlos más comprensibles.
  • El uso descuidado de las plantillas puede provocar un exceso de código . Esto se ha contrarrestado con técnicas especiales dentro de las implementaciones de STL (por ejemplo, utilizando contenedores void * internamente y otras técnicas de "plantilla de dieta") y mejorando las técnicas de optimización de los compiladores. Sin embargo, este síntoma es similar a la copia manual ingenua de un conjunto de funciones para trabajar con un tipo diferente, ya que ambos pueden evitarse con cuidado y una buena técnica.
  • La creación de instancias de plantillas puede aumentar el tiempo de compilación y el uso de la memoria, a cambio de reducir normalmente la toma de decisiones en tiempo de ejecución (por ejemplo, a través de funciones virtuales). Hasta que la tecnología del compilador mejore lo suficiente, este problema solo puede eliminarse parcialmente mediante una codificación cuidadosa, evitando ciertos modismos y simplemente no usando plantillas donde no son apropiadas o donde se prioriza el rendimiento en tiempo de compilación.

Otros asuntos

  • La inicialización de contenedores STL con constantes dentro del código fuente no es tan fácil como las estructuras de datos heredadas de C (tratadas en C ++ 11 con listas de inicializadores ).
  • Los contenedores STL no están pensados ​​para usarse como clases base (sus destructores son deliberadamente no virtuales); derivar de un contenedor es un error común.
  • El concepto de iteradores implementado por STL puede ser difícil de entender al principio: por ejemplo, si se elimina un valor al que apunta el iterador, el iterador en sí ya no es válido. Ésta es una fuente común de errores. La mayoría de las implementaciones de STL proporcionan un modo de depuración que es más lento, pero puede localizar tales errores si se usa. Existe un problema similar en otros lenguajes, por ejemplo, Java . Los rangos se han propuesto como una alternativa más segura y flexible a los iteradores.
  • Ciertos patrones de iteración no se asignan al modelo de iterador de STL. Por ejemplo, las API de enumeración de devolución de llamada no pueden adaptarse al modelo STL sin el uso de corrutinas , que dependen de la plataforma o no están disponibles, y estarán fuera del estándar C ++ hasta C ++ 20.
  • El cumplimiento del compilador no garantiza que los objetos de Allocator , utilizados para la gestión de memoria para contenedores , funcionen con un comportamiento dependiente del estado. Por ejemplo, una biblioteca portátil no puede definir un tipo de asignador que extraiga memoria de diferentes grupos utilizando diferentes objetos de asignación de ese tipo. (Meyers, p. 50) (abordado en C ++ 11 ).
  • El conjunto de algoritmos no está completo: por ejemplo, se omitió el algoritmo, aunque se agregó en C ++ 11 .copy_if

Implementaciones

Ver también

Notas

Referencias

enlaces externos