programación - manual completo de c++ pdf

Conjuntos 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 del puntero o, alternativamente, utilizando técnicas STL como vectores.

Básicamente, quiero que mis dimensiones enteras de matriz se vean así:

[ x ][ y ][ z ]

xey están en el rango 20-6000 z es conocido y es igual a 4.

Answer 1

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 direccionamiento indirecto 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 potencialmente hay dos dimensiones desconocidas, hay un problema con mi propuesta que permite solo 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. Mire aquí 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 se usa C ++, la forma más simple es usar la sobrecarga del operador para seguir con la sintaxis de la matriz:

    {
        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 a InnerTwoDArray (pero un buen compilador probablemente puede optimizarlo) pero usa solo un fragmento 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.

Answer 2

Cabe señalar que, para todos los efectos, se trata solo de una matriz 2D, porque se conoce la tercera dimensión (y la menos significativa).

Usar STL o Boost es un enfoque bastante bueno si no sabes de antemano cuántas entradas tendrás en cada dimensión de la matriz, porque te darán asignación de memoria dinámica, y recomiendo cualquiera de estos enfoques si tu conjunto de datos es permanecer en gran medida estático, o si solo recibe principalmente nuevas entradas y no muchas eliminaciones.

Sin embargo, si conoce algo sobre su conjunto de datos de antemano, como aproximadamente cuántos elementos en total se almacenarán, o si las matrices deben estar escasamente pobladas, es mejor que utilice algún tipo de función hash / bucket, y use el Índices XYZ como su 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 3

Cada par de corchetes es una operación de desreferenciación (cuando se aplica a un puntero). Como 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 usar su sintaxis sugerida, simplemente está desreferenciando el valor devuelto de la primera desreferencia.

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];

Para ir asignando esta matriz, solo necesita 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;
        }
    }
}

La desasignación de este conjunto sigue un proceso similar al de 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 4

Con vectores:

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

Cada elemento es accesible con array3d [x] [y] [z] si el elemento ya fue agregado. (por ejemplo, a través de push_back)

Answer 5

Eche un vistazo a la biblioteca de arreglos multidimensionales de Boost. Aquí hay un ejemplo (adaptado de la documentación de 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 6

El uso de STL para administrar su memoria con el uso de new / delete tiene muchas ventajas. 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 crees que necesitas crear un tipo de vector 3d personalizado, primero investiga 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 7

La sugerencia de Pieter es buena, por supuesto, pero una cosa que debes 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).