Wie deklariere ich ein 2d-Array in C++ mit new?

Question

Wie deklariere ich ein 2d-Array mit new?

Bei einer "normalen" Anordnung würde ich das tun:

int* ary = new int[Size]

mais

int** ary = new int[sizeY][sizeX]

a) nicht funktioniert/kompiliert und b) nichts bewirkt:

int ary[sizeY][sizeX] 

tut.

Answer 1

Wenn Ihre Zeilenlänge eine Kompilierzeitkonstante ist, erlaubt C++11

auto arr2d = new int [nrows][CONSTANT];

Siehe diese Antwort . Compiler wie gcc, die Arrays mit variabler Länge als Erweiterung zu C++ zulassen, können die new wie hier gezeigt um die volle Funktionalität von Array-Dimensionen mit Laufzeitvariablen zu erhalten, wie es C99 erlaubt, aber portable ISO C++ ist darauf beschränkt, dass nur die erste Dimension variabel ist.

Eine andere effiziente Möglichkeit ist, die 2D-Indizierung manuell in einem großen 1D-Array durchzuführen, wie eine andere Antwort zeigt und ermöglicht die gleichen Compiler-Optimierungen wie ein echtes 2D-Array (z. B. den Nachweis oder die Überprüfung, dass sich Arrays nicht gegenseitig aliasieren/überlappen).

---

Andernfalls können Sie ein Array von Zeiger auf Arrays um eine 2D-Syntax wie zusammenhängende 2D-Arrays zu ermöglichen, auch wenn es sich nicht um eine effiziente einzelne große Zuweisung handelt. Sie können es mit einer Schleife initialisieren, etwa so:

int** a = new int*[rowCount];
for(int i = 0; i < rowCount; ++i)
    a[i] = new int[colCount];

Die oben genannten, für colCount= 5 y rowCount = 4 würde folgendes ergeben:

Vergessen Sie nicht delete jede Zeile separat mit einer Schleife, bevor das Array von Zeigern gelöscht wird. Beispiel in eine weitere Antwort .

Answer 2

int** ary = new int[sizeY][sizeX]

sein sollte:

int **ary = new int*[sizeY];
for(int i = 0; i < sizeY; ++i) {
    ary[i] = new int[sizeX];
}

und dann aufräumen würde:

for(int i = 0; i < sizeY; ++i) {
    delete [] ary[i];
}
delete [] ary;

EDITAR: Wie Dietrich Epp in den Kommentaren anmerkte, ist dies nicht gerade eine leichtgewichtige Lösung. Ein alternativer Ansatz wäre die Verwendung eines großen Speicherblocks:

int *ary = new int[sizeX*sizeY];

// ary[i][j] is then rewritten as
ary[i*sizeY+j]

Answer 3

Obwohl diese beliebte Antwort die gewünschte Indizierungssyntax liefert, ist sie doppelt ineffizient: groß und langsam, sowohl was den Platz als auch die Zeit angeht. Es gibt einen besseren Weg.

Warum diese Antwort groß und langsam ist

Die vorgeschlagene Lösung besteht darin, ein dynamisches Array von Zeigern zu erstellen und dann jeden Zeiger in sein eigenes, unabhängiges dynamisches Array zu initialisieren. Die Vorteil Der Vorteil dieses Ansatzes besteht darin, dass Sie die gewohnte Indizierungssyntax erhalten. Wenn Sie also den Wert der Matrix an der Position x,y finden wollen, sagen Sie:

int val = matrix[ x ][ y ];

Das funktioniert, weil matrix[x] einen Zeiger auf ein Array zurückgibt, das dann mit [y] indiziert wird. Aufgeschlüsselt:

int* row = matrix[ x ];
int  val = row[ y ];

Bequem, ja? Wir mögen unsere [ x ][ y ]-Syntax.

Aber die Lösung hat einen großen Nachteil Das heißt, sie ist sowohl fett als auch langsam.

Warum?

