Erklärung des Codes einer Klasse mit überladenem Operator

[Ceryl]

Hallo,

kann mir jemand bitte aus folgendem Codebeispiel diverse Stellen
erklären? Ich beschäftige mich zwar schon seit einiger Zeit nun mit
C++, aber leider bin ich nie auf diese Dinge gestoßen und diese
Probleme über eine Suchmaschine zu lösen stellt sich als eher
schwierig vor, zunächst aber hier erst einmal der Code.

template< typename DataType >
  class Matrix
{
public:
  Matrix()
    : Array_m( 0 ),
      Rows_m( 0 ),
      Cols_m( 0 )
  {}

  Matrix( unsigned int Rows_Init, unsigned int Cols_Init )
    : Array_m( new DataType[ Rows_Init * Cols_Init ] ),
      Rows_m( Rows_Init ),
      Cols_m( Cols_Init )
  {}
  ~Matrix() { delete [] Array_m; }
  DataType* const operator[]( unsigned int Row )
  {
    return Array_m + Row * Cols_m;
  }
  const DataType* const operator[]( unsigned int Row ) const
  {
    return Array_m + Row * Cols_m;
  }
private:
  DataType* Array_m;
  unsigned int Rows_m,
                      Cols_m;
};

(Quelle: http://cboard.cprogramming.com/cplusplus-programming/37843-two-dimensional-dynamic-array.html)

Der Code dient dazu in C++ eine dynamische zweidimensionale Matrix
zu simulieren. Größtenteils ist das die normale Struktur einer Klasse,
aber einige Dinge habe ich noch nie zuvor gesehen:

1. Die Verwendung vom Doppelpunkt in Zeile 6 und 12. Ist das eine
andere Form der Funktion die Parameter zu übergeben? Ergeben sich daraus
andere Vorteile/Nachteile?
2. delete [] Array_m gibt einfach nur den Speicher der Matrix frei
(sonst würde es wohl nicht im Destruktor stehen), richtig? Aber wann
wird diese Funktion dann überhaupt aufgerufen? Ich kenne es aus anderen
Sprachen wie Java nämlich so, dass das gar nicht nötig ist und es dort
von selbst erledigt wird.
3. DataType* const operator[]( unsigned int Row ) ist mir völlig suspekt:
Ist das const hier notwendig? Eigentlich steht es doch für Konstante Werte,
aber damit kann hier nur der operator[] gemeint sein; ein paar Zeilen weiter
(Z.21) wird es sogar noch einmal vor der Klammer verwendet. Warum? So habe
ich die Anwendung noch nie gesehen.
4. Vielleicht ergibt sich diese Frage dann von selbst, momentan ist sie
aber schwer ohne den Code wirklich zu verstehen: Was müsste ich tun, um
noch eine Dimension für das Array hinzuzufügen? Einfach nur die Parameter
um einen weiteren zu erhöhen hilft nicht.

[CStoll]

1. Das nennt sich Initialisierungsliste und dient dazu, die Datenelemente der Klasse direkt zu füllen. (ist nur in Konstruktoren erlaubt)
Der Vorteil davon ist, daß das Element nicht erst mit einem Defaultwert vorbelegt werden muß, bevor es der echte Wert dort reingepackt wird. Außerdem gibt es Situationen, in denen du ohne sowas nicht auskommst (konstante Elemente, Referenzen, Klassen ohne Default-Konstruktor).

2. In C++ muß jeder Speicher, der per new angefordert wurde, auch selber wieder per delete freigegeben werden, weil wir hier keinen Garbage-Collector haben der sich darum kümmern würde. Der Destruktor wird auf jeden Fall dann aufgerufen, wenn der Gültigkeitsbereich einer Variable verlassen wird (im Gegensatz zu GC-Sprachen wie Java oder C# sofort) - und diese Variable zerstört wird.

void test()
{
  Matrix m1(10,10);
  ...
}//hier endet der Gültigkeitsbereich für m1 und der Destruktor wird aufgerufen

Btw, der Code verletzt die Regel der Drei - du hast zwar einen Destruktor, aber weder einen passenden Kopier-Konstruktor noch einen Zuweisungsoperator.

3. Das const bezieht sich auf den zurückgegebenen Zeiger - d.h. der Aufrufer kann zwar die Werte verändern, aber nicht den Zeiger umbiegen. Im zweiten Operator (der für konstante Objekte verwendet wird) kann er auch die Werte nicht ändern).
Aber ich würde überhaupt keine Zeiger an den Aufrufer zurückgeben, sondern stattdessen auf operator() für den Index-Zugriff ausweichen.

4. Zusätzlichen Member für die Ebenenzahl, weiteren Konstruktorparameter anlegen und aus operator[] eine zweidimensionale Hilfsstruktur zurückgeben.

[314159265358979]

Diese Implementierung ist ziemlich schlecht. Ein einfacher std::vector<std::vector<T>> hätte es schon getan.

Den Rest hat CStoll ja schon erklärt.

Edit: Vielleicht wäre std::valarray besser, dazu kenne ich das Ding aber zu wenig.

[Ceryl]

Vielen Dank für die Antworten, das erklärt schon mal einiges!

Zum Thema vector... bei der von mir geposteten Quelle wurde da schon
einiges dazu diskutiert; das Hauptargument für diese Lösung vom Poster
war, dass die vorherige Lösung 20 Pointer erfordert hat und wohl etwas
langsamer war. Von vector war da gar nicht die Rede, sehe ich gerade...
und ich dachte schon einen vector zu benutzen würde mir am Ende
irgendwo Nachteile bringen :).
Ganz so wie 2D Matrizen verhalten sie sich aber dann doch nicht, wie ich
gelesen habe, die Werte sind irgendwie unabhängiger von einander und man
muss mit den Iteratoren aufpassen, aber dazu lese ich mich dann eben
etwas ein.

