The C programming language lacks a built-in Standard Template Library (STL) like C++'s, yet many C developers need efficient data structures and algorithms for real-world projects. This gap can be bridged through several approaches: implementing containers manually, using lightweight header-only libraries, or adopting comprehensive external libraries. This article explores the most practical STL alternatives in C, providing guidance on choosing the right method for your next project.

Understanding the Need for STL‑Like Functionality in C

The C++ STL provides generic, type‑safe containers (vectors, lists, maps, sets) along with algorithms and iterators. C, being a lower‑level language, leaves you to manage memory and data structures directly. The need for dynamic arrays, hash tables, linked lists, and balanced trees arises frequently — in parsers, game engines, network servers, embedded firmware, and scientific computing. Without built‑in support, you must either reinvent these structures or rely on third‑party libraries.

Common Data Structure Requirements

  • Dynamic arrays – resizeable vectors for sequential data.
  • Hash tables – key‑value storage with O(1) average lookup.
  • Linked lists – doubly‑linked or singly‑linked lists for frequent insert/delete.
  • Balanced trees – red‑black trees or AVL trees for ordered associative containers.
  • Queues and heaps – priority queues or simple FIFO structures.

The C standard library offers only basic memory allocation (`malloc`, `realloc`, `free`), file I/O, and string functions. Everything else must be built or borrowed. Fortunately, the open‑source community has produced several mature, high‑quality libraries that fill the void.

Manually Implementing Data Structures

Writing your own data structures in C gives you full control and can be educational. However, it demands careful memory management and attention to performance.

Dynamic Arrays (Resizable Vectors)

A dynamic array in C is typically built on top of `malloc` and `realloc`. You maintain three pieces: a pointer to the allocated memory, the current capacity, and the current length. When the array fills, you double the capacity using `realloc`. Here is a minimal example for an integer vector:

#include <stdlib.h>
typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} IntVector;

void iv_init(IntVector *v) {
    v->data = NULL;
    v->size = 0;
    v->capacity = 0;
}

void iv_push(IntVector *v, int value) {
    if (v->size == v->capacity) {
        v->capacity = v->capacity ? v->capacity * 2 : 4;
        int *tmp = realloc(v->data, v->capacity * sizeof(int));
        if (!tmp) exit(EXIT_FAILURE);
        v->data = tmp;
    }
    v->data[v->size++] = value;
}

void iv_free(IntVector *v) {
    free(v->data);
    v->data = NULL;
    v->size = v->capacity = 0;
}

This pattern works, but you must handle reallocation failures and avoid common pitfalls such as using `realloc` on a pointer that also holds the only reference (always save the return value into a temporary variable). For production code, the doubling strategy and initial capacity should be tuned to your use case.

Linked Lists

Linked lists require defining a node structure with one or more pointers. A doubly‑linked node might look like this:

typedef struct DListNode {
    int data;
    struct DListNode *prev;
    struct DListNode *next;
} DListNode;

You then write functions for insertion, deletion, traversal, and cleanup. The main challenge is avoiding memory leaks — each `malloc` for a node must eventually have a matching `free`. Circular references are not a problem in C, but pointer errors can corrupt the list.

Hash Tables

Rolling your own hash table is significantly more complex. You need a hash function, collision resolution (often chaining with linked lists or open addressing), dynamic resizing, and a way to handle keys of arbitrary types. Most seasoned C developers prefer to use an established library like uthash instead of reinventing this wheel.

Binary Search Trees

Unbalanced binary search trees are straightforward to implement, but degenerate cases lead to O(n) performance. Balanced trees (AVL, red‑black) require rotation logic and careful maintenance of balance invariants. For most applications, the extra effort is not justified when libraries like GLib provide production‑ready tree containers.

The manual approach is most appropriate for small, self‑contained projects or when learning how data structures work. For larger codebases, the time spent debugging custom containers can quickly outweigh the overhead of integrating a library.

Lightweight Header‑Only Libraries

Header‑only libraries are attractive because they require no separate compilation or linking — you simply `#include` one or a few files. Several excellent header‑only C libraries offer STL‑like containers with minimal overhead.

uthash

uthash is a popular header‑only hash table implementation for C. It uses macros to generate type‑specific hash table operations. To use it, you include `uthash.h` and add a `UT_hash_handle` field to your struct. Example:

#include "uthash.h"
struct my_struct {
    int id;            // key
    char name[32];
    UT_hash_handle hh; // makes this structure hashable
};

struct my_struct *users = NULL;

void add_user(int id, const char *name) {
    struct my_struct *s = malloc(sizeof(*s));
    s->id = id; strcpy(s->name, name);
    HASH_ADD_INT(users, id, s);
}

struct my_struct *find_user(int id) {
    struct my_struct *s;
    HASH_FIND_INT(users, &id, s);
    return s;
}

Uthash supports integer, string, and pointer keys, as well as custom hashing. It handles resizing automatically and is widely used in embedded systems, game engines, and command‑line tools. The library is very mature and well documented.

klib (kvec, khash, kbt)

klib is a collection of lightweight header‑only components written by Heng Li. The most relevant for STL‑like functionality are:

  • kvec – dynamic array (like C++ `std::vector`). Uses macro `kvec_t(type)` and functions `kv_push`, `kv_a` (access by index), etc.
  • khash – hash table (like `std::unordered_map`). Provides open addressing with double hashing. Supports integer, string, and generic keys.
  • kbt – balanced binary search tree (like `std::set` or `std::map`). Implements a treap (randomized binary search tree).

