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.