std :: vector y memoria contigua de matrices multidimensionales

Sé que el estándar no obliga a std::vector a asignar bloques de memoria contiguos, pero todas las implementaciones obedecen esto sin embargo.

Supongamos que deseo crear un vector de una matriz estática multidimensional. Considere 2 dimensiones para simplificar, y un vector de longitud N. Es decir, deseo crear un vector con N elementos de, digamos, int[5] .

¿Puedo estar seguro de que todos los enteros N * 5 ahora están contiguos en la memoria? ¿Para que yo, en principio, pueda acceder a todos los enteros simplemente conociendo la dirección del primer elemento? ¿Es esta implementación dependiente?

Para referencia, la forma en que actualmente creo una matriz 2D en un bloque de memoria contigua es haciendo primero una matriz (dinámica) de float * de longitud N, asignando todos los flotantes N * 5 en una matriz y luego copiando la dirección de cada 5to elemento en el primer conjunto de float* .

Para referencia, la forma en que actualmente creo una matriz 2D en un bloque de memoria contigua es haciendo primero una matriz (dinámica) de float * de longitud N, asignando todos los flotantes N * 5 en una matriz y luego copiando la dirección de cada 5to elemento en el primer conjunto de flotador *.

Eso no es una matriz 2D, eso es una matriz de punteros. Si quieres una matriz 2D real, así es como se hace:

 float (*p)[5] = new float[N][5]; p [0] [0] = 42; // access first element p[N-1][4] = 42; // access last element delete[] p; 

Tenga en cuenta que solo hay una sola asignación. ¿Puedo sugerir leer más sobre el uso de matrices en C ++ ?

El estándar requiere que la memoria de un std::vector sea ​​contigua. Por otro lado, si escribes algo como:

 std::vector > v; 

la memoria global (todas las v[i][j] ) no serán contiguas. La forma habitual de crear matrices en 2D es utilizar un solo

 std::vector v; 

y calcule los índices, exactamente como sugiere hacerlo con float . (También puede crear un segundo std::vector con las direcciones si lo desea. Sin embargo, siempre he recalculado los índices).

Se garantiza que los elementos de un vector sean contiguos según el estándar de C ++.
Las citas del estándar son las siguientes:

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 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 un tipo distinto de bool, entonces obedece a la identidad & v [n] == & v [0] + n para todos 0 <= n

Estándar C ++ 03 (23.2.4.1):

Los elementos de un vector se almacenan contiguamente, lo que significa que si v es un vector donde T es un tipo distinto de bool, entonces obedece a la identidad & v [n] == & v [0] + n para todos 0 <= n

Además, vea aquí los puntos de vista de Herb Sutter sobre lo mismo.

Como @Als ya señaló, sí, std::vector (ahora) garantiza la asignación contigua. Sin embargo, no simularía una matriz 2D con una matriz de punteros. En cambio, recomendaría uno de dos enfoques. El más simple por (de lejos) es simplemente usar operator() para la creación de suscripciones, y hacer una multiplicación para convertir la entrada 2D a una dirección lineal en su vector:

 template  class matrix2D { std::vector data; int columns; public: T &operator()(int x, int y) { return data[y * columns + x]; } matrix2D(int x, int y) : data(x*y), columns(x) {} }; 

Si, por algún motivo, desea utilizar el direccionamiento de estilo matrix[a][b] , puede usar una clase proxy para manejar la conversión. Aunque fue para una matriz 3D en lugar de 2D, publiqué una demostración de esta técnica en la respuesta anterior .

Debajo del capó, un vector puede verse aproximadamente como (código p):

 class vector { T *data; size_t s; }; 

Ahora si haces un vector > , habrá un diseño como este

 vector> --> data { vector, vector, vector }; 

o en forma “en línea”

 vector> --> data { {data0, s0}, {data1, s1}, {data2, s2} }; 

Sí, el vector-vector, por lo tanto, usa memoria contigua, pero no, no como te gustaría. Es muy probable que almacene un conjunto de punteros (y algunas otras variables) en lugares externos.

El estándar solo requiere que los datos de un vector sean contiguos, pero no el vector como un todo.

Una clase simple para crear, como usted lo llama, una matriz 2D , sería algo así como:

 template  2DArray { private: T *m_data; int m_stride; public: 2DArray(int dimY, int dimX) : m_stride(dimX) : m_data(new[] T[dimX * dimY]) {} ~2DArray() { delete[] m_data; } T* operator[](int row) { return m_data + m_stride * row; } } 

Es posible usar esto como:

 2DArray myArray(30,20); for (int i = 0; i < 30; i++) for (int j = 0; j < 20; j++) myArray[i][j] = i + j; 

O incluso pase &myArray[0][0] como dirección a funciones de bajo nivel que toman algún tipo de "búferes planos".

Pero como ve, se vuelven ingenuas las expectativas porque es myarray[y][x] .

En términos generics, si interactúa con un código que requiere algún tipo de matriz plana clásica de estilo C, ¿por qué no usar eso?

Editar: Como se dijo, lo anterior es simple . Sin límites, compruebe los bashs de ningún tipo. Al igual que, "una matriz".