What Collections Are Available in Modern C?

In any serious program you write sooner or later you will have the need for a Collection of data. As a C Programmer you may want to know if there are Standard Collections that are available to you.

There are no collections in the C Standard besides the Array. Unlike C++, C has no classes and thus no container classes. If you need a special container class you have to implement it on your own. Usually available Collections are Arrays, Vectors, Lists, Queues, Stacks and Maps.

In this article I will show you which container classes exist in C++ and how a C version of this classes could look like in C. This is a general overview, I will also provide links to articles where one can learn about the implementations in detail.

Collections in Modern C

First we will look at the Standard C Array and then I will show you the most useful container classes alongside with an example how a C implementation could look like.

Then we will show some useful Collections with examples how they could look like in C. I will also provide links to In-Depth Articles on how to implement them.

Standard C Array

An Array is a container which holds Elements of the same type. Arrays in C are fixed in size at compile time. You can access elements of the Array by its index.

Following is an example of using a Standard C Array.

int my_array[4];
my_array[0] = 3;
printf("Array at Index 0:%d\n", my_array[0]);

Array at Index 0: 3

If you want to pass an Array as a parameter to a function you have to use pointers. You may access the array as usual, but the parameter declaration gives no hint about the size. In a larger codebase, it is easier to get access an invalid index.

void takes_array_parameter(int* arrayParam)
{
    arrayParam[0] = 2;
}

int main(int argc, char** argv)
{
    int my_array[4];
    my_array[0] = 3;

    takes_array_parameter(my_array);

    return 0;
}

Array Class

An improved version over the Standard C Array could be an Array Class. Although it is also fixed in size you have functions that give you information about the Array, like size(…). If you pass the array to a function you can then dynamically make sure not to access an invalid index.

You can find a comlete Implementation of an Array Class in C here. With this Implementation you could use an Array like this:

array_t* my_array = array_new();
array_ctr(my_array, 4);
array_set(my_array, 0, 3);
printf("Dynamic Array at Index 0:%d\n", array_at(0));

This leads to the following output:

Dynamic Array at Index 0: 3

Vector

A Vector is the container you will need if you want a flexible Array. Vectors are resizeable and do not need to know the size at compile time. In order to not reallocate memory with every new Element, memory is reserved in advanced and may be unused.

You can find a comlete Implementation of a Vector Class in C here. With this Implementation you could use a Vector like this:

vector_t* my_vector = vector_new();
vector_ctr(my_vector);

vector_push_back(my_vector, 55);
vector_push_back(my_vector, 34);
vector_push_back(my_vector, 67);
vector_push_back(my_vector, 70);

printf("Vector at Index 0: %d\n", vector_at(my_vector, 0));
printf("Vector Size: %d\n", vector_size(my_vector));
printf("Vector Capacity: %d\n", vector_capacity(my_vector));

vector_dtr(my_vector);

Vector at Index 0: 55
Vector Size: 4
Vector Capacity: 4

Linked List

A Linked List provides the flexibility of a Vector but also is more memory efficient because no unused memory is reserved. The trade-off is that Elements are scattered across the heap memory and only linked so we cannot access elements directly but have to traverse through the list.

You can find a comlete Implementation of a Linked List Class in C here. With this Implementation you could use a Linked List like this:

list_t* my_list = list_new();
list_ctr(my_list);

list_push_back(my_list, 42);

printf("Linked List Size: %d\n", list_size(my_list));

list_push_front(my_list, 55);

printf("Linked List at Index 0: %d\n", list_size(my_list));
printf("Linked List Size: %d\n", list_size(my_list));

list_dtr(my_list);

The output shows how the list grows and what the first Element is.

Linked List Size: 1
Linked List at Index 0: 55
Linked List Size: 2

Queue

A Queue is a special container because you cannot access its Elements indiviually but only the front one. Its like a queue in the supermarket where the first person that gets into the queue is served first. This is called FIFO, or First In First Out principle.

You can find a comlete Implementation of a Queue Class in C here. With this Implementation you could use a Queue like this:

queue_t* my_queue = queue_new();
queue_ctr(my_queue);    

queue_push(my_queue, 1);
queue_push(my_queue, 3);
queue_push(my_queue, 5);

printf("Queue Size: %d\n", queue_size(my_queue));
printf("First Element: %d\n", queue_front(my_queue));
printf("Last Element: %d\n", queue_back(my_queue));

queue_dtr(my_queue);

return 0;

We then would have the following output:

Queue Size: 3
First Element: 1 
Last Element: 5

Stack

A Stack is similar to a Queue with the difference that you have only access to the Element you put in last. It works like a stack of magazines where you take the one first that you put there last. It is called LIFO or Last In First Out principle.

You can find a comlete Implementation of a Stack Class in C here. With this Implementation you could use a Stack like this:

stack_t* my_stack = stack_new();
stack_ctr(my_stack);

stack_push(my_stack, 1);
stack_emplace(my_stack, 3);

printf("Stack Size: %d\n", stack_size(my_stack));
printf("Top Element of the Stack is: %d\n", stack_top(my_stack));

stack_dtr(my_stack);

In the output you see that the Top Element is the one we put onto the Stack last.

Stack Size: 2
Top Element of the Stack is: 3

Map

A Map is often also called a Dictionary which describes it very good. You have a Key that serves as an Index and a corresponding Value that you want to find at the Index. The Key can be any type, and the Value does not have to be the same type as the Key. However, a Key must be unique within the Map.

You can find a comlete Implementation of a Map Class in C here. With this Implementation you could use a Map like this:

map_t* my_map = map_new();
map_ctr(my_map);

map_insert(my_map, 1, 'A');
map_insert(my_map, 2, 'B');

printf("Value at Key 1: '%c'\n", map_at(my_map, 1)); /* Valid Key */

map_dtr(my_map);

The output shows the direct access of the Value by its Key.

Value at Key 1: 'A'

Summary

Now you know the most common Container Classes and have an idea how the could be implemented in C. For detailed Implementations you should look into each article of the indiviudal Container Class.