Subject: Re: [boost] Interest in a "breadth first" algorithm?
From: Rutger ter Borg (rutger_at_[hidden])
Date: 2012-06-19 07:43:10
On 2012-06-19 00:47, Gary Powell wrote:
> A while ago I needed to serialize and de-serialize a std::map and I
> realized that the only interface was begin(), end() which of course meant
> that re-creating this same map was the least efficient way possible, as all
> the elements were added in sorted order. Because I wrote them out using
> begin() -> end() So I wrote a breadth first template which takes a
> container, a template to use as the core of a queue, a template for the
> allocator, the container and a function to apply to the elements.
> It doesn't quite do a true breadth first traversal because I don't look at
> the inner data structure of the map, (works with sets as well) but instead
> does a middle, then right, left push until it's hit all of the nodes. And
> it doesn't copy the elements, it pushes the iterators, and calls the
> function on that iterator when the length is 1.
> It ended up speeding up my map recreation by about 20% (because I start
> with a center enough node that it should never have to be rebalanced) at a
> cost of about 5% to write it this way (It's more expensive to create the
> queue, and traverse the map from center on out), for a roughly 15% gain in
> Is there any interest this for boost? I've got working code but not any
> documentation. And rather than spend a huge amount of time on that I'm
> looking to see if anyone else has an interest in this.
Maybe a an obvious question, but is this speedup relative to the
positional insertion overload of std::map?
iterator insert ( iterator position, const value_type& x );
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk