id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
9449,Boost.MPL min_element bug for equal elements (fix included),Rein Halbersma <rhalbersma@…>,Aleksey Gurtovoy,"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
}
}}}",Bugs,new,To Be Determined,mpl,Boost 1.55.0,Problem,,"min_element, bug",