std :: vector de std :: vectores de contigüidad

Question

Sé que std::vector<T> almacena internamente los datos de forma contigua (a menos que sea std::vector<bool>) tanto en el antiguo C++03 estándar y el nuevo C++11.

Nice stackoverflow preguntas que tratan con esto y citan el estándar: answer, answer.

¿Qué pasa con los datos dentro de los vectores anidados std::vector <std::vector <T> >? ¿Cómo se almacena eso?

Si cada vector interno necesita almacenar sus datos de forma contigua, ¿cómo puede ser cierto que &v[n] == &v[0] + n for all 0 <= n < v.size().

Para frase esta ligeramente diferentes, es posible el acceso a todos los elementos almacenado en tal estructura anidada "simplemente" y secuencialmente (a través de un puntero o similar) de la misma manera que se puede hacer para un vector 1-D ?

Answer 1

No. Los elementos de un vector se almacenan en un bloque de memoria asignado dinámicamente; de lo contrario, la capacidad del vector no podría aumentar. El objeto vector solo tiene un puntero a ese bloque.

El requisito de que los elementos se almacenen de forma secuencial se aplica solo a los elementos mismos, y no a los miembros dinámicamente asignados de esos elementos.

Answer 2

std::vector< std::vector<T> > es un vector de objetos, que se almacenan en bloques contiguos de memoria. El hecho de que estos objetos sean vectores también es irrelevante.

Aunque los elementos del vector se almacenan en el bloque contiguo de la memoria, la memoria donde residen los elementos no es la parte del objeto vectorial en sí.

"¿es posible acceder a todos los elementos almacenados en dicha estructura anidada" simplemente "y secuencialmente (mediante un puntero o similar) de la misma manera que se puede hacer para un vector 1-D?"
Para acceder a los elementos de std::vector, es mejor utilizar el método operator[] o at() que recuperar la dirección del primer elemento y usar la aritmética del puntero. Para matrices multidimensionales representadas como vectores de vectores, le sugiero que se quede con operator[], que es fácil de usar y fácil de leer: myVector[i][j]. Vale la pena ver también vector::at vs. vector::operator[] :)

Answer 3

Para responder a su pregunta final: No. Los elementos de un vector de vectores no se almacenan contiguamente.

Considere el siguiente código:

std::vector<std::vector<int> > vv; 
.... fill in v[0], v[1], v[2], etc 
std::vector <int> & v = vv[1]; 
v.push_back (23); 

Si se almacenan de forma contigua, entonces esto haría que cada elemento en los vv [2], vv [3], etc para moverse. ¿Cómo funcionaría eso, ya que solo estás afectando a un único vector 'v'?

Answer 4

¿es posible acceder a todos los elementos almacenados en dicha estructura anidada "simplemente" y secuencialmente (mediante un puntero o similar) de la misma manera que se puede hacer para un vector 1-D?

Sí, si :

• para que sólo necesita añadir cosas al final de su vector de vectores, y

• que está dispuesto a sustituir el vector de construcción de vectores con una estructura de datos personalizada

Lo que puedes hacer entonces es concatenar todos esos sub vectores en un único búfer contiguo, con otro búfer de índice utilizado para acceder a este por índice de entrada de nivel superior.

Ver my article here para más discusión sobre esto, y un ejemplo 'se derrumbó vectorial del vector' implementación de la clase ..