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

From: Thorsten Ottosen (tottosen_at_[hidden])
Date: 2006-02-03 05:37:17

Eric Niebler wrote:
> Thorsten Ottosen wrote:
> 
>>Dear all,
>>
>>The plan is to include range-based overloads of std algorithms in the 
>>next boost.range.
> 
> 
> 
> Range algorithms are more complicated than they look. I think it would 
> be a mistake to bang this out and sneak it in without a full review.

ok, I was hoping for a mani-review, but I don't mind a full review.

>>We have several options for specifying the return type
>>of functions that normally return an iterator that I would like your 
>>feedback on.
> 
> 
> 
> This is, of course, just one of the questions range-based algorithms 
> raise, and probably the least controversial.

the others would be

a. calling members

b ?

>>1. leave the return type as it is.
> 
> 
> 
> Not a good idea. Range algorithms should consume *and* produce ranges. 
> This is so that multiple range algorithms can be composed/chained 
> together, a-la the functional style of programming.

right, but do you also waht sort() to return the sorted range?

>>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) );
> 
> 
> 
> Yes, this one, please.
> 
> But there is no "erase" algorithm. Do you mean something like:
> 
>    vect.erase(br::unique(vect).begin());
> 
> ? This actually argues *against* returning a range, at least until the 
> appropriate members are added to the std containers to accept ranges as 
> arguments. Or are you suggesting adding such an erase() algorithm as a 
> stop-gap until the std is changed:
> 
>    template<typename Rng1, typename Rng2>
>    void erase(Rng1 & rng1, Rng2 const & rng2) {
>      rng1.erase(rng2.begin(), rng2.end());
>    }
> 
> ? This is probably necessary, in fact.

yes, and ditto for push_back, push_front and insert.

>>3. inspired by John Torjo's range lib, provide a whole list of possible 
>>   return values:
>>
>>	std::vector<int> v;
>>	namespace br = boost::ranges;
>>	br::unique(v);
>>	br::unique<br::return_found>(v);
>>	br::unique<br::return_next>(v);
>>	br::unique<br::return_prior>(v);
>>	br::unique<br::return_begin_found>(v);
>>	br::unique<br::return_begin_next>(v);
>>	br::unique<br::return_begin_prior>(v);
>>	br::unique<br::return_found_end>(v);
>>	br::unique<br::return_next_end>(v);
>>	br::unique<br::return_prior_end>(v);
>>
> 
> 
> Yuk! I'd need to see justification.

well, you may comment on the thread with Dave.

> There are lots more issues with range algorithms that have not been 
> discussed yet. What about algorithms that accept an output iterator and 
> write into it? Will they now take an output range? 

My say would be no. We still have the concept of an unbounded iterator.

The unsafe usage of copy should be done with a new function called
overwrite(rng1,rng2) which can tjeck the bounds with an assert.

> ? Is it undefined behavior? Or is this range-checked? And if so, do we 
> truncate, assert or throw? Is there a way to make range-checking 
> optional? Can we specify the failure mode? And what should the default be?

Using an exception seems not to in the spirit of STL.

> And what does br::copy return? You might think the answer is easy: the 
> range designating the unused elements at the end of the second range. 
> But what if br::copy is range-checked and truncates? That return value 
> is no longer sufficient -- if br::copy returns an empty range, did the 
> algorithm truncate, or did it all just fit?

I'd be quite happy with copy returning void.

-Thorsten