Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

dynamical two dimension array according to input

I need to get an input N from the user and generate a N*N matrix. How can I declare the matrix? Generally, the size of the array and matrix should be fixed at the declaration, right? What about vector<vector<int>> ? I never use this before so I need suggestion from veteran.

like image 638
skydoor Avatar asked Nov 29 '22 20:11

skydoor


2 Answers

A vector<vector<int>> (or vector<vector<int> >, for older compilers) can work well, but it's not necessarily the most efficient way to do things1. Another that can work quite nicely is a wrapper around a single vector, that keeps track of the "shape" of the matrix being represented, and provides a function or overloaded operator to access the data:

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]; }
};

Note that the C++ standard only allows operator[] to take a single operand, so you can't use it for this job, at least directly. In the example above, I've (obviously enough) used operator() instead, so subscripts look more like Fortran or BASIC than you're accustomed to in C++. If you're really set on using [] notation, you can do it anyway, though it's mildly tricky (you overload it in the matrix class to return a proxy, then have the proxy class also overload operator[] to return (a reference to) the correct element -- it's mildly ugly internally, but works perfectly well anyway).

Here's an example of how to implement the version using multiple overloads of operator[]. I wrote this (quite a while) before most compilers included std::vector, so it statically allocates an array instead of using a vector. It's also for the 3D case (so there are two levels of proxies involved), but with a bit of luck, the basic idea comes through anyway:

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

Using this, you can address the matrix with the normal C++ syntax, such as:

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. An std::vector is normally implemented as a pointer to some dynamically allocated data, so something like a vector<vector<vector<int>>> will dereference two levels of pointers to get to each piece of data. This means more memory references, which tend to be fairly slow on most modern processors. Since each vector contains separately allocated data, it also leads to poor cache locality as a rule. It can also waste some space, since each vector stores both its allocated size and the size in use.
like image 135
Jerry Coffin Avatar answered Dec 22 '22 20:12

Jerry Coffin


Boost implements matrices (supporting mathematical operations) in its uBLAS library, and provides usage syntax like the following.

#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;
}
like image 39
Steve Guidi Avatar answered Dec 22 '22 21:12

Steve Guidi