[boost] Formal Review Minmax

From: Thomas Witt (witt_at_[hidden])
Date: 2002-09-28 15:12:10

The formal review for the minmax algorithm starts today 28 sep and ends 7 oct.

Herve Bronnimann is the library author and I am the review manager.  Minmax is 
supposed to be part of a full fledged boost algorithm library if such a thing 
will ever make it to existance. For the time being we decided to review 
algorithms one-by-one or in small chunks.

The review sources and documentation can be found here:

http://groups.yahoo.com/group/boost/files/minmax_element/minmax.zip

For guidelines on formal reviews look at:
 
http://www.boost.org/more/formal_review_process.htm.

Following is a short description of minmax

  The minmax library is composed of a single header minmax.hpp.  I
   always thought it is a waste to have to call two functions to compute
   the extent of a range, performing two passes over the input, when one
   should be enough.
   
   The first part implements the function templates minmax and
   minmax_element as straightforward extensions of the C++ standard.
   The second part proposes variants that can usually not be computed by the
   minmax algorithm, and which are more flexible in case some elements are
   equal.
   
   If you are interested about performance, you will see that
   minmax_element is just slightly less efficient than a single min_element
   or max_element, and thus twice as efficient as two separate calls to
   min_element and max_element. From a complexity standpoint, all the
   minmax_element functions perform at most 3n/2+1 comparisons and exactly
   n increments of the ForwardIterator.
   
   (Please note: the intent is not to fix the known defaults of
   std::min and std::max, but to add one more algorithms that combines
   both; see the rationale about references to previous discussions,
   including Alexandrescu's paper and refs therein.)

   SYNOPSIS:

     template <class T>
     std::pair<const T&,const T&>
     minmax(const T& a, const T& b);
   
     template <class T, class BinaryPredicate>
     std::pair<const T&,const T&>
     minmax(const T& a, const T& b, BinaryPredicate comp);
   
     template <class ForwardIterator>
     std::pair<ForwardIterator,ForwardIterator>
     minmax_element(ForwardIterator first, ForwardIterator last);
   
     template <class ForwardIterator, class BinaryPredicate>
     std::pair<ForwardIterator,ForwardIterator>
     minmax_element(ForwardIterator first, ForwardIterator last,
                    BinaryPredicate comp);
   
     // the other more specialized variants can be found in the documentation

Thomas Witt

-- 
Dipl.-Ing. Thomas Witt
Institut fuer Verkehrswesen, Eisenbahnbau und -betrieb, Universitaet Hannover
voice: [phone] - 4273, fax: [phone]
http://www.ive.uni-hannover.de