Matrices tridimensionales de enteros en C++

Question

Me gustaría encontrar formas seguras de implementar matrices tridimensionales de enteros en C++, utilizando la asignación de memoria dinámica/aritmética de puntero o, alternativamente, usando STL técnicas como vectores.

Esencialmente Quiero que mis dimensiones de matriz de enteros que se ven como:

[ x ][ y ][ z ] 

X e Y son en el rango de 20 a 6000 se conoce z y es igual a 4.

Answer 1

Tener un vistazo a la Boost multi-dimensional array biblioteca. Aquí hay un ejemplo (adaptado de la documentación Boost):

#include "boost/multi_array.hpp" 

int main() { 
    // Create a 3D array that is 20 x 30 x 4 
    int x = 20; 
    int y = 30; 
    int z = 4; 

    typedef boost::multi_array<int, 3> array_type; 
    typedef array_type::index index; 
    array_type my_array(boost::extents[x][y][z]); 

    // Assign values to the elements 
    int values = 0; 
    for (index i = 0; i != x; ++i) { 
    for (index j = 0; j != y; ++j) { 
     for (index k = 0; k != z; ++k) { 
     my_array[i][j][k] = values++; 
     } 
    } 
    } 
} 

Answer 2

Cada par de corchetes es una operación de desreferencia (cuando se aplica a un puntero). A modo de ejemplo, los siguientes pares de líneas de código son equivalentes:

x = myArray[4]; 
x = *(myArray+4); 

 

x = myArray[2][7]; 
x = *((*(myArray+2))+7); 

Para utilizar la sintaxis propuestos Está simplemente dereferencing el valor devuelto por el primer desreferenciar.

int*** myArray = (some allocation method, keep reading); 
// 
// All in one line: 
int value = myArray[x][y][z]; 
// 
// Separated to multiple steps: 
int** deref1 = myArray[x]; 
int* deref2 = deref1[y]; 
int value = deref2[z]; 

de ir sobre la asignación de esta matriz, sólo hay que reconocer que en realidad no tiene una matriz tridimensional de números enteros. Tienes una matriz de matrices de matrices de enteros.

// Start by allocating an array for array of arrays 
int*** myArray = new int**[X_MAXIMUM]; 

// Allocate an array for each element of the first array 
for(int x = 0; x < X_MAXIMUM; ++x) 
{ 
    myArray[x] = new int*[Y_MAXIMUM]; 

    // Allocate an array of integers for each element of this array 
    for(int y = 0; y < Y_MAXIMUM; ++y) 
    { 
     myArray[x][y] = new int[Z_MAXIMUM]; 

     // Specify an initial value (if desired) 
     for(int z = 0; z < Z_MAXIMUM; ++z) 
     { 
      myArray[x][y][z] = -1; 
     } 
    } 
} 

desasignación de esta matriz sigue un proceso similar al de su asignación:

for(int x = 0; x < X_MAXIMUM; ++x) 
{ 
    for(int y = 0; y < Y_MAXIMUM; ++y) 
    { 
     delete[] myArray[x][y]; 
    } 

    delete[] myArray[x]; 
} 

delete[] myArray; 

Answer 3

Cabe señalar que, para todos los efectos, que se trata de sólo una matriz 2D, debido a que la tercera (y menos significativo) es conocida la dimensión.

El uso de STL o Boost son enfoques bastante buenos si no sabe de antemano cuántas entradas tendrá en cada dimensión de la matriz, porque le darán asignación de memoria dinámica, y recomiendo cualquiera de estos enfoques si su conjunto de datos permanecerá en gran medida estático o, en su mayor parte, solo recibirá nuevas entradas y no muchas eliminaciones.

Sin embargo, si conoce algo acerca de su conjunto de datos de antemano, como aproximadamente cuántos elementos en total se almacenarán, o si las matrices estarán poco pobladas, es mejor que utilice algún tipo de función hash/bucket y usa los índices XYZ como tu clave. En este caso, suponiendo que no haya más de 8192 (13 bits) entradas por dimensión, podría obtener una clave de 40 bits (5 bytes). O, suponiendo que siempre haya 4 entradas Z, simplemente usaría una clave XY de 26 bits. Esta es una de las compensaciones más eficientes entre velocidad, uso de memoria y asignación dinámica.

Answer 4

con vectores:

std::vector< std::vector< std::vector<int> > > array3d; 

Cada elemento es ingenio accesible array3d [x] [y] [z] si ya se añadió el elemento. (Por ejemplo, a través de push_back)

Answer 5

Existen muchas ventajas al usar el STL para administrar su memoria sobre el uso de new/delete. La elección de cómo representar sus datos depende de cómo planea usarlos.Una sugerencia sería una clase que oculte la decisión de implementación y proporcione métodos get/set tridimensionales a un vector STL unidimensional.

Si realmente cree que necesita crear un tipo de vector 3d personalizado, investigue primero Boost.

// a class that does something in 3 dimensions 

class MySimpleClass 
{ 
public: 

