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

From: Eric Niebler (eric_at_[hidden])
Date: 2006-02-02 15:18:45

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.

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

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

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

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

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? If so, what does this 
mean:

   std::vector<int> v1(4,4), v2;
   br::copy(v1, v2);

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

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'll stop for now. :-)

-- 
Eric Niebler
Boost Consulting
www.boost-consulting.com