Re: Vector with compile-time polymorphism

From: Andrey Semashev (andrey.semashev_at_[hidden])
Date: 2021-04-09 13:12:37

On 4/9/21 3:13 PM, Ivica B via Boost wrote:
> 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.

This sounds a lot like Boost.Fusion to me:

https://www.boost.org/doc/libs/1_75_0/libs/fusion/doc/html/

template< typename... Types >
using multivector = boost::fusion::vector<
   std::vector< Types >...
 >;

multivector<rectangle, circle, triangle> mvect;

boost::fusion::for_each(mvect,
   [&](auto& shape) { shape.draw(bitmap); });