Home

Awesome

STC

STC - Smart Template Containers

Version 5.0 beta 4

Description

STC is a modern, typesafe, fast and compact container and algorithms library for C99. The API naming is similar to C++ STL, but it takes inspiration from Rust and Python as well. The library handles everything from trivial to highly complex data using templates.

Containers

Algorithms

List of contents

Highlights

STC is unique!

  1. Centralized analysis of template parameters. The analyser assigns values to all non-specified template parameters (based on the specified ones) using meta-programming, so that you don't have to! You may specify a set of "standard" template parameters for each container, but as a minimum only one is required: i_key (+ i_val for maps). In this case, STC assumes that the elements are of basic types. For non-trivial types, additional template parameters must be given.
  2. Alternative insert/lookup type. You may specify an alternative type to use for lookup in containers. E.g., containers with STC string elements (cstr) uses const char* as lookup type, so constructing a cstr (which may allocate memory) for the lookup is not needed. Hence, the alternative lookup key does not need to be destroyed after use, as it is normally a POD type. Finally, the key may be passed to an emplace-function. So instead of calling e.g. vec_str_push(&vec, cstr_from("Hello")), you may call vec_str_emplace(&vec, "Hello"), which is functionally identical, but more convenient.
  3. Standardized container iterators. All containers can be iterated in the same manner, and all use the same element access syntax. E.g.:
    • c_foreach (it, MyInts, myints) *it.ref += 42; works for any container defined as MyInts with int elements.
    • c_foreach (it, MyInts, it1, it2) *it.ref += 42; iterates from it1 up to not including it2.

Performance

STC is a fast and memory efficient library, and code compiles fast:

Benchmark

Benchmark notes:

Naming conventions

Usage

STC containers have similar functionality to the C++ STL standard containers. All containers except for a few, like cstr and cbits are generic/templated. No type casting is used, so containers are type-safe like templated types in C++. However, to specify template parameters with STC, you define them as macros prior to including the container, e.g.

#define i_TYPE Floats, float // Container type (name, element type)
#include "stc/vec.h"         // "instantiate" the desired container type
#include <stdio.h>

int main(void)
{
    Floats nums = {0};
    Floats_push(&nums, 30.f);
    Floats_push(&nums, 10.f);
    Floats_push(&nums, 20.f);

    for (int i = 0; i < Floats_size(&nums); ++i)
        printf(" %g", nums.data[i]);

    c_foreach (i, Floats, nums)     // Alternative and recommended way to iterate.
        printf(" %g", *i.ref);      // i.ref is a pointer to the current element.

    Floats_drop(&nums); // cleanup memory
}

Note that i_val* template parameters can be used instead of i_key* for non-map containers.

Switching to a different container type, e.g. a sorted set (sset):

[ Run this code ]

#define i_TYPE Floats, float
#include "stc/sset.h" // Use a sorted set instead
#include <stdio.h>

int main(void)
{
    Floats nums = {0};
    Floats_push(&nums, 30.f);
    Floats_push(&nums, 10.f);
    Floats_push(&nums, 20.f);

    // print the numbers (sorted)
    c_foreach (i, Floats, nums)
        printf(" %g", *i.ref);

    Floats_drop(&nums);
}

Comparison/lookup functions are enabled by default for associative containers and priority queue (hmap, hset, smap, sset, pque). To enable it for the remaining containers, define i_cmp or i_less (and optionally i_eq) on the element type. If the element is an integral type, simply define i_use_cmp to use < and == operators for comparisons.

Note that for #define i_key_class Type, defining i_use_cmp means that Type_cmp() function is expected to exist (along with Type_clone() and Type_drop()).

To summarize, i_use_cmp is only needed to enable comparison (sort/search) functions when defining stack, vec, queue, deq, arc, box. With built-in types, it enables the comparison operators, whereas for keyclass types, it binds comparison to its Type_cmp() function.

If an element destructor i_keydrop is defined, i_keyclone function is required. Alternatively #define i_opt c_no_clone to disable container cloning.

Let's make a vector of vectors, which can be cloned. All of its element vectors will be destroyed when destroying the Vec2D.

[ Run this code ]

#include <stdio.h>

#define i_TYPE Vec, float
#include "stc/vec.h"

#define i_type Vec2D
#define i_key_class Vec  // Use i_key_class instead i_key when element type has "members" _clone(), _drop() and _cmp().
#include "stc/vec.h"

