Biblioteca de plantillas estándar
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 9 de agosto de 2022; la verificación requiere 1 edición .La Biblioteca de plantillas estándar (STL) ( Biblioteca de plantillas estándar en inglés ) es un conjunto de algoritmos genéricos consistentes , contenedores , medios para acceder a sus contenidos y varias funciones auxiliares en C++ .
La biblioteca de plantillas estándar, antes de incluirse en el estándar C++ , fue un desarrollo de terceros, primero de HP y luego de SGI . El lenguaje estándar no lo llama "STL" ya que esta biblioteca se ha convertido en una parte integral del lenguaje, sin embargo, muchas personas aún usan este nombre para distinguirlo del resto de la biblioteca estándar (I/O streams ( iostream ), el inciso C , etc.).
Un proyecto llamado STLPort , basado en SGI STL, mantiene actualizadas las clases STL, iostream y string. Varios otros proyectos también están desarrollando usos privados de la biblioteca estándar para diversas tareas de diseño. Todos los fabricantes de compiladores de C++ deben proporcionar alguna implementación de esta biblioteca, ya que es una parte muy importante del estándar y se usa ampliamente.
La arquitectura STL fue diseñada por Alexander Stepanov y Meng Li.
Estructura de la biblioteca
La biblioteca tiene cinco componentes principales:
- Contenedor ( contenedor inglés ) - almacenamiento de un conjunto de objetos en la memoria.
- Iterador ( iterador en inglés ) - proporciona medios de acceso al contenido del contenedor.
- Un algoritmo es una definición de un procedimiento computacional.
- Adaptador ( adaptador en inglés ): adaptación de componentes para proporcionar una interfaz diferente.
- Objeto funcional ( functor en inglés ): ocultar una función en un objeto para que la usen otros componentes.
La separación le permite reducir el número de componentes. Por ejemplo, en lugar de escribir una función de búsqueda de elementos independiente para cada tipo de contenedor, se proporciona una única versión que funciona con cada uno de ellos, siempre que se cumplan los requisitos básicos.
Contenedores
Los contenedores STL se pueden dividir en cuatro categorías: secuenciales, asociativos, adaptadores y pseudocontenedores.
| Envase | Descripción |
|---|---|
| Contenedores secuenciales | |
| vectores [1] | Matriz dinámica de acceso aleatorio tipo C con cambio de tamaño automático cuando se agrega/elimina un elemento. Acceso por índice para . Agregar/eliminar un elemento al final de un vector toma tiempo amortizado, la misma operación al principio o en medio de un vector toma . Clasificación rápida estándar para . La búsqueda de un elemento por iteración requiere . Existe una especialización de la plantilla vectorial para el tipo bool , que requiere menos memoria al almacenar elementos como bits, pero no admite todas las características de los iteradores. |
| lista [2] | Una lista doblemente enlazada cuyos elementos se almacenan en fragmentos arbitrarios de memoria, a diferencia de un contenedor de vectores donde los elementos se almacenan en un área de memoria contigua. La búsqueda por enumeración es más lenta que la de un vector debido al mayor tiempo de acceso a los elementos. Acceso por índice para . En cualquier lugar del contenedor, la inserción y la eliminación son muy rápidas: en . |
| cubierta [3] | Cola de doble cara . Un contenedor es como un vector, pero con la capacidad de insertar y quitar elementos rápidamente en ambos extremos en . Implementado como una lista doblemente enlazada de matrices lineales . Por otro lado, a diferencia de un vector, un deque no garantiza que todos sus elementos se ubicarán en la memoria contigua , lo que hace imposible usar con seguridad la aritmética de punteros [4] para acceder a los elementos de un contenedor [5] [6] . |
| Contenedores asociativos | |
| establecer | Un conjunto ordenado de elementos únicos. Al insertar/eliminar elementos de un conjunto, los iteradores que apuntan a elementos de este conjunto no se vuelven inválidos. Proporciona operaciones estándar en conjuntos como unión, intersección, resta. El tipo de elemento del conjunto debe implementar un operador de comparación operator<o se debe proporcionar una función de comparación. Implementado sobre la base de un árbol de búsqueda binario autoequilibrado . |
| multiconjunto | Igual que el conjunto, pero le permite almacenar elementos duplicados. |
| mapa | Una matriz asociativa ordenada de pares de elementos que consta de claves y sus valores correspondientes. Las claves deben ser únicas. El orden de los elementos está determinado por las claves. En este caso, el tipo de clave debe implementar el operador operator<de comparación o debe proporcionar una función de comparación. |
| multimapa | Igual que el mapa, pero le permite almacenar varias claves idénticas. |
| Contenedores adaptadores | |
| pila | Una pila es un contenedor en el que se agregan y eliminan elementos de un extremo. |
| cola | Una cola es un contenedor, desde un extremo del cual puede agregar elementos y desde el otro, sacarlos. |
| prioridad_cola | Una cola de prioridad organizada para que el elemento más grande siempre sea el primero. |
| pseudo contenedores | |
| conjunto de bits | Se utiliza para almacenar máscaras de bits. Parece un vector<bool>tamaño fijo. El tamaño se fija cuando se declara el objeto de conjunto de bits. No hay iteradores en el conjunto de bits. Optimizado para el tamaño de la memoria. |
| cadena_básica | Un contenedor para almacenar y procesar cadenas. Almacena elementos en una fila en la memoria como un solo bloque, lo que le permite organizar un acceso rápido a toda la secuencia. Los artículos deben ser POD . La concatenación se define con +. |
| valerray | La plantilla se utiliza para almacenar matrices numéricas y está optimizada para lograr un mayor rendimiento computacional. Algo similar a vector, pero carece de la mayoría de las operaciones de contenedor estándar. Las operaciones se definen en dos valarrays y en un valarray y un escalar (element-sabio). Estas operaciones se pueden implementar de manera efectiva tanto en procesadores vectoriales como en procesadores escalares con bloques SIMD . |
Los contenedores usan semántica de objeto por valor para almacenar elementos. En otras palabras, cuando se agrega, el contenedor obtiene una copia del elemento. Si no se desea realizar una copia, se utiliza un contenedor de punteros de elementos. Los elementos se asignan mediante el operador de asignación y se destruyen mediante el destructor. La tabla muestra los requisitos básicos para elementos en contenedores:
| Método | Descripción | Nota |
|---|---|---|
| copiar constructor | Crea un nuevo elemento idéntico al anterior. | Se utiliza cada vez que se inserta un elemento en un contenedor. |
| operador de asignación | Reemplaza el contenido de un elemento con una copia del elemento original | Se utiliza cada vez que se modifica el elemento. |
| Incinerador de basuras | Destruye el elemento | Se utiliza cada vez que se elimina un elemento. |
| Constructor predeterminado | Crea un elemento sin argumentos. | Se aplica solo a ciertas operaciones. |
| operador == | Compara dos elementos | Se usa cuando se hace operator== en dos contenedores |
| operador< | Determina si un elemento es menor que otro | Se usa al ejecutar operator< en dos contenedores |
Todos los contenedores estándar "llenos" cumplen un cierto conjunto de requisitos (o convenciones). La siguiente tabla asume que C es una clase contenedora que contiene objetos de tipo T.
| Expresión | tipo de retorno | Complejidad | Nota |
|---|---|---|---|
| C::tipo_valor | T | Tiempo de compilación | |
| C::referencia | T | Tiempo de compilación | |
| C::const_referencia | Tiempo de compilación | ||
| C::puntero | Tipo de puntero que apunta a C::reference | Tiempo de compilación | Puntero a T |
| C::iterador | Tipo de iterador que apunta a C::reference | Tiempo de compilación | Un iterador de cualquier tipo que no sea un iterador de salida |
| C::const_iterador | Tipo de iterador que apunta a C::const_reference | Tiempo de compilación | Un iterador de cualquier tipo que no sea un iterador de salida |
| C::tamaño_tipo | tipo entero sin signo | Tiempo de compilación | |
| Cobj; | Constante | Después: obj.tamaño() == 0 | |
| Cobj1; obj1 = obj2; | Lineal | Después: obj1 == obj2 | |
| Cobj; (&obj)->~C(); | Resultado no utilizado | Lineal | Después: obj.size() == 0. |
| obj.begin() | Constante | ||
| obj.fin() | Constante | ||
| obj1 == obj2 | Reversible a booleano | Lineal | |
| obj1 != obj2 | Reversible a booleano | Lineal | |
| obj.tamaño() | tipo de letra | Depende del tipo | No recomendado para verificar si un contenedor está vacío |
| objeto.vacío() | Reversible a booleano | Constante | |
| objeto1 < objeto2 | Reversible a booleano | Lineal | |
| obj1 > obj2 | Reversible a booleano | Lineal | |
| obj1 <= obj2 | Reversible a booleano | Lineal | |
| obj1 >= obj2 | Reversible a booleano | Lineal | |
| obj.intercambiar(obj2) | vacío | Constante |
Iteradores
La biblioteca STL utiliza una abstracción generalizada llamada iterador como intermediario para acceder a los elementos . Cada contenedor mantiene "su propio" tipo de iterador, que es un puntero inteligente "modernizado" [7] que "sabe" cómo acceder a los elementos de un contenedor en particular. El estándar C++ define cinco categorías de iteradores, que se describen en la siguiente tabla:
| Categoría | Operaciones admitidas | Nota |
|---|---|---|
| Aporte | operator++, operator*, operator->, copy constructor, operator=, operator==, operator!= | Proporciona acceso de lectura en una dirección. Le permite realizar una asignación o copia utilizando el operador de asignación y el constructor de copia. |
| fines de semana | operador++, operador*, constructor de copias | Proporciona acceso de escritura en una dirección. No se pueden comparar por igualdad. |
| unidireccional | operator++, operator*, operator->, copy constructor, default constructor, operator=, operator==, operator!= | Proporciona acceso de lectura y escritura en la misma dirección. Le permite realizar una asignación o copia utilizando el operador de asignación y el constructor de copia. Se pueden comparar por igualdad. |
| Bidireccional | operator++, operator--, operator*, operator->, copy constructor, default constructor, operator=, operator==, operator!= | Admite todas las funciones descritas para los iteradores unidireccionales (ver arriba). Además, te permiten navegar al elemento anterior. |
| acceso aleatorio | operator++, operator--, operator*, operator->, copy constructor, default constructor, operator=, operator==, operator!=, operator+, operator-, operator+=, operator-=, operator<, operator>, operator < =, operador>=, operador[] | Equivalente a los punteros normales: admite aritmética de punteros, sintaxis de indexación de matrices y todas las formas de comparación. |
Véase también
Notas
- ↑ estándar::vector . Fecha de acceso: 14 de febrero de 2016. Archivado desde el original el 27 de noviembre de 2015.
- ↑ estándar: lista
- ↑ std::deque . Consultado el 14 de febrero de 2016. Archivado desde el original el 5 de febrero de 2016.
- ↑ Sintaxis de punteros en C++ . Consultado el 14 de febrero de 2016. Archivado desde el original el 11 de marzo de 2016.
- ↑ Biblioteca de iteradores (enlace descendente) . Consultado el 14 de febrero de 2016. Archivado desde el original el 5 de febrero de 2016.
- ↑ Conceptos de C++: iterador . Consultado el 14 de febrero de 2016. Archivado desde el original el 19 de febrero de 2016.
- ↑ Tipos de iterador: Salida vs. entrada contra adelante contra Iterador de acceso aleatorio . Consultado el 14 de febrero de 2016. Archivado desde el original el 23 de febrero de 2016.
Enlaces
- Fuente de referencia de métodos y clases SGI STL
- STL paso a paso (rus.) - artículos de Artem Kaev
- Fundamentos de C++. Biblioteca STL Archivado el 27 de febrero de 2007 en Wayback Machine (ruso) - archivo de lista de correo
- STL - Biblioteca de plantillas estándar. Guía del programador de C++ (rus.) - guía detallada
- Usando STL en C++ (ruso)
Literatura
- Scott Meyers. Uso efectivo de STL = STL efectivo. - Pedro, 2002. - S. 224 . — (Biblioteca del programador). — ISBN 5-94723-382-7 .
- David R. Musser, Gilmer J. Durge, Atul Seini. C++ y STL: Guía de referencia = Guía de referencia y tutorial de STL: Programación en C++ con la plantilla estándar. — 2ª edición. - M. : "Williams" , 2010. - S. 432. - (Serie C++ en Profundidad). — ISBN 5-89818-027-3 .
- Leen Ammeraal. STL para programadores de C++ = STL para programadores de C++. - DMK Press, 1999. - Pág. 240. - ISBN 5-256-00704-1 .
| C++ | |
|---|---|
| Peculiaridades | |
| algunas bibliotecas | |
| compiladores | |
| influenciado | |
| |