Boost logo

Boost :

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

El 15/11/2016 a las 18:38, Thorsten Ottosen escribió:
> Hi Joaquin,
> [...]
> A. This is very useful.

Thanks! Glad you find it interesting.

> B. I'm still wondering if requirering copyability is a good thing.
> After all, references and pointers may be used elsewere in the program
> where copying is really not a good idea. Could it make sense to have a
> variation of cloneable:
> void clone( void* storage ) const;
> // essentially a call to protected or private copy-constructor:
> // new(storage) T( *this )
> which is then used internally when copying is needed? And when no
> copying is needed, the container is not copyable. To insert elements
> that are not copyable we would just use emplace with a type argument:
> coll.emplace<derived>( x, y );

Strictly speaking, copyability is not required, but as concrete types
are stored in rellocatable vectors they must be verify the following:

* be MoveConstructible,
* be Moveassignable or have a noexcept move constructor.

Otherwise, segments wouldn't be able to grow beyond its initial capacity.

As for your clone() proposal, I fail to see why this is preferrable to
simply requiring (move/copy) constructibility. Please note that
moving/copying in Boost.PolyCollection happens in a non-virtual
environment, so we don't need the virtual-enabled clone mechanism as
envisioned in the Clonable concept of Boost.PtrContainer. Please correct
me if I'm missing your point.

> C. perhap some range versions of local iterators would be nice?

Care to elaborate? I've basically replicated the usual interface of
standard containers, of course open to consider justified improvements
on that.

> D. I don't get the use of numeric_limits<T>::max() for capacity of an
> empty container. I would be perfectly happy with 0 unless there is
> something we cannot do with that definition.

Not a strong opinon on that. Having capacity()==infinite for a
segment-less collection makes sense from a mathematical point of view,
but other than that 0 could work equally well. If this eventually make
it into an official proposal I'd adopt whatever the community thinks
makes the most sense.

> E. Boost.PtrContainer does not throw exception when a container cannot
> be cloned or compared. Maybe its must be possible to get compile
> errors here too?

I've re-read Boost.PtrContainer docs and seems like the containers
require Base to be clonable, which is tantamount to requiring
copyability for all derived classes in Boost.PolyCollection. Am I wrong
here? What's the behavior if a Base is not clonable?

> F. when using type restitution for base_collection, could it no make
> sense to provide
> struct visitor
> {
> void operator()( const auto& s ) const
> { s.render(std::cout); }
> void operator()( const warrior& w ) const
> { w.warrior::render(std::cout); }
> // etc for remaining types
> } ;
> that is, would that not guarantee devirtualization?

Very good observation. Yes, that would force devirtualization. The thing
can be packed into something more generic:

     template<typename F1,typename F2>struct overload_class:F1,F2
       overload_class(const F1& f1,const F2& f2):F1{f1},F2{f2}{}
       using F1::operator();
       using F2::operator();

     template<typename F1,typename F2>auto overload(const F1& f1,const
F2& f2)
       return overload_class<F1,F2>{f1,f2};

     auto render=overload(
       [](const sprite& s){
       [](const auto& s){
         using derived=typename std::decay<decltype(s)>::type;

Where the overload for const sprite& is needed because the other
overload would try to get a reference to the pure virtual sprite::render
member function. This probably deserves a mention in the docs.

> G. The performance results are very impressive; do that carry over to
> 100 elements?

Looks like it does; results for n=100-1000, Visual C++ 2015 in 32-bit
(x86) release mode, Windows 7 64-bit, Intel Core i5-2520M @2.5GHz:

n;ptr_vector;sorted ptr_vector;shuffled
(poly::for_each);base_collection (restituted poly::for_each)

> I have sometimes though that my best choice would be poly_vector<base>
> where everything is stored in one big chunk of memory, but I guess the
> type restitution can make up for that.
> Nice work!
> kind regards
> Thorsten
> PS: the upcomming Boost.DoubleEnded has a new deque class that exposes
> segmented iterations. I'm wondering if the algorithms that you have
> made can be reused for that data structure.

Not directly so, as the mechanisms for getting a segment iterator from a
global iterator are Boost.PolyCollection-specific, and type restitution
makes no sense for Boost.DoubleEnded. But the algorithmic part (some of
which is not trivial) can be certainly taken as an inspiration for
Boost.DoubleEnded, and it might be conceivable to factor everything out
to a Boost.SegmentedAlgorithm proposal or something.


Joaquín M López Muñoz

Boost list run by bdawes at, gregod at, cpdaniel at, john at