Biblioteca de contenedores
La biblioteca de contenedores es una colección genérica de plantillas de clase y algoritmos que permite a los programadores implementar fácilmente estructuras de datos comunes, tales como colas, listas y pilas. Existen tres clases de contenedores--contenedores de secuencias (o secuenciales), contenedores asociativos y contenedores asociativos no ordenados--cada uno de los cuales está diseñado para que apoye un conjunto de operaciones distinto.
El contenedor gestiona el espacio de almacenamiento que se asigna para sus elementos y proporciona funciones miembro para accederlos, ya sea directamente o a través de iteradores (objetos con propiedades similares a los punteros).
La mayoría de los contenedores tienen al menos varias funciones miembro en común y comparten funcionalidad. Qué contenedor es el mejor para la aplicación particular depende no solo de la funcionalidad ofrecida, sino también de su eficiencia para diferentes cargas de trabajo.
Contenido |
[editar] Contenedores de secuencias
Los contenedores de secuencias implementan estructuras de datos que pueden accederse secuencialmente.
| (C++11) |
Array estático contiguo. (plantilla de clase) |
| Array dinámico contiguo. (plantilla de clase) | |
Cola doblemente terminada (deque). (plantilla de clase) | |
| (desde C++11) |
Lista enlazada. (plantilla de clase) |
| Lista doblemente enlazada. (plantilla de clase) |
[editar] Contenedores asociativos
Los contenedores asociativos implementan estructuras de datos ordenadas que se pueden buscar rápidamente (complejidad O(log n)).
| Colección de claves, ordenada por claves, donde las claves son únicas. (plantilla de clase) | |
| Colección de pares de clave y valor, ordenados por claves, donde las claves son únicas. (plantilla de clase) | |
| Colección de claves, ordenada por claves. (plantilla de clase) | |
| Colección de pares de clave y valor, ordenados por claves. (plantilla de clase) |
[editar] Contenedores asociativos no ordenados (desde C++11)
Los contenedores asociativos no ordenados implementan estructuras de datos no ordenadas (dispersas o hashed) que se pueden buscar rápidamente (amortizadas a O(1), con complejidad O(n) en el peor de los casos).
| (desde C++11) |
Colección de claves únicas, dispersas (hashed) por claves. (plantilla de clase) |
| (desde C++11) |
Colección de pares de clave-valor, dispersos (hashed) por claves, donde las claves son únicas. (plantilla de clase) |
| (desde C++11) |
Colección de claves, dispersos (hashed) por claves. (plantilla de clase) |
| (desde C++11) |
Colección de pares de clave-valor, dispersos (hashed) por clave. (plantilla de clase) |
[editar] Adaptadores de contenedores
Los adaptadores de contenedores proporcionan distintas interfaces para contenedores de secuencias.
| Adapta un contenedor para proporcionar una pila (estructura de datos UEPS o LIFO, del ingés last in, first out). (plantilla de clase) | |
| Adapta un contenedor para proporcionar una cola (estructura de datos PEPS o FIFO, del inglés first in, first out). (plantilla de clase) | |
| Adapta un contenedor para proporcionar una cola de prioridad. (plantilla de clase) | |
| (C++23) |
Adapta un contenedor para proporcionar una colección de claves únicas, ordenadas por claves. (plantilla de clase) |
| (C++23) |
Adapta dos contenedores para proporcionar una colección de pares clave-valor, ordenados por claves únicas. (plantilla de clase) |
| (C++23) |
Adapta un contenedor para que proporcione una colección de claves, ordenada por clave. (plantilla de clase) |
| (C++23) |
Adapta dos contenedores para proporcionar una colección de pares clave-valor, ordenados por claves. (plantilla de clase) |
[editar] Vistas
Las vistas proporcionan funciones flexibles para interactuar con vistas unidimensionales o multidimensionales sobre un array de elementos no propios.
| (C++20) |
Una vista que no es dueña sobre una secuencia contigua de objetos. (plantilla de clase) |
| (C++23) |
Una vista no dueña a un array multidimensional. (plantilla de clase) |
[editar] Invalidación de iteradores
Los métodos de solo-lectura nunca invalidan ni iteradores ni referencias. Los métodos que modifican el contenido de un contenedor pueden invalidar iteradores y/o referencias, como se resume en esta tabla.
| Categoría | Contenedor | Después de la inserción... | Después del borrado... | Condicionalmente | ||
|---|---|---|---|---|---|---|
| iteradores son válidos? | referencias son válidas? | iteradores son válidos? | referencias son válidas? | |||
| Contenedores de secuencias | array | N/A | N/A | |||
| vector | No | N/A | Inserción cambió la capacidad | |||
| Sí | Sí | Antes del(de los) elemento(s) modificado(s) | ||||
| No | No | En o después del(de los) elemento(s) modificado(s) | ||||
| deque | No | Sí | Sí, excepto el(los) elemento(s) borrado(s) | Primer o último elemento modificado | ||
| No | No | Solamente intermedio modificado | ||||
| list | Sí | Sí, excepto el(los) elemento(s) borrado(s) | ||||
| forward_list | Sí | Sí, excepto el(los) elemento(s) borrado(s) | ||||
| Contenedores asociativos | set multiset map multimap |
Sí | Sí, excepto el(los) elemento(s) borrado(s) | |||
| Contenedores asociativos no ordenados | unordered_set unordered_multiset unordered_map unordered_multimap |
No | Sí | N/A | Inserción causó redispersión | |
| Sí | Sí, excepto el(los) elemento(s) borrado(s) | No hubo redispersión | ||||
Aquí inserción se refiere a cualquier método que añade uno o más elementos al contenedor y borrado se refiere a cualquier método que elimina uno o más elementos del contenedor.
- Ejemplos de métodos de inserción son std::set::insert, std::map::emplace, std::vector::push_back, y std::deque::push_front.
- Observa que std::unordered_map::operator[] también cuenta, ya que puede insertar un elemento en el mapa.
- Ejemplos de métodos de borrado son std::set::erase, std::vector::pop_back, std::deque::pop_front, y std::map::clear.
-
clearinvalida todos los iteradores y referencias. Como borra todos los elementos, técnicamente cumple con las reglas anteriores.
-
El iterador después del final merece una mención particular. En general este iterador se invalida como si fuese un iterador normal a un elemento no borrado. De esta manera, std::set::end nunca se invalida, std::unordered_set::end solamente se invalida durante la redispersión, y std::vector::end siempre se invalida (ya que siempre está después de los elementos modificados), y así sucesivamente.
Hay una excepción: un borrado que borra el último elemento de una cola doblemente terminada, std::deque, invalida el iterador después del final, aun cuando no es un elemento borrado del contenedor (o un elemento en lo absoluto). Combinado con las reglas generales para iteradores de std::deque iterators, el resultado neto es que la única operación modificante que no invalida a std::deque::end es un borrado que borra el primer elemento, pero no el último.
Seguridad de hilos1) Todas las funciones del contenedor pueden ser llamadas simultáneamente por diferentes hilos en diferentes contenedores. De manera más general, las funciones de la biblioteca estándar de C++ no leen objetos accesibles por otros hilos a menos que esos objetos sean accesibles directa o indirectamente a través de los argumentos de la función, incluido el puntero this.
2) Todas las funciones miembro const pueden ser llamadas simultáneamente por diferentes hilos en el mismo contenedor. Además, las funciones miembro
begin(), end(), rbegin(), rend(), front(), back(), data(), find(), lower_bound(), upper_bound(), equal_range(), at(), y, excepto en contenedores asociativos, operator[], se comportan como const para propósitos de seguridad de hilos (es decir, pueden ser llamadas simultáneamente por diferentes hilos en el mismo contenedor). Más generalmente, las funciones de la biblioteca del estándar de C++ no modifican objetos a menos que esos objetos sean accesibles directa o indirectamente a través de los argumentos no const de la función, incluyendo el puntero this.3) Distintos elementos en el mismo contenedor pueden modificarse simultáneamente por diferentes hilos, excepto para elementos de std::vector<bool> (por ejemplo, un vector de objetos std::future puede estar recibiendo valores de múltiples hilos).
4) Las operaciones de iteradores (p. ej., incrementar un iterador) leen, pero no modifican el contenedor subyacente, y pueden ejecutarse simultáneamente con operaciones sobre otros iteradores en el mismo contenedor con las funciones miembro const, o lecturas de los elementos. Las operaciones de contenedor que invalidan cualquier iterador modifican el contenedor y no pueden ejecutarse simultáneamente con ninguna operación en iteradores existentes, incluso si esos iteradores no están invalidados.
5) Los elementos del mismo contenedor pueden modificarse simultáneamente con aquellas funciones miembro que no están especificadas para acceder a estos elementos. En términos más generales, las funciones de la biblioteca estándar de C++ no leen objetos accesibles indirectamente a través de sus argumentos (incluidos otros elementos de un contenedor), excepto cuando así lo requiera su especificación
6) En cualquier caso, las operaciones de contenedor (así como los algoritmos o cualquier otra función de biblioteca estándar de C++) se pueden paralelizar internamente siempre que esto no cambie los resultados visibles para el usuario (p. ej., std::transform puede ser en paralelo, pero no std::for_each que se especifica para visitar cada elemento de una secuencia en orden
|
(desde C++11) |
[editar] Tabla de funciones miembro
| - Funciones presentes en C++03 | |
| - Funciones presentes desde C++11 | |
| - Funciones presentes desde C++17 | |
| - Funciones presentes desde C++20 | |
| - Funciones presentes desde C++23 |
| Esta sección está incompleta Razón: Add C++26 "color" and fill member/non-member function table for std::inplace_vector |
[editar] Véase también
Requisitos denominados de C++:
- Contenedor
- ContenedorDeSecuencia
- ContenedorContiguo
- ContenedorReversible
- ContenedorAsociativo
- ContenedorConscienteDeAsignador
- ContenedorAsociativoNoOrdenado
| arrays numéricos, máscaras de arrays y secciones de array. (plantilla de clase) | |
| Almacena y manipula secuencias de caracteres. (plantilla de clase) | |
| (C++17) |
Vista sobre cadena de solo lectura. (plantilla de clase) |
