Why can I declare a 2D array with both dimensions sized variable but not new one?

Question

As the problem stated, this is doable:

#include <iostream>

int main(int argc, char *argv[])
{
    unsigned short int i;
    std::cin >> i;
    unsigned long long int k[i][i];
}

Here I declared an array that is sized i by i, both dimensions are variables.

But not this:

#include <iostream>

int main(int argc, char *argv[])
{
    unsigned short int i;
    std::cin >> i;
    unsigned long long int** k = new int[i][i];
    delete[] k;
}

I got an compiler message telling me that

error: only the first dimension of an allocated array may have dynamic size

I am forced to do this:

#include <iostream>

int main(int argc, char *argv[])
{
    unsigned short int i;
    std::cin >> i;
    unsigned long long int** k = new unsigned long long int*[i];
    for ( unsigned short int idx = 0 ; idx < i ; ++ i )
        k[idx] = new unsigned long long int[i];
    for ( unsigned short int idx = 0 ; idx < i ; ++ i )
        delete[] k[idx];
    delete[] k;
}

To my understanding, new and delete are used to allocate something on heap, not on stack, which won't be deleted when it goes out of scope, and is useful for passing datas across functions and objects, etc.

What I don't understand is what happens when I declare that k in the first example, I am told that declared array should (and could) only have constant dimensions, and when in need for a array of unknown size, one should always consider new & delete or vectors.

Is there any pros and cons to those two solutions I'm not getting, or is it just what it is?

I'm using Apple's LLVM compiler by the way.

Answer 1

I'm sure you can find implementation for 2D array functionality easily, but you can make your own class too. The simplest way is to use std::vector to hold the data and have an index-mapping function that takes your two coordinates and return a single index into the vector.

The client code will look a little different, instead of arr[x][y] you have arr.at(x,y) but otherwise it does the same. You do not have to fiddle with memory management as that is done by std::vector, just use v.resize(N*N) in constructor or dimension-setting function.

Answer 2

Neither form is C++ standard compliant, because the standard does not support variable-length arrays (VLAs) (interestingly, C99 does - but C is not C++). However, several compilers have an extension to support this, including your compiler:

From Clang's Manual:

Clang supports such variable length arrays in very limited circumstances for compatibility with GNU C and C99 programs:

• The element type of a variable length array must be a POD ("plain old data") type, which means that it cannot have any user-declared constructors or destructors, any base classes, or any members of non-POD type. All C types are POD types.
• Variable length arrays cannot be used as the type of a non-type template parameter.

But given that the extension is in place, why doesn't your second snippet work? That's because VLA only applies to automatic variables - that is, arguments or local variables. k is automatic but it's just a pointer - the array itself is defined by new int[i][i], which allocates on the heap and is decidedly not an automatic variable.

You can read more about this on the relevant GCC manual section.

Answer 3

Essentially what compilers generally do with two-dimensional arrays (fixed or variable) is this:

int arr[x][y] ---> int arr[x*y];

arr[2][4]= something ---> arr[2+4*x]= something;

Basically they are just a nicer way of notation of a one-dimensional array (on the stack). Most compilers require fixed sizes, so the compiler has an easier way of telling what the dimensions are (and thus what to multiply with). It appears you have just a compiler, which can keep track of the dimensions (and multipliers) even if you use variables.

Of course you can mimick that with new[] yourself too, but it's not supported by the compiler per se.

Probably for the same reason, i.e. because it would be even harder keeping track of the dimensions, especially when moving the pointers around.

E.g. with a new-pointer you could later write:

newarr= someotherarray;

and someotherarray could be something with even different dimensions. If the compiler did a 2-dim -> one dim translation, he'd have to track all possible size transitions.

With the stack allocated arr above, this isn't necessary, because at least once the compiler made it, it stays that size.