2239. min/max/minmax requirements

Section: 26.8.9 [alg.min.max] Status: C++17 Submitter: Juan Soulie Opened: 2013-01-26 Last modified: 2017-07-30

Priority: 3

View other active issues in [alg.min.max].

View all other issues in [alg.min.max].

View all issues with C++17 status.

Discussion:

26.8.9 [alg.min.max] requires type T in min, max, and minmax to be LessThanComparable, but I don't believe this should be required for the versions that take a Compare argument.

Paragraphs 1 to 4 of 26.8 [alg.sorting] should apply anyway, although I'm not sure about Compare being required to induce a strict weak ordering here.

Further, min and max also lack formal complexity guarantees.

[2014-06-07 Daniel comments and provides wording]

Certainly, the functions with Compare should not impose LessThanComparable requirements.

In regard to the question whether a strict weak ordering should be required as implied by the Compare requirements, I would like to point out that this is requirement is in fact needed, because the specification of the normative Remarks elements (e.g. "Returns the first argument when the arguments are equivalent.") do depend on the existence of a equivalence relation that can be relied on and this is also consistent with the same strict weak ordering requirement that is indirectly imposed by the LessThanComparable requirement set for functions referring to operator< (Let me note that the very same StrictWeakOrder language concept had intentionally been required for similar reasons during "concept-time" in N2914).

[2015-02 Cologne]

JY: We have library-wide requirements that Comp induce a strict weak ordering.

JY/MC: The un-marked-up "Complexity" (p16) is wrong. DK: I'll fix that.

DK will update the wording for Lenexa.

[2015-03-30 Daniel comments]

The Complexity element of p16 is correct, but some others involving initializer_list arguments are wrong.

[2015-04-02 Library reflector vote]

The issue has been identified as Tentatively Ready based on six votes in favour.

Proposed resolution:

This wording is relative to N4296.

1. Change 26.8.9 [alg.min.max] as indicated:

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

   -1- Requires: For the first form, type T shall beType T is LessThanComparable (Table 18).

   -2- Returns: The smaller value.

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

   -?- Complexity: Exactly one comparison.

   template<class T>
     constexpr T min(initializer_list<T> t);
   template<class T, class Compare>
     constexpr T min(initializer_list<T> t, Compare comp);
   

   -4- Requires: T is LessThanComparable andshall be CopyConstructible and t.size() > 0. For the first form, type T shall be LessThanComparable.

   -5- Returns: […]

   -6- Remarks: […]

   -?- Complexity: Exactly t.size() - 1 comparisons.

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

   -7- Requires: For the first form, type T shall beType T is LessThanComparable (Table 18).

   -8- Returns: […]

   -9- Remarks: […]

   -?- Complexity: Exactly one comparison.

   template<class T>
     constexpr T max(initializer_list<T> t);
   template<class T, class Compare>
     constexpr T max(initializer_list<T> t, Compare comp);
   

   -10- Requires: T is LessThanComparable andshall be CopyConstructible and t.size() > 0. For the first form, type T shall be LessThanComparable.

   -11- Returns: […]

   -12- Remarks: […]

   -?- Complexity: Exactly t.size() - 1 comparisons.

   template<class T> constexpr pair<const T&, const T&> minmax(const T& a, const T& b);
   template<class T, class Compare>
     constexpr pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp);
   

   -13- Requires: For the first form, tType T shall be LessThanComparable (Table 18).

   -14- Returns: […]

   -15- Remarks: […]

   -16- Complexity: Exactly one comparison.

   template<class T>
     constexpr pair<T, T> minmax(initializer_list<T> t);
   template<class T, class Compare>
     constexpr pair<T, T> minmax(initializer_list<T> t, Compare comp);
   

   -17- Requires: T is LessThanComparable andshall be CopyConstructible and t.size() > 0. For the first form, type T shall be LessThanComparable.

   -18- Returns: […]

   -19- Remarks: […]

   -20- Complexity: At most (3/2) * t.size() applications of the corresponding predicate.