Vector with compile-time polymorphism

From: Ivica B (ibogosavljevic_at_[hidden])
Date: 2021-04-09 12:13:27

Hi!

I am doing a performance C++ work and there is a data structure that we use
and I think it is very useful even for the general public. Here is the
description:

Currently, I call it *multivector* (I know there is a data structure with
the same name, this is a temporary name). It works like this:

You specify all the types you want to hold in your multivector:

multivector<rectangle, circle, triangle> mvect;

Each type is held in a separate std::vector for that type. So in the above
case,  multivector<rectangle, circle, triangle> consists of three
std::vectors: std::vector<rectangle>, std::vector<circle> and
std::vector<triangle>.

Now, the magic happens when we use templates to process all three vectors
at once. Imagine there is a function *draw* for all three types. We can do
something like this:

mvect.for_each([&](auto& shape) { shape.draw(bitmap); });

The above code generates three for_each loops, for rectangle, circle and
triangle. Inside the loops it calls the draw method for each type. There is
no dispatching inside the loops, and the loops are really easy for the
compiler to optimize (due to their simplicity).

Prototype implementation:
https://github.com/ibogosavljevic/johnysswlab/blob/master/2021-02-virtualfunctions/multivector.h

Advantages over std::vector<std::variant>>:
* Uses less memory (std::variant uses the amount of memory per element that
is big enough to store the biggest type)
* Is more optimal: each type generates its own processing loop, there is no
dispatching code inside the loop. The compilers vectorized these loops
easier.

Downsides:
* You cannot sort the elements in the whole vectors (even though you can
sort them in individual containers)
* Code bloat (many types can create a lot of code, this is the case with
std::vector<std::variant>> too)

Please let me know what you think.

Ivica