Multi-dimensional vector ?

I'm converting a program which uses a (stack based) temporary multi-dimensional array. The array size is not known at compile time so the existing code (from Linux) looks like this:-

Code:

---

void MakeConnections (int x, int y)
{
        // Create a temporary array
        int connections[x][y];

        // rest of function....
}

---

My understanding is that this is a C99 extension which isn't supported by our current compiler (VC8). Can I achieve the same thing with std::vector or is there a better object for achieving this? Later on in the program I'll need to access the elements in the usual array style - e.g. int x = connections[0][0]; or something similar.

Code:

---

#include <vector>
typedef std::vector<int> IntVector;
typedef std::vector<IntVector> IntVector2d;

void foo(int x, int y)
{
    IntVector2d connections(x, IntVector(y)); // a 2d vector, all elements initialized to 0
    connections[0][0] = 10; // for example
}

---

Also, your code has to check if x >= 0 and y >= 0, otherwise you're accessing invalid elements in the vector (for arrays, you can have negative subscripts, but not for vector)

Regards,

Paul McKenzie

Quote:

---

Originally Posted by John E

My understanding is that this is a C99 extension which isn't supported by our current compiler (VC8).

---

Yes, though with respect to C99 I would call it part of the language rather than an extension.

Quote:

---

Originally Posted by John E

Can I achieve the same thing with std::vector or is there a better object for achieving this? Later on in the program I'll need to access the elements in the usual array style - e.g. int x = connections[0][0]; or something similar.

---

Yes. There is a very direct way:

Code:

---

void MakeConnections(int x, int y)
{
    std::vector<std::vector<int>> connections;
    // rest of function....
}

---

Though it is a little wasteful if you want a rectangular 2D array since each inner vector would presumably store its own size and capacity. If that is a concern, then one solution is to use a single std::vector to store all the int elements, then say, overload operator() for this class so that you can access connections(i, j) as if it were connections[i][j]... or you could do the proxy class thing to get the connections[i][j] syntax anyway.

Thanks guys. I used Paul's suggestion (mostly because it was more convenient for specifying a fixed size array). A couple of questions:-

Q1) In this particular case it makes no difference whether the array is stack based or heap based but suppose it needed to be stack based for some reason... is there any way of doing something similar with _alloca() ?

For example, instead of this:-

Code:

---

void MakeConnections (int x)
{
        if (x > 0)
        {
                char connections[x];

                connections[0] = 'E';
        }
}

---

I can do this:-

Code:

---

void MakeConnections (int x)
{
        if (x > 0)
        {
                char *connections = (char *)_alloca(x);

                connections[0] = 'E';
        }
}

---

As long as the array is one-dimensional the array syntax works fine. But I couldn't find any trick to make the syntax work for a multi-dimensional array. Is there one?


Q2)

Quote:

---

Originally Posted by laserlight

with respect to C99 I would call it part of the language rather than an extension

---

Is C99 implemented in a more recent version of MSVC? At the moment we need to stick with VC8 for other reasons (mostly, the expense of upgrading InstallShield) but I realise we can't stick with VC8 forever.

1) the suggested solution for using a vector of vectors works, but it's not identical.
With the vector of vectors, you get a bunch of memory areas (discontinuous) allocated to hold the actual data. There's also some overhead in calculating the addresses of the data.
This may or may not end up having much of an influence on code performance.

2) an alternative approach is to use a single dimension vector, and calculate the size and internal indices yourself. The code could look a bit more messy, but you can work around that with a class wrapper that makes a 2D array from a 1D vector.

So basically

Code:

---

std::vector<int> connections(x*y);
//Accessing:
connections[ indexY * x + indexX ];  // equivalent to connections[indexY][indexX]

---

depending on need, you can also flip the array (calculating as connections[indexX * y + indexY])
depending on how the function works and how important "locality" is in running the code, this could make a big difference in performance.


