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

Möglich ist es (siehe boost::multi_array) und gebraucht wird es öfters. Warum ist das nicht schon längst in der Standardbibliothek?

Marthog

Die Standardlibrary ist sehr langsam. Nachdem sie etwas aufgenommen haben, können sie es kaum noch verändern, ohne möglicherweise funktionierenden Code unbrauchbar zu machen. Deswegen nehmen sie nur Sachen auf, die aus ihrer Sicht ausreichend getestet sind und außerdem gibt es viel zu viele Anträge und längst nötige Updates.
Ich gebe dir aber recht und hätte auch gerne eine Klasse für mehrdimensionale Arrays.

An einem multi_array kann man doch kaum was falsch machen, oder etwa doch?

SeppJ

abbilder schrieb:

An einem multi_array kann man doch kaum was falsch machen, oder etwa doch?

An einem multi_array gibt es erst einmal viele verschiedene Arten und Weisen, wie man es implementieren kann, alle mit situationsabhängigen Vor- und Nachteilen. Welches ist die richtige Implementierung? Ein einfacher, schneller Wrapper um vector? Eine eierlegende Wollmilchsau wie das multi_array von Boost? Letzteres hatte, zumindest früher, deutliche Laufzeitnachteile, sofern man die Features nicht alle nutzte. Weiß nicht, ob das immer noch so ist. Jedenfalls gibt es auch gute Anwendungsszenarien für eine featurereichere Implementierung. Ein Templatemonster mit policy based Design, bei dem man jede Kleinigkeit der Implementierung feintunen kann, damit man nur das bezahlt, was man möchte? Möglich, aber sehr kompliziert in der Anwendung, würde das noch irgendjemand nutzen?

Du siehst, es mag möglich sein, aber es ist bei weitem nicht so einfach, wie du denkst.

Klaus82

abbilder schrieb:

Möglich ist es (siehe boost::multi_array) und gebraucht wird es öfters. Warum ist das nicht schon längst in der Standardbibliothek?

Ich kann doch std::vector ineinander verschachteln und so recht schnell einen 2D oder eben 3D Array konzipieren, auf den ich mittels vec[i][j][k] bequem zugreifen kann.

Edit:
Die Vorschaufunktion scheint noch nicht richtig zu funktionieren, ansonsten für den schnellen Tech-Support.

Gruß,
-- Klaus.

dot

Ein Ding aus verschachtelten std::vector ist aber halt leider kein dichtes Array, sondern eher sowas wie ein Jagged Array und keine besonders effiziente Lösung, wenn ein dichtes Array benötigt wird...

Klaus82

dot schrieb:

Ein Ding aus verschachtelten std::vector ist aber halt leider kein dichtes Array, sondern eher sowas wie ein Jagged Array und keine besonders effiziente Lösung, wenn ein dichtes Array benötigt wird...

Äh, was ist denn ein dichtes Array? Ich mache doch lediglich Zahlen anhand von Indizes zugänglich (Buchhaltung). Dabei ist es doch egal wie dicht diese beieinander liegen.

Oder soll zwischen diesen Zahlen noch interpoliert werden?

Gruß,
-- Klaus.

dot

Unter einem "dichten Array" verstehe ich ein Array, das kontinuierlich im Speicher liegt. Bei verschachtelten std::vector ist dies nicht der Fall, da hast du für jede Dimension eine zusätzliche Indirektion...

Klaus82

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

Allerdings gehe ich davon aus, dass dieses multiarray schneller ist als zwei oder drei verschachtelte vector ?

Ich sollte mir dieses multiarray anschauen, denn laut Scott Meyers führt kein Weg an Boost vorbei, wer ernsthaft C++ betreiben möchte.

Gruß,
-- Klaus.

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...

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

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...