¿Están garantizados los elementos std :: vector contiguos?

Question

Mi pregunta es simple: ¿los elementos std :: vector están garantizados para ser contiguos? En orden palabra, ¿puedo usar el puntero al primer elemento de std :: vector como C-array?

Si mi memoria me sirve, el estándar C++ no garantiza tanto. Sin embargo, los requisitos de std :: vector eran tales que era prácticamente imposible cumplirlos si los elementos no eran contiguos.

¿Alguien puede aclarar esto?

Ejemplo:

std::vector<int> values; 
// ... fill up values 

if(!values.empty()) 
{ 
    int *array = &values[0]; 
    for(int i = 0; i < values.size(); ++i) 
    { 
     int v = array[i]; 
     // do something with 'v' 
    } 
} 

Answer 1

Esto se omitió desde el estándar C++ 98 propiamente dicho, pero luego se agregó como parte de un TR. El próximo estándar C++ 0x por supuesto lo incluirá como un requisito.

De n2798 (proyecto de C++ 0x):

23.2.6 plantilla de clase vector [vector]

1 Un vector es un contenedor de secuencias que soporta iteradores de acceso aleatorio. Además, admite (amortizado) operaciones de inserción y borrado de tiempo constante al final; insertar y borrar en el medio toma tiempo lineal. La administración del almacenamiento se maneja automáticamente, aunque se pueden dar pistas para mejorar la eficiencia. Los elementos de un vector se almacenan contiguamente, lo que significa que si v es un vector donde T es algún otro tipo que bool, entonces obedece a la identidad & v [n] == & v [0] + n para todos 0 < = n < v.size().

Answer 2

Sí, los elementos de un std :: vector están garantizados para ser contiguos.

Answer 3

El estándar de hecho garantiza que un vector es continuo en la memoria y que &a[0] se puede pasar a una función C que espera una matriz.

La excepción a esta regla es vector<bool> que sólo utiliza un bit por lo tanto bool aunque tiene memoria continua no puede ser utilizado como un bool* (esto es ampliamente considerado como una falsa optimización y un error).

Por cierto, ¿por qué no usa iteradores? Para eso están para.

Answer 4

cplusplus.com:

contenedores vector se implementan como matrices dinámicas; Al igual que las matrices normales, los contenedores vectoriales tienen sus elementos almacenados en ubicaciones de almacenamiento contiguas, lo que significa que se puede acceder a sus elementos no solo utilizando iteradores sino también utilizando compensaciones en punteros regulares a los elementos.

Answer 5

Como han señalado otras respuestas, se garantiza que el contenido de un vector será continuo (exceptuando la rareza de bool).

El comentario que quería agregar es que si realiza una inserción o una eliminación en el vector, lo que podría hacer que el vector reasigne su memoria, hará que todos sus punteros e iteradores guardados se invaliden. .

Answer 6

Como ya se ha dicho, vector utiliza internamente una matriz contigua de objetos. Los punteros en esa matriz deben tratarse como no válidos siempre que cualquier función miembro no const se llame IIRC.

Sin embargo, hay una excepción!

vector<bool> tiene una implementación especializada diseñada para ahorrar espacio, por lo que cada bool solo usa un bit. La matriz subyacente no es una matriz contigua de bool y la aritmética de matriz en vector<bool> no funciona como vector<T>.

(supongo que también es posible que esto sea cierto para cualquier especialización de vectores, ya que siempre podemos implementar uno nuevo. Sin embargo, std::vector<bool> es la única especialización estándar sobre la cual la aritmética de punteros simples no funcionará .)

Answer 7

Encontré este hilo porque tengo un caso de uso donde los vectores que usan memoria contigua son una ventaja.

Estoy aprendiendo a usar objetos de búfer de vértice en OpenGL. Creé una clase contenedora para contener la lógica del buffer, así que todo lo que necesito hacer es pasar una matriz de flotantes y algunos valores de configuración para crear el buffer. Quiero poder generar un búfer desde una función basada en la entrada del usuario, por lo que no se conoce la longitud en tiempo de compilación. Hacer algo como esto sería la solución más fácil:

void generate(std::vector<float> v) 
{ 
    float f = generate_next_float(); 
    v.push_back(f); 
} 

Ahora puede pasar flotadores del vector como una matriz de funciones relacionadas con el búfer de OpenGL. Esto también elimina la necesidad de sizeof para determinar la longitud de la matriz.

Esto es mucho mejor que asignar una gran matriz para almacenar los flotadores y esperar que sea lo suficientemente grande, o hacer mi propia matriz dinámica con almacenamiento contiguo.