Matrici tridimensionali di numeri interi in C++
https://stackoverflow.com/questions/62512
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Vorrei scoprire modi sicuri per implementare array tridimensionali di numeri interi in C++, utilizzando l'aritmetica dei puntatori/allocazione dinamica della memoria o, in alternativa utilizzando STL tecniche come i vettori.
Essenzialmente voglio che le dimensioni del mio array di numeri interi assomiglino a:
[ x ][ y ][ z ]
X e Y sono nell'intervallo 20-6000 z è noto ed è uguale a 4.
Soluzione
Dai un'occhiata al Boost matrice multidimensionale biblioteca.Ecco un esempio (adattato dalla documentazione di 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++;
}
}
}
}
Altri suggerimenti
Ogni coppia di parentesi quadre è un'operazione di dereferenziazione (se applicata a un puntatore).Ad esempio, le seguenti coppie di righe di codice sono equivalenti:
x = myArray[4];
x = *(myArray+4);
x = myArray[2][7];
x = *((*(myArray+2))+7);
Per utilizzare la sintassi suggerita stai semplicemente dereferenziando il valore restituito dal primo dereferenziamento.
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];
Per procedere all'allocazione di questo array, devi semplicemente riconoscere che in realtà non hai un array tridimensionale di numeri interi.Hai una serie di matrici di matrici di numeri interi.
// 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 deallocazione di questo array segue un processo simile all'allocazione:
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;
Di seguito è riportato un modo semplice per creare array 3D utilizzando C o C++ in una porzione di memoria per ogni array.Non c'è bisogno di usare BOOST (anche se è carino), o di dividere l'allocazione tra linee con più riferimenti indiretti (questo è piuttosto negativo in quanto di solito dà una grande penalità alle prestazioni quando si accede ai dati e frammenta la memoria).
L'unica cosa da capire è che non esistono array multidimensionali, ma solo array di array (di array).L'indice più interno è il più lontano nella 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;
}
}
Per il tuo problema reale, poiché potenzialmente esistono due dimensioni sconosciute, c'è un problema con la mia proposta che consente solo una dimensione sconosciuta.Esistono diversi modi per gestirlo.
La buona notizia è che l'uso delle variabili ora funziona con C, si chiama array a lunghezza variabile.Sembri Qui per dettagli.
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 si utilizza C++, il modo più semplice è probabilmente utilizzare l'overload degli operatori per attenersi alla sintassi dell'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]);
}
Il codice precedente ha alcuni costi indiretti per l'accesso a InnerTwoDArray (ma un buon compilatore può probabilmente ottimizzarlo) ma utilizza solo un blocco di memoria per l'array allocato sull'heap.Che di solito è la scelta più efficiente.
Ovviamente anche se il codice riportato sopra è ancora semplice e diretto, STL o BOOST lo fanno bene, quindi non c'è bisogno di reinventare la ruota.Credo ancora che sia interessante sapere che può essere fatto facilmente.
Con i vettori:
std::vector< std::vector< std::vector< int > > > array3d;
Ogni elemento è accessibile con array3d[x][y][z] se l'elemento è già stato aggiunto.(per esempio.tramite push_back)
Va notato che, a tutti gli effetti, si ha a che fare solo con un array 2D, perché la terza (e meno significativa) dimensione è nota.
L'uso di STL o Boost è un approccio abbastanza buono se non sai in anticipo quante voci avrai in ciascuna dimensione dell'array, perché ti daranno un'allocazione dinamica della memoria e consiglio uno di questi approcci se il tuo set di dati lo è rimanere in gran parte statico, o se ricevere per lo più solo nuove voci e non molte eliminazioni.
Tuttavia, se sai qualcosa in anticipo sul tuo set di dati, ad esempio quanti elementi in totale verranno archiviati o se gli array devono essere scarsamente popolati, potrebbe essere meglio utilizzare una sorta di funzione hash/bucket e utilizzare la funzione Indici XYZ come chiave.In questo caso, presupponendo non più di 8192 (13 bit) voci per dimensione, potresti cavartela con una chiave da 40 bit (5 byte).Oppure, supponendo che ci siano sempre 4 voci Z, utilizzeresti semplicemente una chiave XY a 26 bit.Questo è uno dei compromessi più efficienti tra velocità, utilizzo della memoria e allocazione dinamica.
Ci sono molti vantaggi nell'usare STL per gestire la memoria rispetto all'uso di nuovo/elimina.La scelta di come rappresentare i tuoi dati dipende da come prevedi di utilizzarli.Un suggerimento potrebbe essere una classe che nasconda la decisione di implementazione e fornisca metodi get/set tridimensionali a un vettore STL unidimensionale.
Se ritieni davvero di dover creare un tipo di vettore 3D personalizzato, esamina prima 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;
};
Il suggerimento di Pieter è ovviamente valido, ma una cosa da tenere a mente è che in caso di costruzione di array di grandi dimensioni potrebbe essere piuttosto lenta.Ogni volta che la capacità del vettore cambia, tutti i dati devono essere copiati ('n' vettori di vettori).
