Sign in to follow this  
Kada2k6

Expanding the size of an array in C?

Recommended Posts

Arrays are continuous in memory, so can't be resized. Arrays however have O(1) access time, so this is the advantage of that.

Vectors are resizable, but are slower than arrays.

If you have to resize your array, the only way to do it is create a new array of the new size, then copy over all the data from the old array. By the sounds of it, your resize array function is a one off cost that rarely needs to be done, so this would be acceptable, but know that it is usually a computationaly expensive action.

Share this post


Link to post
Share on other sites
Check out realloc().


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

int main()
{
/* Get a pointer to some memory of an adequate size for 16x16 copies
of a struct MapFormat. Note that no cast is needed as malloc returns
void*. */
if(!struct MapFormat *Map = malloc(16 * 16 * sizeof(struct MapFormat)))
{
printf("Insufficient memory for allocation. Terminating.");
exit(1); // Return 1 as an error value
}

// Do whatever with Map

if(!Map = realloc(Map, 128 * 128 * sizeof(struct MapFormat)))
{
printf("Insufficient memory for reallocation. Terminating.");
exit(1);
}

free(Map);
}


EDIT: Tidied code up: checking for NULL, freeing Map.

Share this post


Link to post
Share on other sites
You can't resize an array in C, their size is set at compile time.

You can have a dynamically-sized array-like memory region, but you have to use memory allocation. Master it and move on. Don't let the technology master you. You will be all the happier for it.

Share this post


Link to post
Share on other sites
It is true, you absolutely cannot resize a "vanilla" array. However, you could use a linked list or a vector, both of which can be resized and neither of which is all that difficult to use.

Share this post


Link to post
Share on other sites
You cannot resize an array that is statically declared like your code sample.

You CAN resize a heap-allocated block of memory. However, you cannot use two-dimensional syntax, so you have to calculate the address yourself.

Contrary to what Gullanian said, there is no speed difference between statically declared arrays, and arrays-in-vectors.

Something like this:


struct Array {
MapFormat * element;
size_t width;
size_t height;
};

void init_array(Array * a, size_t width, size_t height) {
a->element = (MapFormat *)calloc(sizeof(MapFormat), width*height);
a->width = width;
a->height = height;
}

MapFormat * get_element(Array const * a, size_t x, size_t y) {
if (x >= a->width) return NULL;
if (y >= a->height) return NULL;
return a->element + x + y * a->width;
}

void resize_array(Array * a, size_t nuWidth, size_t nuHeight) {
MapFormat * nuElem = (MapFormat *)calloc(sizeof(MapFormat), width*height);
for (size_t y = 0; y < min(a->height, nuHeight); ++y) {
for (size_t x = 0; x < min(a->width, nuWidth); ++x) {
nuElem[x + y * nuWidth] = a->element[x + y * a->width];
}
}
free(a->element);
a->element = nuElem;
a->width = nuWidth;
w->height = nuHeight;
}

Share this post


Link to post
Share on other sites
Hidden
Thank you for your quick answers! I guess the solution I was looking for was similiar to the one TheUnbeliever provided, so thanks a lot for that. I will try it out right away. Thanks to all your others as well for explaining!

Share this post


Link to post
It looks like you want to load a map during runtime. Why not include a file header that declares the size of the map, and then allocate however much you need?

Share this post


Link to post
Share on other sites
Quote:
Original post by medevilenemy
It is true, you absolutely cannot resize a "vanilla" array. However, you could use a linked list or a vector, both of which can be resized and neither of which is all that difficult to use.


Well... strictly speaking you cannot resize a stack allocated array:

int foo[5];

You can always resize a heap allocated array (forgive any poor ansi c syntax, been in C++ too long):

int *foo = (int*)malloc( sizeof(int) * 5 );
foo = (int*)realloc( foo, sizeof(int) * 10 );

One mighty source of confusion is that you cannot have classic multi-dimensional arrays on the heap. But you can easily "fake" them:

int *foo = (int*)malloc( sizeof(int) * width * height );

//to simulate foo[x][y]
foo[ y * height + x ];

Just ALWAYS remember to free any memory you malloc.

-me

Share this post


Link to post
Share on other sites
Quote:
Original post by hplus0603
You cannot resize an array that is statically declared like your code sample.

You CAN resize a heap-allocated block of memory. However, you cannot use two-dimensional syntax, so you have to calculate the address yourself.

[emphesis added]


While multi-dimensional allocations are not supported directly, it is possible, though not straight forward, to simulate them.

