Hispanopedia Wiki
Articulo de referencia

Biblioteca de plantillas estándar

La Biblioteca de Plantillas Estándar ( STL ) fue una biblioteca de software diseñada originalmente por Alexander Stepanov para el lenguaje de programación C++ que influyó en muc...

Hispanopedia WikiContenido en espanolLectura gratuita

La Biblioteca de Plantillas Estándar ( STL ) fue 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++ , aunque ya no se mantiene activamente y ahora está integrada en su mayor parte en la propia biblioteca estándar de C++. Proporciona cuatro componentes llamados algoritmos , contenedores , functores e iteradores . [ 1 ]

La STL proporciona un conjunto de clases comunes para C++, como contenedores y matrices asociativas , que pueden utilizarse con cualquier tipo integrado o definido por el usuario que admita operaciones elementales (como copiar y asignar). Los algoritmos de la 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 modernos de C++ están optimizados para minimizar las penalizaciones de abstracción derivadas del uso intensivo de la STL.

La STL se creó como la primera biblioteca de algoritmos y estructuras de datos genéricos para C++, con cuatro ideas en mente: programación genérica , abstracción sin pérdida de eficiencia, el modelo de computación de Von Neumann , [ 2 ] y semántica de valor .

La STL y la Biblioteca Estándar de C++ son dos entidades distintas [ 3 ] , aunque a veces las partes de la Biblioteca Estándar de C++ directamente influenciadas/heredadas de la STL se denominan "la STL". [ 4 ]

Historia

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 motivó una solicitud de Andrew Koenig para que se presentara una propuesta formal a tiempo para la reunión de marzo de 1994. El comité solicitó varias modificaciones y extensiones, y sus miembros se reunieron con Stepanov y Meng Lee para concretar los detalles. Los requisitos para la extensión más significativa ( contenedores asociativos ) debían demostrar su coherencia mediante su implementación completa, tarea que Stepanov delegó a David Musser . La 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 rápida y amplia difusión de la 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 ofrecidas hoy en día por proveedores de compiladores y bibliotecas.

Composición

contenedores

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 . Los contenedores asociativoslist estándar son , , , , , , y . También hay adaptadores de contenedores , , y , que son contenedores con una interfaz específica, que utilizan otros contenedores como implementación.setmultisetmapmultimaphash_sethash_maphash_multisethash_multimapqueuepriority_queuestack

Iteradores

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 hacia adelante (que se pueden leer, escribir y avanzar), iteradores bidireccionales (que son como los iteradores hacia adelante, pero también pueden retroceder) yiteradores de acceso aleatorio (que pueden moverse libremente cualquier número de pasos en una operación).

Un concepto fundamental de STL es el rango , que es un par de iteradores que designan el inicio y el final del cálculo, y la mayoría de las plantillas algorítmicas de la biblioteca que operan sobre estructuras de datos tienen interfaces que utilizan rangos. [ 8 ]

Es posible que los iteradores bidireccionales funcionen como iteradores de acceso aleatorio, de modo que avanzar diez pasos se pueda hacer simplemente avanzando un paso a la vez, un total de diez veces. Sin embargo, contar con iteradores de acceso aleatorio distintos ofrece ventajas en cuanto a eficiencia. Por ejemplo, un vector tendría un iterador de acceso aleatorio, mientras que una lista solo tendría un iterador bidireccional.

Los iteradores son la característica principal que permite la generalidad de la STL. Por ejemplo, un algoritmo para invertir una secuencia se puede implementar usando iteradores bidireccionales, y luego la misma implementación se puede usar 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 usar en el contenedor.

Esta generalidad a veces 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 usando 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 su estructura interna, que es opaca para los algoritmos que usan iteradores.

Algoritmos

La STL 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 mediante iteradores). Los algoritmos de búsqueda como binary_searchutilizan lower_boundbúsqueda binaria y los algoritmos de ordenación como requieren que el tipo de datos implemente un operador de comparación <o que se especifique 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 . Además de estos, se proporcionan algoritmos para crear un montículo 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.

Funciones

