Template vector struct in C11

Question

This one review will be a little bit tricky: I was trying to implement a template Vector struct in C11. Of course, templates don't really exist in C11, so I used a few macros to get the desired interface. Here is the implementation of the core features, trying to mimick those of the c++ std::vector. Some are still missing though. First, the macro define_Vector:

#define define_Vector(T)                                                  \
                                                                          \
    struct _vector_##T;                                                   \
                                                                          \
    typedef struct                                                        \
    {                                                                     \
        void (*delete)(struct _vector_##T*);                              \
        T (*at)(const struct _vector_##T*, size_t);                       \
        T (*front)(const struct _vector_##T*);                            \
        T (*back)(const struct _vector_##T*);                             \
        T* (*data)(const struct _vector_##T*);                            \
        T* (*begin)(struct _vector_##T*);                                 \
        const T* (*cbegin)(const struct _vector_##T*);                    \
        T* (*end)(struct _vector_##T*);                                   \
        const T* (*cend)(const struct _vector_##T*);                      \
        bool (*is_empty)(const struct _vector_##T*);                      \
        size_t (*size)(const struct _vector_##T*);                        \
        size_t (*max_size)(void);                                         \
        void (*reserve)(struct _vector_##T*, size_t);                     \
        size_t (*capacity)(const struct _vector_##T*);                    \
        void (*shrink_to_fit)(struct _vector_##T*);                       \
        void (*clear)(struct _vector_##T*);                               \
        void (*erase1)(struct _vector_##T*, const T*);                    \
        void (*erase2)(struct _vector_##T*, const T*, const T*);          \
        void (*push_back)(struct _vector_##T*, T);                        \
        void (*pop_back)(struct _vector_##T*);                            \
        void (*resize1)(struct _vector_##T*, size_t);                     \
        void (*resize2)(struct _vector_##T*, size_t, T);                  \
    } _vector_functions_##T;                                              \
                                                                          \
    typedef struct _vector_##T                                            \
    {                                                                     \
        T* _data;                                                         \
        size_t _size;                                                     \
        size_t _capacity;                                                 \
        const _vector_functions_##T* _functions;                          \
    } Vector_##T;                                                         \
                                                                          \
Vector_##T* new_Vector_##T();                                             \
void vector_delete_##T(Vector_##T*);                                      \
T vector_at_##T(const Vector_##T*, size_t);                               \
T vector_front_##T(const Vector_##T*);                                    \
T vector_back_##T(const Vector_##T*);                                     \
T* vector_data_##T(const Vector_##T*);                                    \
T* vector_begin_##T(Vector_##T*);                                         \
const T* vector_cbegin_##T(const Vector_##T*);                            \
T* vector_end_##T(Vector_##T*);                                           \
const T* vector_cend_##T(const Vector_##T*);                              \
bool vector_is_empty_##T(const Vector_##T*);                              \
size_t vector_size_##T(const Vector_##T*);                                \
size_t vector_max_size_##T(void);                                         \
void vector_reserve_##T(Vector_##T*, size_t);                             \
size_t vector_capacity_##T(const Vector_##T*);                            \
void vector_shrink_to_fit_##T(Vector_##T*);                               \
void vector_clear_##T(Vector_##T*);                                       \
void vector_erase1_##T(Vector_##T*, const T*);                            \
void vector_erase2_##T(Vector_##T*, const T*, const T*);                  \
void vector_push_back_##T(Vector_##T*, T);                                \
void vector_pop_back_##T(Vector_##T*);                                    \
void vector_resize1_##T(Vector_##T*, size_t);                             \
void vector_resize2_##T(Vector_##T*, size_t, T);                          \
                                                                          \
void vector_delete_##T(Vector_##T* vector)                                \
{                                                                         \
    free(vector->_data);                                                  \
    free(vector);                                                         \
}                                                                         \
                                                                          \
T vector_at_##T(const Vector_##T* vector, size_t index)                   \
{                                                                         \
    return vector->_data[index];                                          \
}                                                                         \
                                                                          \
T vector_front_##T(const Vector_##T* vector)                              \
{                                                                         \
    return vector->_data[0];                                              \
}                                                                         \
                                                                          \
T vector_back_##T(const Vector_##T* vector)                               \
{                                                                         \
    return vector->_data[size(vector)-1];                                 \
}                                                                         \
                                                                          \
T* vector_data_##T(const Vector_##T* vector)                              \
{                                                                         \
    return vector->_data;                                                 \
}                                                                         \
                                                                          \
T* vector_begin_##T(Vector_##T* vector)                                   \
{                                                                         \
    return data(vector);                                                  \
}                                                                         \
                                                                          \
const T* vector_cbegin_##T(const Vector_##T* vector)                      \
{                                                                         \
    return data(vector);                                                  \
}                                                                         \
                                                                          \
T* vector_end_##T(Vector_##T* vector)                                     \
{                                                                         \
    return data(vector) + size(vector);                                   \
}                                                                         \
                                                                          \
const T* vector_cend_##T(const Vector_##T* vector)                        \
{                                                                         \
    return data(vector) + size(vector);                                   \
}                                                                         \
                                                                          \
bool vector_is_empty_##T(const Vector_##T* vector)                        \
{                                                                         \
    return size(vector) == 0;                                             \
}                                                                         \
                                                                          \
size_t vector_size_##T(const Vector_##T* vector)                          \
{                                                                         \
    return vector->_size;                                                 \
}                                                                         \
                                                                          \
size_t vector_max_size_##T(void)                                          \
{                                                                         \
    return SIZE_MAX;                                                      \
}                                                                         \
                                                                          \
void vector_reserve_##T(Vector_##T* vector, size_t new_cap)               \
{                                                                         \
    if (new_cap > capacity(vector))                                       \
    {                                                                     \
        vector->_capacity = new_cap;                                      \
        vector->_data = realloc(vector->_data,                            \
                                new_cap * sizeof(T));                     \
    }                                                                     \
}                                                                         \
                                                                          \
size_t vector_capacity_##T(const Vector_##T* vector)                      \
{                                                                         \
    return vector->_capacity;                                             \
}                                                                         \
                                                                          \
void vector_shrink_to_fit_##T(Vector_##T* vector)                         \
{                                                                         \
    vector->_capacity = size(vector);                                     \
    vector->_data = realloc(vector->_data,                                \
                            size(vector) * sizeof(T));                    \
}                                                                         \
                                                                          \
void vector_clear_##T(Vector_##T* vector)                                 \
{                                                                         \
    vector->_size = 0;                                                    \
}                                                                         \
                                                                          \
void vector_erase1_##T(Vector_##T* vector, const T* pos)                  \
{                                                                         \
    T* it = (T*) pos;                                                     \
    while (it != end(vector)-1)                                           \
    {                                                                     \
        *it = it[1];                                                      \
        ++it;                                                             \
    }                                                                     \
    --vector->_size;                                                      \
}                                                                         \
                                                                          \
void vector_erase2_##T(Vector_##T* vector, const T* first, const T* last) \
{                                                                  \
    T* it1 = (T*) first;                                           \
    T* it2 = (T*) last;                                            \
    while (it2 != end(vector))                                     \
    {                                                              \
        *it1 = *it2;                                               \
        ++it1;                                                     \
        ++it2;                                                     \
    }                                                              \
    vector->_size -= last-first;                                   \
}                                                                  \
                                                                   \
void vector_push_back_##T(Vector_##T* vector, T value)             \
{                                                                  \
    vector->_size += 1;                                            \
    if (capacity(vector) < size(vector))                           \
    {                                                              \
        reserve(vector, capacity(vector)+40);                      \
    }                                                              \
    last(vector) = value;                                          \
}                                                                  \
                                                                   \
void vector_pop_back_##T(Vector_##T* vector)                       \
{                                                                  \
    if (size(vector) > 0)                                          \
    {                                                              \
        vector->_size -= 1;                                        \
    }                                                              \
}                                                                  \
                                                                   \
void vector_resize1_##T(Vector_##T* vector, size_t count)          \
{                                                                  \
    if (count < size(vector))                                      \
    {                                                              \
        while (size(vector) > count)                               \
        {                                                          \
            pop_back(vector);                                      \
        }                                                          \
    }                                                              \
    else                                                           \
    {                                                              \
        reserve(vector, count);                                    \
        vector->_size = count;                                     \
    }                                                              \
}                                                                  \
                                                                   \
void vector_resize2_##T(Vector_##T* vector, size_t count, T value) \
{                                                                  \
    if (count < size(vector))                                      \
    {                                                              \
        while (size(vector) > count)                               \
        {                                                          \
            pop_back(vector);                                      \
        }                                                          \
    }                                                              \
    else                                                           \
    {                                                              \
        while (size(vector) < count)                               \
        {                                                          \
            push_back(vector, value);                              \
        }                                                          \
    }                                                              \
}                                                                  \
                                                                   \
const _vector_functions_##T _vector_funcs_##T = {                  \
    &vector_delete_##T,                                            \
    &vector_at_##T,                                                \
    &vector_front_##T,                                             \
    &vector_back_##T,                                              \
    &vector_data_##T,                                              \
    &vector_begin_##T,                                             \
    &vector_cbegin_##T,                                            \
    &vector_end_##T,                                               \
    &vector_cend_##T,                                              \
    &vector_is_empty_##T,                                          \
    &vector_size_##T,                                              \
    &vector_max_size_##T,                                          \
    &vector_reserve_##T,                                           \
    &vector_capacity_##T,                                          \
    &vector_shrink_to_fit_##T,                                     \
    &vector_clear_##T,                                             \
    &vector_erase1_##T,                                            \
    &vector_erase2_##T,                                            \
    &vector_push_back_##T,                                         \
    &vector_pop_back_##T,                                          \
    &vector_resize1_##T,                                           \
    &vector_resize2_##T,                                           \
};                                                                 \
                                                                   \
Vector_##T* new_Vector_##T()                                       \
{                                                                  \
    Vector_##T* res = malloc(sizeof(Vector_##T));                  \
    res->_functions = &_vector_funcs_##T;                          \
    res->_capacity = 40;                                           \
    res->_size = 0;                                                \
    res->_data = malloc(40*sizeof(T));                             \
    return res;                                                    \
}

To access the functions contained in the global struct, I use the following macros (some also provide extra features):

////////////////////////////////////////////////////////////
// Element access

#define at(collection, index) \
        collection->_functions->at(collection, index)

#define front(collection) \
        collection->_functions->front(collection)

#define back(collection) \
        collection->_functions->back(collection)

#define data(collection) \
        collection->_functions->data(collection)

////////////////////////////////////////////////////////////
// Iterators

#define begin(collection) \
        collection->_functions->begin(collection)

#define cbegin(collection) \
        collection->_functions->cbegin(collection)

#define end(collection) \
        collection->_functions->end(collection)

#define cend(collection) \
        collection->_functions->cend(collection)

////////////////////////////////////////////////////////////
// Capacity

#define is_empty(collection) \
        collection->_functions->is_empty(collection)

#define size(collection) \
        collection->_functions->size(collection)

#define max_size(collection) \
        collection->_functions->max_size()

#define reserve(collection, new_cap) \
        collection->_functions->reserve(collection, new_cap)

#define capacity(collection) \
        collection->_functions->capacity(collection)

#define shrink_to_fit(collection) \
        collection->_functions->shrink_to_fit(collection)

////////////////////////////////////////////////////////////
// Modifiers

#define clear(collection) \
        collection->_functions->clear(collection)

#define erase(collection, ...) \
        DISPATCH(erase, __VA_ARGS__)(collection, __VA_ARGS__)
#define erase1(collection, pos) \
        collection->_functions->erase1(collection, pos)
#define erase2(collection, first, last) \
        collection->_functions->erase2(collection, first, last)

#define push_back(collection, elem) \
        collection->_functions->push_back(collection, elem)

#define pop_back(collection) \
        collection->_functions->pop_back(collection)

#define resize(collection, ...) \
        DISPATCH(resize, __VA_ARGS__)(collection, __VA_ARGS__)
#define resize1(collection, count) \
        collection->_functions->resize1(collection, count)
#define resize2(collection, count, value) \
        collection->_functions->resize2(collection, count, value)

////////////////////////////////////////////////////////////
// Macros to improve usability

/**
 * @def define(type)
 * Defines all the functions for the given type.
 */
#define define(type) \
        define_##type

/**
 * @def new(type)
 * Creates a new instance of the given type and
 * returns a pointer to it.
 */
#define new(type) \
        new_##type

/**
 * @def delete(collection)
 * Calls the class "destructor" to free what has
 * to be freed.
 */
#define delete(collection) \
        collection->_functions->delete(collection)

/**
 * @def elem(collection, index)
 * Returns the given element of a contiguous collection.
 */
#define elem(collection, index) \
        data(collection)[index]

/**
 * @def first(collection)
 * Returns the first element of a contiguous collection.
 */
#define first(collection) \
        data(collection)[0]

/**
 * @def last(collection)
 * Returns the last element of a contiguous collection.
 */
#define last(collection) \
        data(collection)[size(collection)-1]

And here are the macros - only well-known macros - used to implement the interface macros:

// Some compilers need one more level of indirection
// than GCC, hence PASTE_3.
#define PASTE_3(x, y) \
    x ## y
#define PASTE_2(x, y) \
    PASTE_3(x, y)
#define PASTE_1(x, y) \
    PASTE_2(x, y)

// DISPATCH cannot use VA_NARGS because of the
// sizeof check. Therefore, it uses the version
// which cannot handle the 0.
#define VA_NARGS_2(_1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, _13, _14, _15, N, ...) \
    N
// Note: the last dummy parameter sole purpose is
// to avoid a warning
#define VA_NARGS_1(...) \
    VA_NARGS_2(__VA_ARGS__, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, /* dummy */)

/**
 * @def PASTE(x, y)
 * Pastes two macros tokens together to create
 * a new name.
 */
#define PASTE(x, y) \
    PASTE_1(x, y)

/**
 * @def VA_NARGS(...)
 * Counts the number of arguments of the given
 * macro parameter pack.
 */
#define VA_NARGS(...) \
    sizeof(#__VA_ARGS__) == sizeof("") ? 0 : \
    VA_NARGS_1(__VA_ARGS__)

/**
 * @def DISPATCH(func, ...)
 * Calls different functions in function of the
 * number of parameters in the parameter pack.
 * Therefore, it allows to overload macros based
 * on the number of arguments passed to it.
 *
 * @warning Can not handle 0-sized parameter packs.
 */
#define DISPATCH(func, ...) \
    PASTE(func, VA_NARGS_1(__VA_ARGS__))

And finally, here is an example of how to use all the code above:

define(Vector(float))
define(Vector(int))
define(Vector(double))

int main()
{
    Vector(int)* vec_i = new(Vector(int));
    Vector(double)* vec_d = new(Vector(double));

    printf("is_empty: %d\n", is_empty(vec_i));
    printf("size: %u\n", size(vec_i));
    printf("max_size: %u\n", max_size(vec_i));
    printf("capacity: %u\n", capacity(vec_i));
    printf("front: %d == %d\n", front(vec_i), at(vec_i, 0));
    printf("back: %d == %d\n", back(vec_i), at(vec_i, 2));

    reserve(vec_d, 56);
    printf("capacity: %d\n", capacity(vec_d)); // 56
    reserve(vec_d, 30);
    printf("capacity: %d\n", capacity(vec_d)); // 56

    for (int i = 0 ; i < 3 ; ++i)
    {
        push_back(vec_d, 0.0);
    }
    first(vec_d) = 5.6;
    elem(vec_d, 1) = 1.0;
    elem(vec_d, 2) = 2.0;
    for (size_t i = 0 ; i < 3 ; ++i)
    {
        printf("%f ", at(vec_d, i));
    }
    printf("\n");

    shrink_to_fit(vec_d);
    printf("capacity: %d\n", capacity(vec_d)); // 3

    assert(data(vec_d) == vec_d->_data);
    assert(last(vec_d) == elem(vec_d, 2));

    for (int i = 5 ; i > 0 ; --i)
    {
        push_back(vec_i, i);
    }
    printf("size: %u\n", size(vec_i)); // 5
    printf("capacity: %d\n", capacity(vec_i)); // 40
    pop_back(vec_i);
    pop_back(vec_i);
    shrink_to_fit(vec_i);
    printf("size: %u\n", size(vec_i)); // 3
    printf("capacity: %d\n", capacity(vec_i)); // 3
    int foo = 8;
    push_back(vec_i, foo);
    printf("size: %u\n", size(vec_i)); // 4
    printf("capacity: %d\n", capacity(vec_i)); // 43

    delete(vec_i);
    delete(vec_d);

    // erase methods
    Vector(int)* vi = new(Vector(int));
    for (int i = 0 ; i < 10 ; ++i)
    {
        push_back(vi, i);
    }

    printf("\n");
    for (int* it = begin(vi) ; it != end(vi) ; ++it)
    {
        // 0 1 2 3 4 5 6 7 8 9
        printf("%d ", *it);
    }

    printf("\n");
    erase(vi, begin(vi));
    for (size_t i = 0 ; i < size(vi) ; ++i)
    {
        // 1 2 3 4 5 6 7 8 9
        printf("%d ", at(vi, i));
    }

    printf("\n");
    erase(vi, begin(vi)+2, begin(vi)+5);
    for (size_t i = 0 ; i < size(vi) ; ++i)
    {
        // 1 2 6 7 8 9
        printf("%d ", at(vi, i));
    }

    delete(vi);
}

Of course, none of this is meant to be used with a C++ compiler and all this code is merely done for fun; I would never use that as production code. Also, I already know that all those macros pollute everything, but I don't care - all of this is just a proof of concept. So, would there be any way to improve the interface even further? Moreover, are there ovious errors in the Vector implementation?

Answer 1

There is a rather large amount of code here and a lot of macro trickery, so I shall refrain from attempting to comment on it all.

There are, however, a few things that immediately jumped out at me.

---

Don't use new as your allocating macro. That's extremely confusing, and it's going to make compiling it as C++ rather difficult. (Not that having C be compilable as C++ is exactly a noble goal -- it's just not worth throwing away over one word).

---

Your macros should be namespaced. size? at? You don't think anyone else might try to use those names?

Rather than define_Vector have vector_define and then vector_at, vector_size, etc. Not only does this make it immediately clearer that things like size aren't some kind of magic, it should hopefully help avoid potential collisions if someone were to use this with other code.

---

realloc can fail. You need to consider that in vector_reserve, vector_shrink_to_fit and so on.

---

Are you sure your accessors (vector_at, vector_front, etc) should return a T and not a T*? Imagine if you're storing a large struct. You would probably rather be able to mutate the struct inside of the vector rather than having to copy it, modify it, and then put it back. (Yes, you can get direct access like this with your 'iterators', but eh...).

---

This feels a bit incomplete if you're trying to mimic C++. Where are constructors? Destructors? Copiers? What if I have a vector of 10 structs that have FILE* pointers? It would be nice to be able to assign a destructor to those so that calls like vector_clear would not leave a dangling file handle.

---

I actually might consider going with T here like you've done, but it's fairly customary in C to use an automatic form of sizeof rather than explicit. Like:

res->_data = malloc(40*sizeof(*(res->data)));

---

Accepting constant pointers rather than values in a few places would allow you to avoid potential copies. Unfortunately that makes the calling semantics a bit grosser, but welcome to C :).

---

40 is a rather large default capacity. (Also, you have to handle malloc/realloc failures for a library like this.)

It would be nice to be able to avoid a malloc until something is actually stored in the vector. It could avoid a rather costly allocation in certain cases where a vector is created and then not pushed into.

---

I might try to pull the default capacity into a constant or something, but either way, it shouldn't be repeated:

res->_capacity = 40;                                           \
res->_size = 0;                                                \
res->_data = malloc(40*sizeof(T));   

Could be:

res->_capacity = 40;                                           \
res->_size = 0;                                                \
res->_data = malloc(res->_capacity*sizeof(T));   

This is just to avoid a mismatch if at some point 40 is changed on one line and not the other.

---

Unsolicited, blatant opinion incoming :)

Though this is elegant and clever, overall I'm not sure how I feel about it.

As you almost certainly know, data structures in C typically revolve around void* with a complete lack of type safety. Your vector give type safety at a relatively minor cost (binary size), so that's rather nice and a very real benefit.

I can't help but feel though that at the end of the day, you've just recreated templates in a language not meant to support them. In almost all situations where this would be used, I think the proper option would be to just use C++. Then again, I'm very biased towards C++, and my sentiment is almost always "if you can use C++, then you should use C++."

In situations where you're stuck using C, this could be very valuable if type safety is very important. I do believe though that it would require a bit more polishing in terms of the items mentioned above, and it would need to be tested very thoroughly in both functional and performance senses.

Answer 2

I did manage to improve some things since the question was posted. So here is what I discovered, that could somehow improve the implementation and the usability of the Vector(T):

• First of all, there was an error in the code. Shame on me. I shared a piece of code that could not be compiled. I must have posted a version that was not up-to-date. The macro new does not work for two reasons: the token pasting is not well done and I forgot to add the parenthesis for the function call. The first solution to fix that error is to have new(Vector(int)) call new_Vector_int():

  #define new(type) \
      PASTE(new_, type)()
  

  The second solution is to have new(Vector(int)) resolve to new_Vector_int and add the call by hand on the calling site. This would allow to "overload constructors":

  #define new(type) \
      PASTE(new_, type)
  
  Vector(int)* vec_i = new(Vector(int))(/* maybe more paremeters later */);
  

• The define_vector_##T macro introduces names that begin with an underscore in the global scope. Such names are reserved to the implementation; they should either use another prefix or be put somewhere else (for example, the function table could be a static variable in a function. Not that this is a good idea either, but you get it...).

• The typedef between struct _vector_##T and Vector_##T is done quite late. I could have used the "forward typedef":

  typedef struct _vector_##T Vector_##T;
  

  This would have allowed me use Vector_##T instead of struct _vector_##T in the function declarations.

• Actually, I can also use Vector(T) directly instead of Vector_##T in the body of define_Vector. Thanks to that, I can drop many ## operators and the code ends up being easier to read.

• The macros parameters are not always correctly guarded with parenthesis. If I have a stack-allocated vector and try to give its address to a function (e.g. begin(&vec_i)), it fails miserably. More parenthesis are needed:

  #define begin(collection) \
          (collection)->_functions->begin(collection)
  

• Last but not least, I kind of failed (at first) to mimic the C++ functions returning lvalues (non-const references). I can still work around that by having the functions return pointers and having the interface macros dereference those functions returns. Take the example of front. The declaration becomes:

  T* vector_front_##T(const Vector(T)*);
  

  The definition becomes:

  T* vector_front_##T(const Vector(T)* vector)
  {
      return vector->_data;
  }
  

  And the macro front becomes:

  #define front(collection) \
      (*((collection)->_functions->front(collection)))
  

  This new trick allows us to get rid of the workaround macros elem, first and last since at, front and back can now somehow return lvalues instead of simple values, and not only for data structures with contiguous storage. Of all the points, this is the only one that allows to increase the usability of the code.