Implementing Dynamic Arrays in C: From realloc to Generic Containers

Introduction

In C++, std::vector serves as a dynamic array container, offering efficient memory management and convenient operations. However, in C, due to the lack of built-in container support, developers must manually implement similar functionality. Based on Q&A data, this article delves into multiple methods for implementing dynamic arrays in C, ranging from basic realloc usage to advanced generic container implementations, aiming to provide comprehensive technical insights for C developers.

Direct Memory Management with realloc

In C, the realloc function is a common tool for dynamically resizing memory. Its basic usage is as follows:

void* newMem = realloc(oldMem, newSize);
if(!newMem) {
    // handle error
}
oldMem = newMem;

This approach is straightforward but carries risks. For example, a common error is:

oldMem = realloc(oldMem, newSize);
if(!oldMem) {
    // handle error
}

If realloc fails and returns NULL, the original memory oldMem remains valid, but the above code causes a memory leak because oldMem is overwritten with NULL. Therefore, the correct practice is to store the result of realloc in a temporary variable first, and assign it only after success verification.

From a performance perspective, direct use of realloc may not guarantee amortized O(1) time complexity, although it can be more efficient in cases where memory can be expanded in place. In contrast, std::vector typically grows by allocating a new buffer and copying elements, ensuring amortized O(1) performance.

Encapsulated Implementations Based on Structs

To abstract memory management and provide safer interfaces, many C projects implement vector-like APIs. A typical implementation includes a struct to store array metadata and a set of operation functions. For instance, a struct can be defined as:

typedef struct dynamic_array_struct
{
  int* data;
  size_t capacity; /* total capacity */
  size_t size; /* number of elements */
} vector;

Then, functions for initialization, adding elements, and resizing are provided. An initialization function might look like:

int vector_init(vector* v, size_t init_capacity)
{
  v->data = malloc(init_capacity * sizeof(int));
  if (!v->data) return -1;

  v->size = 0;
  v->capacity = init_capacity;

  return 0; /* success */
}

When adding elements, if size exceeds capacity, memory is typically expanded via realloc or by allocating a new buffer. To minimize frequent reallocations, capacity is often increased by a factor (e.g., doubled), similar to the strategy used by std::vector. Note that in C++, std::vector might use placement new for object construction, whereas in C, memcpy is used for copying.

The uivector from the LodePNG library is a practical example, with usage as follows:

uivector v = {};
uivector_push_back(&v, 1);
uivector_push_back(&v, 42);
for(size_t i = 0; i < v.size; ++i)
    printf("%d\n", v.data[i]);
uivector_cleanup(&v);

The downside of this method is that the code can be verbose and requires duplication for different types, lacking generic support.

Generic Container Implementations

To achieve type-safe containers, void* pointers and macro techniques can be employed. The stb_ds.h library offers a concise implementation that works with any type. The core idea is to use macros to generate type-specific code, avoiding duplication. Example usage:

double *v = 0;
arrpush(v, 1.0);
arrpush(v, 42.0);
for(int i = 0; i < arrlen(v); ++i)
    printf("%g\n", v[i]);
arrfree(v);

In this implementation, arrays are represented as pointers to elements, with macros managing memory. For instance, the arrpush macro might internally call realloc to expand memory. This approach not only provides dynamic arrays but also supports other containers like hash maps, achieving effects similar to generic programming through macros.

Another generic implementation uses void* and element size information. For example, a generic vector struct can be defined:

typedef struct vec
{
    unsigned char* _mem;
    unsigned long _elems;
    unsigned long _elemsize;
    unsigned long _capelems;
    unsigned long _reserve;
} vec;

Then, functions like vec_push_back add elements, using memcpy for data copying. This method allows storing data of any type but requires manual management of element size and memory alignment.

Performance and Error Handling Comparison

In terms of performance, struct-based implementations and generic containers typically guarantee amortized O(1) time complexity through preallocation and doubling strategies, similar to std::vector. Direct use of realloc may not provide this guarantee, although it can be more efficient when memory is expandable.

Error handling is a critical consideration. When using realloc directly, care must be taken to avoid memory leaks. In encapsulated implementations, errors can be handled via return values or error flags, e.g., returning -1 in vector_init for failure. Generic containers like stb_ds.h may rely on assertions or return error values, but specifics should be checked in library documentation.

Additionally, memory management strategies differ: std::vector in C++ may involve object construction and destruction, while in C, malloc/free and memcpy are typically used, simplifying operations but requiring manual resource handling.

Conclusion and Best Practices

Implementing dynamic arrays in C offers multiple methods, with the choice depending on project needs. For simple scenarios, direct use of realloc may suffice, but error handling must be cautious. For projects requiring safety and abstraction, encapsulated struct-based implementations are recommended, providing clear APIs and memory management. For generic needs, libraries like stb_ds.h offer efficient and type-safe solutions.

Best practices include: using doubling strategies to optimize performance, ensuring error handling to prevent memory leaks, and considering code reuse via macros or template techniques. Moreover, hiding implementation details (e.g., placing struct definitions in .c files) can enhance encapsulation.

In summary, although C lacks built-in containers, developers can implement powerful and efficient dynamic arrays using the techniques discussed, meeting various application requirements.