To allocate a HxW array of ints -- outined briefly:

int** array = malloc(sizeof(int *) * H);

int* rows = malloc(sizeof(int) * W * H);

for(i = 0; i < H; i++)
array[i] = rows + (i * W);


I don't have a compiler to test this in front of me, however this should be the gist of how it works. To the compiler, a statically-defined multi-dimensional array acts just an array of arrays anyhow, so allocating one manually provides the same results, though it does take a few extra steps and a little more memory.

That said, taking into account that you admit to your shortcomings with memory allocation, its much easier to allocate a single contigious block of memory and to calculate the given row-column position yourself; you can even write a generic function to do so. In this way, you will have 1 allocation, 1 de-allocation, and only 1 chance for a dangling pointer (this simulated multi-dimensional array above is 2, 2, and H+1 respectively.) Calculating the address yourself is also likely faster as it requires one less look-up, yielding one less chance for a cache-miss and keeping your memory accesses localized (good for your cache.) This is the approach I recommend.

The "Easy Way Out", if you know the maximum size of the array and the memory requirements aren't too high, is to simply statically allocate an array large enough for the biggest possible map, but only fill what you need. Stylistically this is bad, but it will work from a practical standpoint. A 256x256 array of integers, for example, is only 256KB (a quarter of a megabyte), and memory is not a limiting factor today like it used to be in the past.

Back in my DOS programming days I had to write a paging system for my RPG engine because I wanted a 4-layer map that could be up to 256x256 tiles. Each layer was a full 64k (using 8bit indices) for a total of 256k for a single map. This was back in the 16bit days, and your application (after DOS, drivers and other services loaded) had about 384-512 K to play in... A Traditional, static approach would have left me 128-256 K for all my code, graphics, scripts, sounds and other data. Clearly this was too limiting so the paging system was born. Today there's little reason to worry too much about a measly 256K - unless you're on the GBA, DS, or some other older, limited platform.

Share this post


Link to post
Share on other sites
if you want to do it the fun way you can use a double pointer, allowing you to use it how you currently are ( Map[ x ][ y ] )


setup the map how you are plus the current width and height...

unsigned int MapWidth = 0, MapHeight = 0;
struct MapFormat ** Map = 0; // except now we have to malloc this array!




then to resize the map you can use this function:

void SetMapSize( unsigned int _Width, unsigned int _Height )
{
unsigned int i;
if( Map == 0 )
{
// create original memory
Map = ( void * )malloc( sizeof( void * ) * _Width );
for( i = 0; i < _Width; i++ )
Map[ i ] = malloc( sizeof( struct MapFormat ) * _Height );
}
else
{
// chop off the extra width if the width is set smaller!
for( i = _Width; i < MapWidth; i++ )
free( Map[ i ] );

// resize width of the map
Map = realloc( Map, sizeof( void * ) * _Width );

// add extra width if the width was set larger!
for( i = MapWidth; i < _Width; i++ )
Map[ i ] = malloc( sizeof( struct MapFormat ) * _Height );

// resize the old height
if( _Height != MapHeight )
for( i = 0; i < ( _Width < MapWidth ? _Width : MapWidth ); i++ )
Map[ i ] = realloc( Map[ i ], sizeof( struct MapFormat ) * _Height );
}
MapWidth = _Width;
MapHeight = _Height;
}




then when you're ending your program don't forget to destroy the allocated memory!!


void DestroyMap()
{
unsigned int i;
for( i = 0; i < MapWidth; i++ )
free( Map[ i ] );
free( Map );
Map = 0;
}



Share this post


Link to post
Share on other sites
Hidden
Quote:
Original post by erissian
It looks like you want to load a map during runtime. Why not include a file header that declares the size of the map, and then allocate however much you need?

Yupp, you read my mind! But I was under the impression that you can't declare variables further down a program or function?

void LoadMap() {
open the file
read the header and get the width & height of the map
declare the struct MapFormat array <- not possible...?
continue loading map
}

Share this post


Link to post
Quote:
Original post by Kada2k6
Quote:
Original post by erissian
It looks like you want to load a map during runtime. Why not include a file header that declares the size of the map, and then allocate however much you need?

Yupp, you read my mind! But I was under the impression that you can't declare variables further down a program or function?

void LoadMap() {
open the file
read the header and get the width & height of the map
declare the struct MapFormat array <- not possible...?
continue loading map
}


Hmm.... So all the logic goes in the LoadMap() function [wink]? What are you going to do with the map if it will disappear once the function ends?

