Matrices tridimensionales de números enteros en C++
https://stackoverflow.com/questions/62512
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Me gustaría descubrir formas seguras de implementar matrices tridimensionales de números enteros en C++, utilizando la aritmética de punteros/asignación de memoria dinámica o, alternativamente, utilizando STL técnicas como los vectores.
Básicamente, quiero que las dimensiones de mi matriz de números enteros se vean así:
[ x ][ y ][ z ]
X e Y están en el rango de 20-6000 Z es conocido y es igual a 4.
Solución
Echa un vistazo al impulso matriz multidimensional biblioteca.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++;
}
}
}
}
Otros consejos
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 utilizar la sintaxis sugerida, simplemente está desreferenciando el valor devuelto por 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 asignar esta matriz, simplemente necesita reconocer que en realidad no tiene una matriz tridimensional de números enteros.Tienes una serie de matrices de matrices de números 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 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;
A continuación se muestra una forma sencilla de crear matrices 3D usando C o C++ en una porción de memoria para cada matriz.No es necesario usar BOOST (incluso si es bueno) o dividir la asignación entre líneas con múltiples direcciones indirectas (esto es bastante malo ya que generalmente genera una gran penalización en el rendimiento al acceder a los datos y fragmenta la memoria).
Lo único que hay que entender es que no existen matrices multidimensionales, solo matrices de matrices (de 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, como potencialmente hay dos dimensiones desconocidas, hay un problema con mi propuesta, ya que solo permite una dimensión desconocida.Hay varias formas de gestionarlo.
La buena noticia es que el uso de variables ahora funciona con C, se llama matrices de longitud variable.tu miras aquí para 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 usa C++, la forma más sencilla probablemente sea usar la sobrecarga de operadores 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 de direccionamiento indirecto para acceder a InnerTwoDArray (pero un buen compilador probablemente pueda optimizarlo) pero usa solo un fragmento de memoria para la matriz asignada en el montón.Que suele ser la opción más eficiente.
Obviamente, incluso si el código anterior sigue siendo simple y directo, STL o BOOST lo hacen bien, por lo que no es necesario reinventar la rueda.Sigo creyendo que es interesante saber que se puede hacer fácilmente.
Con vectores:
std::vector< std::vector< std::vector< int > > > array3d;
Se puede acceder a cada elemento con array3d[x][y][z] si el elemento ya se agregó.(p.ej.a través de push_back)
Cabe señalar que, a todos los efectos, se trata únicamente de una matriz 2D, porque se conoce la tercera (y menos significativa) dimensión.
Usar 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 brindarán una asignación de memoria dinámica, y recomiendo cualquiera de estos enfoques si su conjunto de datos es para permanecer en gran medida estático, o si solo recibe nuevas entradas y no muchas eliminaciones.
Sin embargo, si sabe algo sobre su conjunto de datos de antemano, como aproximadamente cuántos elementos en total se almacenarán, o si las matrices van a estar escasamente pobladas, sería mejor que usara algún tipo de función hash/bucket y usara Índices XYZ como clave.En este caso, suponiendo que no haya más de 8192 (13 bits) entradas por dimensión, podría arreglárselas con una clave de 40 bits (5 bytes).O, suponiendo que siempre haya 4 entradas x 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.
Hay muchas ventajas al usar STL para administrar su memoria en lugar de usar nuevo/eliminar.La elección de cómo representar sus datos depende de cómo planea utilizarlos.Una sugerencia sería una clase que oculte la decisión de implementación y proporcione métodos get/set tridimensionales para un vector STL unidimensional.
Si realmente cree que necesita crear un tipo de vector 3D personalizado, primero investigue 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;
};
La sugerencia de Pieter es buena, por supuesto, pero una cosa que hay que tener en cuenta es que en el caso de que se construyan grandes conjuntos, puede ser bastante lento.Cada vez que cambia la capacidad del vector, todos los datos deben copiarse ('n' vectores de vectores).