Der Grund dafür, dass es sowohl fett als auch langsam ist, ist eigentlich derselbe. Jede "Zeile" in der Matrix ist ein separat zugewiesenes dynamisches Array. Die Zuweisung eines Heaps ist sowohl zeit- als auch platzaufwendig. Der Allokator benötigt Zeit, um die Zuweisung vorzunehmen, und führt manchmal O(n)-Algorithmen aus, um dies zu tun. Und der Allokator "polstert" jedes Ihrer Zeilen-Arrays mit zusätzlichen Bytes für die Buchhaltung und Ausrichtung auf. Dieser zusätzliche Platz kostet... nun ja... zusätzlichen Platz. Der Deallocator wird auch Nehmen Sie sich mehr Zeit, wenn Sie die Zuordnung der Matrix aufheben wollen, indem Sie jede einzelne Zeilenzuordnung mühsam freigeben. Allein der Gedanke daran bringt mich ins Schwitzen.

Es gibt noch einen anderen Grund für die Langsamkeit. Diese separaten Zuweisungen neigen dazu, in unzusammenhängenden Teilen des Speichers zu liegen. Eine Zeile kann sich an der Adresse 1.000 befinden, eine andere an der Adresse 100.000 - Sie verstehen, was ich meine. Das bedeutet, dass man beim Durchlaufen der Matrix wie ein Wilder durch den Speicher springt. Dies führt in der Regel zu Cache-Misses, die die Verarbeitungszeit erheblich verlangsamen.

Wenn Sie also unbedingt Ihre hübsche [x][y]-Indexierungssyntax haben müssen, verwenden Sie diese Lösung. Wenn Sie schnell und klein sein wollen (und wenn Ihnen das egal ist, warum arbeiten Sie dann in C++?), brauchen Sie eine andere Lösung.

Eine andere Lösung

Die bessere Lösung ist es, Ihre gesamte Matrix als ein einziges dynamisches Array zuzuordnen und dann (etwas) clevere Indizierungsmathematik zu verwenden, um auf die Zellen zuzugreifen. Die Indizierung Mathe ist nur sehr geringfügig klug; nein, es ist überhaupt nicht klug: es ist offensichtlich.

class Matrix
{
    ...
    size_t index( int x, int y ) const { return x + m_width * y; }
};

Angesichts dieser index() Funktion (die, wie ich mir vorstelle, Mitglied einer Klasse ist, weil sie die m_width Ihrer Matrix), können Sie auf Zellen innerhalb Ihrer Matrixmatrix zugreifen. Das Matrix-Array wird wie folgt zugewiesen:

array = new int[ width * height ];

Das Äquivalent dazu ist also die langsame, fette Lösung:

array[ x ][ y ]

...ist dies die schnelle, kleine Lösung:

array[ index( x, y )]

Traurig, ich weiß. Aber Sie werden sich daran gewöhnen. Und Ihre CPU wird es Ihnen danken.

Answer 4

In C++11 ist dies möglich:

auto array = new double[M][N]; 

Auf diese Weise wird der Speicher nicht initialisiert. Um ihn zu initialisieren, tun Sie stattdessen Folgendes:

auto array = new double[M][N]();

Beispielprogramm (kompilieren mit "g++ -std=c++11"):

#include <iostream>
#include <utility>
#include <type_traits>
#include <typeinfo>
#include <cxxabi.h>
using namespace std;

int main()
{
    const auto M = 2;
    const auto N = 2;

    // allocate (no initializatoin)
    auto array = new double[M][N];

    // pollute the memory
    array[0][0] = 2;
    array[1][0] = 3;
    array[0][1] = 4;
    array[1][1] = 5;

    // re-allocate, probably will fetch the same memory block (not portable)
    delete[] array;
    array = new double[M][N];

    // show that memory is not initialized
    for(int r = 0; r < M; r++)
    {
        for(int c = 0; c < N; c++)
            cout << array[r][c] << " ";
        cout << endl;
    }
    cout << endl;

    delete[] array;

    // the proper way to zero-initialize the array
    array = new double[M][N]();

    // show the memory is initialized
    for(int r = 0; r < M; r++)
    {
        for(int c = 0; c < N; c++)
            cout << array[r][c] << " ";
        cout << endl;
    }

    int info;
    cout << abi::__cxa_demangle(typeid(array).name(),0,0,&info) << endl;

    return 0;
}

Ausgabe:

2 4 
3 5 

0 0 
0 0 
double (*) [2]

Answer 5

Ich nehme an, von Ihrem statischen Array Beispiel, dass Sie ein rechteckiges Array wollen, und nicht eine gezackte ein. Sie können das Folgende verwenden:

int *ary = new int[sizeX * sizeY];

Dann können Sie auf Elemente wie:

ary[y*sizeX + x]

Vergessen Sie nicht, delete[] zu verwenden ary .