EDIT: And also - IIRC Ansi C doesn't allow variable-sized stack arrays. That is, this would be illegal (even though some compilers probably allow it):

int a = 34;
int b = 7;

int map[a][b]; // IIRC isn't allowed


I simply suggest you use the free-store.

Share this post


Link to post
Share on other sites
Quote:
Original post by agi_shi
EDIT: And also - IIRC Ansi C doesn't allow variable-sized stack arrays. That is, this would be illegal (even though some compilers probably allow it):
*** Source Snippet Removed ***
I simply suggest you use the free-store.


C89 doesn't allow it but C99 does. C99 allows for variable length arrays on the stack, but "If an identifier is declared to be an object with static storage duration, it shall not have a variable length array type." (6.7.5.2 Array declarators) Many compilers also provide an implementation of alloca for dynamic stack allocations even though it is non-standard.

Share this post


Link to post
Share on other sites
Quote:
Original post by Kada2k6
Thank you for your quick answers! I guess the solution I was looking for was similiar to the one TheUnbeliever provided, so thanks a lot for that. I will try it out right away. Thanks to all your others as well for explaining!


The wrapper proposed by hplus is far more sane. realloc() has no way of knowing that your array "is 2-dimensional". It will copy the old data across, but the net result is that it isn't where you want it to be - instead it gets strung out across the first couple of "rows" of the larger array. Plus, you still have to do indexing calculations, so you may as well wrap up the size information in a struct together with the array, and may as well make a function to wrap up the index calculation.

But do you *really* need to use *C*, in the year 2006?

Quote:
Original post by agi_shi
EDIT: And also - IIRC Ansi C doesn't allow variable-sized stack arrays. That is, this would be illegal (even though some compilers probably allow it):


It's not a matter of the compiler, but the language standard. C99 is a fair bit different (as it should be) from C90.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
Quote:
Original post by Kada2k6
Thank you for your quick answers! I guess the solution I was looking for was similiar to the one TheUnbeliever provided, so thanks a lot for that. I will try it out right away. Thanks to all your others as well for explaining!


The wrapper proposed by hplus is far more sane. realloc() has no way of knowing that your array "is 2-dimensional". It will copy the old data across, but the net result is that it isn't where you want it to be - instead it gets strung out across the first couple of "rows" of the larger array. Plus, you still have to do indexing calculations, so you may as well wrap up the size information in a struct together with the array, and may as well make a function to wrap up the index calculation.


Very true, I didn't think of quite how messy that could get (well, not that hplus0603's wrapper is messy). However, I was making the assumption that if he's loading a new map, the contents of the old one don't matter - so the indexing can be done as normal. Then again, if that's true then you're as well freeing the old Map pointer and allocating a new, appropriately sized, chunk of memory.

Share this post


Link to post
Share on other sites
You are gonna hate this answer but in fact it is a completely valid solution.

Just analyze the maximum map size and reserve that space. Then Use the ammount you need from that space. That means:
char map[256][256];

And then use two variables:
int mapSizeX = 16, mapSizeY = 16;

Before you start flaming this answer shouting things like "You are wasting memory!!!!"... and all that just think a moment... How much memory will you really waste? 1MB? Thats too little for a compoter these days and the advantages are greater.

Searching a value in an array is faster than searching in a couple of vectors (slightly faster but you will access it time and time again). Also clearing the array is way faster as you can clear it in a single call. Thats useful for some algortithms like A*.

Computer science is always a battle between fast code and memory efficient code. Fast code usually uses a lot of memory. Memory efficient is slower. I'm not saying at all you must always do everything this way and that memory allocation is useless. I'm just saying that some data structures require more attention to memory management while others, like a map definition, won't hit your memory and your performace can be improved (and your code will be easier) by just 'wasting' some non critical memory.

Luck!
Guimo


Share this post


Link to post
Share on other sites
Quote:

Before you start flaming this answer shouting things like "You are wasting memory!!!!"... and all that just think a moment... How much memory will you really waste? 1MB? Thats too little for a compoter these days and the advantages are greater.


It's not the memory "waste" that is a concern, it the frailty of such a solution in the presence of maintainence and, even worse, change.

Share this post


Link to post
Share on other sites
Quote:
Original post by Guimo
How much memory will you really waste? 1MB? Thats too little for a compoter these days and the advantages are greater.


That's fine for heap memory or unitialized data, but it's more than enough to blow the stack or bloat the executable.

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