Danke nochmal!

[314159265358979]

vector hat nur Vorteile. Er nimmt dir das Verwalten des Speichers ab.

[pumuckl]

314159265358979 schrieb:

vector hat nur Vorteile. Er nimmt dir das Verwalten des Speichers ab.

Du schreibst "nur Vorteile", nennst aber nur einen. Einen Performance-vorteil hat dein 2D-Vector zum Beispiel nicht, weil bei Zugriffen die doppelte Indirektion über die Datenpointer in Kauf genommen wird, verglichen zu nur einer Indirektion in der vorliegenden Implementierung. Außerdem liegen beim 2D-vector im Ernstfall die verschiedenen Zeilen über den gesamten Heap verteilt, im vorliegenden Fall am Stück. Das macht vor allem dann was aus, wenn du im gesamten Bereich lesen/schreiben musst. Während der vorliegende Einzelblock vermutlich in ein oder zwei Pages in den Cache geschoben werden kann, musst du mit dem 2D-vector schlimmstenfalls so viele Seiten laden, wie du Zeilen hast. Mit solchen Aussagen wie "nur Vorteile" wäre ich also doch eher vorsichtig.

[314159265358979]

Er stellt sicher, dass operator = und matrix(const matrix&) richtig funktionieren, in C++0x auch die Move-Funktionen.

Aber ich sehe auch keinen Grund, die Größe der Matrix erst zur Laufzeit festzulegen. Da ist eine Matrix<X, Y, T> sinnvoller, man denke an die Matrizenmultiplikation. Dann kann man auch std::array verwenden. -> Speicher an einem Block.

[Ceryl]

Das ganze ist für eine Tilemap, die in ein Spiel geladen werden soll.
Dabei ist die Datei aus mehreren Long-Werten aufgebaut und die ersten
zwei Long-Werte sollen mir angeben, wie groß die Karte ist und anhand
davon wird dann die Matrix erstellt.
Das geht aber leider nicht, weil C++ bei Matrizen konstante Werte
verlangt. Deshalb muss ich sie zur Laufzeit festlegen.
Fraglich ist nur ob das bei einer vergleichsweisen so einfachen Anwendung
wirklich erhebliche Nachteile hätte.

