Re: Andrei's "iterators must go" presentation

Hakusa wrote:


I don't think there is, unless e.g. you use memory chunks in which case
computing overlap O(1). But I also don't think that's a problem at all.

I used to worry a lot about that in my early days with ranges. Just like
you, I'd predicted the need for computing range overlap will come up
very frequently. (I now believe this was because I initially wanted to
do iterator-style coding with ranges, much like Fotran people would try
to write Fortran in C++ and notice a lot of trouble that they attribute
to C++.) So I defined a function

Range overlap(Range, Range)

and only implemented it for memory chunks (where it's cheap) and decided
to think about the rest later. After experience with implementing
probably more than 200% of <algorithm> (including really weird functions
like n-way set union and string kernels), I hadn't needed overlap() even
once. There was always a range-based solution that was simpler and more
elegant. Also, the tyranny of the three-legged functions (e.g. partition
or rotate) was very happily overthrown by generalizing them to two-range
functions that are actually much more general.

There is a function I did need exactly once and it's not mentioned on
the slides. For implementing the rotate() algorithm (which I think is a
pretty important one) you must have a primitive

bool same_head(Range, Range);

that tells whether two ranges start at the same position. (Notice that
the types of the two ranges are identical). I initially thought that
that's only one optimization, but after a second pass through the
algorithm I realized it's a fundamental requirement.

So I think same_head is also a necessary primitive. One way to avoid
that is to deem two ranges to have same_head if the addresses of fronts
are identical: &(r1.front()) == &(r2.front()). I keep on thinking there
might be some weird range that may break this. For example two stride
ranges may have the same head but otherwise not iterate over the same
elements. Passing such strides to rotate() may get it confused.

Beyond that, I think that ranges foster creative solutions that not only
avoid their perceived difficulties, but also generalize behavior in
unexpected ways. Consider my find() example - as soon as I say it
returns the right-hand side, the natural question is: "but what if I
want the left-hand side?" After some thinking, I defined a simple range
called "until" that lazily iterates another range until a specific value
is found. For example, until(a, 5) against an range containing (2, 3, 7,
5, 4, 6) is a lazy range that gives you (2, 3, 7). The nice thing is
that using until() is more general than STL's find() because the former
gives you the opportunity to work with an input iterator, whereas the
latter doesn't - as soon as find() returned, the left-hand side of the
input is lost forever. So all of a sudden not only we have a solution
that is as good as find() on forward ranges, but we also have a solution
better than find() on input ranges.

Andrei

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]