Re: [boost] Re: Formal Review Minmax

From: Herve Bronnimann (hbr_at_[hidden])
Date: 2002-10-09 22:59:55

On Mon, Oct 07, 2002 at 07:17:38PM +0100, Alisdair Meredith wrote:
> I have not had a chance to run the code through my compiler, so my
> comments are entirely based on the documentation, which I assume is
> accurate.  [I will run up some test cases later tonight, but don't want
> to miss the review deadline]

Thanks for taking the trouble to meet the deadline. And apologies for
not replying earlier.

> The main difference is that we pass in the result type as an output
> parameter.  This is useful for us because we also support larger
> statical return objects containing the sum, mean and variance.  That
> being beyond the scope of this library, the pair return makes sense.

I'd be very interested to know how you do that, since I mention in the
rationale that an accumulator library (with min_accumulator
complementing a bunch of other accumulators, esp. sum, mean, and
variance) would make a lot of sense, although probably an extension of the minmax
library and not to subsume it.

> We also suffer from drop-outs in our data, represented by invalid values
> [such as NAN]  We automatically filter such values when parsing the
> data.  Again, where we have done this intrusively in our algorithms it
> would seem the filter_iterator_adaptor combined with minmax do a
> superior job, another point to minmax!

I was just going to suggest the filter_iterator_adaptor before I
finished reading your sentence. I agree.

> I wondered what would happen if minmax were given an empty range, and
> the documentation is no clearer.  It merely insists that the passed
> range is valid as a precondition.  Would 'valid and non-empty' be better
> phrasing, or is an empty range automatically be assumed invalid?  This
> is not the case for any of the STL algorithms I can recall, and so worth
> highlighting anyway.

I DO assume that an empty range IS valid. This is the definition of
validity (IIRC): last must be attainable from first by a finite
nonnegative number of applications of ++ (this number can be 0).

About the return value, the algorithms perform fine if the range is
empty. To quote the documentation:

  Postconditions:
  In addition to the semantic description abover, for minmax_element and
  all the which_min_what_max_element variants, the return value is last or
  std::make_pair(last,last) if and only if [first, last) is an empty
  range.
  
It's also the convention in all these algorithms to return last if the
input range is empty, so I don't think I innovated there. That's also
why I didn't insist on it either.

Of course, it's informative that you couldn't find that point, but I
don't think I mistated it in the documentation. I could add it in the
description more explicitly, if you prefer.

> I'm not sold on the first/last algorithms, and did not follow why the
> policy based approach was rejected.  Rather than use a default policy,
> minmax_element could be overloaded so that the extra versions [that are
> non-standard anyway] use the policy and the default version carries
> straight over to standardisation.

The policy-based approach is not rejected, but I don't want to use it
for the minmax_element algorithm. I may very well use it for the
first/last variants (in the implementation, and perhaps export it to the
documentation).

> A final thought was that the pair might be more efficiently built using
> call_traits, but that may be a premature optimisation.

Premature optimisation is the root of all evil :)
I haven't investigated call_traits lately, but I tend to think of pair
as small enough that every decent optimiser will work properly on it.
Especially since it's part of the C++ standard now.

> This being my first review, and critiquing another's work without
> putting up any of my own, I find it hard to say 'no' so do not oppose
> the addition of minmax into boost.  However, I would rather see more
> discussion about the first/last variants before voting a wholehearted
> 'yes'.

You'll be happy: I'll soon post in the sandbox a policy-based implementation,
and we can continue the discussion from there. Although for me it's an
implementation detail to use policies, since I don't want to change the
interface of boost::minmax_element<..>(). This might change in the
future if minmax_element is integrated, then the boost version could use
policies. As it is now, I'd rather keep it clean and simple.

Thanks for your review,
-- 
Herve'