Boost logo

Boost :

Subject: Re: [boost] [poly_collection] Request for comments: fast polymorphic collections
From: Thorsten Ottosen (tottosen_at_[hidden])
Date: 2016-11-15 12:38:36

Hi Joaquin,

> A couple of years ago I wrote two blog entries about high-performance
> data structures
> for polymorphic objects:


> and I'd be very grateful if people could give their opinion on
> usefulness, design, etc.
> so as to determine potential interest in an eventual official submission
> to Boost.

A. This is very useful.

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 );

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

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.

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?

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?

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

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


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.

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