|
Boost : |
Subject: [boost] Interest in a "breadth first" algorithm?
From: Gary Powell (gwpowell_at_[hidden])
Date: 2012-06-18 18:47:03
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-
-- ------------------ powellg_at_[hidden] "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' or you'll sink like a stone. For the times they are a-changin'" Bob Dylan
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk