Re: [boost] poly_collection (was sentinels vs iterators)

Subject: Re: [boost] poly_collection (was sentinels vs iterators)
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2014-08-24 04:59:46

Ion Gaztañaga <igaztanaga <at> gmail.com> writes:

> 
> El 23/08/2014 20:53, Joaquin M Lopez Munoz escribió:
> >>
> >> On 21/08/2014 12:12, Joaquin M Lopez Munoz wrote:
> >>> Some
> >>> months ago I explored a container-like construct for polymorphic
> >>> objects that group elements by run-time type so as to greatly
> >>> speed up for_each processing:
> >>>
> >>> http://bannalia.blogspot.com.es/2014/05/
> >>> fast-polymorphic-collections.html
> >
> > [...] if you are managing
> > collections of polymorphics objects and traversal order is not relevant,
> > you are probably better off using something like poly_collection (or the
> > intrusive structure you mention) rather than
> > std::vector<std::unique_ptr<Base>> (or boost::ptr_vector<Base>, for that
> > matter).
> 
> An interesting data structure. Erasure also seems a bit curious. I guess 
> you could implement it with an iterator that maybe contains a pointer to 
> a base class and:
> 
> -> calls each segment::erase(it);
> -> if the segment detects the address of the base is inside vector's 
> memory, then :
> a) Derived *pderived = static_cast<Derived*>(it.base)
> b) vec_it = segment.vector.begin() + (pderived - &vector[0])
> c) segment.vector.erase(vec_it);

Erasure can be implemented without segment detection if iterators
are equipped with a pointer (or, better yet, a std::map<std::type_index,
pointer>::iterator) to the chunk (or poly_collection_segment_base
in the source code terminology) they belong in --after all, something
like this is needed to implement interchunk increment.

> A container that is not a sequence, unordered but not associative. 
> unordered_collection might be an alternative name.

This name misses the critical feature that elements are polymorphic.

> An interesting addition to Boost.Container? 

If I had the time :-/ I' ve been considering working a little more on
this to turn the initial sketch into something resembling a full-fledged
container, but it'd take me some days' work I don't have.

Joaquín M López Muñoz
Telefónica