Dreidimensionale Arrays von Ganzzahlen in C ++
https://stackoverflow.com/questions/62512
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich möchte sichere Möglichkeiten zur Implementierung von dreidimensionalen Arrays von Ganzzahlen in C ++ ermitteln, unter Verwendung von Zeiger arithmetischen / dynamischen Speicherzuweisung oder alternativ verwendet STL Techniken wie Vektoren.
Im Wesentlichen möchte ich, dass meine Ganzzahl -Array -Dimensionen aussehen wie:
[ x ][ y ][ z ]
x und y befinden sich im Bereich von 20-6000 Z ist bekannt und gleich 4.
Lösung
Schauen Sie sich den Schub an Mehrdimensionales Array Bibliothek. Hier ist ein Beispiel (angepasst aus der Boost -Dokumentation):
#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++;
}
}
}
}
Andere Tipps
Jedes Paar quadratischer Klammern ist eine Derferenzoperation (wenn sie auf einen Zeiger angewendet wird). Beispielsweise sind die folgenden Codepaare entsprechend:
x = myArray[4];
x = *(myArray+4);
x = myArray[2][7];
x = *((*(myArray+2))+7);
Um Ihre vorgeschlagene Syntax zu verwenden, sind Sie einfach den von der ersten Dereferenz zurückgegebenen Wert.
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];
Um dieses Array zuzuweisen, müssen Sie lediglich erkennen, dass Sie eigentlich kein dreidimensionales Array von Ganzzahlen haben. Sie haben eine Reihe von Arrays von Zahlenarrays.
// 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;
}
}
}
Das Handeln dieses Arrays folgt einem ähnlichen Prozess, um es zuzuweisen:
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;
Unten finden Sie eine einfache Möglichkeit, 3D -Arrays mit C oder C ++ in einem Speicherback für jedes Array zu erstellen. Sie müssen Boost nicht verwenden (auch wenn es schön ist) oder die Zuordnung zwischen Linien mit mehreren Indirektionen aufzuteilen (dies ist ziemlich schlecht, da es normalerweise eine große Leistungsstrafe beim Zugriff auf Daten und IT -Fragsspeicher verleiht).
Das einzige, was zu verstehen ist, ist, dass es keine mehrdimensionalen Arrays gibt, nur Arrays von Arrays (von Arrays). Der innerste Index ist am weitesten im Gedächtnis.
#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;
}
}
Für Ihr tatsächliches Problem, da es möglicherweise zwei unbekannte Dimensionen gibt, gibt es ein Problem mit meinem Vorschlag, nur eine unbekannte Dimension zu ermöglichen. Es gibt verschiedene Möglichkeiten, das zu verwalten.
Die gute Nachricht ist, dass die Verwendung von Variablen jetzt mit C funktioniert und Arrays mit variabler Länge genannt wird. Sie sehen hier für Details.
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);
}
Wenn Sie C ++ verwenden, ist es wahrscheinlich am einfachsten, die Operatorüberladung zu verwenden, um sich an die Array -Syntax zu halten:
{
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]);
}
Der obige Code enthält einige Indirektionen für den Zugriff auf InnertWodarray (aber ein guter Compiler kann ihn wahrscheinlich optimieren), verwendet jedoch nur ein Speicherblock für Array, das auf dem Haufen zugewiesen wird. Dies ist normalerweise die effizienteste Wahl.
Selbst wenn der obige Code immer noch einfach und unkompliziert ist, macht STL oder Boost es gut, daher müssen das Rad nicht neu erfunden. Ich glaube immer noch, dass es interessant ist zu wissen, dass es leicht zu tun ist.
Mit Vektoren:
std::vector< std::vector< std::vector< int > > > array3d;
Jedes Element ist mit Array3d [x] [y] [z] zugänglich, wenn das Element bereits hinzugefügt wurde. (zB via push_back)
Es ist zu beachten, dass Sie in jeder Hinsicht nur mit einem 2D -Array zu tun haben, da die dritte (und am wenigsten signifikante) Dimension bekannt ist.
Die Verwendung des STL oder Boost sind ziemlich gute Ansätze, wenn Sie vorher nicht wissen, wie viele Einträge Sie in jeder Dimension des Arrays haben werden, da sie Ihnen eine dynamische Speicherzuweisung geben, und ich empfehle einen dieser Ansätze, wenn Ihr Datensatz ist weitgehend statisch bleiben oder meistens nur neue Einträge und nicht viele Löschungen erhalten.
Wenn Sie jedoch vorher etwas über Ihren Datensatz wissen, z. B. ungefähr wie viele Elemente insgesamt gespeichert werden oder wenn die Arrays spärlich besiedelt sein sollen, können Sie eine Art Hash/Bucket -Funktion besser verwenden und die verwenden und die verwenden XYZ -Indizes als Schlüssel. In diesem Fall können Sie mit einem 40-Bit-Taste (5-Bit) auskommen, wenn nicht mehr als 8192 (13 Bit) Einträge pro Dimension auskommen. Oder unter der Annahme, dass es immer 4 x Z-Einträge gibt, würden Sie einfach einen 26-Bit-XY-Schlüssel verwenden. Dies ist einer der effizienteren Kompromisse zwischen Geschwindigkeit, Speicherverbrauch und dynamischer Zuordnung.
Es gibt viele Vorteile, die STL zu verwenden, um Ihren Speicher über die Verwendung von New/Delete zu verwalten. Die Wahl, wie Sie Ihre Daten darstellen, hängt davon ab, wie Sie sie verwenden möchten. Ein Vorschlag wäre eine Klasse, die die Implementierungsentscheidung verbirgt und dreidimensionale Get/Set -Methoden für einen eindimensionalen STL -Vektor bereitstellt.
Wenn Sie wirklich glauben, dass Sie einen benutzerdefinierten 3D -Vektor -Typ erstellen müssen, untersuchen Sie zuerst 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;
};
Der Vorschlag von Pieter ist natürlich gut, aber eine Sache, die Sie beachten, ist, dass es bei großen Arrays, die es bauen, ziemlich langsam sein kann. Jedes Mal, wenn sich die Vektorkapazität ändert, müssen alle Daten kopiert werden ('n' Vektoren von Vektoren).
