Matrizes tridimensionais de inteiros em C++
https://stackoverflow.com/questions/62512
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu gostaria de descobrir maneiras seguras de implementar matrizes tridimensionais de números inteiros em C++, usando alocação de memória aritmética/dinâmica de ponteiro ou, alternativamente, usando STL técnicas como vetores.
Essencialmente, quero que as dimensões da minha matriz inteira sejam assim:
[ x ][ y ][ z ]
X e Y estão no intervalo de 20-6000 z é conhecido e é igual a 4.
Solução
Dê uma olhada no Boost matriz multidimensional biblioteca.Aqui está um exemplo (adaptado da documentação do 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++;
}
}
}
}
Outras dicas
Cada par de colchetes é uma operação de desreferenciação (quando aplicada a um ponteiro).Por exemplo, os seguintes pares de linhas de código são equivalentes:
x = myArray[4];
x = *(myArray+4);
x = myArray[2][7];
x = *((*(myArray+2))+7);
Para usar a sintaxe sugerida, você está simplesmente desreferenciando o valor retornado da primeira desreferência.
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 alocar esse array, você simplesmente precisa reconhecer que na verdade não possui um array tridimensional de inteiros.Você tem uma matriz de matrizes de matrizes de números inteiros.
// 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;
}
}
}
A desalocação desta matriz segue um processo semelhante à sua alocação:
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;
Abaixo está uma maneira direta de criar arrays 3D usando C ou C++ em um pedaço de memória para cada array.Não há necessidade de usar BOOST (mesmo que seja bom) ou dividir a alocação entre linhas com múltiplas indireções (isso é muito ruim, pois geralmente causa grande penalidade de desempenho ao acessar dados e fragmenta a memória).
A única coisa a entender é que não existem arrays multidimensionais, apenas arrays de arrays (de arrays).O índice mais interno é o mais distante na memória.
#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 o seu problema real, como existem potencialmente duas dimensões desconhecidas, há um problema com a minha proposta de permitir apenas uma dimensão desconhecida.Existem várias maneiras de gerenciar isso.
A boa notícia é que o uso de variáveis agora funciona com C, são chamados de arrays de comprimento variável.Você parece aqui para detalhes.
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);
}
Se estiver usando C++, a maneira mais simples é provavelmente usar a sobrecarga do operador para manter a sintaxe do array:
{
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]);
}
O código acima tem algum custo indireto para acessar o InnerTwoDArray (mas um bom compilador provavelmente pode otimizá-lo), mas usa apenas um pedaço de memória para o array alocado no heap.Qual geralmente é a escolha mais eficiente.
Obviamente, mesmo que o código acima ainda seja simples e direto, STL ou BOOST funcionam bem, portanto não há necessidade de reinventar a roda.Ainda acredito que é interessante saber que isso pode ser feito facilmente.
Com vetores:
std::vector< std::vector< std::vector< int > > > array3d;
Cada elemento é acessível com array3d[x][y][z] se o elemento já tiver sido adicionado.(por exemplo.via push_back)
Deve-se notar que, para todos os efeitos, você está lidando apenas com uma matriz 2D, porque a terceira (e menos significativa) dimensão é conhecida.
Usar STL ou Boost são abordagens muito boas se você não sabe de antemão quantas entradas terá em cada dimensão do array, porque elas fornecerão alocação dinâmica de memória, e eu recomendo qualquer uma dessas abordagens se seu conjunto de dados for permanecer em grande parte estático ou receber apenas novas entradas e não muitas exclusões.
No entanto, se você sabe algo sobre seu conjunto de dados de antemão, como aproximadamente quantos itens no total serão armazenados ou se as matrizes devem ser preenchidas de forma esparsa, talvez seja melhor usar algum tipo de função hash/bucket e usar o Índices XYZ como sua chave.Nesse caso, assumindo não mais que 8.192 (13 bits) entradas por dimensão, você poderia usar uma chave de 40 bits (5 bytes).Ou, supondo que sempre haja 4 entradas Z, você simplesmente usaria uma chave XY de 26 bits.Esta é uma das compensações mais eficientes entre velocidade, uso de memória e alocação dinâmica.
Há muitas vantagens em usar o STL para gerenciar sua memória em vez de usar novo/excluir.A escolha de como representar seus dados depende de como você planeja usá-los.Uma sugestão seria uma classe que ocultasse a decisão de implementação e fornecesse métodos get/set tridimensionais para um vetor STL unidimensional.
Se você realmente acredita que precisa criar um tipo de vetor 3D personalizado, investigue primeiro o 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;
};
A sugestão de Pieter é boa, claro, mas uma coisa que você deve ter em mente é que, no caso de grandes arrays, a construção pode ser bastante lenta.Cada vez que a capacidade do vetor muda, todos os dados devem ser copiados ('n' vetores de vetores).
