Title
min/max/minmax requirements
Status
c++17
Section
[alg.min.max]
Submitter
Juan Soulie

Created on 2013-01-26.00:00:00 last changed 81 months ago

Messages

Date: 2015-04-02.21:06:18

Proposed resolution:

This wording is relative to N4296.

  1. Change [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.

Date: 2015-04-02.00:00:00

[ 2015-04-02 Library reflector vote ]

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

Date: 2015-03-30.00:00:00

[ 2015-03-30 Daniel comments ]

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

Date: 2015-03-29.19:02:30

[ 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.

Date: 2014-06-07.00:00:00

[ 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).

Date: 2013-01-26.00:00:00

[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 [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.

History
Date User Action Args
2017-07-30 20:15:43adminsetstatus: wp -> c++17
2015-05-22 18:31:21adminsetstatus: ready -> wp
2015-04-02 21:06:18adminsetmessages: + msg7309
2015-04-02 21:06:18adminsetstatus: open -> ready
2015-03-29 19:02:30adminsetmessages: + msg7269
2015-03-29 19:02:30adminsetmessages: + msg7268
2015-03-29 19:02:30adminsetstatus: new -> open
2014-06-07 13:29:36adminsetmessages: + msg7002
2014-06-07 13:29:36adminsetmessages: + msg7001
2013-01-26 00:00:00admincreate