La STL incluye clases que sobrecargan el operador de llamada a función ( ). Las instancias de estas clases se denominan functores u objetos de función . Los functores permiten parametrizar el comportamiento de la función asociada (por ejemplo, mediante argumentos pasados ​​al constructor del functor ) y pueden utilizarse para mantener información de estado asociada a cada functor junto con la función. Dado que tanto los functores como los punteros a funciones pueden invocarse utilizando la sintaxis de una llamada a función, son intercambiables como argumentos de plantillas cuando el parámetro correspondiente solo aparece en contextos de llamada a 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, 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 por defecto, que a su vez llama al operador menor que <.

Críticas

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

  • Los mensajes de error relacionados con las plantillas suelen ser muy largos y difíciles de descifrar. Este problema se ha considerado tan grave que se han desarrollado varias herramientas que simplifican y formatean los mensajes de error relacionados con STL para hacerlos más comprensibles.
  • El uso descuidado de plantillas puede provocar un exceso de código . [ 9 ] Esto se ha contrarrestado con técnicas especiales dentro de las implementaciones de la STL (por ejemplo, usando contenedores void* internamente y otras técnicas de "plantillas dietéticas") y mejorando las técnicas de optimización de los compiladores. Sin embargo, este problema es similar a copiar manualmente, de forma ingenua, un conjunto de funciones para trabajar con un tipo diferente, ya que ambos pueden evitarse con cuidado y una buena técnica.
  • La instanciación de plantillas puede aumentar el tiempo de compilación y el uso de memoria, a cambio de reducir, por lo general, la toma de decisiones en tiempo de ejecución (por ejemplo, mediante funciones virtuales). Hasta que la tecnología de compiladores mejore lo suficiente, este problema solo puede eliminarse parcialmente mediante una programación cuidadosa, evitando ciertas prácticas comunes y, simplemente, no utilizando plantillas donde no sean apropiadas o donde se priorice el rendimiento en tiempo de compilación.

Otros problemas incluyen:

  • La inicialización de contenedores STL con constantes dentro del código fuente no es tan sencilla como la de las estructuras de datos heredadas de C (problema abordado en C++11 con listas de inicialización ).
  • 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. [ 10 ] [ 11 ]
  • El concepto de iteradores, tal como lo implementa la STL, puede resultar difícil de comprender al principio: por ejemplo, si se elimina un valor al que apunta el iterador, este deja de ser válido. Esta es una fuente común de errores. La mayoría de las implementaciones de la STL ofrecen un modo de depuración más lento, pero que permite localizar dichos errores si se utiliza. Un problema similar existe en otros lenguajes, como Java . Se han propuesto los rangos como una alternativa más segura y flexible a los iteradores. [ 12 ]
  • Ciertos patrones de iteración, como las API de enumeración de devolución de llamada, no se pueden adaptar al modelo STL sin el uso de corrutinas , [ 13 ] que estuvieron fuera del estándar C++ hasta C++20.
  • El cumplimiento del compilador no garantiza que los objetos Allocator , utilizados para la gestión de memoria en contenedores , funcionen con un comportamiento dependiente del estado. Por ejemplo, una biblioteca portable no puede definir un tipo de asignador que extraiga memoria de diferentes grupos utilizando distintos objetos asignadores de ese tipo. (Meyers, p.  50) (abordado en C++11 ).
  • El conjunto de algoritmos no está completo: por ejemplo, copy_ifse omitió el algoritmo, [ 14 ] aunque se ha añadido en C++11 . [ 15 ]

Implementaciones

Véase también

