Matrix mittels Pointer deklarieren

TFTomSun

hallo,

wie kann ich eine Matrix (zb n x n) mittels pointer deklarieren. Ein Vektor kann ich ja wie folgt erzeugen:

int n=10
BYTE *pByteVektor = new BYTE[n];

damit kann ich ja dann mittels BYTE[0],BYTE[1], ...,usw. auf die einzelnen Werte zugreifen

Aber wie mach ich das, dass ich am ende eine Matrix erzeuge so dass ich wie folgt drauf zugreifen kann. ( BYTE[0][0]=,BYTE[1][0]=,BYTE[n][n]= ... usw.)

danke schonmal

mfg, TFTS

CStoll

Wenn du beide Dimensionen erst zur Laufzeit kennst, bleibt dir nur manueller Aufbau:

BYTE **pMatrix = new BYTE*[ncol];
for(int i=0;i<ncol;++i)pMatrix[i]=new BYTE[nrow];
//...
for(int i=0;i<ncol;++i)delete[]pMatrix[i];
delete[]pMatrix;

(ich würde die ganze Verwaltung in eine eigene Klasse packen)

Wenn du die Zeilennzahl zur Compilezeit kennst, geht noch so etwas:

BYTE *pMatrix[nrow] = new BYTE[nrow][ncol];//oder war's umgekehrt?
//...
delete[]pPatrix;

Plan C wäre, ganz auf Pointer zu verzichten und einen vector<vector<BYTE> > zu verwenden.

evilissimo

Erstellen:

size_t n = 10;

BYTE ** vec2d = new BYTE*[n];
for(size_t i = 0 ; i < n; ++i)
   vec2d[i] = new BYTE[n];

Löschen:

for(size_t i = 0 ; i < n; ++i)
   delete[] vec2d[i];
delete[] vec2d;

TFTomSun

vielen dank!

Werner Salomon

CStoll schrieb:

ich würde die ganze Verwaltung in eine eigene Klasse packen

Genau!

man muss ja nicht gleich mit dem großen Holzhammer ala boost.uBlas oder ähnlichen kommen. Schon wenn man sich auf wenig beschränkt - etwa so wie dies

// Datei: simple_matrix.h
#include <algorithm>  // std::fill

template< typename T >
class Matrix
{
public:
    typedef T value_type;

    Matrix( int nRow, int nCol )
        : m_nCol( nCol )
        , m_ptr( new value_type[ nCol * nRow ] )
    {
        std::fill( m_ptr, m_ptr + nCol * nRow, value_type(0) );
    }
    ~Matrix() { delete[] m_ptr; }

    value_type* operator[]( int iRow )
    {
        return m_ptr + iRow * m_nCol;
    }
private:
    int m_nCol;
    value_type* m_ptr;

    // -- einfachste Matrix-Variante ist nicht kopierbar
    Matrix( const Matrix& );
    Matrix& operator=( const Matrix& );
};

.. hat man faustdicke Vorteile (s.u.).

Die Anwendung ist absolut identisch zu einem statischen 2D-Array. Zum Beispiel

#include "simple_matrix.h"
#include <iostream>

int main()
{
    int arr[2][5]; // statisches 2D-Array
    arr[1][2] = 8;
    arr[1][3] = 9;
    Matrix< int > mx(2, 5); // dynamisch
    mx[1][2] = 8;
    mx[1][3] = 9;

    std::cout << "Element[1][2] = " << mx[1][2] << std::endl;
    return 0;
}

Die drei entscheidenden Vorteilen:
- die Größe der Matrix ist zur Laufzeit dynamisch wählbar
- kein Löschen der Elemente notwendig (kein potentielles Memory-Leak)
- Alle Elemente sind nach Anlegen der Matrix initialisiert

Zeitnachteile beim Zugriff sollten - zumindest theoretisch - keine auftreten. Wenn man die Klasse noch etwas aufpoppt- z.B. Zugriff auf einzelne Reihen oder Spalten - so darf man sogar Performance-Vorteile gegenüber einen Zugriff mit Indizes zu erwarten.

