Document number: N2199=07-0059

Howard E. Hinnant
2007-03-09

Improved min/max

Introduction

The current standard min and max have some deficiencies, namely:

This paper proposes new definitions of min and max which eliminate all of the listed deficiencies. min and max will be able to be assigned to if both arguments are non-const lvalues of the same type. It will not be possible to form a reference to a destructed rvalue. And the new min and max will interoperate with move-only types with the expected semantics.

Additionally this definition of min and max restricts mixed mode integral comparisons to those that are intrinsically safe. For example:

Proposed Wording

25.3.7 Minimum and maximum [alg.min.max]


template <class T, class U>
struct min_max_return {typedef implementation type;};

The struct min_max_return serves to define the return type of the min and max functions. The typedef type shall indicate the return type, except in certain cases outlined below where it is specified that the typedef shall not be present.


template<class T> const T& min(const T& a, const T& b);
template<class T, class Compare>
  const T& min(const T& a, const T& b, Compare comp);

template<class T, class U>
typename min_max_return<T&&, U&&>::type
min(T&& a, U&& b);
template<class T, class U, class Compare>
  typename min_max_return<T&&, U&&>::type
  min(T&& a, U&& b, Compare comp);

-1- Requires: The first signature requires Type T U is to be LessThanComparable (20.1.2) with type T. If the return type is not a reference type (see min_max_return) and the argument is an rvalue, the type of that argument must be MoveConstructible. Else if the return type is not a reference type and the argument is an lvalue, the type of that argument must be CopyConstructible.

-2- Returns: The smaller value. If b < a or comp(b, a) is true, returns b, else returns a.

-3- Remarks: Returns the first argument when the arguments are equivalent.


template<class T> const T& max(const T& a, const T& b);
template<class T, class Compare>
  const T& max(const T& a, const T& b, Compare comp);

template<class T, class U>
typename min_max_return<T&&, U&&>::type
max(T&& a, U&& b);
template<class T, class U, class Compare>
  typename min_max_return<T&&, U&&>::type
  max(T&& a, U&& b, Compare comp);

-4- Requires: The first signature requires Type T is to be LessThanComparable (20.1.2) with type U. If the return type is not a reference type (see min_max_return) and the argument is an rvalue, the type of that argument must be MoveConstructible. Else if the return type is not a reference type and the argument is an lvalue, the type of that argument must be CopyConstructible.

-5- Returns: The larger value. If a < b or comp(a, b) is true, returns b, else returns a.

-6- Remarks: Returns the first argument when the arguments are equivalent.

Reference Implementation

namespace detail
{

template <class T, bool make_const, bool make_volatile>
struct union_cv_helper;

template <class T>
struct union_cv_helper<T, false, false>
{
    typedef T type;
};

template <class T>
struct union_cv_helper<T, false, true>
{
    typedef volatile T type;
};

template <class T>
struct union_cv_helper<T, true, false>
{
    typedef const T type;
};

template <class T>
struct union_cv_helper<T, true, true>
{
    typedef const volatile T type;
};

}  // detail

template <class T, class U>
struct union_cv
{
    static const bool make_const = std::tr1::is_const<T>::value || std::tr1::is_const<U>::value;
    static const bool make_volatile = std::tr1::is_volatile<T>::value || std::tr1::is_volatile<U>::value;
    typedef typename std::tr1::remove_cv<T>::type Tr;
    typedef typename std::tr1::remove_cv<U>::type Ur;
    typedef typename detail::union_cv_helper<Tr, make_const, make_volatile>::type type;
};

template <class T, class U>
struct promote
{
    static T t;
    static U u;
    static bool b;
    typedef typename std::tr1::remove_cv<decltype(b ? t : u)>::type type;
};

