Multi-dimensional vector ?
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 11 of 11

Thread: Multi-dimensional vector ?

Hybrid View

  1. #1
    John E is offline Elite Member Power Poster
    Join Date
    Apr 2001
    Location
    Manchester, England
    Posts
    4,242

    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.
    "A problem well stated is a problem half solved. - Charles F. Kettering

  2. #2
    Join Date
    Apr 1999
    Posts
    27,427

    Re: Multi-dimensional vector ?

    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

  3. #3
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,273

    Re: Multi-dimensional vector ?

    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.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  4. #4
    John E is offline Elite Member Power Poster
    Join Date
    Apr 2001
    Location
    Manchester, England
    Posts
    4,242

    Re: Multi-dimensional vector ?

    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 View Post
    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.
    "A problem well stated is a problem half solved. - Charles F. Kettering

  5. #5
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    3,879

    Re: Multi-dimensional vector ?

    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.

  6. #6
    John E is offline Elite Member Power Poster
    Join Date
    Apr 2001
    Location
    Manchester, England
    Posts
    4,242

    Re: Multi-dimensional 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?)
    "A problem well stated is a problem half solved. - Charles F. Kettering

  7. #7
    Join Date
    Apr 1999
    Posts
    27,427

    Re: Multi-dimensional vector ?

    Quote Originally Posted by John E View Post
    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
    Last edited by Paul McKenzie; August 27th, 2013 at 10:29 AM.

  8. #8
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,365

    Re: Multi-dimensional vector ?

    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.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  9. #9
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,365

    Re: Multi-dimensional vector ?

    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;
    }
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  10. #10
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,273

    Re: Multi-dimensional vector ?

    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?).
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  11. #11
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    3,879

    Re: Multi-dimensional vector ?

    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.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center