Tableaux tridimensionnels d'entiers en C ++
https://stackoverflow.com/questions/62512
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'aimerais trouver des moyens sûrs d'implémenter des tableaux tridimensionnels d'entiers en C ++, en utilisant l'allocation de mémoire dynamique arithmétique par pointeur ou, alternativement, en utilisant des techniques STL telles que les vecteurs.
Je souhaite essentiellement que les dimensions de mon tableau de nombres entiers ressemblent à:
[ x ][ y ][ z ]
x et y sont compris entre 20 et 6000 z est connu et vaut 4.
La solution
Consultez la bibliothèque multidimensionnelle multidimensionnelle Boost. Voici un exemple (adapté de la documentation 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++;
}
}
}
}
Autres conseils
Chaque paire de crochets est une opération de déréférencement (lorsqu'elle est appliquée à un pointeur). Par exemple, les paires de lignes de code suivantes sont équivalentes:
x = myArray[4];
x = *(myArray+4);
& nbsp;
x = myArray[2][7];
x = *((*(myArray+2))+7);
Pour utiliser la syntaxe suggérée, il vous suffit de déréférencer la valeur renvoyée par le premier déréférencement.
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];
Pour allouer ce tableau, vous devez simplement reconnaître que vous n’avez pas réellement de tableau à trois dimensions d’entiers. Vous avez un tableau de tableaux de tableaux d'entiers.
// 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 désallocation de ce tableau suit un processus similaire pour l'allouer:
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;
Voici un moyen simple de créer des tableaux 3D en utilisant C ou C ++ dans un bloc de mémoire pour chaque tableau. Pas besoin d'utiliser BOOST (même si c'est agréable), ou de diviser l'allocation entre plusieurs lignes avec un indirection multiple (c'est assez grave, car cela entraîne généralement de lourdes pertes de performances lors de l'accès aux données et fragmente la mémoire).
La seule chose à comprendre est qu’il n’existe pas de tableaux multidimensionnels, mais simplement de tableaux de tableaux (de tableaux). L'index le plus interne étant le plus éloigné de la mémoire.
#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;
}
}
En ce qui concerne votre problème actuel, comme il existe potentiellement deux dimensions inconnues, il existe un problème lié à ma proposition: autorisez une seule dimension inconnue. Il y a plusieurs façons de gérer cela.
La bonne nouvelle est que l'utilisation de variables fonctionne maintenant avec C, on l'appelle des tableaux de longueur variable. Vous regardez ici pour plus de détails.
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 vous utilisez C ++, le moyen le plus simple consiste probablement à utiliser la surcharge d'opérateur pour vous en tenir à la syntaxe de tableau:
{
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]);
}
Le code ci-dessus a un coût indirectionnel pour accéder à InnerTwoDArray (mais un bon compilateur peut probablement l’optimiser), mais n’utilise qu’un seul bloc de mémoire pour le tableau alloué sur le tas. Quel est généralement le choix le plus efficace.
Évidemment, même si le code ci-dessus est toujours simple et simple, STL ou BOOST le fait bien, il n’est donc pas nécessaire de réinventer la roue. Je crois toujours qu'il est intéressant de savoir que cela peut être facilement fait.
Avec des vecteurs:
std::vector< std::vector< std::vector< int > > > array3d;
Chaque élément est accessible avec array3d [x] [y] [z] si l'élément a déjà été ajouté. (par exemple via push_back)
Il convient de noter que, à toutes fins pratiques, vous ne travaillez qu'avec un tableau 2D, car la troisième dimension (la moins significative) est connue.
L’utilisation de STL ou de Boost est une très bonne approche si vous ne savez pas à l’avance le nombre d’entrées que vous aurez dans chaque dimension du tableau, car elles vous donneront une allocation de mémoire dynamique, et je recommande l’une ou l’autre de ces approches si votre l'ensemble de données doit rester en grande partie statique ou ne recevoir que de nouvelles entrées et pas beaucoup de suppressions.
Toutefois, si vous connaissez au préalable des informations sur votre jeu de données, telles que le nombre d'éléments stockés au total, ou si les tableaux doivent être peu peuplés, il est peut-être préférable d'utiliser une fonction de hachage / compartiment, et utilisez les indices XYZ comme clé. Dans ce cas, en supposant que le nombre d'entrées par dimension ne dépasse pas 8 192 (13 bits), vous pouvez vous en sortir avec une clé de 40 bits (5 octets). Ou, en supposant qu'il y ait toujours 4 x Z entrées, vous utiliseriez simplement une clé XY 26 bits. C’est l’un des compromis les plus efficaces entre vitesse, utilisation de la mémoire et allocation dynamique.
Il existe de nombreux avantages à utiliser la STL pour gérer votre mémoire plutôt qu’à l’aide de new / delete. Le choix de la manière de représenter vos données dépend de la manière dont vous prévoyez de l’utiliser. Une suggestion serait une classe qui cache la décision d'implémentation et fournit des méthodes tridimensionnelles get / set à un vecteur STL unidimensionnel.
Si vous pensez vraiment que vous devez créer un type de vecteur 3D personnalisé, étudiez d'abord 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 suggestion de Pieter est bonne, bien sûr, mais vous devez garder à l’esprit que lorsqu’un grand nombre de tableaux est construit, elle peut être assez lente. Chaque fois que la capacité du vecteur change, toutes les données doivent être copiées ("n" vecteurs de vecteurs).
