Dynamisches zweidimensionales Array entsprechend der Eingabe

Lesezeit: 5 Minuten

Dynamisches zweidimensionales Array entsprechend der Eingabe
Himmelstür

Ich muss eine Eingabe N vom Benutzer erhalten und eine N * N-Matrix generieren. Wie kann ich die Matrix deklarieren? Im Allgemeinen sollte die Größe des Arrays und der Matrix bei der Deklaration festgelegt werden, oder? Wie wäre es mit vector<vector<int>> ? Ich benutze das noch nie, also brauche ich einen Vorschlag von einem Veteranen.

  • Dynamische mehrdimensionale Arrays in [c] wurden mehrfach diskutiert, und dieser Stil ist ebenfalls verfügbar.

    – dmckee — Ex-Moderator-Kätzchen

    7. Februar 2010 um 16:51 Uhr

Dynamisches zweidimensionales Array entsprechend der Eingabe
Jerry Sarg

EIN vector<vector<int>> (oder vector<vector<int> >für ältere Compiler) kann gut funktionieren, aber es ist nicht unbedingt der effizienteste Weg, Dinge zu tun1. Ein anderer, der recht gut funktionieren kann, ist ein Wrapper um einen einzelnen Vektor, der die “Form” der dargestellten Matrix verfolgt und eine Funktion oder einen überladenen Operator für den Zugriff auf die Daten bereitstellt:

template <class T>
class matrix { 
    int columns_;
    std::vector<T> data;
public:
    matrix(int columns, int rows) : columns_(columns), data(columns*rows) {}

    T &operator()(int column, int row) { return data[row*columns_+column]; }
};

Beachten Sie, dass der C++-Standard nur erlaubt operator[] um einen einzelnen Operanden zu nehmen, also können Sie ihn nicht für diesen Job verwenden, zumindest nicht direkt. Im obigen Beispiel habe ich (offensichtlich genug) verwendet operator() Stattdessen sehen Indizes eher wie Fortran oder BASIC aus, als Sie es von C++ gewohnt sind. Wenn Sie wirklich darauf aus sind, zu verwenden [] Notation können Sie es trotzdem tun, obwohl es leicht knifflig ist (Sie überladen es in der Matrixklasse, um einen Proxy zurückzugeben, und lassen dann die Proxyklasse ebenfalls überladen operator[] um das richtige Element (einen Verweis auf) zurückzugeben – es ist intern etwas hässlich, funktioniert aber trotzdem perfekt).

Hier ist ein Beispiel für die Implementierung der Version mit mehreren Überladungen von operator[]. Ich habe dies (eine ganze Weile) vor den meisten Compilern geschrieben std::vector, sodass ein Array statisch zugewiesen wird, anstatt einen Vektor zu verwenden. Es ist auch für den 3D-Fall (es gibt also zwei Ebenen von Proxys), aber mit etwas Glück kommt die Grundidee trotzdem durch:

template<class T, int size>
class matrix3 {

    T data[size][size][size];

    friend class proxy;
    friend class proxy2;

    class proxy { 
        matrix3 &m_;
        int index1_, index2_;
    public:
        proxy(matrix3 &m, int i1, int i2) 
            : m_(m), index1_(i1), index2_(i2) 
        {}

        T &operator[](int index3) { 
            return m_.data[index1_][index2_][index3];
        }
    };

    class proxy2 { 
        matrix3 &m_;
        int index_;
    public:
        proxy2(matrix3 &m, int d) : m_(m), index_(d) { }

        proxy operator[](int index2) { 
            return proxy(m_, index_, index2);
        }
    };
public:
    proxy2 operator[](int index) {
        return proxy2(*this, index);
    }
};

Damit können Sie die Matrix mit der normalen C++-Syntax ansprechen, wie zum Beispiel:

matrix3<double, size> m;

