Re: [boost] [Range] initial feedback on return values of algorithms

From: David Abrahams (dave_at_[hidden])
Date: 2006-02-03 08:47:53

Thorsten Ottosen <tottosen_at_[hidden]> writes:

> David Abrahams wrote:
>> Thorsten Ottosen <tottosen_at_[hidden]> writes:
>> 
>> 
>>>David Abrahams wrote:
>>>
>>>>Thorsten Ottosen <tottosen_at_[hidden]> writes:
>
>> In that case, this should *not* be integrated with the algorithms, but
>> should instead be provided (if it's needed) as a separate layer that
>> can adjust the endpoints of a range:
>> 
>>     drop_front(r)  ->  new view of r with the begin iterator incremented
>>     grow_front(r)  ->  new view of r with the begin iterator decremented
>>     drop_back(r)  ->  new view of r with the end iterator decremented
>>     grow_back(r)  ->  new view of r with the end iterator incremented
>> 
>> Okay, I see from your points below that the "grow" variants can be
>> dangerous.
>
> Well, all versions can be dangerous: just remember that r can be empty.

No, the "drop" versions are always safe because you can avoid
shrinking past empty.

> More importantly, to make them safe, you need to supply the original 
> range as a second input. This implies that you need to store a temporary
> --- this what we are actually trying to avoid.

No, that only applies to the "grow" versions.

> At least for me this *proves* that we can't extract the adjustsments of 
> the return value from the algorithm itself. I agree it would have been 
> nice if we could.

It would only be nice if we need it.  I still don't think we need it.

>>>>I'm wary of introducing any such complexity without a strong catalog
>>>>of use cases.
>>>
>>>basically it makes splitting of ranges way easier and safer.
>>>
>>>assume I want to find the first occurence of 5 and then copy the
>>>range [begin,found] (that is, [begin,next(found)) ) somewhere:
>>>
>>>	std::vector<int> v = ...;
>>>	std::vector<int>::iterator i = find( v, 5 );
>>>	if( i != v.end() )
>>>         {
>>>   	  ++i;
>>>           copy( v.begin(), i, out );
>>>         }
>>>
>>>vs
>>>
>>>	copy( find<return_begin_next>( v, 5 ), out ); (*)
>> 
>> 
>>     copy( drop_front( find( v, 5 ) ), out );
>> 
>> it's even shorter.
>
> and it will lead to undefined behavior of the range was empty.

No.  drop_front checks for empty ranges in just the same way.

>> If this is an important case (still not convinced), 
>
> generally it is hard to say what is important to all people. I do think, 
> however, that splitting a range into different sub-ranges is a fairly
> common activity. Some ranges are more common:
>
> [begin,found)
> [found,end)

For that drop_front works great.

> for example, take unique:
>
> erase( rng, unique(rng) );       // unique should return[found,end)
> copy( unique<return_begin_found>(rng), out );
>
> but I'm sure that sometimes you want to include the found value in the
>
>> I would consider
>> generalizing find with this overload:
>> 
>>       find( -1, v, 5 )
>> 
>> That is, "find the element before the one that's equal to 5".  And I
>> would *certainly* make it work for forward ranges with somewhat
>> reduced efficiency. 
>
> I'm not that keen on providing to many new algoriths.

What do you think this thing called "find" with the explicit template
parameter is, if not a new algorithm?!

> The return-value mechanism is a more like a layer on top of the 
> algorithm, not a new algorithm.

How is that distinct from the much simpler find illustrated above?
Are you saying that the use of the explicit template argument is what
makes it "not a new algorithm?"

>> That's consistent with the spirit of generic programming.
>
> well, as soon as we have to implement different algorithms for
> different iterator categories, some of the benefits and beauty goes
> away IMO.

Beauty is in the eye of the beholder, I guess.  I don't know what
benefits you think go away, but the specialization of algorithms to
take advantage of specific knowledge when you have it (e.g. that you
can iterate backwards) is a fundamental part of generic programming.

>> I don't think it's necessary to have the policy be a
>> compile-time thing.  But if it were, I'd still pass it by by value.
>
> it is necessary if you want the algorithm to be able to return
> either an iterator or a range. 

I don't want that, but please explain.

> if only ranges are supported, using a parameter seems like the thing
                                       ^
     regular run-time function---------+
??
> to do.

> the iterator version may of course be emjulated easily by calling
> foo<return_begin_found>(rng).end() etc.

Ick.

>> Anyway, how do you check for success?  What if 5 is the first element?
>> Do you get an empty range or do you just get v back?
>
> you get an empty range back if nothing is found:

Of course you do.  That wasn't my question.  In the original example
you were searching for 5.  So what happens when you ask for the range
beginning just before (or just after, for that matter) 5 in a
single-element range containing just 5?

> if( find( v, 6 ) )
> { ... }
>
>>>Thus we would be forced to create a temporary.
>
> yes, but only if you're not passing the range directly to another
> algorithm.

Now you're arguing with yourself.  I'm happy to sit back and see who
wins this one.

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com