static_vector Needs Type-Erasure

TL;DR

Ichor now has a (not entirely complete) type-erasable StaticVector implementation. This can be used to store static_vector of different sized inside of another static_vector, having everything be stack allocated.

What Is static_vector?

P0843R6 proposes a new container type to C++. static_vector, much like vector is a dynamic container with a variable size. The biggest difference is that where vector can grow indefinitely (until your RAM is 100% full), static_vector has a compile-time defined size limit. Moreover, because the size is known at compile time, static_vector’s elements are entirely stack allocated. In environments where dynamic memory allocation is undesired, this is a huge win.

Using it is very similar to the regular vector:

static_vector<int, 2> sv; // stack-allocated, dynamic container with a maximum of 2 elements, by default everything is uninitialized
sv.push_back(123);
std::cout << (sv[0] == 123) << "\n"; // prints 123
std::cout << sv.size() << "\n"; // prints 1
std::cout << sv.capacity() << "\n"; // prints 2
sv.push_back(234); // OK
sv.push_back(345); // undefined behaviour, but likely to hit an assert and crash your program

My Use-case

The Ichor project I am working on has a specific use-case for static_vector. For those who don’t know Ichor, Ichor is a framework that provides easily swappable implementations against interfaces, using dependency injection. Requested dependencies are registered at compile-time, meaning that the information is available at compile-time as well and can be optimized for as such.

For example, implementations know exactly which interfaces they expose that other implementations can depend on:

class MyEtcdImplementation : public IEtcdV3, public ILogger {
    /// ... combined etcd and logger interface implementation ...
};

int main() {
    auto queue = std::make_unique<PriorityQueue>();
    DependencyManager &dm = queue->createManager();
    dm.createServiceManager<MyEtcdImplementation, IEtcdV3, ILogger>(); // need to specify interfaces here again until C++ introduces compile-time reflection
    // ...
}

In this case, Ichor creates a manager object that keeps track of the 0 dependency requests the MyEtcdImplementation makes and the 2 interfaces that it provides. However, because Ichor provides run-time dependency injection, it has to store all the manager objects in an iterable, type-erased container. That is, Ichor is made to allow users to add and remove implementations at run-time, through for example some plugin loading mechanism. Because of that, although the provided interfaces per manager are known at compile-time, they get stored in a container that can be requested through an IManager interface using virtual functions.

It is technically possible to limit the number of provided interfaces (you’ll never need more than 640k), but I’d rather provide a framework that leaves it up to the user. On top of std::array needing default constructors on the element type, the user-defined limit is also the reason why std::array<T, N> would not work, as the N template parameter cannot be known in the IManager interface.

My Solution

So far, Ichor has been using vector to solve this issue, but we can do better. Combined with some size optimizations that David Stone showed in his CppCon ‘21 talk on static_vector, Ichor now has a (not entirely complete) type-erasable StaticVector implementation.

There are a couple of trade-offs that have been made that deviate from the proposal as well as impact performance:

• Most functions are virtual, introducing pointer indirection if using the interface instead of the concrete type
• Templated functions like emplace_back are only present on the concrete type, by definition they cannot be available on a pure virtual base class
• The capacity and max_size functions cannot be static, as the interface has no knowledge on the underlying size.
• Because Ichor aims to be usable in an embedded context, the currently allocated number of elements is potentially stored in a smaller size type (e.g. unsigned char) than the interfaces’ size_t.

Notably, the constexpr definitions from the proposal are all kept intact. As long as the element type is is_trivially_default_constructible_v and is_trivially_destructible_v, the underlying data type can be a (constexpr) array.

One caveat here is that due to time constraints, Ichor’s implementation does not yet implement the LegacyRandomAccessIterator named requirement as well as some constructors and functions from the proposal. They will be added in due time.

Other Use-cases

One other use-case is to be able to store static_vector of different sized inside of another static_vector, having everything be stack allocated:

// this is all stack-allocated.
Ichor::StaticVector<Ichor::IStaticVector<int>*, 10> sv_of_svs;
Ichor::StaticVector<int, 5> sv_one{}
Ichor::StaticVector<int, 15> sv_two{}

sv_one.push_back(123);
sv_one.push_back(234);

sv_two.push_back(999);

sv_of_svs.push_back(&sv_one);
sv_of_svs.push_back(&sv_two);

// this loop prints 2\n123\n234\n1\n999\n
for(auto &sv : sv_of_svs) {
    std::cout << sv.size() << "\n";
    for(auto &elem : sv) {
        std::cout << elem << "\n";
    }
}

This could f.e. be useful if you have a list of drivers in your RTOS which all provide their own number of virtual file-system endpoints, but don’t want to dynamically allocate them at run-time. Iterating over all drivers is possible using the IStaticVector interface provided type-erasure.