¿Se garantiza que los elementos std :: vector sean contiguos?

111

Mi pregunta es simple: ¿se garantiza que los elementos std :: vector sean contiguos? En orden, ¿puedo usar el puntero al primer elemento de un std :: vector como una matriz C?

Si mi memoria no me sirve bien, el estándar C ++ no ofrecía tal garantía. 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'
    }
}
Martin Cote
fuente
Sé que estás en problemas si mutas valuesdentro de ese ifbloque. Sin embargo, no sé la respuesta a tu pregunta, así que solo dejo un comentario. :)
Greg D
@Greg: ¿Qué problema? ¿Puedes dar más detalles?
Reunanen
Supongo que quiso decir que presionar nuevos valores puede desencadenar una "reasignación" que haría que la matriz se volviera inválida.
Martin Cote
Las llamadas que mutan values, específicamente las que cambian su tamaño (por ejemplo, push_back()), pueden provocar una reasignación del vector subyacente que invalida el puntero copiado array. Es el mismo principio detrás del uso de un vector :: iterador en lugar de un puntero al vector. :)
Greg D
1
Sí, puse el `` alrededor de los valores para tratar de dejar en claro que estaba hablando de la clase en sí, no de los valores contenidos en ella. :) Nombramientos desafortunados y todo eso. Sin embargo, no creo que sea realmente un problema en el caso general donde esta pregunta es relevante: ¿por qué alguien tomaría un puntero a la memoria y luego comenzaría a jugar con el vector en lugar de usar el puntero? Tontería.
Greg D

Respuestas:

118

Esto se omitió del 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 requisito.

Desde n2798 (borrador de C ++ 0x):

23.2.6 Vector de plantilla de clase [vector]

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

dirkgently
fuente
3
Esto también se establece en ISO 14882, 2da edición: Sección 23.2.4 [lib.vector]: "Los elementos de un vector se almacenan contiguamente, lo que significa que si v es un vector <T, Allocator> donde T es un tipo distinto de bool, entonces obedece a la identidad & v [n] == & v [0] + n para todo 0 <= n <v.size () ".
Mike Caron
4
entonces s, TR, TC, :) En realidad, C ++ 03 también se llama C ++ 98-TC1 (corrección técnica) por lo que leí
Johannes Schaub - litb
2
¿Qué pasa con los vectores de vectores? ¿Los vectores internos están justo después de los vectores internos del último grupo?
huseyin tugrul buyukisik
1
@huseyin tugrul buyukisik ¿aprendiste la respuesta a esto? También me pregunto cómo funciona esto
David Doria
1
@huseyin tugrul buyukisik Por supuesto, es cierto, pero son las instancias posteriores std::vectorlas contiguas. Ej .: en std::vector<std::vector<int>> vlos elementos v[0], v[1], ... posteriormente se almacenan en la memoria, pero el elemento v[0].back()y v[1].front()no se garantiza que sea.
jarzec
27

Como han señalado otras respuestas, se garantiza que el contenido de un vector sea continuo (excepto 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, entonces hará que todos sus punteros e iteradores guardados se invaliden.

Bill Lynch
fuente
1
Los elementos aún se almacenarían en un bloque de memoria contiguo, simplemente estaría en un lugar diferente. La pregunta se refería específicamente a la contigüidad.
Dima
2
Pero los punteros e iteradores existentes quedarían invalidados.
Bill Lynch
Buen punto. Debería poner eso en su respuesta para aclarar lo que quiere decir.
Dima
respuesta más útil para mí
CoffeDeveloper
Ahora sé por qué mi programa estaba fallando ayer, cuando lo recorrí en un bucle doble eliminando ciertos elementos :) ¡Gracias!
user2891462
9

De hecho, el estándar garantiza que a vectorsea ​​continuo en la memoria y que &a[0]se pueda pasar a una Cfunción que espera una matriz.

La excepción a esta regla es vector<bool>que solo usa un bit por bool, por lo tanto, aunque tiene memoria continua, no se puede usar como bool*(esto se considera una optimización falsa y un error).

Por cierto, ¿por qué no usas iteradores? Para eso son.

Motti
fuente
1
> Por cierto, ¿por qué no usas iteradores? Para eso son. Tal vez leyó el nuevo artículo de Alexanrescu sobre el tema: boostcon.com/site-media/var/sphene/sphwiki/attachment/2009/05/…
Nemanja Trifunovic
Gracias por el enlace, iré a mi lista de lectura (trato de no perderme los artículos de Alexandresu)
Motti
Mwahaha, todos parecen estar hablando de esa presentación en estos días. Mira, la discusión todavía está caliente al respecto: groups.google.com/group/comp.lang.c++.moderated/browse_thread/…
Johannes Schaub - litb
Si lo lee con atención, el artículo de Alexandrescu realmente no dice "No use iteradores en C ++", dice "Revise D". El enfoque que describe en ese documento es sorprendentemente similar a cualquier lenguaje y marco existente que haya absorbido la herencia funcional (List, Scheme, Haskell) y dudo seriamente que otra sintaxis basada en C sea un punto de partida ideal para mejorar manejo de listas. En algún momento del año pasado, traté brevemente de persuadirlo para que volviera su considerable talento para mejorar un lenguaje ya establecido como C #, ¡pero me temo que sin éxito! :)
Daniel Earwicker
6

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

¡¡Como sea, hay una excepción!!

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

(Supongo que también es posible que esto sea cierto para cualquier especialización de vector, ya que siempre podemos implementar una nueva. Sin embargo, std::vector<bool>es la única especialización estándar en la que la aritmética de puntero simple no funcionará).

Wuggy
fuente
El usuario no puede especializarse std::vectory todos los demás vectores deben usar almacenamiento contiguo. Por lo tanto, std::vector<bool>es (afortunadamente) el único vector estándar que es extraño. (Soy muy de la opinión de que esta especialización debería ser obsoleta y reemplazada por, por ejemplo, una std::dynamic_bitsetcon la misma funcionalidad. No es una mala estructura de datos, simplemente no es un vector).
Arne Vogel
3

Encontré este hilo porque tengo un caso de uso en el que 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 búfer, por lo que todo lo que necesito hacer es pasar una matriz de flotantes y algunos valores de configuración para crear el búfer. Quiero poder generar un búfer a partir de una función basada en la entrada del usuario, por lo que no se conoce la longitud en el momento de la compilación. Hacer algo como esto sería la solución más sencilla:

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

Ahora puedo pasar los flotantes del vector como una matriz a las 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 matriz enorme para almacenar los flotadores y esperar que sea lo suficientemente grande, o hacer mi propia matriz dinámica con almacenamiento contiguo.

Nadie Importante
fuente
2
esta función no tiene ningún sentido para mí. ¿Quiere usted pasar una referencia o un puntero en vlugar de a vsí mismo? porque pasar vsolo hará que se haga una copia dentro de la función, que dejará de existir después de que finalice la función. Por lo tanto, está presionando algo en el vector solo para eliminar el vector cuando finaliza la función.
johnbakers
1

cplusplus.com:

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

Igor Oks
fuente
1

Sí, se garantiza que los elementos de un std :: vector son contiguos.

Benoît
fuente
Correcto. Supongo que uso demasiado de esos :)
Benoît