At Thu, 14 Oct 2010 23:27:21 -0700, Jeffrey Lee Hellrung, Jr. wrote:
IIUC, there already is support for segmented Boost.Fusion iterators somewhere.
If you can provide more direction here, I would appreciate it. There is boost::fusion::joint_view, but that only concatenates 2 Boost.Fusion sequences, not 2 ranges...
Eric knows more about this than I do. Eric?
By the way, I did run a comparison between a segmented iteration, with nested for-loops, and a flattened iteration. I was very much surprised in the runtime difference. It obviously depends on the operation you do per iteration, but for just incrementing a counter, the difference was 2 or 3 orders of magnitude. Needless to say, I'm more convinced of the value of exposing the segmentation of data structures now.
:-)
Here's what I'm getting from this discussion: I see 2 viable approaches to address iteration over non-linear data structures, where efficiency is a major concern. One is an external, segmented iterator interface, possibly enriched to enable iteration over Boost.Fusion sequences at any depth. The other is an internal "push" or visitation iteration suggested originally by Mathias. Neither models seem to yield *convenient* implementations of *all* iteration algorithms in <algorithm>,
Some things definitely become significantly more complicated to implement.
but I can see enough utility that one model and/or the other would be worth investigating. I'm not sure yet if either iteration model is more powerful than the other, though it seems there are some algorithms expressable via segmented iteration that would be challenging to express via push iteration.
Anything that requires bidirectional or random access, for example.
In any case, David, I appreciate your patience and participation.
np. Glad this topic is getting some much-needed exposure. -- Dave Abrahams BoostPro Computing http://www.boostpro.com