for (int x=0; x<size; x++)
    for (int y = 0; y<size; y++)
        for (int z = 0; z<size; z++)
            m[x][y][z] = x*100 + y * 10 + z;

  1. Ein std::vector wird normalerweise als Zeiger auf einige dynamisch zugewiesene Daten implementiert, also so etwas wie a vector<vector<vector<int>>> wird zwei Ebenen von Zeigern dereferenzieren, um zu jedem Datenelement zu gelangen. Dies bedeutet mehr Speicherreferenzen, die auf den meisten modernen Prozessoren ziemlich langsam sind. Da jeder Vektor separat zugeordnete Daten enthält, führt dies in der Regel auch zu einer schlechten Cache-Lokalität. Es kann auch etwas Platz verschwenden, da jeder Vektor sowohl seine zugewiesene Größe als auch die verwendete Größe speichert.

  • Möchten Sie etwas Licht in den Ineffizienzteil von Vektor der Vektoren bringen?

    – Murali Vizepräsident

    7. Februar 2010 um 5:35 Uhr

  • @Murali: Im Grunde genommen haben Sie in mehrfacher Hinsicht Ineffizienz. Zunächst einmal speichert jeder seine eigene Länge, obwohl alle Teilvektoren (sozusagen) die gleiche Größe haben werden. Zweitens wird ein Vektor (zumindest normalerweise) mit einem Zeiger auf dynamisch zugewiesene Daten implementiert, sodass Sie bei einem Vektor von Vektoren zwei Ebenen von Zeigern durchlaufen müssen, um zu den echten Daten zu gelangen. Die Verwendung eines einzelnen Vektors erfordert stattdessen eine Multiplikation, was früher ein schlechter Kompromiss war, aber mit CPUs, die schneller als der Speicher sind, ist es jetzt fast immer ein Gewinn (zusätzliche CPU-Zeit gegenüber der Möglichkeit eines zusätzlichen Speicherzugriffs).

    – Jerry Sarg

    7. Februar 2010 um 5:45 Uhr

  • Sie könnten auch std::valarray verwenden, da es bereits eine Vielzahl von Subset-Zugriffsmechanismen unterstützt.

    – MSN

    7. Februar 2010 um 6:31 Uhr

  • @MSN: Sie könnten — valarray ist etwas, das ich in der Vergangenheit ein paar Mal erwähnt habe, aber ehrlich gesagt ist das ein Banner, das ich sozusagen beschlossen habe, damit aufzuhören. Einfache Verwendungen davon mögen sinnvoll sein, aber sobald Sie sich mit Slice, Gslice, Slice_array usw. befassen, wird es für mindestens 99 % der C++-Community völlig undurchsichtig. Schlimmer noch, es wurde wirklich für Vektorprozessoren entwickelt; es ist relativ Cache-unfreundlich, also selbst wenn Sie wissen, was es tut, und ein Leser es auch tut, wird es oft sowieso eine ziemlich ineffiziente Art sein, es zu tun.

    – Jerry Sarg

    7. Februar 2010 um 16:26 Uhr

  • aber denken Sie an all die Tipparbeit, die Sie sich sparen würden! 🙂

    – MSN

    7. Februar 2010 um 18:34 Uhr

Dynamisches zweidimensionales Array entsprechend der Eingabe
Steve Guidi

Boost implementiert Matrizen (unterstützende mathematische Operationen) in seinem uBLAS-Bibliothekund stellt eine Verwendungssyntax wie die folgende bereit.

#include <boost/numeric/ublas/matrix.hpp>

int main(int argc, char* argv[])
{
    unsigned int N = atoi(argv[1]);
    boost::matrix<int> myMatrix(N, N);

    for (unsigned i = 0; i < myMatrix.size1 (); ++i)
        for (unsigned j = 0; j < myMatrix.size2 (); ++j)
            myMatrix(i, j) = 3 * i + j;

    return 0;
}

Beispielcode:

template<class T>
class Array2D
{
public:
    Array2D(int a, int b)  
    {
        num1 = (T**)new int [a*sizeof(int*)];
        for(int i = 0; i < a; i++)
            num1[i] = new int [b*sizeof(int)];

        for (int i = 0; i < a; i++) {
            for (int j = 0; j < b; j++) {
                num1[i][j] = i*j;
            }
        }
    }
    class Array1D
    {
    public:
        Array1D(int* a):temp(a) {}
        T& operator[](int a)
        {
            return temp[a];
        }
        T* temp;
    };

    T** num1;
    Array1D operator[] (int a)
    {
        return Array1D(num1[a]);
    }
};


int _tmain(int argc, _TCHAR* argv[])
{
    Array2D<int> arr(20, 30);

    std::cout << arr[2][3];
    getchar();
    return 0;
}

    enter code here

963930cookie-checkDynamisches zweidimensionales Array entsprechend der Eingabe

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy