Re: [Boost-users] iterators must go

Subject: Re: [Boost-users] iterators must go
From: Daniel James (daniel_james_at_[hidden])
Date: 2009-05-16 04:33:29

2009/5/16 Scott McMurray <me22.ca+boost_at_[hidden]>:
>
> I'm very curious how that's supposed to work.  What if, for example,
> the second range is a superset of the first?  Or, since they can be
> two different types, what happens if I do the same thing as the above,
> but "retro" one or both of the ranges?

>From the reference:

Preconditions:
Either front and back are disjoint, or back is reachable from front
and front is not reachable from back.

It's not entirely clear what 'reachable' means - does it just mean
that the front is at the same position, or does it mean that the
ranges are identical. If you look at the code for bringToFront it uses
a method called 'sameHead' (not sameFront for some reason) to detect
this case, so I think it's referring to that. Here's a test:

    import std.algorithm;
    import std.range;
    import std.stdio;

    // Used to prevent bringToFront from using sameHead.
    struct ArrayRange {
        int[] x;

        this(int[] x1) { x = x1; }
        void popFront() { x.popFront(); }
        bool empty() { return x.empty(); }
        ref int front() { return x.front(); }
    }

    void main() {
        int[] arr = [0,1,2,3,4,5,6];
        bringToFront(arr, arr[3..5]);
        writeln(arr);

        arr = [0,1,2,3,4,5,6];
        bringToFront(arr, retro(arr[3..5]));
        writeln(arr);

        arr = [0,1,2,3,4,5,6];
        bringToFront(arr, ArrayRange(arr[3..5]));
        writeln(arr);

        arr = [0,1,2,3,4,5,6];
        bringToFront(arr, ArrayRange(arr[3..7]));
        writeln(arr);
    }

Output:

    3 4 0 1 2 5 6
    4 3 0 6 5 1 2
    3 4 0 5 6 1 2
    3 4 5 6 1 2 0

Unsuprisingly, it only gets the first one right. How would the STL
deal with cases that don't meet the preconditions?

> It just sounds brittle to me.

Compared to what?

> Or, even simpler, how do I do this?
>
> size_t strnlen(char *p, size_t n) {
>    return find(p, p+n, '\0') - p;
> }
>
> That's the size of a range, but I don't know how to get that range.

Since you require a random access iterator:

    arr.length - find(arr, '\0').length

But I suspect your point is more to do with partitioning forward and
bidirectional ranges and that does seem a weakness. I suppose that
when you've got 'sameHead', you've got a means for two ranges to
define a subrange, although it's a little inefficient.

There's a trade off here - he could have efficient partitioning if he
implemented another range that remembers its original front and can
return the range from that up to its current front but I suspect he
doesn't want to have multiple range classes and doesn't want to have
to store an extra index/pointer in his ranges.

In the specific case of arrays, I was surprised to find out that the
member functions aren't member functions at all, but just functions
that operate on the built in arrays (in D, arr.popFront() is the same
as popFront(arr)) - so you can implement this kind of thing quite
easily yourself.

FWIW, I don't know much about this, I looked at D 2.0 for the first
time last night. You might be better of going to the source.

Daniel