Boost.MPL min_element bug for equal elements (fix included)

[Rein Halbersma <rhalbersma@…>]

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, 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
}

[Rein Halbersma <rhalbersma@…>]

Sorry, the bug report contained bad code: lambda<Predicate, _2, _1> (not sure why this even compiled since lambda only takes 2 arguments). The (now hopefully) correct fix should be to write bind<typename lambda<Predicate>::type, _2, _1> instead.

Because max_element takes a lambda expression (metafunction class or placeholder expression), and because bind takes only a metafunction class, we need lambda<Predicate>::type to convert a placeholder expression Predicate into a metafunction class.

Corresponding modified test program at: ​http://coliru.stacked-crooked.com/a/f8658230325c9dd8

#include <boost/mpl/begin_end.hpp>
#include <boost/mpl/bind.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 takes a lambda expression (metafunction class or placeholder expression)
    // bind takes only a metafunction class, so we need lambda<Predicate>::type 
    // to convert a placeholder expression Predicate into a metafunction class
    max_element<Sequence, bind<typename lambda<Predicate>::type, _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
}