At Wed, 13 Oct 2010 12:08:43 -0700, Jeffrey Lee Hellrung, Jr. wrote:
On 10/13/2010 08:04 AM, David Abrahams wrote:
At Wed, 13 Oct 2010 03:44:37 -0700, Jeffrey Lee Hellrung, Jr. wrote:
Seems to me segmented iterators and a visitation-based/push-based iteration address fundamentally different problems. At least, I don't see how segmented iterators help here. The problem that visitation-based iteration seems to try to solve is improving iteration efficiency over join(t)_range-like ranges...
That's the same problem (in essence) that segmented iterators are solving. Did you read the Austern paper?
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 ;-)
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.
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."
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.
and I think such ranges are closer to what Mathias has in mind (to be verified......). But perhaps I'm just not seeing your generalization beyond the immediate scope of the Austern paper?
- Jeff
[1] 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. -- Dave Abrahams BoostPro Computing http://www.boostpro.com