[Boost-bugs] [Boost C++ Libraries] #9449: Boost.MPL min_element bug for equal elements (fix included)

Subject: [Boost-bugs] [Boost C++ Libraries] #9449: Boost.MPL min_element bug for equal elements (fix included)
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2013-12-01 22:24:50

#9449: Boost.MPL min_element bug for equal elements (fix included)
-------------------------------------------+-----------------------
 Reporter:  Rein Halbersma <rhalbersma@…>  |      Owner:  agurtovoy
     Type:  Bugs                           |     Status:  new
Milestone:  To Be Determined               |  Component:  mpl
  Version:  Boost 1.55.0                   |   Severity:  Problem
 Keywords:  min_element, bug               |
-------------------------------------------+-----------------------
 For equal elements, Boost.MPL `min_element` with a predicate `Pred` does
 not satisfy its own requirements of returning the '''first''' element `i`
 that satifies `!Pred(j, i)` for all `j`. It turns out that `min_element`
 is implemented in terms of `max_element` with the negated predicate
 `not_<Pred>`. In turn, `max_element` with its own predicate `Pred` is
 required to (and in fact does) return the first element `i` that satisfies
 `!Pred(i, j)`.

 It is straightforward to see that negating the predicate is a bug. The
 current implementation of `min_element` has `less` as its default
 predicate, and subsequently calls `max_element` with `greater_equal`,
 whereas the requirements indicate that it should use `greater`. This
 results in `min_element` returning the '''last''' element of the sequence,
 rather than the first.

 To get the required semantics, users currently have to supply `less_equal`
 to `min_element` as a workaround. The proper fix would be to implement
 `min_element` by calling `max_element` with the arguments for the
 predicate reversed: `lambda<Pred, _2, _1>`.

 See below for a short example that displays the problem and implements the
 fix. The program sets up a `vector` of three equal elements. Both
 `min_element` and `max_element` are specified to return an iterator to the
 first (index 0) element. Instead, `min_element` returns an iterator to the
 last (index 2) element. Both the redefined predicate work-around and the
 reimplementation of `min_element` fix the problem. The example can be run
 from http://coliru.stacked-crooked.com/a/c517d85cbc0aee66


 {{{#!c++
 #include <boost/mpl/begin_end.hpp>
 #include <boost/mpl/distance.hpp>
 #include <boost/mpl/lambda.hpp>
 #include <boost/mpl/less_equal.hpp>
 #include <boost/mpl/max_element.hpp>
 #include <boost/mpl/min_element.hpp>
 #include <boost/mpl/placeholders.hpp>
 #include <boost/mpl/vector_c.hpp>
 #include <iostream>

 using namespace boost::mpl;

 template<class Sequence, class Predicate = less<_1,_2>>
 struct stable_min_element
 :
     // mpl::min_element uses max_element<Sequence, not_<Predicate>>
     max_element<Sequence, lambda<Predicate, _2, _1>>
 {};

 int main()
 {
     using V = vector_c<int, 1, 1, 1>;

     using MinIdx   = distance<begin<V>::type, min_element<V>::type>;
     using LEMinIdx = distance<begin<V>::type, min_element<V,
 less_equal<_1, _2> >::type>;
     using SMinIdx  = distance<begin<V>::type,
 stable_min_element<V>::type>;
     using MaxIdx   = distance<begin<V>::type, max_element<V>::type>;

     std::cout << MinIdx::value;     // ERROR: prints 2 instead of 0
     std::cout << LEMinIdx::value;   // 0
     std::cout << SMinIdx::value;    // 0
     std::cout << MaxIdx::value;     // 0
 }
 }}}

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/9449>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.