namespace detail
{

template <class T, class Tr, class U, class Ur>
struct min_max_return_helper
{
    typedef typename promote<T&, U&>::type type;
};

template <class T, class Tr, class U>
struct min_max_return_helper<T, Tr, U, Tr>
{
    typedef typename union_cv<T, U>::type& type;
};

template <class T, T t, class U, U u>
struct safe_less_equal
{
    static const bool Tsigned = std::tr1::is_signed<T>::value;
    static const bool Usigned = std::tr1::is_signed<U>::value;
    static const bool Tneg = Tsigned && t < T(0);
    static const bool Uneg = Usigned && u < U(0);
    static const bool value = Tneg == Uneg ? t <= u : Tneg;
};

template <class T>
struct int_min
{
    static const T value = std::tr1::is_signed<T>::value ? T(T(1) << std::numeric_limits<T>::digits) : T(0);
};

template <class T>
struct int_max
{
    static const T value = T(~int_min<T>::value);
};

template <class T, class U, bool = std::tr1::is_integral<T>::value && std::tr1::is_integral<U>::value>
struct safe_compare_imp
{
    typedef typename promote<T, U>::type R;
    static const R Rmin = int_min<R>::value;
    static const R Rmax = int_max<R>::value;

    static const T Tmin = int_min<T>::value;
    static const T Tmax = int_max<T>::value;

    static const U Umin = int_min<U>::value;
    static const U Umax = int_max<U>::value;

    static const bool value = safe_less_equal<R, Rmin, T, Tmin>::value &&
                              safe_less_equal<R, Rmin, U, Umin>::value &&
                              safe_less_equal<T, Tmax, R, Rmax>::value &&
                              safe_less_equal<U, Umax, R, Rmax>::value;
};

template <class T, class U>
struct safe_compare_imp<T, U, false>
{
    static const bool value = true;
};

template <class T>
struct safe_compare_imp<T, T, true>
{
    static const bool value = true;
};

template <class T>
struct safe_compare_imp<T, T, false>
{
    static const bool value = true;
};

template <class T, class U>
struct safe_compare
{
private:
    typedef typename std::tr1::remove_cv<typename std::tr1::remove_reference<T>::type>::type Tr;
    typedef typename std::tr1::remove_cv<typename std::tr1::remove_reference<U>::type>::type Ur;
public:
    static const bool value = detail::safe_compare_imp<Tr, Ur>::value;
};

}  // detail

template <class T, class U, bool = detail::safe_compare<T, U>::value>
struct min_max_return {};

template <class T, class U>
struct min_max_return<T&&, U&&, true>
{
    typedef typename promote<T&&, U&&>::type type;
};

template <class T, class U>
struct min_max_return<T&&, U&, true>
{
    typedef typename promote<T&&, U&>::type type;
};

template <class T, class U>
struct min_max_return<T&, U&&, true>
{
    typedef typename promote<T&, U&&>::type type;
};

template <class T, class U>
struct min_max_return<T&, U&, true>
{
private:
    typedef typename std::tr1::remove_cv<T>::type Tr;
    typedef typename std::tr1::remove_cv<U>::type Ur;
public:
    typedef typename detail::min_max_return_helper<T, Tr, U, Ur>::type type;
};

template <class T, class U>
inline
typename min_max_return<T&&, U&&>::type
min(T&& a, U&& b)
{
    if (b < a)
        return std::forward<U>(b);
    return std::forward<T>(a);
}

template <class T, class U, class Compare>
inline
typename min_max_return<T&&, U&&>::type
min(T&& a, U&& b, Compare comp)
{
    if (comp(b, a))
        return std::forward<U>(b);
    return std::forward<T>(a);
}

template <class T, class U>
inline
typename min_max_return<T&&, U&&>::type
max(T&& a, U&& b)
{
    if (a < b)
        return std::forward<U>(b);
    return std::forward<T>(a);
}

template <class T, class U, class Compare>
inline
typename min_max_return<T&&, U&&>::type
max(T&& a, U&& b, Compare comp)
{
    if (comp(a, b))
        return std::forward<U>(b);
    return std::forward<T>(a);
}