Gruß
Werner

TFTomSun

wow ... das klingt recht interessant ... gibts da vielleicht noch eine kleine quellcode kommentierung dazu? ... so wie es scheint übersteigt das meinen momentanen C-Wissensstand

mfg, TFTS

Werner Salomon

Hallo TFTS,

es wäre einfacher für mich, wenn Du konkrete Fragen zum Code stellst. Ansonsten kann man viel dazu erzählen. Ich versuch's erstmal mit Kommentaren

#include <algorithm>  // std::fill

template< typename T >
// die Klasse ist als Template realisiert, so dass sich der Anwender den Typ der Elemente
// aussuchen kann (int, double, BYTE, o.a.)
class Matrix
{
public:
    typedef T value_type;

    // im Konstruktor wird jedes Member (s.u.) in der Initialisierungsliste 
    // initialisiert
    // 'nRow' ist die Anzahl (number) der Zeilen (row); 'nCol' die der Spalten (column)
    Matrix( int nRow, int nCol )
        : m_nCol( nCol )   // die Anzahl der Spalten für operator[] merken
        , m_ptr( new value_type[ nCol * nRow ] ) // Memory für Elemente allokieren
    {
        // alle Elemente werden mit ihrem Default-Wert vorbelegt
        std::fill( m_ptr, m_ptr + nCol * nRow, value_type() );
    }
    ~Matrix() { delete[] m_ptr; }  // im Destruktor Memory wieder freigeben

    // der operator[] liedert den Pointer auf das erste Element der Zeile(row) 'iRow'
    value_type* operator[]( int iRow )
    {
        return m_ptr + iRow * m_nCol;
    }
private:
    int m_nCol;  // Anzahl der Spalten der Matrix
    value_type* m_ptr; // Pointer auf das erste Element

    // -- einfachste Matrix-Variante ist nicht kopierbar
    //  (siehe auch 'rule/law of the big 3')
    //  der Destruktor ist nicht trivial (s.o.), folglich muss man sich auch über den
    //  Kopie-Konstruktor und Zuweisungsoperator Gedanken machen.
    //  Am einfachsten ist, beide stillzulegen (private), dann kann sie niemand benutzen
    //  und es gibt keine Probleme
    Matrix( const Matrix& );
    Matrix& operator=( const Matrix& );
};

Wenn man in C oder C++ ein zweidimensinales Array anlegt, dann wird der Speicher zeilenweise organisiert. Z.B. bei einer 3x4 Matrix mit 3 Zeilen und 4 Spalten liegen die Elemente a_ij so im Speicher:

a00 a01 a02 a03 a10 a11 a12 a13 a20 a21 a22 a23
Index im Speicher  0   1   2   3   4   5   6   7   8   9   10  11

oder die Indizes in Matrix-Form

[ 0   1   2   3  ]
    [ 4   5   6   7  ]
    [ 8   9   10  11 ]

Der Member 'm_ptr' zeigt auf das 0.Element 'a00'. Um an das Element a21 bez. a[2][1] ranzukommen, arbeitet man sich zunächst zum Anfang der Zeile mit dem Index 2 vor. Dazu muss man die Länge einer Zeile kennen; nämlich die Anzahl der Spalten -> Member 'm_nCol' - hier im Beispiel 4.
Folglich zeigt der Ausdruck m_ptr + 2 * 4 auf das 0.Element der Zeile mit dem Index 2 - also a20 (Memory-Index 8). In C und C++ kann man mit [] auf diesen Pointer noch einen Offset aufschlagen um dann zum gewünschte Element zu kommen. In Code sähe das etwa so aus

