int[n][m], where n and m are known at runtime

Question

I often need to create a 2D array with width and height (let them be n and m) unknown at compile time, usually I write :

vector<int> arr(n * m);

And I access elements manually with :

arr[j * m + i] 

I recently got told that I could instead write :

int arr[n][m] // n and m still only known at runtime.

So here are 2 questions :

1. Is this behaviour allowed by the C++ Standard ?
2. How should I pass such an array to a function ? g++ reports that arr has type int (*)[n], but again, n is dynamic and not known outside the function where it is declared (main).

Answer 1

The feature you are asking about (where the dimensions are only made known at runtime) is a non-standard extension of C++, but a standard one of C.99 (made into an optional feature in C.11). The feature is called variable-length array (VLA), and the link is the documentation for GCC.

If you are using GCC, then you are to pass the length of the array as a parameter to the function.

void foo (int m, int arr[][m]) {
    //...
}

However, there seems to be a bug in either the compiler or the documentation, as the above function prototype syntax only works when compiling C code, not C++ (as of gcc version 4.8.2). The only work-around I found was to use a void * parameter, and cast it int the function body:

int foo_workaround (int m, void *x)
{
    int (*arr)[m] = static_cast<int (*)[m]>(x);
    //...
}

There are other solutions if you do not want to rely on a compiler extension. If you don't mind a separate allocation for each row, you can use a vector of vectors, for example:

std::vector<std::vector<int> > arr(n, std::vector<int>(m));

However, if you want a single allocation block like you demonstrated in your own example, then it is better to create a wrapper class around vector to give you 2-d like syntax.

template <typename T>
class vector2d {

    int n_;
    int m_;
    std::vector<T> vec_;

    template <typename I>
    class vector2d_ref {
        typedef std::iterator_traits<I> TRAITS;
        typedef typename TRAITS::value_type R_TYPE;
        template <typename> friend class vector2d;
        I p_;
        vector2d_ref (I p) : p_(p) {}
    public:
        R_TYPE & operator [] (int j) { return *(p_+j); }
    };

    typedef std::vector<T> VEC;
    typedef vector2d_ref<typename VEC::iterator> REF;
    typedef vector2d_ref<typename VEC::const_iterator> CREF;

    template <typename I> 
    vector2d_ref<I> ref (I p, int i) { return p + (i * m_); }

public:

    vector2d (int n, int m) : n_(n), m_(m), vec_(n*m) {}
    REF operator [] (int i) { return ref(vec_.begin(), i); }
    CREF operator [] (int i) const { return ref(vec_.begin(), i); }

};

The wrapper's operator[] returns an intermediate object that also overloads operator[] to allow 2-dimensional array syntax when using the wrapper.

    vector2d<int> v(n, m);
    v[i][j] = 7;
    std::cout << v[i][j] << '\n';

Answer 2

Why not have an std::vector of std::vector's?

std::vector<std::vector<int> > arr(n, std::vector<int>(m));

Accessing an item then becomes:

std::cout << "(2,1) = " << arr[2][1] << std::endl;

Answer 3

A std::vector of std::vector's (from #include <vector>) would do the same thing as a 2-Dimensional array:

int n = 10, m = 10; //vector dimensions
std::vector<std::vector<int>> arr(n, std::vector<int>(m)); //Create 2D vector (vector will be stored as "std::vector<int> arr(n * m);

//you can get values from 2D vector the same way that you can for arrays
int a = 5, b = 5, value = 12345;
arr[a][b] = 12345;
std::cout << "The element at position (" << a << ", " << b << ") is " << arr[a][b] << "." << std::endl;

outputs:

The element at position (5, 5) is 12345.