[krümelkacker]

314159265358979 schrieb:

Diese Implementierung ist ziemlich schlecht.

Ja. Die Dreierregel wurde verletzt.

314159265358979 schrieb:

Ein einfacher std::vector<std::vector<T>> hätte es schon getan.

Naja, ein lineares Speicherlayout hat auch Vorteile. vector<vector<T>> ist da nicht immer die beste Idee.

'gibt auch noch boost::multi_array.

[otze]

314159265358979 schrieb:

Aber ich sehe auch keinen Grund, die Größe der Matrix erst zur Laufzeit festzulegen.

Ausser zum Beispiel, wenn man den Datensatz aus einer Datei ließt und nicht weiß, wie viele Werte ein Datensatz haben kann. Ausserhalb der Spieleprogrammierung ist das der Standardfall.

Da ist eine Matrix<X, Y, T> sinnvoller, man denke an die Matrizenmultiplikation.

Hab ich alles mal ausgemessen. Zur Compilezeit bekannte Grenzen helfen nur sehr selten, weil die Compiler eh vektorisierten Code erzeugen. Speicher am Stück hingegen ist super wichtig. Da hauste dir mal locker Faktor 3 mit rein wenn du vector<vector<T> > verwendest.

[SeppJ]

krümelkacker schrieb:

'gibt auch noch boost::multi_array.

Das ist übrigens auch übelst langsam, wenn wir hier schon von Performance sprechen. Ein guter alter 1D-vector mit einem kleinen Wrapper für 2D drumherum ist bei performancekritischen Sachen doch wohl noch immer mit unter den besten und gleichzeitig noch komfortabel.

[314159265358979]

otze schrieb:

314159265358979 schrieb:

Aber ich sehe auch keinen Grund, die Größe der Matrix erst zur Laufzeit festzulegen.

Ausser zum Beispiel, wenn man den Datensatz aus einer Datei ließt und nicht weiß, wie viele Werte ein Datensatz haben kann. Ausserhalb der Spieleprogrammierung ist das der Standardfall.

Ja, da hast du natürlich Recht. Hier habe ich zu beschänkt gedacht.

otze schrieb:

314159265358979 schrieb:

Da ist eine Matrix<X, Y, T> sinnvoller, man denke an die Matrizenmultiplikation.

Hab ich alles mal ausgemessen. Zur Compilezeit bekannte Grenzen helfen nur sehr selten, weil die Compiler eh vektorisierten Code erzeugen. Speicher am Stück hingegen ist super wichtig. Da hauste dir mal locker Faktor 3 mit rein wenn du vector<vector<T> > verwendest.

Ich meinte eher wegen der Fehlerüberprüfung zur Compilezeit.

[camper]

SeppJ schrieb:

krümelkacker schrieb:

'gibt auch noch boost::multi_array.

Das ist übrigens auch übelst langsam, wenn wir hier schon von Performance sprechen. Ein guter alter 1D-vector mit einem kleinen Wrapper für 2D drumherum ist bei performancekritischen Sachen doch wohl noch immer mit unter den besten und gleichzeitig noch komfortabel.

Hast du dafür Benchmarks?

[SeppJ]

camper schrieb:

SeppJ schrieb:

krümelkacker schrieb:

'gibt auch noch boost::multi_array.

Das ist übrigens auch übelst langsam, wenn wir hier schon von Performance sprechen. Ein guter alter 1D-vector mit einem kleinen Wrapper für 2D drumherum ist bei performancekritischen Sachen doch wohl noch immer mit unter den besten und gleichzeitig noch komfortabel.

Hast du dafür Benchmarks?

