Boost logo

Boost :

Subject: [boost] [Serialization] Interest in a "breadth first" algorithm?
From: Dave Abrahams (dave_at_[hidden])
Date: 2012-06-21 14:55:13


This thread needed the tag in the subject line.

on Mon Jun 18 2012, Gary Powell <gwpowell-AT-gmail.com> 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
> speed.
>
> 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.
>
> -Gary-

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk