Storing a Dynamic Array of Structures

Question

I have been working on a project which utilizes a dynamic array of structures. To avoid storing the number of structures in its own variables (the count of structures), I have been using an array of pointers to the structure variables with a NULL terminator.

For example, let's say my structure type is defined as:

typedef struct structure_item{
    /* ... Structure Variables Here ... */
} item_t;

Now let's say my code has item_t **allItems = { item_1, item_2, item_3, ..., item_n, NULL }; and all item_#s are of the type item_t *.

Using this setup, I then do not have to keep track of another variable which tells me the total number of items. Instead, I can determine the total number of items as needed by saying:

int numberOfStructures;
for( numberOfStructures = 0;
     *(allItems + numberOfStructures) != NULL;
     numberOfStructures++
  );

When this code executes, it counts the total number of pointers before NULL.

As a comparison, this system is similar to C-style strings; whereas tracking the total number of structures would be similar to a Pascal-style string. (Because C uses a NULL terminated array of characters vs. Pascal which tracks the length of its array of characters.)

My question is rather simple, is an array of pointers (pointer to pointer to struct) really necessary or could this be done with an array of structs (pointer to struct)? Can anybody provide better ways to handle this?

Note: it is important that the solution is compatible with both C and C++. This is being used in a wrapper library which is wrapping a C++ library for use in standard C.

Thank you all in advance!

Unless you have an easy way to detect the last NULL type structure, you usage of indirection via pointers is ideal. Moreover, with the pointers, you can reorganize without moving large structures, and expand without hitting large reallocations. However, as slick as the NULL end solution is, traversing the entire array to determine the length may become an expensive operation where a length variable or end pointer could alleviate. — George Houpis
– George Houpis, Commented Jan 31, 2015 at 21:48
A simple question: if one of the pointers you store happened to be set to NULL, what would happen with everything stored after that pointer ? Most likely you'd lose track of the pointers and the pointed memory, causing memory leaks. So I guess you'd have to make really sure this never happens. — SirDarius
– SirDarius, Commented Jan 31, 2015 at 22:00
@SirDarius, this is something I thought about and I am hoping someone can suggest a solution which would handle this case. That said, storing the number of structures presents this same risk because int numberOfStructures could just as easily be misassigned somewhere. — Spencer D
– Spencer D, Commented Jan 31, 2015 at 22:13
That is why I believe having all structs directly together, allocated only once with malloc, and the array growing with realloc would be easier to manage, since when having to free the array, all elements would be freed in one operation, instead of having to iterate. Also you would probably get better performance overall with this approach due to the principle of locality. — SirDarius
– SirDarius, Commented Jan 31, 2015 at 22:23
@SirDarius, good point. That is definitely something to consider. — Spencer D
– Spencer D, Commented Jan 31, 2015 at 22:33

Quentin · Accepted Answer · 2015-01-31 21:49:53Z

2

What you need is a sentinel value, a recognizable valid value that means "nothing". For pointers, the standard sentinel value is NULL.

If you want to use your structs directly, you will need to decide on a sentinel value of type item_t, and check for that. Your call.

answered Jan 31, 2015 at 21:49

Quentin

63.5k7 gold badges139 silver badges199 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Spencer D Over a year ago

That's what I was afraid of. I suppose I'll stick with the array of pointers because my code is already written that way and my actual structures have some overhead. Thanks for input.

Rob · Accepted Answer · 2015-01-31 21:59:28Z

Yes, it is possible to have an array of structs, and (at least) one of those a defined sentinel (which is that the '\0' used at the end of strings, and the NULL pointer in your case).

What you need to do, for your struct type, is reserve one or more possible values of that struct (composed of the set of values of its members) to indicate a sentinel.

For example, let's say we have a struct type

struct X {int a; char *p};

then define a function

int is_sentinel(struct X x)
{
    return x.p == NULL;
}

This will mean any struct X for which the member p is NULL can be used as a sentinel (and the member a would not matter in this case).

Then just loop looking for a sentinel.

Note: to be compatible in both C and C++, the struct type needs to be compatible (e.g. POD).

Collectives™ on Stack Overflow

Storing a Dynamic Array of Structures

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related