Thread: two dimensional dynamic array?

  1. #1
    GA ichijoji's Avatar
    Join Date
    Nov 2002
    Posts
    179

    two dimensional dynamic array?

    I'm working on a tile engine, and I want to have the maps in a .dat file. In order for minimum memory usage and maximum versatility, I thought I'd do something like this:
    Code:
    ifstream data;
    data.open("map.dat");
    int mapw, maph;
    data >> mapw >> maph;
    int *map = new int[mapw][maph];
    but when I compile that I get this error:
    initialization to 'int *' from 'int[*][((maph - 1) + 1)]' lacks a cast
    I'm running Dev-cpp, any ideas?
    Illusion and reality become impartiality and confidence.

  2. #2
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    To create a 20x20 array dynamically:
    Code:
    int ** twoDimensionalArray = new int * [20];
    for( int curIndex = 0; curIndex < 20; curIndex++ )
        twoDimensionalArray[curIndex] = new int[20];
    ...and to delete it:
    Code:
    for( int curIndex = 0; curIndex < 20; curIndex++ )
        delete[] twoDimensionalArray[curIndex];
    delete[] twoDimensionalArray;
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  3. #3
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    Hi,

    The first dimension of an array is not part of the type, so a pointer to a one dimensional array is declared like this:

    int array[10]={0};
    int* parray = array;

    However, the second dimension of an array is part of the type, so to declare a pointer to a two dimensional array, you would do this:

    int array[10][7]={0};
    int (*parray)[7] = array;

    Note the parentheses are needed otherwise you would have:

    int* parray[7]

    which is an array of pointers to type int.
    Last edited by 7stud; 04-12-2003 at 04:52 PM.

  4. #4
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    Just allocate the entire 2D array as a 1D array of size width * height and just access it via Row * Width + Col. This is what C++ does internally anyways with regular 2D arrays. It's wasteful to allocate memory in the way the above 2 replies do.

  5. #5
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    > It's wasteful to allocate memory in the way the above 2 replies do.


    how is it wastefull? dont you just end up with a pointer and a chunk of memory either way. unless you mean wastefull with respect to time...

  6. #6
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    Originally posted by Salem
    > how is it wastefull?
    Well for a [20][x] array, just 20 pointers. As far as data structure overhead goes, its pretty small change (compare with a list or a tree).
    Not just 20 pointers, but also the data that will most-likely be saved prior to each and every dynamically allocated array, which is usually another 4 bytes per array. I also wasn't just refering to wasting memory -- I was also reffering to wasting time. You have to loop x + 1 times to allocate the entire structure (where x is the number of columns), same goes for deallocation. You're potentially uneccissarily fragmenting your memory. You lose the benefit of being able to use inter-row pointer arithmetic. It's not just a "small change" in memory usage -- it can be quite a bit of a change, not to mention the rest of the problems it causes.

    Originally posted by Salem
    But which would you prefer to do in your code later on?
    Save 80 bytes and write arr[y*20+x] all over your code. This technique is a crock from the old days when crippled languages could not do multi-dimensional arrays.
    Salem, don't be silly. I know you know better than that

    You don't have to access it manually like arr[y*20+x] everytime. You just encapsulate it in a class and overload operator() or operator[] so you can access it like

    Matrix< int > Test( 10, 40 ); // Initial dimensions
    Test[5][8] = 15; // Set the 6th row, 9th column to 15

    And you can always inline the function as well to most-likely get the equivalent assembly of arr[y*20+x], but without the confusion you mention.

    Originally posted by Salem
    Or do it properly and just write arr[y][x]

    If later on, you decide to replace your 2D array with a 2D STL vector say, then [y][x] notation will slide right on in with no effort (not so with [y*20+x]).
    "Properly?" Making the syntax exactly the same as a regular array is trivial when the underlying implementation is completely different. Besides, I already showed that you could still accomplish it with the same exact syntax. Why be concerned about using [][] anyways? It's a silly thing to be concerned about, and if you really were concerned for some reason about having the same syntax, you could always just overload the class's operator[] as I mentioned, to return the address of row x (where x is the integer input to the overloaded operator[]). In that case you can literally get exactly the same syntax as arr[y][x]. Happy?

    Code:
    template< typename DataType >
      class Matrix
    {
    public:
      Matrix()
        : Array_m( 0 ),
          Rows_m( 0 ),
          Cols_m( 0 )
      {}
    
      Matrix( unsigned int Rows_Init, unsigned int Cols_Init )
        : Array_m( new DataType[ Rows_Init * Cols_Init ] ),
          Rows_m( Rows_Init ),
          Cols_m( Cols_Init )
      {}
      ~Matrix() { delete [] Array_m; }
      DataType* const operator[]( unsigned int Row )
      {
        return Array_m + Row * Cols_m;
      }
      const DataType* const operator[]( unsigned int Row ) const
      {
        return Array_m + Row * Cols_m;
      }
    private:
      DataType* Array_m;
      unsigned int Rows_m,
                          Cols_m;
    };
    That's just including the functionality mentioned so far. Obviously there would most-likely be more to it.

    Then you can access it just like you would a normal 2D array.

    Matrix< int > Test( 10, 40 );
    Test[5][8] = 6;

    Happy?

    (though I personally recommend overloading operator() instead so that when accessing an individual element and not just a row, you limit the access to one call).

    Originally posted by Salem
    Here's another reason for not allocating it in one massive block. Perhaps you don't want to store all the rows of your array (its a sparse array), or perhaps you want to have rows of different lengths (this is especially true for strings). 80 bytes looks like a real bargain compared to all the dead space you would otherwise have.
    Then you obviously would NOT want a 2 dimensional array, just like you wouldn't want a NON-dynamically allocated 2 dimensional array if you were working with an array of strings. You said yourself that you'd want that when the rows are of different length, while a true 2-dimensional array can not have rows of differing length. You wouldn't make an array of strings a regular 2D array, now would you? Why, then, do you feel that this should be accounted for with a "dynamic" multidimensional array. What you actually want for that situation is an entirely different type of datastructure. If you really want the rows of different length, then, quite simply, a 2D array is NOT what you are looking for. What you would want is an array of pointers to the first elements of other arrays, which is a different concept entirely.

    Originally posted by Salem
    Besides, if you need a [y][20] array (the minor dimension is constant), you can allocate it all in one block and still have [y][x] notation as well
    If the minor dimension is a constant as you are mentioning, then you could just make a single dimensional array of Datatype[SomeConstant].

    For instance

    Array< int[20] > Viola( 5 ); // 5 rows, each with 20 elements
    Array[12][3] = 16; // See, just as simple

    // Where Array is a simple templated dynamic 1D array class

    Originally posted by Salem
    Like not wanting to store all the tiles in memory all at the same time
    Again, if that is the case, then, quite simply, a 2D array is not what the person is looking for.

  7. #7
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    Good

    All I wanted to see was it allocated in one block. I find it funny that you called my example "class trickery." Are you against classes, or are you just joking around. I gather that you're more a C programmer, but I have to say, I'm quite appauled by this anti-oop attitude

    Still, you're using more memory for the row pointers, but it's understandable that one may want to use the extra memory for the speed increase. However, for an array with many rows, that can be quite a bit wasteful. Depends on whether you have to optimize memory use or access speed.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Dynamic Array Allocation function
    By P4R4N01D in forum C++ Programming
    Replies: 6
    Last Post: 05-15-2009, 02:04 AM
  2. Replies: 2
    Last Post: 07-11-2008, 07:39 AM
  3. Dynamic 2 Dimensional Array
    By mrb260478 in forum C Programming
    Replies: 23
    Last Post: 06-21-2008, 07:19 AM
  4. Dynamic 2 dimensional array with new?
    By Quantum1024 in forum C++ Programming
    Replies: 10
    Last Post: 11-19-2005, 02:46 PM
  5. total size of dynamic memory allocated array
    By trekker in forum C Programming
    Replies: 10
    Last Post: 03-10-2002, 12:59 PM