Notas

  1. ^ Holzner, Steven (2001). C++  : Libro Negro . Scottsdale, Arizona: Grupo Coriolis. pag.  648.ISBN​ 1-57610-777-9La STL está compuesta por contenedores , iteradores , objetos de función y algoritmos .
  2. ↑ Musser, David (2001). Tutorial y guía de referencia de STL: Programación en C++ con la biblioteca de plantillas estándar . Addison Wesley . ISBN 0-201-37923-6.
  3. ↑ Lightness Races in Orbit (5 de marzo de 2011). "¿Cuál es la diferencia entre "STL" y "C++ Standard Library"?" . Stack Overflow . Consultado el 21 de octubre de 2021 .
  4. ↑ Comité de Estándares de C++. (2021). P2412R0 - Refinamientos adicionales al diseño de módulos de C++ . Recuperado de https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p2412r0.pdf Archivado el 20 de noviembre de 2024 (error de fecha) en Wayback Machine
  5. ↑ " [ vector.bool ] " . Eelis . Consultado el 22 de diciembre de 2024 .
  6. ↑ Josuttis, Nicolai M. (1999). La biblioteca estándar de C++: un tutorial y manual . Addison-Wesley Professional. pág . 547. ISBN  9780201379266.
  7. ^ Vandevoorde, David; Josuttis, Nicolai M. (2002). Plantillas C++: la guía completa . Addison Wesley . ISBN 0-201-73484-2.
  8. ↑ Stepanov, Alexander; Lee, Meng (31 de octubre de 1995). "The Standard Template Library" (PDF) . Recuperado el 16 de diciembre de 2018. La mayoría de las plantillas algorítmicas de la biblioteca que operan sobre 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 de la estructura de datos comenzando con el apuntado por i y hasta, pero sin incluir, el apuntado por j. El rango [i, j) es válido si y solo si j es alcanzable desde i.
  9. ↑ Adrian Stone. "Minimizando la sobrecarga de código: sobreespecialización de plantillas" .
  10. ↑ Meyers, Scott (2005). Effective C++ Third Edition – 55 Specific Ways to Improve Your Designs . Addison Wesley . ISBN  0-321-33487-6.
  11. ↑ Sutter, Herb ; Alexandrescu, Andrei (2004). Estándares de codificación de C++: 101 reglas, directrices y mejores prácticas . Addison-Wesley. ISBN 0-321-11358-6.
  12. ↑ Andrei Alexandrescu (6 de mayo de 2009). "Los iteradores deben irse" (PDF) . BoostCon 2009. Consultado el 19 de marzo de 2011 .
  13. ↑ Matthew Wilson (febrero de 2004). "API de enumeración de devolución de llamada y el concepto de iterador de entrada" . Dr. Dobb's Journal .
  14. ↑ Bjarne Stroustrup (2000). El lenguaje de programación C++ (3.ª ed.). Addison-Wesley. ISBN  0-201-70073-5.: pág. 530
  15. ↑ Más algoritmos STL (revisión 2)
  16. ↑ "Biblioteca estándar de Apache C++" . stdcxx.apache.org . Consultado el 1 de marzo de 2023 .

Referencias

  • Alexander Stepanov y Meng Lee, La biblioteca de plantillas estándar. Informe técnico de HP Laboratories 95-11(R.1), 14 de noviembre de 1995. (Versión revisada de AA Stepanov y M. Lee: La biblioteca de plantillas estándar, Informe técnico X3J16/94-0095, WG21/N0482, Proyecto de lenguaje de programación C++ de la ISO, mayo de 1994).
  • Alexander Stepanov (2007). Notas sobre programación (PDF) .Stepanov reflexiona sobre el diseño del STL.
  • Nicolai M. Josuttis (2000). La biblioteca estándar de C++: un tutorial y una referencia . Addison-Wesley. ISBN 0-201-37926-0.
  • Scott Meyers (2001). Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library . Addison-Wesley. ISBN 0-201-74962-9.
  • Al Stevens (marzo de 1995). "Al Stevens entrevista a Alex Stepanov" . Dr. Dobb's Journal . Consultado el 18 de julio de 2007 .
  • David Vandevoorde y Nicolai M. Josuttis (2002). Plantillas C++: la guía completa . Profesional de Addison-Wesley. ISBN 0-201-73484-2.
  • Atul Saini y David R. Musser (1996). Tutorial y guía de referencia de STL: Programación en C++ con la biblioteca de plantillas estándar. Prólogo de Alexander Stepanov; Copyright Modena Software Inc. Addison-Wesley. ISBN 0-201-63398-1.
  • Referencia de C++
  • Referencia de la STL de C++ , incluye características de C++11.
  • Guía del programador STL de SGI . Originalmente en(contenido retirado).
  • Referencia de clases de la biblioteca estándar de C++ de Apache (anteriormente Rogue Wave)
  • Guía del usuario de la biblioteca estándar de C++ de Apache (anteriormente Rogue Wave)
  • Bjarne Stroustrup sobre el surgimiento de la STL (Página 5, Sección 3.1)
  • Especificación estándar de C++