Re: Vector with compile-time polymorphism

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

On 4/9/21 4:12 PM, Andrey Semashev wrote:
> 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); });

Correction:

   boost::fusion::for_each(mvect,

     [&](auto& vect) {
       std::for_each(vect.begin(), vect.end(),
         [&](auto& shape) { shape.draw(bitmap); });
     });