3) if you needed to use _alloca(), then you'd eigher have to do everything yourself as in before the C99 addition, or you'd have to write a container class of your own that did this. (using the above methodology.. allocate an x*y element buffer, and do all index calculations yourself.

if the size is know at compiletime, and it needed to be on the stack, you could use std::array instead of std::vector.

Thanks. This is probably the most common problem that we see when trying to build Linux source code with VC8 so ultimately, I guess we'll have to upgrade MSVC. Are these kind of arrays supported in more recent versions? (i.e. can we declare arrays of unknown size in VC9 / VC10 or whatever?)

Quote:

---

Originally Posted by John E

Thanks. This is probably the most common problem that we see when trying to build Linux source code with VC8 so ultimately

---

The real issue is the compiler, not the OS.

What was more than likely used to compile the Linux version is the gcc compiler. It is the gcc compiler that comes with these extensions -- it has nothing to do with Linux. You can get the gcc compiler for Windows, Mac, etc. all with the same array extensions.

So if you really did not want to change any code, you should have used gcc (MingW, etc.) to compile the code with no changes. Otherwise, your job is to take non-standard C++ code and making it standard. Nothing wrong with that -- just making you aware of what you're actually trying to do.

Regards,

Paul McKenzie

Quote:

---

Are these kind of arrays supported in more recent versions? (i.e. can we declare arrays of unknown size in VC9 / VC10 or whatever?)

---

Not that I'm aware of. As per Paul's post #7, if you don't want to change the code to make it compatible with the current version of MSVS then you'll need to use the gcc compiler in some form.

From my understanding of Microsoft's statements regarding c, VS2012 supports c90 and those parts of c99 that are part of c++11. Parts of c99 (such as variable length arrays) that are not part of c++11 are not currently implemented. Microsoft may, at some future date, add such support to their c compiler but this is not a priority for them - unless they get a large number of requests from 'big users'. Microsoft's focus is on implementing c++11 and then c++14.

So I wouldn't hold my breath waiting for VLA in a Microsoft compiler any time soon.

Quote:

---

But I couldn't find any trick to make the syntax work for a multi-dimensional array. Is there one?

---

Using dynamic memory, a 2d array can be created and manipulated something like this

Code:

---

#include <stdlib.h>
#include <stdio.h>

typedef int** intarray;

intarray CreateArray(int row, int col)
{
intarray array;

        if ((array = (intarray)calloc(row, sizeof(int*))) == NULL)
                return NULL;

        for (int r = 0; r < row; r++)
                if ((array[r] = (int*)calloc(col, sizeof(int))) == NULL)
                        return NULL;

        return array;
}

void DeleteArray(intarray array, int row, int)
{
        for (int r = 0; r < row; r++)
                free(array[r]);

        free(array);
}

int main()
{
int rno = 10,
    cno = 20;

intarray array;

        if ((array = CreateArray(rno, cno)) == NULL)
                return 1;

        array[2][3] = 23;
        array[4][5] = 45;
        array[6][8] = 68;
        array[3][4] = 34;
        array[5][7] = 57;

        for (int r = 0; r < rno; r++) {
                for (int c = 0; c < cno; c++) {
                        printf("%2i ", array[r][c]);
                }
                puts("");
        }

        DeleteArray(array, rno, cno);

        return 0;
}

---

Quote:

---

Originally Posted by 2kaud

Using dynamic memory, a 2d array can be created and manipulated something like this

---

That's basically a version of a std::vector<std::vector<int>>, except that you are doing manual memory management, but avoid the space wastage due to each inner vector storing its own size and capacity. I've already mentioned how to avoid the space wastage while still using a std::vector, and I note that OReubens echoed my suggestion with an example, though without demonstrating how to get approximate or equivalent syntax as for a 2D array (but, John E, is that syntax necessary in the first place?).

well a very simple implementation for a 2D from single vector would be something like:

Code:

---

class twodeeintarray
{
public:
        twodeeintarray(int x, int y) :
                sizex(x),
                sizey(y),
                arr(x*y)
                {
                }
        int operator()(int x, int y) const // the "getter" operator
                {
                        // potentially test that x<sizex and y<sizey
                        return arr[ y * sizex + x ];
                }
        int& operator()(int x, int y) // the "setter" operator
                {
                        // potentially test that x<sizex and y<sizey
                        return arr[ y * sizex + x ];
                }

private:
        std::vector<int> arr;
        int sizex;
        int sizey;
};


// Usage:
void foo(int sizex, int sizey)
{
        twodeeintarray t(sizex,sizey);
        t(1,1) = 23;  // set value
        int x=t(1,1); // read value
}

---

note that you can't use array[x][y] in this case, but you need to use array(x,y) instead.
making this work with [][] type syntax is possible, but it'll add a load of overhead and extra code.
the above uses int, should be obvious how to templatize this for another type.
and there's a lot of extra features you could add as well such as making it more std::algorithm friendly and such.