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

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

David Abrahams wrote:
> 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.

right, my mistake.

Now consider having the range [found,end) being returned. How do you
supply the functionality given by the return_begin_found flag?

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

right.

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

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

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

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.

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

It also illustrates that if we change the template parameter to
a function parameter, pack() becomes a big function with a switch case.

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

right.

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

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

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.

-Thorsten