Isn't using find with retro awkward?

Steven Schveighoffer schveiguy at yahoo.com
Tue Feb 15 06:20:05 PST 2011


On Mon, 14 Feb 2011 22:35:21 -0500, Andrej Mitrovic <none at none.none> wrote:

> import std.stdio, std.algorithm, std.range;
>
> void main()
> {
>     writeln( find([5, 1, 2, 3, 4, 5, 1], 5) );
>     writeln( find(retro([5, 1, 2, 3, 4, 5, 1]), 5) );
> }
>
> Output:
> [5, 1, 2, 3, 4, 5, 1]
> [5, 4, 3, 2, 1, 5]
>
> The docs for find are:
> "returns : haystack advanced such that binaryFun!pred(haystack.front,  
> needle) is true "
> "To find the last occurence of needle in haystack, call  
> find(retro(haystack), needle). "
>
> To me, if I was looking for the last element in a range I would expect  
> to get a range with the found element followed by an elements after it.  
> Obviously retro reverses the range (it just hard-wires front=back,  
> back=front for those not in the know), so this code is correct.
>
> Still, I would expect that finding a last element in this range:
> [5, 1, 2, 3, 4, 5, 1]
>
> would return the range:
> [5, 1]
>
> and not:
> [5, 4, 3, 2, 1, 5]
>
> Isn't that what most people would want when they're looking for the last  
> matching element?

This is one of the fundamental problems with ranges -- a more useful  
construct for find to return is a reference to the individual element,  
then you could create a subrange based on that element location.   
Essentially, there are two things find does and it's impossible to unlink  
them -- 1) find the needle, 2) choose which side of the needle is the  
range you want to get back.

So really, there are *4* operations that we need, find remainder, find  
until, find reverse remainder, and find reverse until.  I should be able  
to get these four ranges with the different instances of find:

[]
[5, 1, 2, 3, 4, 5, 1]
[5, 1, 2, 3, 4]
[5, 1]

This is why dcollections uses cursors -- tiny ranges that refer to exactly  
one element.  Then you can use cursors to slice the original container.

-Steve


More information about the Digitalmars-d-learn mailing list