On 10/14/2010 1:23 AM, David Abrahams wrote:
At Wed, 13 Oct 2010 12:08:43 -0700, Jeffrey Lee Hellrung, Jr. wrote: [...]
Yes. But I'm not convinced yet that iterators exposing the segmentation of the data structure are the right solution to presenting a flattened view of that data structure.
Good; that's not what they're for ;-)
I think I missed something, then. Are we not applying sequential algorithms (e.g., fill, for_each, ...) to hierarchical data structures?
1) It doesn't play nice with standard C++ looping constructs, specifically for loops.
The whole point of hierarchical algorithms is to avoid flat loops for segmented data structures.
It certainly avoids flat loops, to the point of outright precluding their use. I can add here a 1a) How would you go about iterating through segmented data structures in parallel?
2) I have yet to see a benchmark comparison between segmented iterators and alternatives (other than a side-note claim in the paper). I'm open to looking at some specific comparisons if one has already done this, and this is something I'm interested enough in that I might try to do myself. Seems to me a more general solution is a "flat_multirange_iterator" templated on the outer range and the "segmentation depth". I.e., a flat_multirange_iterator< vector< vector<T> >, 2> would iterate over the T's.
That's gonna be slow. Lots of testing and branching.
"Note that the joined range incurs a performance cost due to the need to check if the end of a range has been reached internally during traversal."
First, that quote applies directly to a join_iterator, though I'll give you that it *may* apply to my hypothetical a flat_multirange_iterator. What I'm having trouble with is it *looks* to me like you have the same tests and branches with a segmented iterator as with a flat_multirange_iterator. Comparing the nested for-loop on page 5 of the Austern paper (which is what a segmented iterator would give you) with the flattened while-loop on page 6 (let's replace the while-condition with true put an inserted break statement when !(node != nodes.end())), they both have the same number of iterator increments, comparisons, and assignments. What am I missing? Are compilers just able to produce better code for nested for-loops than flattened loops?
To address your claim that "that's the same problem ... that segmented iterators are solving", what I meant by a join_range or joint_range is, essentially, a flattened out Boost.Fusion sequence of ranges of *differing* types (but with compatible value_type's and references). E.g., the thing that boost::join [1] returns. Segmented iterators can't deal with such ranges (at least with a strict reading of Austern's paper),
I don't see why you say that.
Show me what the equivalent nested for-loop looks like if a join_range can be "segmentedly" iterated over. If I tried, I'd be inclined to write a for-loop over a Boost.Fusion sequence. If you want to include a join_iterator within the family of segmented iterators, you'd have to enrich the interface of segmented iterators to include Boost.Fusion sequences. Is that desirable? Maybe? [...]
http://www.boost.org/doc/libs/1_44_0/libs/range/doc/html/range/reference/uti...
Looks like this doc is missing something about the value/reference type requirements, BTW.
Yes :( - Jeff