[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

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

This archive was generated by hypermail 2.1.7 : 2017-02-16 18:50:14 UTC