Warum gibt es kein dynamisches mehrdimensionales Array in C++?

[otze]

Und die ist richtig teuer. In einem dichten Array kannst du so laufen, dass du nie durch den speicherspringst, sondern nur immer das nächste element im speicher verwendest. Dadurch kann der Cache schon die nächsten Speicherbereiche laden, während du noch das letzte Element verarbeitest. In einem jagged array ist das nicht der Fall. Die Geschwindigkeitsunterschiede sind enorm

[Skym0sh0]

Klaus82 schrieb:

... denn laut Scott Meyers führt kein Weg an Boost vorbei, wer ernsthaft C++ betreiben möchte.

[dot]

Klaus82 schrieb:

Okay,
das ist mir noch zu hoch - ich bin raus!

Ist nicht so kompliziert. Was ist denn ein std::vector? Im Prinzip nix anderes als ein Pointer auf einen Speicherbereich, in dem hintereinander die einzelnen Elemente liegen. Wenn du jetzt std::vector verschachtelst, bekommst du einen Pointer auf einen Speicherbereich in dem Pointer auf weitere Speicherbereiche liegen. Wenn du nun per Index auf ein Element zugreifen willst, musst du erstmal den ersten Pointer lesen, ausrechnen wo der Pointer auf die nächste Ebene zu finden ist, diesen lesen, basierend auf diesem ausrechnen, wo die nächste Ebene zu finden ist usw. Wenn stattdessen einfach N1×N2×N3×... Elemente in einen zusammenhängenden Speicherbereich packst (was man normalerweise unter einem mehrdimensionalen Array versteht), kannst du die Adresse eines Elementes direkt ausrechnen und direkt drauf zugreifen...

[Ruvi++]

Ich bin noch neu in C++ aber ich haette was das Thema angeht eine Fragen.

Warum biegt ihr euch ein richtiges Array oder einen vector nicht einfach zu einem mehrdimensionalen Array um?

Ich habe einen Map(Spielfeld) Generator geschrieben und habe einfach eine Index-Schicht oben drueber gezogen.

Ich joine den Vector/Array dann mit x und y koordinaten die ich dann nachher auf den richtigen Index umrechne.

Breite des (Pseudo)Arrays * Y + X = Index im Vector/Array.

[Klaus82]

Ruvi++ schrieb:

Warum biegt ihr euch ein richtiges Array oder einen vector nicht einfach zu einem mehrdimensionalen Array um?

Du meinst warum man aus einer 3 x 4 Matrix nicht einfach einen Vektor mit 12 Einträgen macht? Immerhin geht es nur darum über 12 Elemente Buch zu führen?

Gruß,
-- Klaus.

[SeppJ]

Ruvi++ schrieb:

Warum biegt ihr euch ein richtiges Array oder einen vector nicht einfach zu einem mehrdimensionalen Array um?

Ich behaupte mal, der Threadersteller möchte nur provozieren. Das was du beschreibst ist eine übliche und gute Methode. Die ist dem TE auch sicherlich bekannt. Er fragt sich (wenn es keine Scherzfrage ist), warum das nicht der Standard ist.

[Ruvi]

Klaus82 schrieb:

Du meinst warum man aus einer 3 x 4 Matrix nicht einfach einen Vektor mit 12 Einträgen macht? Immerhin geht es nur darum über 12 Elemente Buch zu führen?

Gruß,
-- Klaus.

Ja, genau.
Bei einem "normalen" mehrdimensionalen Array bekommt (soweit ich das verstanden habe) jedes einzelne Array seinen eigenen Platz im Speicher.

Das bedeutet du hast bei e.g. Array[1024][1024]; 1024 einzelne Arrays verteilt im Speicher liegen die "verpointert" wurden.

Ich persoenlich nutze wann immer es moeglich ist eindimensionale Arrays auf die ich eine "Index" Schicht lege.

[SeppJ]

Ruvi schrieb:

Ja, genau.
Bei einem "normalen" mehrdimensionalen Array bekommt (soweit ich das verstanden habe) jedes einzelne Array seinen eigenen Platz im Speicher.

Dann hast du das falsch verstanden.

Das bedeutet du hast bei e.g. Array[1024][1024]; 1024 einzelne Arrays verteilt im Speicher liegen die "verpointert" wurden.

Nein, dies ist im Speicher eine lange, zusammenhängende Struktur. Du denkst an die schreckliche Unsitte ein 2D-Array so zu gestalten (Miner Erfahrung nach besonders in C beliebt):

int **Array = malloc(10 * sizeof(*Array));
for(int i = 0; i < 10; ++i)
 Array[i] = malloc(20 * sizeof(*Array[i]));

oder C++:

vector<vector<int>> Array(10, vector<int>(20));

[Korintenkacker]

Ruvi schrieb:

Das bedeutet du hast bei e.g. Array[1024][1024]; 1024 einzelne Arrays verteilt im Speicher liegen die "verpointert" wurden.

Ich persoenlich nutze wann immer es moeglich ist eindimensionale Arrays auf die ich eine "Index" Schicht lege.

Das ist so erstmal ungenau, wenn nicht sogar falsch. Wie bereits in diesem Thread weit und breit erklärt stimmt die Behauptung so für std::vector.

Aber schreibt man etwa Folgendes,

int var[3][4];

so liegt das Array durchaus zusammenhängend im Speicher. IIRC Werden zunächst alle Zellen der ersten Zeile in den Speicher gelegt, dann die der zweiten Zeile, dann die der Dritten usw.

[Columbo]

Dann hast du das falsch verstanden.

Nein, das hat er, soweit ich sehen kann, voellig richtig verstanden.

int arr[8][8];

Ist ein Array von 8 Arrays von int s. Jedes hat seinen eigenen Speicher; So zumindest interpretiere ich seine Aussage.

die "verpointert" wurden.

Was soll denn das heissen?

[dot]

Ein int array[42][3]; liegt zusammenhängend im Speicher, da es sich um ein Array aus 3 Arrays aus 42 int handelt. Arrays liegen zusammenhängend im Speicher, in einem Array aus Arrays liegen eben Arrays zusammenhängend im Speicher, deren Elemente wiederum zusammenhängend im Speicher liegen; zwangsweise liegt da also alles zusammenhängend im Speicher...

[Ruvi]

SeppJ schrieb:

Nein, dies ist im Speicher eine lange, zusammenhängende Struktur. Du denkst an die schreckliche Unsitte ein 2D-Array so zu gestalten (Miner Erfahrung nach besonders in C beliebt):

int **Array = malloc(10 * sizeof(*Array));
for(int i = 0; i < 10; ++i)
 Array[i] = malloc(20 * sizeof(*Array[i]));

Ja, du hast Recht.
Ich habe daran gedacht, mein Fehler.

Edit:

Hier nochmal um keine Verwirrung aufkommen zu lassen.

Short = 2 byte.

short a[2][2];
	a [1][1] = 1;
	a [1][2] = 2;
	a [2][1] = 3;
	a [2][2] = 4;

	cout<<	&a [1][1] << endl;
	cout<< 	&a [1][2] << endl;
	cout<<	&a [2][1] << endl;
	cout<<	&a [2][2] << endl;

e.g. Speicherbereich:
0045F776 (+2)
0045F778 (+2)
0045F77A (+2)
0045F77C

[SeppJ]

Arcoth schrieb:

Dann hast du das falsch verstanden.

Nein, das hat er, soweit ich sehen kann, voellig richtig verstanden.

int arr[8][8];

Ist ein Array von 8 Arrays von int s. Jedes hat seinen eigenen Speicher; So zumindest interpretiere ich seine Aussage.

Ich bin ziemlich sicher, dass du das falsch verstanden hast. Diese Aussage wäre trivial.

die "verpointert" wurden.

Was soll denn das heissen?

Hier ist die entscheidende Erläuterung. Es handelt sich laut Ruvi um unabhängige 1D-Arrays und eine Sammlung von Pointern auf diese. Also so, wie es gerade nicht gemacht werden sollte und wie es hier auch nicht ist.

edit: Hat sich inzwischen ja geklärt.

[Caligulaminus]

dot schrieb:

Ein int array[42][3]; liegt zusammenhängend im Speicher, da es sich um ein Array aus 3 Arrays aus 42 int handelt.

Fast. Es sind 42 Arrays aus 3 int.

~Die Vorschau spinnt bei Verwendung von Umlauten.~

[dot]

Caligulaminus schrieb:

dot schrieb:

Ein int array[42][3]; liegt zusammenhängend im Speicher, da es sich um ein Array aus 3 Arrays aus 42 int handelt.

Fast. Es sind 42 Arrays aus 3 int.

stimmt natürlich...

[Duji-Buji]

SeppJ schrieb:

Du denkst an die schreckliche Unsitte ein 2D-Array so zu gestalten (Miner Erfahrung nach besonders in C beliebt):

int **Array = malloc(10 * sizeof(*Array));
for(int i = 0; i < 10; ++i)
 Array[i] = malloc(20 * sizeof(*Array[i]));

oder C++:

vector<vector<int>> Array(10, vector<int>(20));

Wieso sollte man das denn nicht so machen?
Und ich hoffe niemand ist mir böse, weil dieses Thema schon 2 Monate alt ist

[dot]

Duji-Buji schrieb:

SeppJ schrieb:

Du denkst an die schreckliche Unsitte ein 2D-Array so zu gestalten (Miner Erfahrung nach besonders in C beliebt):

int **Array = malloc(10 * sizeof(*Array));
for(int i = 0; i < 10; ++i)
 Array[i] = malloc(20 * sizeof(*Array[i]));

oder C++:

vector<vector<int>> Array(10, vector<int>(20));

Wieso sollte man das denn nicht so machen?

Kurze Antwort: Weil es ineffizient und auch semantisch verschieden von einem richtigen 2D Array ist...

[c++coder11]

bau dir halt deine eigene array class (siehe beispiel) oder nimm std::array...

#include <iostream>
#include <vector>
using namespace std;

class MyArray {
	private:
		vector<int> vec;
		int size_x;
		int size_y;

	public:
		MyArray(int dim_x, int dim_y): size_x(dim_x), size_y(dim_y) {
			vec.resize(size_x*size_y);
		}

		void set_x_y(int x, int y, int val) {
			int index = x * size_x + y;
			vec[index] = val;
		}

		int get_x_y(int x, int y) {
			int index = x * size_x + y;
			return vec[index];
		}
};

int main() {
	// your code goes here
	MyArray arr(2,2);

	arr.set_x_y(1, 1, 22);
	cout << arr.get_x_y(1, 1) << endl;

	return 0;
}