int* m_ptr = new int[12]; // Platz für eine 3x4-Matrix
    int* pZeile2 = m_ptr + 2*4; // zeigt jetzt auf Element a20
    pZeile2 + 1; // zeigt 1 weiter also a21
    pZeile2[1];  // identisch zu *(pZeile2 + 1)
    // jetzt ist der Zugriff auf a21 da
    pZeile2[1] = ...; // schreiben
    int i = pZeile2[1]; // lesen

Der Matrix::operator[] (s.o.) macht nicht anderes als den Pointer 'pZeile2' zu liefern und das angehängte ['Index der Spalte'] realisiert dann den Zugriff auf das gewünschte Element.

Matrix< int > a(3, 4);
    int* pZeile2 = a[2];
    pZeile2[1]; // Zugriff auf a[2][1]

Gruß
Werner

TFTomSun

und wann wird der speicher einer matrix wieder freigegeben? wenn ich eine neue matrix erzeuge? das würde ja heissen irgendwann wird der dekonstruktor aufgerufen, richtig? bloß wann?

mfg, TFTS

Der DTor wird erst aufgerufen, wenn Du den scope verläßt, in dem das objekt erzeugt wurde.

Bsp:

int main()
{
    Matrix< int > mx(2, 5);
    Matrix< int > mx2(3, 7);

    return 0;
}//Hier wird erst der DTor von mx2 und dann der von mx aufgerufen

camper

Matrix( int nRow, int nCol )
        : m_nCol( nCol )   // die Anzahl der Spalten für operator[] merken
        , m_ptr( new value_type[ nCol * nRow ] ) // Memory für Elemente allokieren
    {
        // alle Elemente werden mit ihrem Default-Wert vorbelegt
        std::fill( m_ptr, m_ptr + nCol * nRow, value_type() );
    }

new und dann fill_n ist nicht zweckmässig. wenn T ein POD ist, spielt es zwar keine rolle, aber diese information hast du nicht. zweckmässiger ist ein zusätzlicher parameter und direkte initialisierung (wenn du willst, kannst du auch noch einen haufen template-konstruktoren angeben, die dann alle möglichen parameter aufnehemn, falls T nicht copy-konstruiert werden sollen):

Matrix( int nRow, int nCol, const value_type& init = value_type()  )
        : m_nCol( nCol )   // die Anzahl der Spalten für operator[] merken
        , m_ptr( new value_type[ nCol * nRow ]( init ) ) // Memory für Elemente allokieren und initialisieren
    { }

zweitens ist es evtl. zweckmässig mit vorzeichenlosen typen (am besten std::size_t) für die arraygrenzen zu arbeiten. vorzeichenbehaftete typen für werte, die prinzipiell nie negativ werden können, zu benutzen macht stets nur probleme.

Werner Salomon

camper schrieb:

new und dann fill_n ist nicht zweckmässig. wenn T ein POD ist, spielt es zwar keine rolle, aber diese information hast du nicht.

Meine Güte; Du hast völlig Recht. Das sollte mir eigentlich nicht mehr passieren

Bei näherer Betrachtung ist mir dann auch aufgefallen, dass der Konstruktor nicht exception-sicher ist. const-correctness fehlt auch - das wußte ich vorher. Ich wollte den OP nicht überfrachten. Aber jetzt kommt es wohl nicht mehr drauf an.

Auf die Gefahr hin, dass der arme TFTS jetzt völlig verwirrt wird. Hier der zweite Versuch:

#include <memory>   // std::uninitialized_fill_n
#include <cstddef>  // std::size_t

template< typename T >
class Matrix
{
public:
    typedef T value_type;
    typedef std::size_t size_type;

