Sign in to follow this  
Uphoreum

Multidimensional Dynamic Arrays

Recommended Posts

I learned how to make dynamic arrays, like this:
int* array = new int[size];

And access it like this:
array[i] = someNumber;

So, I tried to do a multidimensional dynamic array, like this:
int* array = new int[width][height];

But, it always tells me that the second dimension "cannot be used in a constant expression" or something like that. This leads me to believe that you can't declare a multidimensional dynamic array in the same way you can a normal array. If that's true, how can you create a multidimensional dynamic array? I know another thing you can do is to make an array like, int[WIDTH * HEIGHT], but I can't remember how you differentiate between rows and columns when using that method, like, if I were cycling through and drawing rows of blocks. If someone could explain the above method, I think that would be easiest. ^ Thanks!

Share this post


Link to post
Share on other sites
You're going to have to create one dimension first, and then loop through the array and make each element an array of the second dimension.


int **array;

array = new int*[width];

for(int i = 0; i < width; i++){
array[i] = new int[height];
}




Or you could use a vector of vectors:

#include <vector>

int main{
int height = 5, width = 4;
std::vector<std::vector<int> > array;

array.resize(width);

for (int i = 0; i < width; i++)
array[i].resize(height);
}

Share this post


Link to post
Share on other sites
It's worth mentioning also that C [and c++] does NOT store size information when you dynamicly allocate things, and that when you use an array like this :

array[width][height]
accessed like this :
array[x][y]

the compiler converts it to....

array[width * height]
accessed like this :
array[x + y * width]

...Now with that information in mind, it makes perfect sense that you could not do what you're trying to do, because of this :

array[x + y * WIDTH!]

note that the size information requires being stored [which c/c++ does not store]. It works when it's staticly defined because, in that case, it is a constant expression that can be converted at compile-time from one form to the other. This is also why you have to provide one of the dimensions when you're passing multi-dimensional arrays as parameters to functions. In short, you can't do what you're trying to do. You can define it as a pointer to [width * height], you can make one of the dimensions static, and define it as a dynamic pointer to int[width]'s, you can make it static, or you can have an int** array, and dynamicly define each dimesion independantly, but you can't put the c/c++ compiler in a position that would require it to track the size of a dynamicly defined array.

Share this post


Link to post
Share on other sites
Thanks guys!

I would have used vectors, but I'm working on a project for a camp and the guidelines say "must use dynamic array".

I went with the "array of arrays" mentioned in the first reply.

Share this post


Link to post
Share on other sites
Quote:
Original post by Uphoreum
I would have used vectors, but I'm working on a project for a camp and the guidelines say "must use dynamic array".


"A camp"? I'm intrigued. They seem to be teaching you utter nonsense, though. :(

Share this post


Link to post
Share on other sites
sometimes its easier to make a dynamic array thats only a single dimension, but the way you access the elements is sort of multi-dimensional:


WIDTH = 20
HEIGHT = 10

int* array = new int[WIDTH * HEIGHT];

the item i want is at x=5, y = 7
access that element like this:

array[x + (y * WIDTH)];



makes reasonable sense to me, i used to do that in qbasic all the time for 2d tile games i made, haha ;)

Share this post


Link to post
Share on other sites
Quote:
the compiler converts it to....

array[width * height]
accessed like this :
array[y + + x * height]
Fixed, see my post in this thread or google for "column major vs row major"
Quote:
the item i want is at x=5, y = 7
access that element like this:

array[y + (x * HEIGHT) ];

Doing it the other way will trash the cache if you try to iterate over it with
for (int i = 0; i < WIDTH; ++i)
{
for (int j = 0; j < HEIGHT; ++j)
{
// acesses WIDTH * 0 + 1, WIDTH * 1 + 1, WIDTH * 2 + 1, ... element
array[i + j * WIDTH] = 0;
// acesses 0, 1, 2, ... element
array[j + i * HEIGHT] = 0;
}
}


Quote:
Obligatory link to the Boost Multidimensional Array Library.


Seconded

Quote:
But, it always tells me that the second dimension "cannot be used in a constant expression" or something like that. This leads me to believe that you can't declare a multidimensional dynamic array in the same way you can a normal array.


Just to explain the error message, you can declare multidimensional arrays dynamically but only if the second dimension is a compile time constant so the compiler was complaining that height was not a compile time constant.

Share this post


Link to post
Share on other sites
Good Post Julian, i didnt think of that.

***

But i dont feel like my suggestion was "wrong", i guess i assumed that the OP would read from left to right first, then move on to the next row. Lets take a .bmp for example: when reading or writing a bitmap, you would not have the y variable moving in the inner for-loop, it would be in the outside for-loop. In fact, i think *most* of the time when poeple are drawing "rows of blocks" (quoted from the OP, sounds like hes trying to draw left-to-right first, then move onto the next row) they would be traversing through x's first. That said, i dont think this would trash the cache:

array[x + (y * WIDTH)];



Just defending my original post, although, when it comes down to it id probably just use a multidimensional array anyways




EDIT: OK i see now, that you edited my post to show how it would trash the cache......gotcha, good call!

Share this post


Link to post
Share on other sites
Quote:
Original post by Julian90
**Points out my retarded typo**
Thanks, I completely missed that when i reread the post before hitting 'reply'. Good eye, but afraid you caught the wrong typo. Arrays of this type are aligned with the rows placed end-to-end.

Thanks for keeping me on my toes.

But in all honesty, while your method works great for traversing an image that is stored a certain way, most images are stored with the Y-value being the row index, and the X-value being the column index, so to retain cache coherency, you would use (x + (y * width)) instead of (y + (x * height)). I did goof up when i was specifying the original 2d version. Using the Y axis as the column will have the picture stored side-ways.

There isn't a 'right answer' here though. Really, it doesn't matter that much [so long as you twist the image right-way-up previous to making a texture out of it, and textures use x for column-index, and y for the row-index]. Just make sure when you're iterating over it, the inner loop is the added part, and the outer loop is the multiplied part [thus retaining the cache]. So it'll be (inner_loop_index + (outer_loop_index * pitch)) where pitch is the column count [also known as the size of the width]

Either way, thanks Julian90 for keeping me re-reading my posts for accuracy. Don't want to get sloppy.

Whatever axis is major doesn't matter, so long as it's consistent, and I wasn't consistent. Thanks for not letting my carelessness taint others.

Share this post


Link to post
Share on other sites
Quote:
But i dont feel like my suggestion was "wrong"


Quote:
Either way, thanks Julian90 for keeping me re-reading my posts for accuracy. Don't want to get sloppy.

Whatever axis is major doesn't matter, so long as it's consistent, and I wasn't consistent. Thanks for not letting my carelessness taint others.


No neither way is wrong so to speak as long as you iterate over it in the right order as Drigovas said, just most of the code i have seen iterates over y in the inner loop so i tend to emphasize column major when trying to explain it.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this