Dreidimensionale Arrays von ganzen Zahlen in C++

Question

Ich möchte sichere Möglichkeiten zur Implementierung von dreidimensionalen Arrays von ganzen Zahlen in C++, mit Pointer Arithmetik/dynamische Speicherzuweisung, oder alternativ mit STL Techniken wie Vektoren.

Grunde möchte ich meine Integer-Array Dimensionen aussehen:

[ x ][ y ][ z ] 

x und y im Bereich von 20 bis 6000 z bekannt ist und gleich 4

Answer 1

Werfen Sie einen Blick auf die Boost multi-dimensional array Bibliothek. Hier ist ein Beispiel (von der Boost-Dokumentation angepasst):

#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++; 
     } 
    } 
    } 
} 

Answer 2

Jedes Paar von eckigen Klammern ist ein dereferenzierenden Betrieb (wenn auf einen Zeiger angewandt wird). Als Beispiel sind die folgenden Paare von Codezeilen äquivalent:

x = myArray[4]; 
x = *(myArray+4); 

 

x = myArray[2][7]; 
x = *((*(myArray+2))+7); 

Ihre vorgeschlagene Syntax nutzen zu können, sind einfach dereferencing der Wert aus dem ersten Dereferenzierung zurückgegeben.

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]; 

über die Zuweisung dieses Array zu gehen, müssen Sie einfach zu erkennen, dass Sie tatsächlich ein dreidimensionales Array von ganzen Zahlen nicht haben. Sie haben ein Array von Arrays aus ganzen Zahlen.

// 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; 
     } 
    } 
} 

dieses Array ausplanen folgt ein ähnliches Verfahren es Zuweisung:

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; 

Answer 3

Es soll beachtet werden, dass für alle Absichten und Zwecke, Sie mit nur einem 2D-Array zu tun hat, weil die dritten (und am wenigsten signifikante) Dimension ist bekannt. Die Verwendung der STL oder Boost sind ziemlich gute Ansätze, wenn Sie nicht im Voraus wissen, wie viele Einträge Sie in jeder Dimension des Arrays haben werden, weil sie Ihnen dynamische Speicherzuweisung geben, und ich empfehle eine dieser Ansätze, wenn Ihr Datensatz soll weitgehend statisch bleiben, oder wenn er meist nur neue Einträge und nicht viele Löschungen erhält.

Wenn Sie jedoch zuvor etwas über Ihre Datenmenge wissen, etwa ungefähr, wie viele Elemente insgesamt gespeichert werden, oder wenn die Arrays dünn besiedelt werden sollen, verwenden Sie besser eine Art Hash/Bucket-Funktion und verwende die XYZ-Indizes als Schlüssel. Wenn Sie in diesem Fall nicht mehr als 8192 (13 Bit) Einträge pro Dimension annehmen, können Sie mit einem 40-Bit-Schlüssel (5 Byte) auskommen. Oder, vorausgesetzt, es gibt immer 4 x Z-Einträge, würden Sie einfach einen 26-Bit-XY-Schlüssel verwenden. Dies ist einer der effizienteren Kompromisse zwischen Geschwindigkeit, Speichernutzung und dynamischer Zuordnung.

Answer 4

mit Vektoren:

std::vector< std::vector< std::vector<int> > > array3d; 

Jedes Element zugänglich ist wit array3d [x] [y] [z], wenn das Element wurde bereits hinzugefügt. (z. B. über push_back)

Answer 5

Es gibt viele Vorteile, wenn Sie die STL verwenden, um Ihren Speicher gegenüber der Verwendung von new/delete zu verwalten. Die Entscheidung, 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; 
}; 

Answer 6

Pieter Vorschlag ist natürlich gut, aber eine Sache, die Sie im Auge zu behalten, ist, dass bei großen Arrays Gebäuden kann es recht langsam sein. Jedes Mal, wenn sich die Vektorkapazität ändert, müssen alle Daten kopiert werden ("n" Vektoren von Vektoren).

Answer 7

Unten ist eine einfache Möglichkeit zum Erstellen von 3D-Arrays mit C oder C++ in einem Stück Speicher für jedes Array. Es ist nicht nötig BOOST zu verwenden (auch wenn es nett ist), oder die Aufteilung zwischen Zeilen mit mehrfacher Indirection zu teilen (das ist ziemlich schlecht, da es normalerweise eine große Leistungseinbuße beim Zugriff auf Daten bedeutet und den Speicher fragmentiert).

Das einzige, was zu verstehen ist, dass es keine mehrdimensionalen Arrays gibt, nur Arrays von Arrays (von Arrays). Der innerste Index ist der am weitesten im Speicher.

#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 Ihre eigentliche Problem, als potentiell zwei unbekannte Dimensionen ist, gibt es ein Problem mit meinem Vorschlag es nur eine unbekannte Dimension ermöglichen. Es gibt mehrere Möglichkeiten, dies zu verwalten.

Die gute Nachricht ist, dass die Verwendung von Variablen jetzt mit C funktioniert, es heißt Arrays variabler Länge. Sie sehen here 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 C++ Der einfachste Weg ist wahrscheinlich Operator zu verwenden Überlastung mit Array-Syntax bleiben:

{ 
     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 hat einige indirection Kosten für InnerTwoDArray Zugriff (aber ein guter Compiler kann wahrscheinlich optimieren weg), verwendet jedoch nur einen Speicherblock für das Array, das auf dem Heap zugeordnet ist. Welches ist normalerweise die effizienteste Wahl.

Offensichtlich, auch wenn der obige Code immer noch einfach und unkompliziert ist, macht STL oder BOOST es gut, daher muss das Rad nicht neu erfunden werden. Ich glaube immer noch, dass es interessant ist zu wissen, dass es leicht gemacht werden kann.