    // 'nRow' ist die Anzahl (number) der Zeilen (row); 'nCol' die der Spalten (column)
    // als dritter Parameter kann ein Wert für die Belegung der Matrix angegeben werden
    Matrix( size_type nRow, size_type nCol, const value_type& x = value_type() )
        : m_size( nRow * nCol )
        , m_nCol( nCol )                // Anzahl der Spalten für operator[] merken
        , m_ptr( new value_type[ m_size ] )     // Memory für Elemente allokieren
    {
        try {
            // die Elemente im Memory anlegen (Konstruktor-Aufruf)
            std::uninitialized_fill_n( m_ptr, m_size, x );
        }
        catch( ... )
        {
            delete[] m_ptr;             // auch im Fehlerfall kein Memory-Leak
            throw;                      // re-throw
        }
    }
    ~Matrix() 
    { 
        value_type* const pEnd = m_ptr + m_size;
        for( value_type* p = m_ptr; p != pEnd; ++p )
            p->~T();                    // Pendant zu uninitialized_fill_n (s.o.)
        delete[] m_ptr;                 // Memory wieder freigeben
    }

    // der operator[] liefert den Pointer auf das erste Element der Zeile(row) 'iRow'
    // diese Methode ermöglicht den Zugriff mit 
    //      Matrix< Type > mx( nRow, nCol );
    //      mx[iRow][iCol] = ... ;
    value_type* operator[]( int iRow )
    {
        return m_ptr + iRow * m_nCol;
    }
    const value_type* operator[]( int iRow ) const
    {
        return m_ptr + iRow * m_nCol;
    }

private:
    size_type   m_size; // Anzahl der Elemente 
    size_type   m_nCol; // Anzahl der Spalten der Matrix
    value_type* m_ptr;  // Pointer auf das erste Element

    // -- einfachste Matrix-Variante ist nicht kopierbar
    Matrix( const Matrix& );
    Matrix& operator=( const Matrix& );
};

Jetzt geht z.B. auch

Matrix< std::string > ms( 5, 7 );
    ms[3][2] =  "Hallo";

    // .. und
    Matrix< char > mx( 3, 9, 'x' ); // alle Elemente mit 'x' vorbelegen

was lernen wir daraus: C++ ist nicht so einfach. Aber die Anwendung von Matrix<> sollte einfach und jetzt auch sicher sein

Gruß
Werner

camper

Werner Salomon schrieb:

Bei näherer Betrachtung ist mir dann auch aufgefallen, dass der Konstruktor nicht exception-sicher ist.

nein? ich denke doch, (sofern der destructor von T nicht wirft, versteht sich). dein code ist im übrigen schlechter geworden, denn die elemente werden ja bereits bei new default-konstruiert, sofern es keine PODs sind

camper

hab nochmal ein bisschen im stroustrup gestöbert. der hat mich daran erinnert, dass eine matrix auch als kombination von valarray und slices gebaut werden kann, was mitunter besser ist.

Werner Salomon

camper schrieb:

Werner Salomon schrieb:

Bei näherer Betrachtung ist mir dann auch aufgefallen, dass der Konstruktor nicht exception-sicher ist.

nein? ich denke doch, (sofern der destructor von T nicht wirft, versteht sich).

Hallo Camper,

es hätte gereicht, wenn der (Copy-)Konstruktor von T wirft. Dann wäre das Memory

, m_ptr( new value_type[ nCol * nRow ] )

nicht mehr freigegeben worden, da bei einer Exception im Konstruktor der Destruktor nicht mehr aufgerufen wird.

Gruß
Werner

camper

Werner Salomon schrieb:

camper schrieb:

Werner Salomon schrieb:

Bei näherer Betrachtung ist mir dann auch aufgefallen, dass der Konstruktor nicht exception-sicher ist.

nein? ich denke doch, (sofern der destructor von T nicht wirft, versteht sich).

Hallo Camper,

es hätte gereicht, wenn der (Copy-)Konstruktor von T wirft. Dann wäre das Memory
, m_ptr( new value_type[ nCol * nRow ] )
nicht mehr freigegeben worden, da bei einer Exception im Konstruktor der Destruktor nicht mehr aufgerufen wird.

Gruß
Werner

