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

From: David Abrahams (dave_at_[hidden])
Date: 2006-02-02 16:52:41

Thorsten Ottosen <tottosen_at_[hidden]> writes:

> David Abrahams wrote:
>> Thorsten Ottosen <tottosen_at_[hidden]> writes:
>
>>>1. leave the return type as it is.
>>>
>>>2. return an iterator_range describing the range [found,end)
>>>this allows us to do stuff like
>>>
>>>    namespace br = boost::ranges;
>>>    br::erase( rng, br::unique(rng) );
>>>
>>>3. inspired by John Torjo's range lib, provide a whole list of possible 
>>>   return values:
>
> [snip]
>
>> 2 is the answer for me.
>> 
>> 
>>>the default would be the range [found,end), but the you can pick
>>>different slices or simply iterators. In the above scheme, "found" is 
>>>the iterator normally returnes by the algorithm, "next" means 
>>>boost::next(found) and "prior" means boost::prior(found).
>> 
>> 
>> And that works for ranges without bidirectional iterators, e.g. slist?
>
> "prior" can of course not work with bidirectional iterators.

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.

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

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

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

If this is an important case (still not convinced), 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.  That's consistent with the spirit 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.

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?

> Thus we would 
> be forced to create a temporary.

> -Thorsten
>
> (*) without much extra work, I could probably get a generalized
> version like
>
>    xx_next<N>
>    xx_prior<N>
>
> to work.

No offense, but bleah.  Keep it simple.

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