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

From: Thorsten Ottosen (tottosen_at_[hidden])
Date: 2006-02-03 06:09:48

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.

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.

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.

>>>>The advantage of the latter approach is
>>>>
>>>>- flexibility/power
>>>>- safety (we can tjeck that next(found) and prior(found) stays in range)
>>>>
>>>>The disadvantage is that it will require twice as many overloads in 
>>>>C++03 (since we can't put defaults template arguments in function 
>>>>templates).
>>>
>>>
>>>And it's complex.
>>
>>implementation wise or interface wise?
> 
> 
> Yes.  And documentation-wise.  And comprehension-wise.

well, implementation wise it consist of 9 partial specializations
and twice as many function overloads (remark: in C++0x 4 functions 
reduce to one function)

documentation-wise you don't have to explain the mechanism for every 
function, just
show an interface that supports it.

comprehension-wise, well, all new things take time.

>>>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.

>>If found == v.end(), the returned ranges are empty and so you completely
>>avoid forgetting about checking for the end iterator.
>>
>>Having only (2) we can still, however, do a little better than above:
>>
>>	copy( find( c, 5 ).advance_end(1), out )
>>
>>but now we can't be sure we don't iterator past the end. 
> 
> 
> Okay, that's a different case.  Why would you ever want to advance the
> *end* of a find?  It's really beside the point, though.
> 
> Feh.  

right, stupid example.

> 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 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.

The return-value mechanism is a more like a layer on top of the 
algorithm, 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.

 > 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. if only ranges are supported, using
a parameter seems like the thing to do.

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

> 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:

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.

-Thorsten