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)
> 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk