Isn't using find with retro awkward?

[Steven Schveighoffer]

On Wed, 16 Feb 2011 13:43:57 -0500, spir <denis.spir at gmail.com> wrote:

> On 02/16/2011 05:24 PM, Steven Schveighoffer wrote:
>> On Wed, 16 Feb 2011 11:14:27 -0500, Andrej Mitrovic
>> <andrej.mitrovich at gmail.com> wrote:
>>
>>> On 2/16/11, spir <denis.spir at gmail.com> wrote:
>>>>
>>>> for any reason, I would prefere
>>>> findBack(haystack, needle);
>>>> :-)
>>>
>>> Or maybe find should have an extra parameter that decides if the
>>> search begins from the beginning or the end of the range.
>>
>> I just realized, this isn't possible in the general case. That is,  
>> given your
>> original range [5, 1, 2, 3, 4, 5, 1], the only way to get [5, 1] is to  
>> use
>> popFront.
>>
>> Think about this. What are the basic operations of a bidirectional  
>> range?
>> popFront and popBack. There is no way to search from the back, and then  
>> use
>> that as the front end of the resulting range.
>>
>> Essentially, the range API does not allow what you want unless you have  
>> a
>> random-access range, and I don't even know if that can be generalized.  
>> The
>> operation you are looking for is very different from what find does.
>
> Agreed.
> On the other hand, it is a basic operation very often provided by APIs  
> for collections --together with several other operations having a right-  
> or -last or version. And it's not like a trivial one-liner one would  
> occasionnally re-implement on occasion. This is ypically, I guess, the  
> kind of service std.algorithm is supposed to deliver. And we shouldn't  
> find it elsewhere since this module is precisely supposed to provide  
> general purpose algorithms.
> Thus, don't we face a contradiction, due to the fact that std.algorithm  
> is mainly range-oriented? How to reconciliate this with the broader  
> "range" of operations one would expect to find there?
>
> In this case, couldn't we still have the extra parameter, and check the  
> collection allows random-access? Or have a variant with this extra param  
> beeing non-optional and a stricter template constraint allowing only  
> random-access ranges/collections?

The problem is ranges are missing some features that iterators make  
possible.

If we think back to C++ iterators, a "range" is a pair of iterators.  But  
you have the power to use whatever two iterators you want for your range.

So what Andrej wants is possible in C++ (although ugly):

target = std::find(std::reverse_iterator(r.end),  
std::reverse_iterator(r.begin), 5);
target++;
myrange = Range(target.base(), r.end)

now the "range" myrange is [5, 1]

one could easily abstract this into a function (e.g. rfind) so you could  
do:

myrange = Range(rfind(r.begin, r.end), r.end);

The issue is that find returns a range, and you cannot easily "flip"  
ranges given the original range.  But if you get an iterator (or cursor in  
the case of dcollections), then constructing the correct subrange is  
trivial.  With dcollections cursors, it's actually also safe too.

-Steve