Re: [boost] Review Request: poly_collection

Subject: Re: [boost] Review Request: poly_collection
From: Joaquin M López Muñoz (joaquinlopezmunoz_at_[hidden])
Date: 2017-03-03 11:11:00

El 02/03/2017 a las 18:46, Vicente J. Botet Escriba via Boost escribió:
> Le 02/03/2017 à 10:41, Joaquin M López Muñoz via Boost a écrit :
>> El 01/03/2017 a las 23:15, Vicente J. Botet Escriba escribió:
>>> In your blog there were some comments about a collection of 
>>> variants. Have
>>> you considered adding a variant_collection<Ts...>
>>
>> I've thought about it. Such a collection would deviate from the 
>> others both in terms
>> of its interface (no type registration, for instance) and 
>> implementation --the data
>> structure detail::poly_collection relies on could be used to support 
>> variants, but
>> more efficient implementations exist for this particular case.
>
> Ok, I see. Even if it needs a specific implementation I believe it is 
> worth having it. I say
> that because more and more people are using variant as an alternative 
> way of
> polymorphism (See Andrzej blog - Another polymorphism)
> https://akrzemi1.wordpress.com/2016/02/27/another-polymorphism/

This can be defintely included in the lib roadmap. A variant_collection 
won't fit 100% within
the current concepts in Boost.PolyCollection (e.g. type registration 
makes no sense, type
restitution shoul be provided through a different interface as there's 
no need for the user
to specify the restituted types), but I guess we could work it out. A 
variant-specific
implementation could be very fast as no virtual calls are needed and 
segment visitation
can be resolved statically (detail::poly_collection uses a 
virtual-powered backend).

>> I'd say similarities with unordered_multiset are superficial 
>> (segments resemble
>> buckets) and the interfaces ultimately are too different. I chose 
>> "collection" because
>> the term is not overloaded in the STL or Boost.
>
> My intention was to confirm we have something close to a multiset. 
> Anyway, it would
> be great to see a comparison table. Aside construction, what is 
> provided by
> std::unordered_multiset that is not provided by the poly_collections 
> (or it is provided
> in a different way) ?

poly collections do not behave like multisets in many respects:

* There is no predicate-induced ordering of elements: order in a poly 
collection is free for
the user to change *within a segment* (much like in a regular 
std::vector<T>).
* No binary-search lookup interface.
* segments might resemble buckets, but they're completely different 
beasts: segments
are dedicated vector-like structures for same-type elements, whereas 
elements in
an unordered multiset migrate from bucket to bucket as the container 
grows (rehashes).

All in all, I really don't see much connection between both data structures.

> I talked of polymorphic_value as it close to std::function and 
> boost::type_erasure::any.
> At the end all of them are type erasures for some concept. IMO, you 
> base_collection<T>
> is closer to vector<polymorphic_value<T>> than to ptr_vector<T>. Of 
> course the layout
> is not the same, and this makes the difference of your poly_collections.
>

Exactly. Both structures hide pointer indirections away.

> For the normal algorithms, the function has as parameter the const 
> value_type and
> needs to use dynamic polymorphism.

Right. (Parameter is (const) value_type&, note the '&'.)

> When we use the “restituted" algorithm overload, the algorithm 
> "restitutes" the specific
> types and call to an heterogeneous function, an overload set  for the 
> reconstituted
> types, as if it were a visitor, isn't it?

Exactly. The nice thing about generic lambdas is that code such as this

   [](auto& x){
     //use common interface of all types
   }

automatically generates the necessary overloads. For instance:

   struct base
   {
     virtual void f();
   };

   struct derived1:base{...};
   struct derived2:base{...};
   struct derived3:base{...};

   poly_collection::for_each<derived1,derived2,derived3>(
     c.begin(),c.end(),
     [](auto& x){x.f();}};

generates overloads in the lambda function for derived1, derived2 and
derived3, which sufficiently smart compilers (GCC , Clang) can use to
completely eliminate virtual machinery in calling x.f().

> hana::overload function should be useful here.

Can be useful when you want to use a different interface for each type:

   struct base
   {
     virtual void f();
   };

   struct derived1:base{void d1();...};
   struct derived2:base{void d2();...};
   struct derived3:base{void d3();...};

   poly_collection::for_each<derived1,derived2,derived3>(
     c.begin(),c.end(),
     hana::overload(
       [](derived1& x){x.f();x.d1();},
       [](derived2& x){x.f();x.d2();},
       [](derived3& x){x.f();x.d3();})};

Joaquín M López Muñoz