std :: vector versus std :: array en C ++

¿Cuál es la diferencia entre a std::vectory an std::arrayen C ++? ¿Cuándo se debe preferir uno sobre otro? ¿Cuáles son los pros y los contras de cada uno? Todo lo que mi libro de texto hace es enumerar cómo son iguales.

std::vectores una clase de plantilla que encapsula una matriz dinámica ¹ , almacenada en el montón, que crece y se reduce automáticamente si se agregan o eliminan elementos. Proporciona todos los ganchos ( begin(), end()iteradores, etc.) que hacen que funcione bien con el resto del STL. También tiene varios métodos útiles que le permiten realizar operaciones que en una matriz normal serían engorrosas, como, por ejemplo, insertar elementos en el medio de un vector (maneja todo el trabajo de mover los siguientes elementos detrás de escena).

Como almacena los elementos en la memoria asignada en el montón, tiene algo de sobrecarga con respecto a las matrices estáticas.

std::arrayes una clase de plantilla que encapsula una matriz de tamaño estático, almacenada dentro del propio objeto, lo que significa que, si crea una instancia de la clase en la pila, la matriz misma estará en la pila. Su tamaño debe conocerse en el momento de la compilación (se pasa como un parámetro de plantilla) y no puede crecer ni reducirse.

Es más limitado que std::vector, pero a menudo es más eficiente, especialmente para tamaños pequeños, porque en la práctica es principalmente un envoltorio liviano alrededor de una matriz de estilo C. Sin embargo, es más seguro, ya que la conversión implícita a puntero está deshabilitada, y proporciona gran parte de la funcionalidad relacionada con STL de std::vectory de los otros contenedores, por lo que puede usarla fácilmente con algoritmos STL & co. De todos modos, por la limitación del tamaño fijo, es mucho menos flexible que std::vector.

Para una introducción a std::array, eche un vistazo a este artículo ; para una introducción rápida a std::vectorlas operaciones que son posibles en él, puede consultar su documentación .

1. En realidad, creo que en el estándar se describen en términos de máxima complejidad de las diferentes operaciones (por ejemplo, acceso aleatorio en tiempo constante, iteración sobre todos los elementos en tiempo lineal, adición y eliminación de elementos al final en tiempo amortizado constante, etc.), pero AFAIK no hay otro método para cumplir tales requisitos que no sea el uso de una matriz dinámica. Según lo indicado por @Lucretiel, el estándar realmente requiere que los elementos se almacenen contiguamente, por lo que es una matriz dinámica, almacenada donde el asignador asociado lo coloca.

Usando la std::vector<T>clase:

• ... es tan rápido como usar matrices integradas, suponiendo que solo está haciendo lo que las matrices integradas le permiten hacer (leer y escribir en elementos existentes).

• ... cambia automáticamente de tamaño cuando se insertan nuevos elementos.

• ... le permite insertar nuevos elementos al principio o en el medio del vector, "desplazando" automáticamente el resto de los elementos "hacia arriba" (¿tiene sentido?). También le permite eliminar elementos en cualquier parte del std::vector, desplazando automáticamente el resto de los elementos hacia abajo.

• ... le permite realizar una lectura de verificación de rango con el at()método (siempre puede usar los indexadores []si no desea que se realice esta verificación).

Hay dos tres advertencias principales para usar std::vector<T>:

1. No tiene acceso confiable al puntero subyacente, lo que puede ser un problema si se trata de funciones de terceros que exigen la dirección de una matriz.

2. La std::vector<bool>clase es tonta. Se implementa como un campo de bits condensado, no como una matriz. ¡Evítalo si quieres una variedad de bools!

3. Durante el uso, los std::vector<T>s serán un poco más grandes que una matriz C ++ con el mismo número de elementos. Esto se debe a que necesitan realizar un seguimiento de una pequeña cantidad de otra información, como su tamaño actual, y porque cada vez que std::vector<T>cambian el tamaño, reservan más espacio del que necesitan. Esto es para evitar que tengan que cambiar el tamaño cada vez que se inserta un nuevo elemento. Este comportamiento se puede cambiar proporcionando una costumbre allocator, ¡pero nunca sentí la necesidad de hacerlo!

Editar: Después de leer la respuesta de Zud a la pregunta, sentí que debería agregar esto:

La std::array<T>clase no es lo mismo que una matriz de C ++. std::array<T>es una envoltura muy delgada alrededor de las matrices de C ++, con el objetivo principal de ocultar el puntero al usuario de la clase (en C ++, las matrices se convierten implícitamente en punteros, a menudo con un efecto desalentador). La std::array<T>clase también almacena su tamaño (longitud), que puede ser muy útil.

Para enfatizar un punto hecho por @MatteoItalia, la diferencia de eficiencia es donde se almacenan los datos. La memoria de almacenamiento dinámico (requerida con vector) requiere una llamada al sistema para asignar memoria y esto puede ser costoso si está contando ciclos. La memoria de la pila (posible para array) es prácticamente "cero sobrecarga" en términos de tiempo, porque la memoria se asigna simplemente ajustando el puntero de la pila y se realiza solo una vez al ingresar a una función. La pila también evita la fragmentación de la memoria. Para estar seguro, std::arrayno siempre será en la pila; depende de dónde lo asigne, pero aún implicará una asignación de memoria menos del montón en comparación con el vector. Si tienes un

• "matriz" pequeña (por ejemplo, menos de 100 elementos) - (una pila típica es de aproximadamente 8 MB, así que no asigne más de unos pocos KB en la pila o menos si su código es recursivo)
• el tamaño será fijo
• la duración está en el alcance de la función (o es un valor de miembro con la misma duración que la clase principal)
• estás contando ciclos,

Definitivamente use un std::arraysobre un vector. Si alguno de esos requisitos no es cierto, utilice a std::vector.

Si está considerando usar matrices multidimensionales, entonces hay una diferencia adicional entre std :: array y std :: vector. Un std :: array multidimensional tendrá los elementos empaquetados en la memoria en todas las dimensiones, tal como lo es el array de estilo ac. Un std :: vector multidimensional no se empaquetará en todas las dimensiones.

Dadas las siguientes declaraciones:

int cConc[3][5];
std::array<std::array<int, 5>, 3> aConc;
int **ptrConc;      // initialized to [3][5] via new and destructed via delete
std::vector<std::vector<int>> vConc;    // initialized to [3][5]

Un puntero al primer elemento en la matriz de estilo c (cConc) o std :: array (aConc) se puede iterar a través de toda la matriz agregando 1 a cada elemento precedente. Están bien embalados.

Un puntero al primer elemento en la matriz de vectores (vConc) o la matriz de punteros (ptrConc) solo puede iterarse a través de los primeros 5 elementos (en este caso), y luego hay 12 bytes (en mi sistema) de sobrecarga para el siguiente vector

Esto significa que una matriz std :: vector> inicializada como una matriz [3] [1000] será mucho más pequeña en la memoria que una inicializada como una matriz [1000] [3], y ambas serán más grandes en la memoria que una std: matriz asignada de cualquier manera.

Esto también significa que no puede simplemente pasar una matriz de vectores (o punteros) multidimensionales a, por ejemplo, openGL sin tener en cuenta la sobrecarga de memoria, sino que ingenuamente puede pasar una std :: array multidimensional a openGL y hacer que funcione.

Un vector es una clase contenedor mientras que una matriz es una memoria asignada.