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

From: Thorsten Ottosen (tottosen_at_[hidden])
Date: 2006-02-03 18:38:10

David Abrahams wrote:
> Thorsten Ottosen <tottosen_at_[hidden]> writes:

>>>For that drop_front works great.
>>
>>how do you construct the range [begin,found) if the algorithm
>>returns ther range [found,end) ?
> 
> 
> Maybe you just write an algorithm for that?
> 
> There are lots of ways to approach this.  Maybe you want an uber-find
> that returns a quadruple of iterators from which you can choose:
> 
>      uber_find( x, 5 ).range(0,2);
> 
> or
> 
>      uber_find( x, 5 ).range(_0,_2);
> 
> that is, it grabs the 0th (beginning) and 2nd (after-found-element)
> iterators from the result.

That can just be a member function in iterator_range<T>, eg 
slice(size_type,size_type).

Anyway, if the convention of range-based algorithms should
be "always return [found,end)", it raises the question why we think
this range is more imoprtant than [begin,found) (and some of the others).

The natural answer is of course: it is not more important or more 
fundamental.

Therefore it is natural to investigates means to return the slices you 
need. We have already seen that seperate slice functions cannot be
always be safe unless they require the use of a temporary, thus 
defeating the much purpose of ranges.

>>>>>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.
>>
>>For eaxmple, take unique():
>>
>>		
>>	template< range_return_value re, class Rng >
>>	inline BOOST_DEDUCED_TYPENAME range_return<Rng,re>::type
>>	unique( Rng& r )
>>	{
>>		return range_return<Rng,re>::pack( std::unique(boost::begin(r),
>>												boost::end(r)),
>>		r );
>>        }
>>
>>this allows the algorithm to return an iterator like the old version.
> 
> 
> How is that choice made?
> 

at the call site:

unique<return_found>( rng );

range_return_value is just an enumeration used to implement partical 
specializations of range_return<T,range_return_value>.

>>It also illustrates that if we change the template parameter to
>>a function parameter, pack() becomes a big function with a switch case.
> 
> 
> I don't see it.  It looks like my function is a new overload of find.

well, you have to decide which range to construct based on the indexes 
passed to the algorihtm.

>>>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?
>>
>>then you get an empty range.
> 
> 
> Even when you're asking for the range from found-1 to end?
> In that case, there is no "found-1" position, right?

I'm have settled on anything certain here, I'm just giving the samentics
I find most natural.

The basic principle should be that the range is always open at the end.

Let's recab:

// rng = {5}

find<return_begin_found>( rng, 5 ) returns an empty range
find<return_begin_prior>( rng, 5 ) returns an empty range
find<return_begin_next>( rng, 5 )  returns a range with one element
find<return_found_end>( rng, 5 )   returns a range with one element
find<return_prior_end>( rng, 5 )   returns a range with one element
find<return_next_end>( rng, 5 )    returns an empty range

thus we only increment or decrement if we does not exceed the bounds of 
the range.

>>[Dave:]
>> >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?
>>
>>
>>>>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.
>>
>>
>>You asked how you check for success. My reply was the if-statement above.
> 
> 
> Huh?  The result of find is now convertible to bool?

yes, iterator_range<T> defines operator unspecified_bool().

>>If you ask for a range [begin,found) when you search for 5, and 5 is the 
>>fist element, then of course you get back an empty range.
> 
> 
> Yes, but suppose you ask for [found-1,end)?

correponds to the case return_prior_end above: a range with one element.

-Thorsten