Boost logo

Boost :

Subject: Re: [boost] Interest in a "breadth first" algorithm?
From: Brian Wood (woodbrian77_at_[hidden])
Date: 2012-06-23 12:20:44

Gary Powell:
> 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
> 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.

I'm interested. If you like I'll give you an investment in Ebenezer
Enterprises [1]. If you post it here or send it to me, I'll probably use
it in the archive available here -->

[1] Past performance is not a guarantee of future results.

> "Come gather 'round people wherever you roam. And admit that the waters
> around you have grown. And accept it that soon you'll be drenched to the
> bone. If your time to you is worth savin'. Ahh you better start swimmin'
> you'll sink like a stone. For the times they are a-changin'" Bob Dylan
Huh. Bob Dylan is from the Hibbing/Duluth part of Minnesota.
In the days after you posted, that area received a summer's worth
of rain in 36 hours. An 8 year old boy nearly died in the flooding
when he was swept down a culvert. Thankfully he popped up a mile
down the system and has been giving interviews since.

Brian Wood
Ebenezer Enterprises <>

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