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

From: David Abrahams (dave_at_[hidden])
Date: 2006-02-03 11:50:41

Thorsten Ottosen <tottosen_at_[hidden]> writes:

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

>>>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?!
>
> It's a utility wrapper of an existing std algorihtm.

And my suggestion is not?

> You'l need to implement a new version of find so that it works for
> forward iterators, you don't just forward to an existing.

Actually you can, if you're willing to pay a little more.
Writing a new one is just an optimization.

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

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

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

> [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?

> 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)?

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