int main(void)
{
    Vec* v;
    Vec2D vec = {0};                  // All containers in STC can be initialized with {0}.
    v = Vec2D_push(&vec, Vec_init()); // push() returns a pointer to the new element in vec.
    Vec_push(v, 10.f);
    Vec_push(v, 20.f);

    v = Vec2D_push(&vec, Vec_init());
    Vec_push(v, 30.f);
    Vec_push(v, 40.f);

    Vec2D clone = Vec2D_clone(vec);   // Make a deep-copy of vec

    c_foreach (i, Vec2D, clone)       // Loop through the cloned vector
        c_foreach (j, Vec, *i.ref)
            printf(" %g", *j.ref);

    c_drop(Vec2D, &vec, &clone);      // Cleanup all (6) vectors.
}

This example uses four different container types:

[ Run this code ]

#include <stdio.h>

#define i_key int
#include "stc/hset.h"   // hset_int: unordered/hash set (assume i_key is basic type, uses `==` operator)

struct Point { float x, y; };
// Define cvec_pnt and enable linear search by defining i_eq
#define i_TYPE vec_pnt, struct Point
#define i_eq(a, b) (a->x == b->x && a->y == b->y)
#include "stc/vec.h"    // vec_pnt: vector of struct Point

#define i_key int
#define i_use_cmp       // enable sort/search. Use native `<` and `==` operators
#include "stc/list.h"   // list_int: singly linked list

#define i_TYPE smap_int, int, int
#include "stc/smap.h"  // sorted map int => int

int main(void)
{
    // Define four empty containers
    hset_int set = {0};
    vec_pnt vec = {0};
    list_int lst = {0};
    smap_int map = {0};

    c_defer( // Drop the containers at scope exit
        hset_int_drop(&set),
        vec_pnt_drop(&vec),
        list_int_drop(&lst),
        smap_int_drop(&map)
    ){
        enum{N = 5};
        int nums[N] = {10, 20, 30, 40, 50};
        struct Point pts[N] = { {10, 1}, {20, 2}, {30, 3}, {40, 4}, {50, 5} };
        int pairs[N][2] = { {20, 2}, {10, 1}, {30, 3}, {40, 4}, {50, 5} };

        // Add some elements to each container
        for (int i = 0; i < N; ++i) {
            hset_int_insert(&set, nums[i]);
            vec_pnt_push(&vec, pts[i]);
            list_int_push_back(&lst, nums[i]);
            smap_int_insert(&map, pairs[i][0], pairs[i][1]);
        }

        // Find an element in each container
        hset_int_iter i1 = hset_int_find(&set, 20);
        vec_pnt_iter i2 = vec_pnt_find(&vec, (struct Point){20, 2});
        list_int_iter i3 = list_int_find(&lst, 20);
        smap_int_iter i4 = smap_int_find(&map, 20);

        printf("\nFound: %d, (%g, %g), %d, [%d: %d]\n",
                *i1.ref, i2.ref->x, i2.ref->y, *i3.ref,
                i4.ref->first, i4.ref->second);

        // Erase all the elements found
        hset_int_erase_at(&set, i1);
        vec_pnt_erase_at(&vec, i2);
        list_int_erase_at(&lst, i3);
        smap_int_erase_at(&map, i4);

        printf("After erasing the elements found:");
        printf("\n set:");
        c_foreach (i, hset_int, set)
            printf(" %d", *i.ref);

        printf("\n vec:");
        c_foreach (i, vec_pnt, vec)
            printf(" (%g, %g)", i.ref->x, i.ref->y);

        printf("\n lst:");
        c_foreach (i, list_int, lst)
            printf(" %d", *i.ref);

        printf("\n map:");
        c_foreach (i, smap_int, map)
            printf(" [%d: %d]", i.ref->first, i.ref->second);
    }
}

Output

Found: 20, (20, 2), 20, [20: 2]
After erasing the elements found:
 set: 40 10 30 50
 vec: (10, 1) (30, 3) (40, 4) (50, 5)
 lst: 10 30 40 50
 map: [10: 1] [30: 3] [40: 4] [50: 5]

Installation

STC is primarily a "headers-only" library, so most headers can simply be included in your program. By default, all templated functions are static (many inlined). This is often optimal for both performance and compiled binary size. However, if container type instances, e.g. a vec_int is used used in several translation units, (e.g. more than 3-4 TUs), consider creating a separate header file for them and link it shared as described here. In this case, one (of the) c-file must implement the templated container, e.g.:

#define i_implement // define shared symbols
#include "vec_int.h"

