En informática, los contenedores de secuencia se refieren a un grupo de plantillas de clases de contenedor en la biblioteca estándar del lenguaje de programación C ++ que implementa el almacenamiento de elementos de datos. Al ser plantillas , se pueden utilizar para almacenar elementos arbitrarios, como enteros o clases personalizadas. Una propiedad común de todos los contenedores secuenciales es que se puede acceder a los elementos de forma secuencial. Como todos los demás componentes de biblioteca estándar, residen en el espacio de nombres std .
Los contenedores siguientes se definen en la versión actual de la C ++ estándar: array
, vector
, list
, forward_list
, deque
. Cada uno de estos contenedores implementa diferentes algoritmos para el almacenamiento de datos, lo que significa que tienen diferentes garantías de velocidad para diferentes operaciones: [1]
array
implementa una matriz no redimensionable en tiempo de compilación.vector
implementa una matriz con acceso aleatorio rápido y la capacidad de cambiar el tamaño automáticamente al agregar elementos.deque
implementa una cola de dos extremos con acceso aleatorio comparativamente rápido.list
implementa una lista doblemente enlazada .forward_list
implementa una lista enlazada individualmente .
Dado que cada uno de los contenedores necesita poder copiar sus elementos para que funcione correctamente, el tipo de elementos debe cumplir CopyConstructible
y los Assignable
requisitos. [2] Para un contenedor dado, todos los elementos deben pertenecer al mismo tipo. Por ejemplo, no se pueden almacenar datos en forma de char e int dentro de la misma instancia de contenedor.
Historia
Originalmente, solo vector
, list
y deque
fueron definidos. Hasta la estandarización del lenguaje C ++ en 1998, formaban parte de la biblioteca de plantillas estándar (STL), publicada por SGI .
El array
contenedor apareció al principio en varios libros con varios nombres. Más tarde se incorporó a una biblioteca de Boost y se propuso su inclusión en la biblioteca estándar de C ++. La motivación para la inclusión de array
fue que resuelve dos problemas de la matriz de estilo C: la falta de una interfaz similar a STL y la imposibilidad de copiarse como cualquier otro objeto. Apareció por primera vez en C ++ TR1 y luego se incorporó a C ++ 11 .
El forward_list
contenedor se agregó a C ++ 11 como una alternativa de uso eficiente del espacio list
cuando no se necesita la iteración inversa.
Propiedades
array
, vector
Y deque
todo el apoyo rápido acceso aleatorio a los elementos. list
admite iteración bidireccional, mientras que forward_list
solo admite iteración unidireccional.
array
no admite la inserción o extracción de elementos. vector
admite la inserción o extracción rápida de elementos al final. Cualquier inserción o eliminación de un elemento que no esté al final del vector necesita elementos entre la posición de inserción y el final del vector a copiar. Los iteradores de los elementos afectados quedan así invalidados. De hecho, cualquier inserción puede invalidar potencialmente todos los iteradores. Además, si el almacenamiento asignado en el vector
es demasiado pequeño para insertar elementos, se asigna una nueva matriz, todos los elementos se copian o se mueven a la nueva matriz y la antigua matriz se libera. deque
, list
Y forward_list
todo el apoyo rápida inserción o retirada de elementos en cualquier parte del recipiente. list
y forward_list
conserva la validez de los iteradores en dicha operación, mientras que los deque
invalida todos.
Vector
Los elementos de a vector
se almacenan de forma contigua. [3] Como todas las implementaciones de matrices dinámicas , los vectores tienen poco uso de memoria y una buena localidad de referencia y utilización de caché de datos . A diferencia de otros contenedores STL, como deques y listas , los vectores permiten al usuario indicar una capacidad inicial para el contenedor.
Los vectores permiten el acceso aleatorio ; es decir, se puede hacer referencia a un elemento de un vector de la misma manera que a los elementos de matrices (mediante índices de matriz). Las listas y conjuntos enlazados , por otro lado, no admiten el acceso aleatorio o la aritmética de punteros.
La estructura de datos vectoriales es capaz de asignar rápida y fácilmente la memoria necesaria para el almacenamiento de datos específicos, y puede hacerlo en un tiempo constante amortizado. Esto es particularmente útil para almacenar datos en listas cuya longitud puede no conocerse antes de configurar la lista, pero donde la eliminación (que no sea, quizás, al final) es poco común. Borrar elementos de un vector o incluso borrar el vector por completo no necesariamente libera nada de la memoria asociada con ese elemento.
Capacidad y reasignación
Una implementación de vector típica consiste, internamente, en un puntero a una matriz asignada dinámicamente , [1] y posiblemente miembros de datos que tienen la capacidad y el tamaño del vector. El tamaño del vector se refiere al número real de elementos, mientras que la capacidad se refiere al tamaño de la matriz interna.
Cuando se insertan nuevos elementos, si el nuevo tamaño del vector es mayor que su capacidad, se produce la reasignación . [1] [4] Esto normalmente hace que el vector asigne una nueva región de almacenamiento, mueva los elementos previamente retenidos a la nueva región de almacenamiento y libere la antigua región.
Debido a que las direcciones de los elementos cambian durante este proceso, cualquier referencia o iterador a elementos en el vector se invalida. [5] El uso de una referencia invalidada provoca un comportamiento indefinido .
La operación reserve () se puede utilizar para evitar reasignaciones innecesarias. Después de una llamada a reservar (n), se garantiza que la capacidad del vector sea al menos n. [6]
El vector mantiene un cierto orden de sus elementos, de modo que cuando se inserta un nuevo elemento al principio o en el medio del vector, los elementos subsiguientes se mueven hacia atrás en términos de su operador de asignación o constructor de copia . En consecuencia, las referencias y los iteradores a elementos posteriores al punto de inserción se invalidan. [7]
Los vectores de C ++ no admiten la reasignación de memoria en el lugar, por diseño; es decir, tras la reasignación de un vector, la memoria que tenía siempre se copiará a un nuevo bloque de memoria utilizando el constructor de copia de sus elementos y luego se liberará. Esto es ineficaz para los casos en los que el vector contiene datos antiguos simples y hay espacio contiguo adicional más allá del bloque de memoria retenido disponible para asignación.
Especialización en bool
La biblioteca estándar define una especialización de la vector
plantilla para bool
. La descripción de esta especialización indica que la implementación debe empaquetar los elementos para que cada bool
uno solo use un bit de memoria. [8] En general, esto se considera un error. [9] [10] vector
no cumple los requisitos para un contenedor de biblioteca estándar de C ++ . Por ejemplo, un container
debe ser un verdadero lvalue de tipo T
. Este no es el caso de vector
, que es una clase de proxy convertible a bool
. [11] De manera similar, vector
no produce a bool&
cuando se desreferencia . Existe un consenso general entre el Comité de Estándares de C ++ y el Grupo de Trabajo de Bibliotecas que vector
debería ser obsoleto y posteriormente eliminado de la biblioteca estándar, mientras que la funcionalidad se reintroducirá con un nombre diferente. [12]
Lista
La list
estructura de datos implementa una lista doblemente enlazada . Los datos se almacenan de forma no contigua en la memoria, lo que permite que la estructura de datos de la lista evite la reasignación de memoria que puede ser necesaria con vectores cuando se insertan nuevos elementos en la lista.
La estructura de datos de la lista asigna y desasigna memoria según sea necesario; por lo tanto, no asigna memoria que no esté usando actualmente. La memoria se libera cuando se elimina un elemento de la lista.
Las listas son eficientes al insertar nuevos elementos en la lista; esto es unoperación. No se requiere desplazamiento como con los vectores.
Las listas no tienen la capacidad de acceso aleatorio como los vectores (operación). Acceder a un nodo en una lista es una operación que requiere un recorrido de lista para encontrar el nodo al que se debe acceder.
Con tipos de datos pequeños (como ints), la sobrecarga de memoria es mucho más significativa que la de un vector. Cada nodo ocupa . Los punteros suelen ser de una palabra (normalmente cuatro bytes en sistemas operativos de 32 bits), lo que significa que una lista de enteros de cuatro bytes ocupa aproximadamente tres veces más memoria que un vector de números enteros.sizeof(type) + 2 * sizeof(type*)
Lista de reenvío
La forward_list
estructura de datos implementa una lista enlazada individualmente .
Deque
deque
es una plantilla de clase de contenedor que implementa una cola de dos extremos . Proporciona una complejidad computacional similar a la vector
de la mayoría de las operaciones, con la notable excepción de que proporciona inserción y eliminación amortizadas en tiempo constante de ambos extremos de la secuencia de elementos. A diferencia vector
, deque
utiliza bloques de memoria no contiguos y no proporciona ningún medio para controlar la capacidad del contenedor y el momento de reasignación de la memoria. Like vector
, deque
ofrece soporte para iteradores de acceso aleatorio , y la inserción y eliminación de elementos invalida todos los iteradores de la deque.
Formación
array
implementa una matriz no redimensionable . El tamaño se determina en tiempo de compilación mediante un parámetro de plantilla. Por diseño, el contenedor no admite asignadores porque es básicamente un contenedor de matriz de estilo C.
Resumen de funciones
Los contenedores se definen en encabezados nombrados después de los nombres de los contenedores, por ejemplo, vector
se define en el encabezado
. Todos los recipientes cumplen los requisitos de la Container concepto , que significa que tienen begin()
, end()
, size()
, max_size()
, empty()
, y swap()
métodos.
Funciones de los miembros
Funciones | array ( C ++ 11 ) | vector | deque | list | forward_list ( C ++ 11 ) | Descripción |
---|---|---|---|---|---|---|
Lo esencial | (implícito) | (constructor) | (constructor) | (constructor) | (constructor) | Construye el contenedor a partir de una variedad de fuentes. |
(incinerador de basuras) | (incinerador de basuras) | (incinerador de basuras) | (incinerador de basuras) | Destruye el contenedor y los elementos contenidos | ||
operator= | operator= | operator= | operator= | Asigna valores al contenedor | ||
N / A | assign | assign | assign | assign | Asigna valores al contenedor | |
Asignadores | get_allocator | get_allocator | get_allocator | get_allocator | Devuelve el asignador utilizado para asignar memoria para los elementos. | |
Acceso a elementos | at | at | at | N / A | N / A | Accede al elemento especificado con comprobación de límites. |
operator[] | operator[] | operator[] | Accede al elemento especificado sin comprobar los límites. | |||
front | front | front | front | front | Accede al primer elemento | |
back | back | back | back | N / A | Accede al último elemento | |
data | data | N / A | N / A | Accede a la matriz subyacente | ||
Iteradores | begincbegin | begincbegin | begincbegin | begincbegin | begincbegin | Devuelve un iterador al comienzo del contenedor. |
endcend | endcend | endcend | endcend | endcend | Devuelve un iterador al final del contenedor. | |
rbegincrbegin | rbegincrbegin | rbegincrbegin | rbegincrbegin | N / A | Devuelve un iterador inverso al principio inverso del contenedor. | |
rendcrend | rendcrend | rendcrend | rendcrend | Devuelve un iterador inverso al final inverso del contenedor | ||
Capacidad | empty | empty | empty | empty | empty | Comprueba si el contenedor está vacío |
size | size | size | size | N / A | Devuelve el número de elementos del contenedor. | |
max_size | max_size | max_size | max_size | max_size | Devuelve el número máximo posible de elementos en el contenedor. | |
N / A | reserve | N / A | N / A | N / A | Reserva de almacenamiento en el contenedor. | |
capacity | Devuelve el número de elementos que se pueden almacenar en el almacenamiento asignado actualmente. | |||||
shrink_to_fit | shrink_to_fit | Reduce el uso de memoria al liberar memoria no utilizada ( C ++ 11 ) | ||||
Modificadores | clear | clear | clear | clear | Borra el contenido | |
insert | insert | insert | N / A | Inserta elementos | ||
emplace | emplace | emplace | Construye elementos in situ ( C ++ 11 ) | |||
erase | erase | erase | Borra elementos | |||
N / A | push_front | push_front | push_front | Inserta elementos al principio | ||
emplace_front | emplace_front | emplace_front | Construye elementos in situ al principio ( C ++ 11 ) | |||
pop_front | pop_front | pop_front | Elimina el primer elemento | |||
push_back | push_back | push_back | N / A | Inserta elementos hasta el final | ||
emplace_back | emplace_back | emplace_back | Construye elementos in situ al final ( C ++ 11 ) | |||
pop_back | pop_back | pop_back | Elimina el último elemento | |||
N / A | N / A | N / A | insert_after | Inserta elementos después de la posición especificada ( C ++ 11 ) | ||
emplace_after | Construye elementos en el lugar después de la posición especificada ( C ++ 11 ) | |||||
erase_after | Borra elementos en el lugar después de la posición especificada ( C ++ 11 ) | |||||
resize | resize | resize | resize | Cambia el número de elementos almacenados | ||
swap | swap | swap | swap | swap | Intercambia el contenido con otro recipiente del mismo tipo | |
fill | N / A | N / A | N / A | N / A | Llena la matriz con el valor dado |
Hay otras operaciones que están disponibles como parte de la clase de lista y hay algoritmos que son parte de C ++ STL ( Algoritmo (C ++) ) que se pueden usar con la clase list
y forward_list
:
Operaciones
list::merge
yforward_list::merge
- Fusiona dos listas ordenadaslist::splice
yforward_list::splice_after
- Mueve elementos de otra listalist::remove
yforward_list::remove
- Elimina elementos iguales al valor dadolist::remove_if
yforward_list::remove_if
- Elimina elementos que satisfacen criterios específicos.list::reverse
yforward_list::reverse
- Invierte el orden de los elementos.list::unique
yforward_list::unique
- Elimina elementos duplicados consecutivoslist::sort
yforward_list::sort
- Ordena los elementos
Funciones no miembros
Ejemplo de uso
El siguiente ejemplo demuestra varias técnicas que involucran un vector y algoritmos de la biblioteca estándar de C ++ , en particular, mezclar , ordenar , encontrar el elemento más grande y borrar de un vector usando el lenguaje borrar-eliminar .
#include #include #include #include // sort, max_element, random_shuffle, remove_if, lower_bound#include // mayor#include // inicio, fin, cbegin, cend, distancia// usado aquí por conveniencia, utilícelo con prudencia en programas reales. usando el espacio de nombres std ;int principal () { array arr { 1 , 2 , 3 , 4 }; // inicializar un vector de un vector de matriz < int > numeros ( cbegin ( arr ), cend ( arr )); // inserta más números en los números vectoriales . retroceso ( 5 ); números . retroceso ( 6 ); números . retroceso ( 7 ); números . retroceso ( 8 ); // el vector contiene actualmente {1, 2, 3, 4, 5, 6, 7, 8} // mezcla aleatoriamente los elementos shuffle ( begin ( numbers ), end ( numbers )); // localizar el elemento más grande, O (n) de automóviles más grandes = max_element ( cbegin ( números ), CEND ( números )); cout << "El número más grande es" << * más grande << " \ n " ; cout << "Se encuentra en el índice" << distancia ( mayor , cbegin ( números )) << " \ n " ; // ordenar los elementos sort ( begin ( numbers ), end ( numbers )); // encuentra la posición del número 5 en el vector auto five = lower_bound ( cbegin ( números ), cend ( números ), 5 ); cout << "El número 5 se encuentra en el índice" << distancia ( cinco , cbegin ( números )) << '\ n ' ; // borra todos los elementos mayores de 4 números . borrar ( eliminar_si ( inicio ( números ), final ( números ), [] ( auto n ) constexpr { retorno n > 4 ; }); // imprime todos los números restantes para ( const auto & element : numbers ) cout << element << "" ; }
La salida será la siguiente:
El número más grande es 8Se encuentra en el índice 6 (dependiente de la implementación).El número 5 se encuentra en el índice 41 2 3 4
Referencias
- William Ford, William Topp. Estructuras de datos con C ++ y STL , segunda edición. Prentice Hall, 2002. ISBN 0-13-085850-1 . Capítulo 4: La clase de vectores, págs. 195-203.
- Josuttis, Nicolai M. (1999). La biblioteca estándar de C ++ . Addison-Wesley. ISBN 0-201-37926-0.
Notas
- ^ a b c Josuttis, Nicolai (1999). Biblioteca estándar de C ++: tutorial y referencia . Addison-Wesley.
- ^ ISO / IEC (2003). ISO / IEC 14882: 2003 (E): Lenguajes de programación - C ++ §23.1 Requisitos del contenedor [lib.container.requirements] párr. 4
- ^ ISO / IEC (2003). ISO / IEC 14882: 2003 (E): Lenguajes de programación - C ++ §23.2.4 Vector de plantilla de clase [lib.vector] párr. 1
- ^ ISO / IEC (2003). ISO / IEC 14882: 2003 (E): Lenguajes de programación - Modificadores de vector C ++ §23.2.4.3 [lib.vector.modifiers] párr. 1
- ^ ISO / IEC (2003). ISO / IEC 14882: 2003 (E): Lenguajes de programación - C ++ §23.2.4.2 capacidad vectorial [lib.vector.capacity] párr. 5
- ^ ISO / IEC (2003). ISO / IEC 14882: 2003 (E): Lenguajes de programación - C ++ §23.2.4.2 capacidad vectorial [lib.vector.capacity] párr. 2
- ^ ISO / IEC (2003). ISO / IEC 14882: 2003 (E): Lenguajes de programación - Modificadores de vector C ++ §23.2.4.3 [lib.vector.modifiers] párr. 3
- ^ ISO / IEC (2003). ISO / IEC 14882: 2003 (E): Lenguajes de programación - C ++ §23.2.5 Vector de clase
[lib.vector.bool] párr. 1 - ^ "vector : Más problemas, mejores soluciones" (PDF) . Agosto de 1999 . Consultado el 28 de noviembre de 2017 .
- ^ "Una especificación para desaprobar el vector " . Marzo de 2007 . Consultado el 28 de noviembre de 2017 .
- ^ ISO / IEC (2003). ISO / IEC 14882: 2003 (E): Lenguajes de programación - C ++ §23.2.5 Vector de clase
[lib.vector.bool] párr. 2 - ^ "96. Vector no es un contenedor" . Consultado el 28 de junio de 2018 .