Jain. Ich habe das mal früher durch Profiling in einem meiner Projekte als Flaschenhals ausgemacht. Das war so arg langsam, dass es selbst in der zweitinnersten Schleifenebene die Performance des Gesamtprogramms um 50% gegenüber dem 1D-vector gedrückt hat. Was habe ich gemacht? Bei jedem Durchgang ein 2D-Array mit dynamsicher Größe erzeugt, in der innersten Schleife ein paar Werte da rein geschriebnen und hinterher alle Werte zusammen gezählt. Besonders letzteres war übelst lahm. Das acuumulate das ich jetzt drin habe ist so unendlich viel schneller, dass es im Profiler gar nicht sichtbar auftaucht, während vorher diese eigentlich triviale Funktion ein dicker Batzen der Gesamtlaufzeit war. Und ja: Ich habe die Makros gesetzt, die die Bereichsprüfung ausschalten.

Ich kann dir also keinen konkreten Benchmark geben, der zeigt wo und warum es versagt, sondern nur dieses Praxisbeispiel, welches du mir einfach glauben musst, da ich den Code hier nicht zeigen kann. Ein Benchmark wäre auch mal interessant, aber ist mir nicht wichtig genug, um einen zu schreiben. Ich bin jedenfalls nun glücklich mit meiner allgemeinen Wrapperklasse die ich auf alle 2D-Probleme anwenden kann. Ist zwar bei weitem nicht so flexibel und mächtig wie boost::multi_array, aber wenn dessen Vorteile auf Kosten der Laufzeit gehen, dann lehne ich dankend ab.

[otze]

314159265358979 schrieb:

Ich meinte eher wegen der Fehlerüberprüfung zur Compilezeit.

In der Theorie gut, in der Parix selten Sinnvoll. In den Szenarios in denen du deine Größen kennst, wirst du selten unterschiedlich große Matrizen haben. Dynamisch ist natürlich nicht so konfortabel, aber ich komme gut mit meinen SIZE_CHECK() Makros im Debug Modus klar. Müssen die Unit Tests halt gescheit sein

@camper

simpler Benchmark(eventuell noch Syntaxfehler drin, ich tipp das hier nur runter):

const unsigned int SizeX = 100;
const unsigned int SizeY = 256;
const unsigned int Runs = 100;

double array[SizeX][SizeY];//ground truth data
std::vector<std::vector<double> > arraySlow(SizeX,std::vector<double>(SizeY));
for(unsigned int x = 0; x!= SizeX;++x){
   for(unsigned int y = 0; y!= SizeY;++y){
       array[x][y]=x+y;//oder rand oder whatever
       arraySlow[x][y]=x+y;
   }
}

//version1:
double result = 0;
for(unsigned int r = 0; r != Runs; ++r){
    for(unsigned int x = 0; x!= SizeX;++x){
       for(unsigned int y = 0; y!= SizeY;++y){
           result+=array[x][y];
   }
}

//version2:
double result2 = 0;
for(unsigned int r = 0; r != Runs; ++r){
    for(unsigned int y = 0; y!= SizeY;++y){//nur vertauscht!
        for(unsigned int x = 0; x!= SizeX;++x){
           result2+=array[x][y];
        }
    }
}

//version3:
double result3 = 0;
for(unsigned int r = 0; r != Runs; ++r){
    for(unsigned int x = 0; x!= SizeX;++x){
       for(unsigned int y = 0; y!= SizeY;++y){
           result3+=arraySlow[x][y];//nur vector statt array
   }
}

Den Zeitmesscode musst du natürlich selbst einbauen. Version 2 sollte gegen Version 1 mit steigendem SizeY immer krasser abfallen. Version3 sollte immer schlechter oder maximal gleich gut wie Version2 sein. Version 2 und 3 kranken am selben Problem: Cache Misses

[314159265358979]

Und wie siehts aus mit new double[x*y] ?

[otze]

Äquivalent zu version 1 weil das Array dicht ist.

[314159265358979]

Musst aber die Allokation draufrechnen.

[otze]

kannste ja selbst machen. Ich kümemre mich nicht um konstante Terme wenn dagegen Algorithmen stehen die 10000 mal häufiger auf den Daten aufgerufen werden.

[camper]

otze schrieb:

Version 2 sollte gegen Version 1 mit steigendem SizeY immer krasser abfallen.

Belibt die spannende Frage, ob der Compiler damit besser umgehen kann, wenn fastmath erlaubt ist (loop interchange).