nö, new macht das schon richtig. falls in einem new ausdruck eine exception fliegt, werden alle bis dahin bereits konstruierten objekte zerstört und der speicher freigegeben, bevor ein handler in aktion treten kann. andernfalls wäre es prinzipiell nicht möglich, new mit objekten zu benutzen, die werfen können.

Werner Salomon

camper schrieb:

hab nochmal ein bisschen im stroustrup gestöbert. der hat mich daran erinnert, dass eine matrix auch als kombination von valarray und slices gebaut werden kann, was mitunter besser ist.

Stimmt - macht bloß keiner. valarray gehört meiner Meinung nach zu den ungenutzten Featuren des C++-Standards; so wie etwa std::messages.

Wie würdest Du denn eine Matrix mit valarray und slices bauen?

Werner Salomon

camper schrieb:

nö, new macht das schon richtig. falls in einem new ausdruck eine exception fliegt, werden alle bis dahin bereits konstruierten objekte zerstört und der speicher freigegeben, bevor ein handler in aktion treten kann. andernfalls wäre es prinzipiell nicht möglich, new mit objekten zu benutzen, die werfen können.

Stimmt, aber das meine ich nicht. Ich meine vielmehr:

Matrix( int nRow, int nCol )
        : m_nCol( nCol )
        , m_ptr( new value_type[ nCol * nRow ] )
    {
        // der Speicher ist allokiert

        // bis hierher sei alles gut gegangen
        std::fill( m_ptr, m_ptr + nCol * nRow, value_type(0) );
        // im fill wird kopiert; evt fliegt hier jetzt eine Exception
    }
    // der Konstruktor wird mit mit einer Exception verlassen ..

.. daraufhin werden die Destruktoren der Member aufgerufen. Aber das sind Pointer und int-Typen; da passiert nix. Der Destruktor von Matrix wird nicht aufgerufen und der allokierte Speicher bleibt hängen.

camper

Werner Salomon schrieb:

Wie würdest Du denn eine Matrix mit valarray und slices bauen?

keine Lust. Stroustrup macht das in "The C++ Programming Language" schon sehr ausführlich in Abschnitt 22.4 Vektor Arithmetik
Ich bin auch nicht der Ansicht, dass valarray wirklich wenig benutzt wird. es ist nat. auch kein allerwelts-container, sondern mehr für HPC ausgelegt.

camper

achso, du meintest deinen konstruktor, nicht meinen vorschlag
nat. könnte und sollte man besser ein boost::scoped_array verwenden. dann hat man dieses problem nicht und auch nicht das eines implizit angelegten copy-ctors.

Werner Salomon

camper schrieb:

achso, du meintest deinen konstruktor

natürlich, zu diesen Zeitpunkt war kein anderer da.

camper schrieb:

nicht meinen vorschlag

welchen Vorschlag meinst Du?
etwa dies:

camper schrieb:

zweckmässiger ist ein zusätzlicher parameter und direkte initialisierung (wenn du willst, kannst du auch noch einen haufen template-konstruktoren angeben, die dann alle möglichen parameter aufnehemn, falls T nicht copy-konstruiert werden sollen

Dabei ist mir nicht klar, wie so ein Konstruktor aussehen soll.

Im übrigen hast Du mich jetzt völlig konfus gemacht. Das hier:

Werner Salomon schrieb:

Matrix( size_type nRow, size_type nCol, const value_type& x = value_type() )
        : m_size( nRow * nCol )
        , m_nCol( nCol )                // Anzahl der Spalten für operator[] merken
        , m_ptr( new value_type[ m_size ] )     // Memory für Elemente allokieren
    {
        try {
            // die Elemente im Memory anlegen (Konstruktor-Aufruf)
            std::uninitialized_fill_n( m_ptr, m_size, x );

ist grob falsch; wie Du schon bemerkt hast. Klar bei new value_type[ m_size ] wird der Konstruktor von T aufgerufen .

Mach Du doch mal einen Vorschlag für so einen Konstruktor. 'Keine Lust' gilt jetzt nicht

Gruß
Werner