A Simple Dynamic Array

A lightweight, single-header, type-generic auto-growing array (commonly called a "vector") for C.

By default, the vector doubles in size when its capacity is exceeded. This can be configured.

API

The library is implemented as macros, so vectors can contain any type.

Creating

vec_of(type)
Declares a vector of type type. Synonym for type *.
Variable should be set to NULL, ie vec_of(int) vi = NULL;

vec_init(vec, cap)
Optionally performs an initial allocation with enough capacity to hold cap elements.
Helps avoid mallocs during early growth.

Accessing Elements

vec[idx] – O(1)
A vector's elements can be accessed like a normal array.

vec_last(vec) – O(1)
Returns a pointer to the last item in vec.

vec_end(vec) – O(1)
Returns a pointer one past the last element vec.
Can be used to iterate through the vector:
int *it; for(it = vi; it != vec_end(vi); it++) { ... }

Iterating

vec_each(vec, fn) – O(n)
Calls fn(elem) for each elem in vec.

vec_eachp(vec, fn) – O(n)
Calls fn(&elem) for each elem in vec.

vec_iter(vec, T)
Begins a loop inside which the variable T *it is a pointer to the current element.
Synonym of: for (T *it=vec; it != vec_end(vec); it++)
(though it caches vec_end(vec) for a slight speed boost)

Operations

vec_push(vec, x) – O(1) – grows if necessary
Insert the element x at the end vec.

vec_pop(vec) – O(1)
Removes the last element of vec.

vec_ins(vec, idx, x) – O(n) – grows if necessary
Inserts x at position idx. Shifts later elements forward.

vec_insp(vec, ptr, x) – O(n) – grows if necessary
Inserts x just before ptr. Shifts later elements forward.
ptr must be a pointer to an element in vec.

vec_del(vec, idx) – O(n)
Removes element at position idx. Shifts later elements back.

vec_delp(vec, ptr) – O(n)
Removes element pointed to by ptr. Shifts later elements back.
ptr must be a pointer to an element in vec.

vec_trim(vec) – O(1)
Reallocates vec to have a capacity equal to the current number of elements.
No-op if vec is full.

vec_clear(vec) – O(1)
Resets vec's length to 0, while retaining the allocated capacity.
Does not zero-out the cleared space.

vec_free(vec) – O(1) amortized (like free())
Frees all memory associated vec.
Do not attempt to free a vector with free().

Inspecting

vec_len(vec) – O(1)
Returns the current number of elements in vec.

vec_cap(vec) – O(1)
Returns the current capacity of vec.

---

Except for vec, each argument is only evaluated once, so side-effects are safe. However, vec itself may be evaluated multiple times.

Implementation

It works like many allocators, and sds strings:

• Allocate a few words more than requested
• Use those words to store a size/capacity header
• Return a pointer to the data directly

The allocated data looks like:

  ┌──────┬──────────┬───────────────────────────────────┐
  │ size │ capacity │ data...                           │
  └──────┴──────────┴───────────────────────────────────┘
                    ↑
                    └─ user pointer

And all it takes to get an element is myvec[idx].

Configuration

It is possible to use custom malloc/free functions by defining the following macros:

/* If you define one of these, you must define them all: */
#define VEC_MALLOC   mymalloc
#define VEC_REALLOC  myrealloc
#define VEC_FREE     myfree

You can control the growth rate of the vector by defining the following macro:

#define VEC_GROW_RATE 1
  /* Allocates just enough capacity to hold the new size.
     Uses less memory, but slower if frequently added to. */

#define VEC_GROW_RATE 2   /* the default */
  /* Allocates double the current capacity if resize is needed.
     Uses more memory, but faster if frequently added to. */

Assertions are used after attempting to allocate memory. You can use a custom assert function by defining the following macro:

#define VEC_ASSERT  myassert

TODO

• Add tests