Re: [boost] [poly_collection] Request for comments: fast polymorphic collections

Subject: Re: [boost] [poly_collection] Request for comments: fast polymorphic collections
From: Joaquin M López Muñoz (joaquinlopezmunoz_at_[hidden])
Date: 2016-11-23 15:19:59

El 23/11/2016 a las 18:23, Thorsten Ottosen escribió:
> On 19-11-2016 10:09, Joaquin M López Muñoz wrote:
>
>> So, we can only provide capacity information for *registered* types,
>> which is precisely what the exotic definition of capacity() does. Do you
>> see any other viable definition?
>
> Hm. Maybe not. We have
>
> cc.capacity()
> cc.capacity(index)
> cc.capacity<U>()
>
> and the first is specified as
>
> "the minimum return value of capacity for each of the segments of the 
> collection, or std::numeric_limits<size_type>::max if there are no 
> segments."
>
> I can't see how that is useful for much. The segment specific ones are 
> useful, of course. I would still say it should return 0 if there are 
> no segments, or that it should not be provided at all. If provided, it 
> should follow size() which I assume sums over all segment sizes. That 
> is, it should sum over all capacities.
>

Re-thinking this, seems to me that the main use case of capacity() for a 
regular container like std::vector is in the expression

X = v.capacity()-v.size()

to calculate how many more insertions can one make without reallocation. 
Maybe we can define capacity() in Boost.PolyCollection to allow for the 
same use case: if we denote by si, ci the sizes and capacities of the 
different elements i=0,1,... then the equivalent expression for X taking 
into consideration only registered types and assuming the worst case 
(all insertions happen in the segment with the least unused capacity) is

X = min{ci-si} = min{c1-si} + (s0+s1+...) - (s0+s1+...) = min{c1-si} + 
(s0+s1+...) - v.size()

which leads to v.capacity() being defined as

min{c1-si} + (s0+s1+...)

i.e. the size of the entire collection plus the minimum *unused* 
capacity. Maybe this is too weird. Maybe we should drop capacity() 
altogether (not the sector-specific versions, of course).

> Here are some design questions:
>
> A. Do we want these two states to be independently observable:
>
> - empty, but with empty segments
> - empty, but with no segments

These two states are indeed observably different: A collection with a 
segment for D returns true for is_registered<D>(). The distinction is 
important; for instance, the following

   Base x;
   D& d=x; // D is derived from Base
   p.insert(d);

throws if D is not previously registered into the collection p.

> B. If I call shrink_to_fit on an container with empty segements, does 
> it end up with no segments?

No. The only way to remove a segment from a collection p is to assign it 
a different collection q (without that segment), swap it or move it (in 
whch case all segments are gone).
Again, my thinking is that having empty segments is a good thing in as 
much as this is tied to the fact that the associated types are 
registered into the collection. For that reason, the lib does nothing in 
particular to remove empty segments.

> C. Could the segment type be a template argument, or is there good 
> reasons for not dong that? 

Like replacing std::vector with some other contiguous-memory container? 
This can certainly be done but I fail to see any reasonable use case for 
that. Also, the library is extremely sensitve to the requirements 
imposed on stored concrete types (moevability etc.) which are precisely 
coded for std::vector but may dffer wildly for other vector-like containers.

Joaquín M López Muñoz