    MySimpleClass(const size_t inWidth, const size_t inHeight, const size_t inDepth) : 
    mWidth(inWidth), mHeight(inHeight), mDepth(inDepth) 
    { 
     mArray.resize(mWidth * mHeight * mDepth); 
    } 


    // inline for speed 
    int Get(const size_t inX, const size_t inY, const size_t inZ) { 
    return mArray[(inZ * mWidth * mHeight) + (mY * mWidth) + mX]; 
    } 

    void Set(const size_t inX, const size_t inY, const size_t inZ, const int inVal) { 
    return mArray[(inZ * mWidth * mHeight) + (mY * mWidth) + mX]; 
    } 

    // doing something uniform with the data is easier if it's not a vector of vectors 
    void DoSomething() 
    { 
    std::transform(mArray.begin(), mArray.end(), mArray.begin(), MyUnaryFunc); 
    } 

private: 

    // dimensions of data 
    size_t mWidth; 
    size_t mHeight; 
    size_t mDepth; 

    // data buffer 
    std::vector<int> mArray; 
}; 

Answer 6

sugerencia de Pieter es bueno, por supuesto, pero una cosa que tienes que tener en cuenta es que en el caso de la construcción de grandes matrices puede ser bastante lento. Cada vez que cambia la capacidad del vector, todos los datos deben copiarse ('n' vectores de vectores).

Answer 7

A continuación se muestra una forma sencilla de crear matrices 3D utilizando C o C++ en un trozo de memoria para cada matriz. No es necesario usar BOOST (incluso si es agradable), o dividir la asignación entre líneas con indirección múltiple (esto es bastante malo ya que generalmente da una gran penalización de rendimiento al acceder a los datos y fragmenta la memoria).

Lo único que hay que entender es que no existen las matrices multidimensionales, solo las matrices de las matrices (de las matrices). El índice más interno es el más lejano en la memoria.

#include <stdio.h> 
#include <stdlib.h> 

int main(){ 

    { 
     // C Style Static 3D Arrays 
     int a[10][20][30]; 
     a[9][19][29] = 10; 
     printf("a[9][19][29]=%d\n", a[9][19][29]); 
    } 

    { 
     // C Style dynamic 3D Arrays 
     int (*a)[20][30]; 
     a = (int (*)[20][30])malloc(10*20*30*sizeof(int)); 
     a[9][19][29] = 10; 
     printf("a[9][19][29]=%d\n", a[9][19][29]); 
     free(a); 
    } 

    { 
     // C++ Style dynamic 3D Arrays 
     int (*a)[20][30]; 
     a = new int[10][20][30]; 
     a[9][19][29] = 10; 
     printf("a[9][19][29]=%d\n", a[9][19][29]); 
     delete [] a; 
    } 

} 

para su problema real, ya que es potencialmente dos dimensiones desconocidas, hay un problema con mi propuesta en que permite sólo una dimensión desconocida. Hay varias formas de gestionar eso.

La buena noticia es que el uso de variables ahora funciona con C, se llama arrays de longitud variable. Miras here para más detalles.

int x = 100; 
    int y = 200; 
    int z = 30; 

    { 
     // C Style Static 3D Arrays 
     int a[x][y][z]; 
     a[99][199][29] = 10; 
     printf("a[99][199][29]=%d\n", a[99][199][29]); 
    } 

    { 
     // C Style dynamic 3D Arrays 
     int (*a)[y][z]; 
     a = (int (*)[y][z])malloc(x*y*z*sizeof(int)); 
     a[99][199][29] = 10; 
     printf("a[99][199][29]=%d\n", a[99][199][29]); 
     free(a); 
    } 

Si usando C++ la forma más sencilla es probablemente usar la sobrecarga de operadores para seguir con matriz sintaxis:

{ 
     class ThreeDArray { 
      class InnerTwoDArray { 
       int * data; 
       size_t y; 
       size_t z; 
       public: 
       InnerTwoDArray(int * data, size_t y, size_t z) 
        : data(data), y(y), z(z) {} 

       public: 
       int * operator [](size_t y){ return data + y*z; } 
      }; 

      int * data; 
      size_t x; 
      size_t y; 
      size_t z; 
      public: 
      ThreeDArray(size_t x, size_t y, size_t z) : x(x), y(y), z(z) { 
       data = (int*)malloc(x*y*z*sizeof data); 
      } 

      ~ThreeDArray(){ free(data); } 

      InnerTwoDArray operator [](size_t x){ 
       return InnerTwoDArray(data + x*y*z, y, z); 
      } 
     }; 

     ThreeDArray a(x, y, z); 
     a[99][199][29] = 10; 
     printf("a[99][199][29]=%d\n", a[99][199][29]); 
    } 

El código anterior tiene algún costo indirecto para acceder InnerTwoDArray (pero un buen compilador probablemente puede optimizar de distancia) pero utiliza solo un trozo de memoria para la matriz asignada en el montón. Que suele ser la elección más eficiente.

Obviamente, incluso si el código anterior sigue siendo simple y directo, STL o BOOST lo hace bien, por lo tanto, no es necesario reinventar la rueda. Todavía creo que es interesante saber que se puede hacer fácilmente.