Example using kvec for a dynamic array of floats:

#include "kvec.h"
kvec_t(float) array;
kv_init(array);
kv_push(float, array, 1.5f);
kv_push(float, array, 2.3f);
for (size_t i = 0; i < kv_size(array); i++) {
    printf("%f\n", kv_A(array, i));
}
kv_destroy(array);

klib components are minimal, fast, and have been battle‑tested in bioinformatics tools like SAMtools.

STB Data Structures (stb_ds.h)

STB by Sean Barrett includes `stb_ds.h`, a single‑header library providing dynamic arrays, hash maps, and hash sets using macros. Its API is concise and similar to C++ STL containers. For instance, to create a dynamic array of integers:

#define STB_DS_IMPLEMENTATION
#include "stb_ds.h"

int *arr = NULL;
arrput(arr, 10);
arrput(arr, 20);
printf("Length: %zu\n", arrlen(arr));  // 2
arrfree(arr);

Hash maps are equally simple. The library manages memory and reallocation transparently. STB is public domain and extremely portable.

Comprehensive Libraries: GLib

GLib is a heavyweight but performance‑oriented general‑purpose utility library. It provides not only data structures but also memory allocation, string utilities, event loops, threading, and more. GLib is the foundation of GTK+, but it can be used entirely independently in non‑GUI applications.

Key Containers

  • GArray – dynamic array, resizes automatically, supports element‑aligned storage.
  • GHashTable – hash map with arbitrary key and value types (using GDestroyNotify).
  • GList / GSList – doubly‑linked and singly‑linked lists.
  • GQueue – double‑ended queue.
  • GTree – balanced binary tree (red‑black).
  • GPtrArray – array of pointers.

Example: Using GHashTable

#include <glib.h>

int main() {
    GHashTable *table = g_hash_table_new(g_str_hash, g_str_equal);
    g_hash_table_insert(table, "key1", "value1");
    g_hash_table_insert(table, "key2", "value2");
    gchar *val = g_hash_table_lookup(table, "key1");
    g_print("Found: %s\n", val);  // "Found: value1"
    g_hash_table_destroy(table);
    return 0;
}

GLib containers are fully featured, support iteration via `GHashTableIter`, and integrate well with GLib's memory‑slicing allocator for performance. However, GLib is a large library; linking it adds roughly 200 KB to your binary even if you use only one container. It also relies on its own type system and memory management conventions.

For desktop applications, server daemons, or projects that already depend on GTK, GLib is a natural choice. For tiny embedded systems, it may be overkill.

Choosing Between Manual Implementation and Libraries

No single approach fits all projects. Evaluate the following factors:

Project Size and Complexity

Small utilities or exploration code can get away with manual implementations. Larger applications, especially those maintained by a team, benefit from well‑tested libraries to reduce bugs and development time.

Performance Requirements

Manual implementations can be optimized for a specific usage pattern — e.g., a custom memory pool for frequent small allocations. Libraries like GLib and uthash are already highly optimized for general use. Benchmarking is always recommended.

Maintainability and Documentation

Libraries have documentation, examples, and community support. Rolling your own means you own every bug. Time spent debugging a subtle hash table issue could have been spent integrating a library.

Portability and Dependencies

Header‑only libraries (uthash, klib, STB) are extremely portable — you only need a C99 or later compiler. GLib requires building its own library and may have platform quirks, though it is widely supported on Linux, macOS, and Windows.

Learning Value

If your goal is to understand how data structures work under the hood, manual implementation is invaluable. For shipping product code, leverage existing work.

Practical Recommendations

  • For hash tables – use uthash unless you need red‑black trees, in which case turn to GLib or klib's kbt.
  • For dynamic arrays – kvec or stb_ds are excellent choices. If you prefer an AMT (array‑map‑table) hybrid, consider stb_ds.
  • For linked lists – rarely needed in modern C; dynamic arrays or hash maps often suffice. If you must have a list, GLib's GList is robust.
  • For balanced trees – GLib's GTree or klib's kbt. Avoid manual red‑black trees unless you have a specific requirement.
  • Memory‑constrained environments – use header‑only libraries; avoid GLib.

Performance Considerations

All the libraries mentioned are implemented in efficient C and generally match or exceed the performance of hand‑rolled code. The real cost is often memory overhead rather than CPU cycles. For example, GLib's GHashTable uses separate allocation for each key/value pair, while uthash embeds the hash handle directly in your struct, saving a pointer indirection. klib's khash uses open addressing, which has better cache locality than chaining.

When performance is critical, profile with your actual workload. Write a small test harness that exercises insertion, lookup, deletion, and iteration. Compare against a simple manual implementation. In many cases, the library version wins because it incorporates years of optimization (e.g., uthash's macro‑based code avoids function call overhead).

Conclusion

C does not have an STL, but you are not forced to write every container from scratch. The ecosystem offers multiple viable alternatives: manual implementations for learning and tiny projects, lightweight header‑only libraries like uthash, klib, and stb_ds for minimal dependencies, and comprehensive libraries like GLib when you need a full toolkit. By understanding the trade‑offs and your project's constraints, you can choose the approach that delivers robust, maintainable, and performant code.