Note that the non-templated string types cstr, csview uses shared linking by default (may use static linking by #define i_static before include). Most functions in csview are inlined though, and the zero-terminated string view, czview is fully inlined.

Conveniently, src\libstc.c implements all the non-templated functions with shared linking for cstr, csview, cregex, utf8, and crand.

Additionally, #define i_import works as i_implement for cregex or cstr, but it will also implement the dependent utf8 functions (utf8 case conversions, etc.). Or you can simply link with libstc.

Specifying template parameters

Each templated type requires one #include, even if it's the same container base type, as described earlier. The template parameters are given by a #define i_xxxx statement, where xxxx is the parameter name. The list of template parameters:

Properties:

Key:

Val: (hmap/smap mapped value only)

Specials: Meta-template parameters. Use instead of i_key / i_val.

Notes:

Specifying comparison parameters

The table below shows the template parameters which must be defined to support element search and sort for various containers versus element types.

For the containers marked optional, the features are disabled if the template parameter(s) are not defined. Note that the (integral type) columns also applies to "special" types, specified with i_key_str, i_key_arcbox, and i_key_class, and not only true integral types like int or float.

Containerfind (integral type)sort (integral type)|find (struct elem)sort (struct elem)optional
stack, queuen/an/an/an/an/a
vec, deq, listi_use_cmpi_use_cmpi_eqi_cmp / i_lessyes
box, arci_use_cmpi_use_cmpi_eq + i_hashi_cmp / i_lessyes
hmap, hsetn/ai_eq + i_hashn/ano
smap, sseti_cmp / i_lessi_cmp / i_lessno
pquen/an/ai_cmp / i_lessno

The emplace methods

STC, like c++ STL, has two sets of methods for adding elements to containers. One set begins with emplace, e.g. vec_X_emplace_back(). This is an ergonimic alternative to vec_X_push_back() when dealing non-trivial container elements, e.g. strings, shared pointers or other elements using dynamic memory or shared resources.

The emplace methods constructs / clones the given element when they are added to the container. In contrast, the non-emplace methods moves the element into the container.

Note: For containers with integral/trivial element types, or when neither i_keyraw/i_valraw is defined, the emplace functions are not available (or needed), as it can easier lead to mistakes.

non-emplace: Moveemplace: Embedded copyContainer
insert(), push()emplace()hmap, smap, hset, sset
insert_or_assign()emplace_or_assign()hmap, smap
push()emplace()queue, pque, stack
push_back(), push()emplace_back()deq, list, vec
push_front()emplace_front()deq, list

Strings are the most commonly used non-trivial data type. STC containers have proper pre-defined definitions for cstr container elements, so they are fail-safe to use both with the emplace and non-emplace methods:

#define i_implement     // define in ONE file to implement longer functions in cstr
#include "stc/cstr.h"

#define i_key_str       // special macro to enable container of cstr
#include "stc/vec.h"   // vector of string (cstr)
...
vec_str vec = {0};
cstr s = cstr_lit("a string literal");
const char* hello = "Hello";

vec_str_push(&vec, cstr_from(hello);    // make a cstr from const char* and move it onto vec
vec_str_push(&vec, cstr_clone(s));      // make a cstr clone and move it onto vec

vec_str_emplace(&vec, "Yay, literal");  // internally make a cstr from const char*
vec_str_emplace(&vec, cstr_clone(s));   // <-- COMPILE ERROR: expects const char*
vec_str_emplace(&vec, cstr_str(&s));    // Ok: const char* input type.

cstr_drop(&s)
vec_str_drop(&vec);

This is made possible because the type configuration may be given an optional conversion/"rawvalue"-type as template parameter, along with a back and forth conversion methods to the container value type.

Rawvalues are primarily beneficial for lookup and map insertions, however the emplace methods constructs cstr-objects from the rawvalues, but only when required:

hmap_str_emplace(&map, "Hello", "world");
// Two cstr-objects were constructed by emplace

hmap_str_emplace(&map, "Hello", "again");
// No cstr was constructed because "Hello" was already in the map.

hmap_str_emplace_or_assign(&map, "Hello", "there");
// Only cstr_lit("there") constructed. "world" was destructed and replaced.

hmap_str_insert(&map, cstr_lit("Hello"), cstr_lit("you"));
// Two cstr's constructed outside call, but both destructed by insert
// because "Hello" existed. No mem-leak but less efficient.

it = hmap_str_find(&map, "Hello");
// No cstr constructed for lookup, although keys are cstr-type.

Apart from strings, maps and sets are normally used with trivial value types. However, the last example on the hmap page demonstrates how to specify a map with non-trivial keys.

The erase methods

NameDescriptionContainer
erase()key basedsmap, sset, hmap, hset, cstr
erase_at()iterator basedsmap, sset, hmap, hset, vec, deq, list
erase_range()iterator basedsmap, sset, vec, deq, list
erase_n()index basedvec, deq, cstr
remove()remove all matching valueslist

User-defined container type name

Define i_type instead of i_tag, or i_TYPE to define both i_type and i_key:

#define i_type MyVec
#define i_key int
// #define i_TYPE MyVec,int // shorthand
#include "stc/vec.h"

MyVec vec = {0};
MyVec_push(&vec, 42);
...

Forward declarations

There are two ways to pre-declare templated containers in header files:

  1. Include the templated container type instance as a header file. This also exposes all container functions, which can be used by client code. It requires that the element type is complete.
  2. Or, pre-declare the container type only. In this case, the container can be a "private" member of a user struct (the container functions will not be available to the user).

1. Include as a header file

Create a dedicated header for the container type instance:

#ifndef PointVec_H_
#define PointVec_H_
// Do not to include user defined headers here if they use templated containers themselves

// NB! struct Point must be complete at this point!
#define i_TYPE PointVec,struct Point
#define i_header    // Do not implement, only expose API
#include "stc/vec.h"

#endif

Usage from e.g. other headers is trivial:

#ifndef Dataset_H_
#define Dataset_H_
#include "Point.h"         // include element type separately
#include "PointVec.h"

typedef struct Dataset {
    PointVec vertices;
    PointVec colors;
} Dataset;
...
#endif

Implement PointVec in a c-file:

#include "Point.h"
#define i_implement        // define immediately before PointVec.h
#include "PointVec.h"
...

2. Forward declare only

// Dataset.h
#ifndef Dataset_H_
#define Dataset_H_
#include "stc/types.h"   // include various container data structure templates

// declare PointVec. Note: struct Point may be an incomplete/undeclared type.
forward_vec(PointVec, struct Point);

typedef struct Dataset {
    PointVec vertices;
    PointVec colors;
} Dataset;

void Dataset_drop(Dataset* self);
...
#endif

Define and use the "private" container in the c-file:

// Dataset.c
#include "Dataset.h"
#include "Point.h"                        // Point must be defined here.

#define i_is_forward                      // flag that the container was forward declared.
#define i_type PointVec
#define i_val struct Point
#include "stc/vec.h"                     // Implements PointVec with static linking by default
...

Per container-instance customization

Sometimes it is useful to extend a container type to store extra data, e.g. a comparison or allocator function pointer or a context which the function pointers can use. Most libraries solve this by adding an opaque pointer (void*) or function pointer(s) into the data structure for the user to manage. This solution has a few disadvantages: the pointers are not typesafe, and they take up space when not needed. STC solves this by letting the user create a container wrapper struct where both the container and extra data fields can be stored. The template parameters may then access the extra data using the "container_of" technique.

The example below shows how to customize containers to work with PostgreSQL memory management. It adds a MemoryContext to each container by defining the i_extend template parameter followed the by inclusion of "stc/extend.h". Note that pgs_realloc and pgs_free is also passed the allocated size of the given pointer, unlike standard realloc and free.

// stcpgs.h
#define pgs_malloc(sz) MemoryContextAlloc(c_extend()->memctx, sz)
#define pgs_calloc(n, sz) MemoryContextAllocZero(c_extend()->memctx, (n)*(sz))
#define pgs_realloc(p, old_sz, sz) (p ? repalloc(p, sz) : pgs_malloc(sz))
#define pgs_free(p, sz) (p ? pfree(p) : (void)0) // pfree/repalloc does not accept NULL.

#define i_allocator pgs
#define i_no_clone
#define i_extend MemoryContext memctx;
#include "stc/extend.h"

To use it, define both i_type and i_base (the container type) before including the custom header:

#define i_type IMap
#define i_base smap
#define i_key int
#define i_val int
#include "stcpgs.h"

// Note the wrapper struct type is IMap_ext. IMap is accessed by .get
void maptest()
{
    IMap_ext map = {.memctx=CurrentMemoryContext};
    c_forrange (i, 1, 16)
        IMap_insert(&map.get, i*i, i);

    c_foreach (i, IMap, map.get)
        printf("%d:%d ", i.ref->first, i.ref->second);

    IMap_drop(&map.get);
}

Memory efficiency

STC is generally very memory efficient. Memory usage for the different containers:

Version History

Version 4.3

Version 4.2

Version 4.1.1

Major changes:

API changes summary V4.0

Changes version 3.8

Changes version 3.7

Changes version 3.6