C dynamically growing array

Question

I have a program that reads a "raw" list of in-game entities, and I intend to make an array holding an index number (int) of an indeterminate number of entities, for processing various things. I would like to avoid using too much memory or CPU for keeping such indexes...

A quick and dirty solution I use so far is to declare, in the main processing function (local focus) the array with a size of the maximum game entities, and another integer to keep track of how many have been added to the list. This isn't satisfactory, as every list holds 3000+ arrays, which isn't that much, but feels like a waste, since I'll possible use the solution for 6-7 lists for varying functions.

I haven't found any C (not C++ or C#) specific solutions to achieve this. I can use pointers, but I am a bit afraid of using them (unless it's the only possible way).

The arrays do not leave the local function scope (they are to be passed to a function, then discarded), in case that changes things.

If pointers are the only solution, how can I keep track of them to avoid leaks?

Answer 1

There are a couple of options I can think of.

1. Linked List. You can use a linked list to make a dynamically growing array like thing. But you won't be able to do array[100] without having to walk through 1-99 first. And it might not be that handy for you to use either.
2. Large array. Simply create an array with more than enough space for everything
3. Resizing array. Recreate the array once you know the size and/or create a new array every time you run out of space with some margin and copy all the data to the new array.
4. Linked List Array combination. Simply use an array with a fixed size and once you run out of space, create a new array and link to that (it would be wise to keep track of the array and the link to the next array in a struct).

It is hard to say what option would be best in your situation. Simply creating a large array is ofcourse one of the easiest solutions and shouldn't give you much problems unless it's really large.

Answer 2

You might want to consider using hash tables.

http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_hashtable.aspx

http://en.wikipedia.org/wiki/Hash_table

Answer 3

When you're saying

make an array holding an index number (int) of an indeterminate number of entities

you're basically saying you're using "pointers", but one which is a array-wide local pointer instead of memory-wide pointer. Since you're conceptually already using "pointers" (i.e. id numbers that refers to an element in an array), why don't you just use regular pointers (i.e. id numbers that refers to an element in the biggest array: the whole memory).

Instead of your objects storing a resource id numbers, you can make them store a pointer instead. Basically the same thing, but much more efficient since we avoid turning "array + index" into a "pointer".

Pointers are not scary if you think of them as array index for the whole memory (which is what they actually are)

Answer 4

Glib has a good solution for C with reference counting to help with memory management, and is free and cross platform. If you want something more basic, you should look at realloc. C programming is really, really hard to do without pointers. May as well start getting comfortable with them now.

Answer 5

I can use pointers, but I am a bit afraid of using them.

If you need a dynamic array, you can't escape pointers. Why are you afraid though? They won't bite (as long as you're careful, that is). There's no built-in dynamic array in C, you'll just have to write one yourself. In C++, you can use the built-in vector class. C# and just about every other high-level language also have some similar class that manages dynamic arrays for you.

If you do plan to write your own, here's something to get you started: most dynamic array implementations work by starting off with an array of some (small) default size, then whenever you run out of space when adding a new element, double the size of the array. As you can see in the example below, it's not very difficult at all: (I've omitted safety checks for brevity)

typedef struct {
  int *array;
  size_t used;
  size_t size;
} Array;

void initArray(Array *a, size_t initialSize) {
  a->array = (int *)malloc(initialSize * sizeof(int));
  a->used = 0;
  a->size = initialSize;
}

void insertArray(Array *a, int element) {
  if (a->used == a->size) {
    a->size *= 2;
    a->array = (int *)realloc(a->ptr, a->size * sizeof(int));
  }
  a->array[a->used++] = element;
}

void freeArray(Array *a) {
  free(a->array);
  a->array = NULL;
  a->used = a->size = 0;
}

Using it is just as simple:

Array a;
int i;

initArray(&a, 5);  // initially 5 elements
for (i = 0; i < 100; i++)
  insertArray(&a, i);  // automatically resizes as necessary
printf("%d\n", a.array[9]);  // print 10th element
printf("%d\n", a.used);  // print number of elements
freeArray(&a);