Array of structs vs. Array of pointers to structs

Question

As I continue learning the C language I got a doubt. Which are the differences between using an array in which each element is an struct and using an array in which each element is a pointer to the same type of struct. It seems to me that you can use both equally (Although in the pointers one you have to deal with memory allocation). Can somebody explain me in which case it is better to use one or the other?

Thank you.

Answer 1

Arrays of structures and arrays of pointers to structures are different ways to organize memory.

Arrays of structures have these strong points:

• it is easy to allocate such an array dynamically in one step with struct s *p = calloc(n, sizeof(*p));.
• if the array is part of an enclosing structure, no separate allocation code is needed at all. The same is true for local and global arrays.
• the array is a contiguous block of memory, a pointer to the next and previous elements can be easily computed as struct s *prev = p - 1, *next = p + 1;
• accessing array element members may be faster as they are close in memory, increasing cache efficiency.

They also have disadvantages:

• the size of the array must be passed explicitly as there is no way to tell from the pointer to the array how many elements it has.
• the expression p[i].member generates a multiplication, which may be costly on some architectures if the size of the structure is not a power of 2.
• changing the order of elements is costly as it may involve copying large amounts of memory.

Using an array of pointers has these advantages:

• the size of the array could be determined by allocating an extra element and setting it to NULL. This convention is used for the argv[] array of command line arguments provided to the main() function.
• if the above convention is not used, and the number of elements is passed separately, NULL pointer values could be used to specify missing elements.
• it is easy to change the order of elements by just moving the pointers.
• multiple elements could be made to point to the same structure.
• reallocating the array is easier as only the array of pointers needs reallocation, optionally keeping separate length and size counts to minimize reallocations. Incremental allocation is easy too.
• the expression p[i].member generates a simple shift and an extra memory access, but may be more efficient than the equivalent expression for arrays of structures.

and the following drawbacks:

• allocating and freeing this indirect array is more cumbersome. An extra loop is required to allocate and/or initialize the structures pointed to by the array.
• access to structure elements involve an extra memory indirection. Compilers can generate efficient code for this if multiple members are accessed in the same function, but not always.
• pointers to adjacent structures cannot be derived from a pointer to a given element.

EDIT: As hinted by David Bowling, one can combine some of the advantages of both approaches by allocating an array of structures on one hand and a separate array of pointers pointing to the elements of the first array. This is a handy way to implement a sort order, or even multiple concomitant sort orders with separate arrays of pointers, like database indexes.