123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532 |
- <!DOCTYPE html public "-//w3c//dtd html 4.0 transitional//en">
- <HTML>
- <HEAD>
- <LINK REL="stylesheet" TYPE="text/css" HREF="../../../boost.css">
- <META http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
- <META name="GENERATOR" content="Mozilla/4.77 [en] (X11; U; Linux 2.2.19 i686) [Netscape]">
- <META name="Author" content="Herve Bronnimann">
- <META name="Description" content="Small library to propose minmax_element algorithm.">
- <title>Boost Minmax library</title>
- </HEAD>
- <body text="#000000" bgcolor="#FFFFFF" link="#0000EE" vlink="#551A8B" alink="#FF0000">
- <h2><img src="../../../boost.png" WIDTH="276" HEIGHT="86">Header <<A
- HREF="../../../boost/algorithm/minmax.hpp">boost/algorithm/minmax.hpp</A>> </H2>
- <quote>
- <b>
- <a href="#minmax_element">Motivation</a><br>
- <a href="#synopsis">Synopsis</a><br>
- <a href="#description">Function templates description</a><br>
- <a href="#definition">Definition</a><br>
- <a href="#reqs">Requirements on types</a><br>
- <a href="#precond">Preconditions</a><br>
- <a href="#postcond">Postconditions</a><br>
- <a href="#complexity">Complexity</a><br>
- <a href="#example">Example</a><br>
- <a href="#notes">Notes</a><br>
- <a href="#rationale">Rationale</a><br>
- <a href="#perf">Note about performance</a><br>
- <a href="#acks">Acknowledgements</a>
- </b>
- </quote>
- <a name="minmax_element">
- <h3>
- Motivation</h3>
- <p>The minmax library is composed of two headers, <a
- href="../../../boost/algorithm/minmax.hpp"><boost/algorithm/minmax.hpp></a>
- and <a
- href="../../../boost/algorithm/minmax_element.hpp"><boost/algorithm/minmax_element.hpp></a>.
- (See <a href="#two_headers">rationale</a>.)
- The problem solved by this library is that simultaneous min and max
- computation requires
- only one comparison, but using <tt>std::min</tt> and <tt>std::max</tt>
- forces two comparisons. Worse, to compute the minimum and
- maximum elements of a range of <tt>n</tt> elements requires only
- <tt>3n/2+1</tt> comparisons, instead of the <tt>2n</tt> (in two passes)
- forced by <tt>std::min_element</tt> and <tt>std::max_element</tt>.
- 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 present library solves both problems.</p>
- <p>The first file implements the function templates
- <tt>minmax</tt>
- as straightforward extensions of the C++
- standard. As it returns a pair of <tt>const&</tt>, we must use the <a
- href="../../tuple/index.html">Boost.tuple</a> library to construct such
- pairs. (Please note: the intent is not to fix the known defaults of
- <tt>std::min</tt>
- and <tt>std::max</tt>, but to add one more algorithms that combines both; see the
- <a href="#no-fix">rationale</a>.)</p>
- <p>The second file implements the function templates
- <tt>minmax_element</tt>. In a
- second part, it also proposes variants that can usually not be computed by
- the minmax algorithm, and which are more flexible in case some elements are equal.
- Those variants could have been also provided with policy-based design,
- but I ruled against that (see <a href="#no-policy">rationale</a>).
- </p>
- <p>If you are interested about
- <a href="doc/minmax_benchs.html">performance</a>,
- you will see that <tt>minmax_element</tt> is just slightly less efficient
- than a single <tt>min_element</tt> or <tt>max_element</tt>, and thus
- twice as efficient as two separate calls to <tt>min_element</tt> and
- <tt>max_element</tt>. From a
- theoretical standpoint,
- all the <tt>minmax_element</tt> functions perform at most
- <tt>3n/2+1</tt>
- comparisons and exactly n increments of the
- <tt>ForwardIterator</tt>.</p>
- </a>
- <a name="synopsis">
- <h3>
- Synopsis of <tt><boost/algorithm/minmax.hpp></tt></h3>
- <pre>#include <boost/tuple/tuple.hpp>
- namespace boost {
- template <class T>
- tuple<T const&, T const&>
- minmax(const T& a, const T& b);
- template <class T, class <a href="https://www.boost.org/sgi/stl/BinaryPredicate.html">BinaryPredicate</a>>
- tuple<T const&, T const&>
- minmax(const T& a, const T& b, BinaryPredicate comp);
- }
- </pre>
- <h3>
- Synopsis of <tt><boost/algorithm/minmax_element.hpp></tt></h3>
- <pre>#include <utility> // for std::pair
- namespace boost {
- template <class <a href="https://www.boost.org/sgi/stl/ForwardIterator.html">ForwardIterator</a>>
- std::pair<ForwardIterator,ForwardIterator>
- minmax_element(ForwardIterator first, ForwardIterator last);
- template <class <a href="https://www.boost.org/sgi/stl/ForwardIterator.html">ForwardIterator</a>, class <a href="https://www.boost.org/sgi/stl/BinaryPredicate.html">BinaryPredicate</a>>
- std::pair<ForwardIterator,ForwardIterator>
- minmax_element(ForwardIterator first, ForwardIterator last,
- BinaryPredicate comp);
- }
- </pre>
- In addition, there are a bunch of extensions which specify
- which element(s) you want to pick in case of equal elements. They are:
- <ul>
- <li><tt>first_min_element</tt> and <tt>last_min_element</tt></li>
- <li><tt>first_max_element</tt> and <tt>last_max_element</tt></li>
- <li><tt>first_min_first_max_element</tt>,
- <tt>first_min_last_max_element</tt>,
- <tt>last_min_first_max_element</tt>, and
- <tt>last_min_last_max_element</tt></li>
- </ul>
- I won't bore you with the complete synopsis, they have exactly the same
- declaration as their corresponding <tt>_element</tt> function. Still,
- you can find the complete synopsis <a href="doc/minmax_synopsis.html">here</a>.
- </a>
- <a name="description">
- <h3>
- Function templates description</h3>
- The <tt>minmax</tt> algorithm returns a pair <tt>p</tt> containing either
- <i>(a,b)</i>
- or <i>(b,a)</i>, such that <tt>p.first<p.second</tt> in the first version,
- or <tt>comp(p.first,p.second)</tt> in the second version. If the elements
- are equivalent, the pair <i>(a,b) </i>is returned. <a href="#Note1">[1]</a>
- <p>The <tt>minmax_element </tt>is semantically equivalent to <tt>first_min_first_max_element</tt>.
- <p><tt>First_min_element</tt> and <tt>first_max_element</tt> find the smallest
- and largest elements in the range <tt>[first, last)</tt>. If there are
- several instance of these elements, the first one is returned. They are
- identical to
- <tt>std::min_element</tt> and <tt>std::max_element</tt>and
- are only included in this library for symmetry.
- <p><tt>Last_min_element</tt> and <tt>last_max_element</tt> find the smallest
- and largest elements in the range <tt>[first, last)</tt>. They are almost
- identical to
- <tt>std::min_element</tt> and <tt>std::max_element</tt>, except
- that they return the last instance of the largest element (and not the
- first, as <tt>first_min_element</tt> and <tt>last_max_element</tt> would).
- <p>The family of algorithms comprising <tt>first_min_first_max_element</tt>,
- <tt>first_min_last_max_element</tt>,
- <tt>last_min_first_max_element</tt>,
- and <tt>last_min_last_max_element</tt> can be described generically as
- follows (using <i><tt>which</tt></i> and
- <i><tt>what</tt></i> for <tt>first</tt>
- or <tt>last</tt>): <tt><i>which</i>_min_<i>what</i>_max_element</tt> finds
- the (first or last, according to <i><tt>which</tt></i>) smallest element
- and the (first or last, according to <i><tt>what</tt></i>) largest element
- in the range
- <tt>[first, last)</tt>. The first version is semantically
- equivalent to:
- <pre><tt> std::make_pair(boost::<i>which</i>_min_element(first,last),
- boost::<i>what</i>_max_element(first,last))</tt>,</pre>
- and the second version to:
- <pre><tt> std::make_pair(boost::<i>which</i>_min_element(first,last,comp),
- boost::<i>what</i>_max_element(first,last,comp))</tt>.</pre>
- <p><br><b><i>Note</i></b>: the <tt>first_min_last_max_element</tt> can also be described
- as finding the first and last elements in the range if it were stably sorted.
- </a>
- <a name="definition">
- <h3>
- Definition</h3>
- Defined in <a href="../../../boost/algorithm/minmax.hpp">minmax.hpp</a>
- and
- in <a href="../../../boost/algorithm/minmax_element.hpp">minmax_element.hpp</a>.
- </a>
- <a name="reqs">
- <h3>
- Requirements on types</h3>
- For minmax, <tt>T</tt> must be a model of <a href="https://www.boost.org/sgi/stl/LessThanComparable.html">LessThan
- Comparable</a>.
- <p>For all the other function templates, versions with two template parameters:
- <ul>
- <li>
- <tt>ForwardIterator</tt> is a model of <a href="https://www.boost.org/sgi/stl/ForwardIterator.html">Forward
- Iterator</a>.</li>
- <li>
- <tt>ForwardIterator</tt>'s value type is <a href="https://www.boost.org/sgi/stl/LessThanComparable.html">LessThan
- Comparable</a>.</li>
- </ul>
- For the versions with three template parameters:
- <ul>
- <li>
- <tt>ForwardIterator</tt> is a model of <a href="https://www.boost.org/sgi/stl/ForwardIterator.html">Forward
- Iterator</a>.</li>
- <li>
- <tt>BinaryPredicate</tt> is a model of <a href="https://www.boost.org/sgi/stl/BinaryPredicate.html">Binary
- Predicate</a>.</li>
- <li>
- <tt>ForwardIterator</tt>'s value type is convertible to <tt>BinaryPredicate</tt>'s
- first argument type and second argument type.</li>
- </ul>
- </a>
- <a name="precond">
- <h3>
- Preconditions</h3>
- <ul>
- <li>
- <tt>[first, last)</tt> is a valid range.</li>
- </ul>
- </a>
- <a name="postcond">
- <h3>
- Postconditions</h3>
- In addition to the semantic description above. for <tt>minmax_element</tt>
- and all the <tt><i>which</i>_min_<i>what</i>_max_element</tt>
- variants, the return value is
- <tt>last</tt> or <tt>std::make_pair(last,last)</tt>
- if and only if <tt>[first, last)</tt> is an empty range. Otherwise, the
- return value or both members of the resulting pair are iterators in the
- range
- <tt>[first, last)</tt>.
- </a>
- <a name="complexity">
- <h3>
- Complexity</h3>
- Minmax performs a single comparison and is otherwise of constant complexity.
- The use of <tt>boost::tuple<T const&></tt> prevents copy
- constructors in case the arguments are passed by reference.
- <p>The complexity of all the other algorithms is linear. They all perform
- exactly n increment operations, and zero comparisons if <tt>[first,last)</tt>
- is empty, otherwise :
- <ul>
- <li>
- all the <tt>min_element</tt> and <tt>max_element</tt> variants perform
- exactly<tt>(n-1)</tt> comparisons,</li>
- <li>
- <tt>minmax_element</tt> , <tt>first_min_first_max_element</tt>, and <tt>last_min_last_max_element</tt>
- perform at most <tt>3(n/2)-1</tt> comparisons if <tt>n</tt> is even and
- non-zero, and at most <tt>3(n/2)+1</tt> if <tt>n</tt> is odd,
- <a href="#Note2">[2]</a></li>
- <li>
- <tt>first_min_last_max_element</tt>, and <tt>last_min_first_max_element</tt>
- perform exactly <tt>3n/2-2</tt> comparisons if n is even and non-zero,
- and at most <tt>3(n/2)</tt> if <tt>n</tt> is odd,
- <a href="#Note1">[3]</a></li>
- </ul>
- where <tt>n</tt> is the number of elements in <tt>[first,last)</tt>.
- </a>
- <a name="example">
- <h3>
- Example</h3>
- This example is included in the distribution in the examples section of
- the library under
- <a href="example/minmax_ex.cpp">minmax_ex.cpp</a>.
- <pre>int main()
- {
- using namespace std;
- boost::tuple<int const&, int const&> result1 = boost::minmax(1, 0);
- assert( result1.get<0>() == 0 );
- assert( result1.get<1>() == 1 );
- <a href="https://www.boost.org/sgi/stl/List.html">list</a><int> L;
- <a href="https://www.boost.org/sgi/stl/generate_n.html">generate_n</a>(<a href="https://www.boost.org/sgi/stl/front_insert_iterator.html">front_inserter</a>(L), 1000, rand);
- typedef list<int>::const_iterator iterator;
- pair< iterator, iterator > result2 = boost::minmax_element(L.begin(), L.end());
- cout << "The smallest element is " << *(result2.first) << endl;
- cout << "The largest element is " << *(result2.second) << endl;
- assert( result2.first == std::min_element(L.begin(), L.end());
- assert( result2.second == std::max_element(L.begin(), L.end());
- }</pre>
- </a>
- <a name="notes">
- <h3>
- Notes</h3>
- <a NAME="Note1"></a><a href="#Note1">[1]</a> We do not support
- idioms such as <tt><a href="../../tuple/doc/tuple_users_guide.html#tiers">tie</a>(a,b)=minmax(a,b)</tt>
- to order two elements <tt>a</tt>, <tt>b</tt>, although this would have
- the desired effect if we returned a reference instead of a constant
- reference. The reason is that two unnecessary assignments are
- performed if a and b are in order. It is better to stick to <tt>if (b<a)
- swap(a,b)</tt> to achieve that effect.
- <p><a NAME="Note2"></a><a href="#Note2">[2]</a> These algorithms always
- perform at least <tt>3n/2-2</tt> comparisons, which is a lower bound on
- the number of comparisons in any case (Cormen, Leiserson, Rivest: "Introduction
- to Algorithms", section 9.1, Exercise 9.1-). The algorithms essentially compare
- the elements in pairs, performing 1 comparison for the first two elements,
- then 3 comparisons for each remaining pair of elements (one to order the
- elements and one for updating each the minimum and and the maximum). When
- the number of elements is odd, the last one needs to be compared to the
- current minimum and also to the current maximum. In addition, for <tt>minmax</tt>,
- in cases where equality of the two members in the pair could occur, and
- the update stores the second, we save the first to check at the end if
- the update should have stored the first (in case of equality). It's hard
- to predict if the last comparison is performed or not, hence the at most
- in both cases.
- <p><a NAME="Note3"></a><a href="#Note3">[3]</a> These algorithms always
- perform at least <tt>3n/2-2</tt> comparisons, which is a lower bound on
- the number of comparisons in any case. The method is the same as in note
- <a href="#Note2">[2]</a>
- above, and like above, when the number of elements is odd, the last one
- needs to be compared to the current minimum and also to the current maximum.
- We can avoid the latter comparison if the former is successful, hence the
- <i>at
- most</i> instead of <i>exactly</i> in the odd case.
- </a>
- <a name="rationale">
- <h3>
- <b>Rationale:</b></h3>
- <a name="two_headers">
- <h4><b>Why not a single header <tt><boost/algorithm/minmax.hpp></tt>?</b></h4>
- <p>This was the design originally proposed and approved in the formal
- review. As the need for Boost.tuple became clear (due to the limitations
- of <tt>std::pair</tt>), it became also annoying to require another
- library for <tt>minmax_element</tt> which does not need it. Hence the
- separation into two header files.</p>
- <a name="no-fix">
- <h4><b>Your minmax suffers from the same problems as std::min and
- std::max.</b></h4>
- <p>I am aware of the problems with std::min and
- std::max, and all the debate that has been going on (please consult
- <a href="#Alexandrescu">Alexandrescu's paper</a> and the links therein). But I don't see the purpose of this
- library as fixing something that is part of the C++ standard. I humbly
- think it's beyond the scope of this library. Rather, I am
- following the way of the standard in simply providing one more function
- of the same family. If someone else wants to fix std::min, their fix
- would probably apply to boost::minmax as well.</p>
- </a>
- <h4><b>Why no <tt>min/max_element_if</tt>?</b></h4>
- <p>In a first version of the library, I proposed <tt>_if</tt> versions of
- all the algorithms (well, not all, because that would be too much).
- However, there is simply no reason to do so, and all the versions I had
- were just as fast implemented using the excellent
- <tt><boost/iterator_adaptors.hpp></tt> library. Namely, a call to
- <tt>min_element_if(first, last, pred)</tt> would be just as well
- implemented by:
- <pre>
- // equivalent to min_element_if(first, last, pred)
- min_element(boost::make_filter_iterator(first, last, pred),
- boost::make_filter_iterator(last, last, pred));
- </pre>
- Arguably, the <tt>min_element_if</tt> version is somewhat shorter, but
- the overhead of iterator adaptors is not large, and they get rid of a
- lot of code (think of all the combinations between first/last and
- doubling them with _if variants!).</p>
- <h4><b>Discussion: about std::max_element</b></h4>
- <p>This rationale is somewhat historical, but explains why there are all
- these <tt>first/last_min/max_element</tt> functions.</p>
- <p>The C++ standard mandates that <tt>std::min_element</tt> and <tt>std::max_element</tt>
- return the first instance of the smallest and largest elements (as opposed
- to, say, the last). This arbitrary choice has some consistency: In the
- case of v of type vector<int>, for instance, it is true that <tt>std::min_element(v.begin(),v.end(),std::less<int>())
- == std::max_element(v.begin(),v.end(),std::greater<int>())</tt>.
- <p>There is of course nothing wrong with this: it's simply a matter of
- choice. Yet another way to specify min_element and max_element is to define
- them as the first and the last elements if the range was stably sorted.
- (The <i>stable</i> sort is necessary to disambiguate between iterators
- that have the same value.) In that case, min should return the first instance
- and max should return the last. Then, both functions are related by
- <tt>reverse_iterator(std::first_min_element(v.begin(),v.end(),std::less<int>()))
- ==
- std::last_max_element(v.rbegin(),v.rend(),std::greater<int>())</tt>.
- This definition is subtly different from the previous one.</p>
- <p>The definition problem surfaces when one tries to design a minmax_element,
- using the procedure proposed in (Cormen, Leiserson, Rivest: "Introduction
- to Algorithms", section 9.1). It <i>should</i> be possible to derive an
- algorithm using only <tt>3n/2</tt> comparisons if <tt>[first,last) </tt>has
- <tt>n</tt>
- elements, but if one tries to write a function called <tt>first_min_first_max_element()</tt>
- which returns both <tt>std::min_element</tt> and <tt>std::max_element</tt>
- in a pair, the trivial implementation does not work. The problem, rather
- subtly, is about equal elements: I had to think for a while to find a
- way to perform only three
- comparisons per pair and return the first min and first max elements.
- For a long time, it seemed any
- attempts at doing so would consume four comparisons per pair in the worst
- case. This implementation achieves three.</p>
- <p>It is not possible (or even desirable) to change the meaning of
- <tt>max_element</tt>,
- but it is still beneficial to provide a function called <tt>minmax_element</tt>,
- which returns a pair of <tt>min_element</tt> and <tt>max_element</tt>.
- Although it is easy enough to call <tt>min_element</tt> and <tt>max_element</tt>,
- this performs
- <tt>2(n-1)</tt> comparisons, and necessitates <b>two</b>
- passes over the input. In contrast,
- <tt>minmax_element</tt> will perform
- the fewer comparisons and perform a <b>single</b> pass over the input.
- The savings can be significant when the iterator type is not a raw pointer,
- or even is just a model of the InputIterator concept (although in that
- case the interface would have to be
- changed, as the return type could not be copied, so one could e.g.
- return a value).</p>
- <p>In order to benefit from all the variants of the algorithm, I propose
- to introduce both <tt>first_min_element</tt> and <tt>last_min_element</tt>,
- and their counterparts <tt>first_max_element</tt> and <tt>last_max_element</tt>.
- Then I also propose all the variants algorithms: <tt>first_min_last_max_element</tt>
- and <tt>last_min_first_max_element</tt>, which perform only at most <tt>3n/2</tt>
- comparisons, and only a single pass on the input. In fact, it can be proven
- that computing minmax requires at least <tt>3(n/2)-2</tt> comparisons in
- any instance of the problem (Cormen, Leiserson, Rivest, 2nd edition, section
- 9.1). The implementation I give does not perform unnecessary comparisons
- (whose result could have been computed by transitivity from previous
- comparisons).</p>
- <p>It appears that <tt>first_min_last_max_element</tt> may be just a tad
- slower than
- <tt>first_min_element</tt> alone, still much less than <tt>first_min_element</tt>
- and
- <tt>last_max_element</tt> called separately. <a href="#Note2">[2]</a>
- <h4><b>Why algorithms and not accumulators?</b></h4>
- <p>The minmax algorithms are useful in computing the extent of a range.
- In computer graphics, we need a bounding box of a set of objects.
- In that case the need for a single pass is even more stringent
- as all three directions must be done at once. Food for thoughts: there
- is matter for a nice generic programming library with stackable <tt>update_min</tt>
- and <tt>update_max</tt> function objects which store a reference to the
- <tt>min_result</tt>and
- <tt>max_result</tt> variables, in conjunction with the <tt>for_each</tt>
- algorithm).</p>
- <p>I believe many standard sequential algorithms could be reformulated
- with accumulators (and many others, such as in statistics, expectation /
- variance / etc.). It seems that there is room for another library, but I
- do not see it competing with minmax, rather extending several algorithms
- (including minmax) to the accumulator framework. However, I felt it is
- beyond the scope of this library to provide such accumulators.</p>
- <a NAME="no-policy">
- <h4><b>This first/last is a perfect application for a policy-based
- design.</b></h4>
- <p>True, and I could have gone that way, with the default policy for
- <tt>min_element</tt> and <tt>max_element</tt> to pick the first
- occurence of the result. This would have thinned the number of
- combinations of the minmax_element variants. But it would also have
- meant to change the interface of <tt>boost::minmax_element</tt>.
- One of the goals of the <tt>minmax_element</tt> algorithm is its
- eventual addition to the C++ standard, in connection with
- <tt>std::min_element</tt> and <tt>std::max_element</tt>
- (and I feel that it would be quite natural
- given the shortness of the implementation, and the not quite trivial
- detail which is needed to get it right). So changing the interface by
- adding policies would have meant unfortunately to depart from the
- standard and created an obstacle towards that goal. Besides, the code
- remains rather readable and simple without policies. So I am quite happy
- to keep it like this.
- </p></a>
- </a>
- <a name="perf">
- <a href="doc/minmax_benchs.html"><h3><b>About performance</b></h3></a>
- </a>
- <a name="acks">
- <h3>
- Acknowledgements</h3>
- <a name="Alexandrescu">
- <a href="http://www.drdobbs.com/generic-min-and-max-redivivus/184403774">Generic: Min and Max Redivivus, by Andrei Alexandrescu</a>
- Dr. Dobbs, April 2001
- <p>My students in CS903 (Polytechnic Univ., <a href="http://photon.poly.edu/~hbr/cs903/">http://photon.poly.edu/~hbr/cs903/</a>)
- who had <tt>minmax_element</tt> as an assignment helped clarify the issues,
- and also come up with the optimum number of comparisons for <tt>first_min_last_max_element</tt>.
- The identification of the issue surrounding <tt>max_element</tt> is solely
- my own.
- <p>One <tt>minmax_element</tt> implementation, which performs <tt>3(n/2)+O(log
- n)</tt> comparisons on the average when the elements are <tt>random_shuffle</tt>d,
- was suggested by my student Marc Glisse. The current one, which performs
- <tt>3(n/2)+1</tt>
- comparisons in the worst case, was suggested by John Iacono.<p>
- <p>Finally, Matthew Wilson and Jeremy Siek contributed pre-review
- comments, while Gennadiy Rozental, John Maddock, Craig Henderson, Gary
- Powell participated in the review of the library, managed by Thomas
- Witt. In particular, Gennadiy suggested a factorization of the code;
- while I haven't followed it all the way, his suggestions do make the
- code more readable and still work with older compilers.
- Late after the review, as I finally scrounged to add the library for a
- release, Eric Niebler noted the bad behavior of <tt>std::pair</tt> for
- <tt>minmax</tt> and suggested to use Boost.tuple instead.
- All my thanks for the excellent advice and reviews from all.
- <h3>
- See also</h3>
- <tt><a href="https://www.boost.org/sgi/stl/min.html">min</a></tt>, <tt><a href="https://www.boost.org/sgi/stl/max.html">max</a></tt>,
- <tt><a href="https://www.boost.org/sgi/stl/min_element.html">min_element</a></tt>,
- <tt><a href="https://www.boost.org/sgi/stl/max_element.html">max_element</a></tt>,
- <tt><a href="https://www.boost.org/sgi/stl/LessThanComparable.html">LessThan
- Comparable</a></tt>,
- <tt><a href="https://www.boost.org/sgi/stl/sort.html">sort</a></tt>,
- <tt><a href="https://www.boost.org/sgi/stl/nth_element.html">nth_element</a></tt>
- .
- <hr SIZE="6">
- <br>Last modified 2012-12-10
- <p><font face="Arial,Helvetica"><font size=-1>© Copyright Hervé
- Brönnimann, Polytechnic University, 2002--2004.
- Use, modification, and distribution is subject to the Boost Software
- License, Version 1.0. (See accompanying file <a href="../../../LICENSE_1_0.txt">License_1_0.txt</a> or copy at
- <a href="http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)
- </font></font>
- </body>
- </html>
|