160

C++ Templates - The Complete Guide, 2nd Edition introduces the max template: 

template<typename T>
T max (T a, T b)
{
  // if b < a then yield a else yield b
  return  b < a ? a : b;
}

And it explains using “b < a ? a : b” instead of “a < b ? b : a”:

Note that the max() template according to [StepanovNotes] intentionally returns “b < a ? a : b” instead of “a < b ? b : a” to ensure that the function behaves correctly even if the two values are equivalent but not equal.

How to understand "even if the two values are equivalent but not equal."? “a < b ? b : a” seems have the same result for me.

Nan Xiao
  • 16,671
  • 18
  • 103
  • 164
  • 9
    Looks wrong to me... Both answers are "correct", but if `a` and `b` are **equivalent**, then `!(a < b) && !(b < a)` is true, so `a < b` and `b < a` are both false, so in `b < a ? a : b`, `b` is returned, which is not what you want... You want `a < b ? b : a`. – Holt Jun 13 '18 at 10:03
  • 1
    You can often distinguish between equivalent `a` and `b` with `std::addressof` et. al. – Caleth Jun 13 '18 at 10:14
  • 14
    If you do `a = max(a, b);` (repeatedly) you might not want to replace `a` unnecessarily. – Bo Persson Jun 13 '18 at 10:15
  • 2
    BTW this template should take parameters by const-references and return them by const-reference, otherwise, you are doing a bunch of useless copies (and you are going to override `a` with a copy of `a`). – Holt Jun 13 '18 at 10:26
  • 3
    @Caleth: The canonical type which has both equivalence and equality is the CaseInsensitiveString. For that type, neither a – MSalters Jun 13 '18 at 10:40
  • @MSalters ah, I was thinking of `std::max`, didn't notice the by-value template – Caleth Jun 13 '18 at 11:13
  • 2
    You can refer to [Stepano'v Notes on Programming for more details](https://twitter.com/shafikyaghmour/status/987917106724286464) I tweeted about this after reading that because the explanation was not detailed enough. – Shafik Yaghmour Jun 13 '18 at 15:12
  • 2
    Hilarious. How many c++ programmers does it take to write the `max` function? Maybe they should make two functions `maxFirstIfEqual` and `maxSecondIfEqual` just to make it even more laughable. – Atomosk Jun 20 '18 at 02:24

3 Answers3

154

std::max(a, b) is indeed specified to return a when the two are equivalent.

That's considered a mistake by Stepanov and others because it breaks the useful property that given a and b, you can always sort them with {min(a, b), max(a, b)}; for that, you'd want max(a, b) to return b when the arguments are equivalent.

T.C.
  • 133,968
  • 17
  • 288
  • 421
  • 49
    From that link "It is hard for me to blame people who do so: after all, they just follow the C++ standard specification of **max** written by me. It took me several years to see that I was mistaken." - wow! – Jack Aidley Jun 13 '18 at 12:11
  • 23
    can't you just do `{min(a, b), max(b, a)}`? – Captain Man Jun 13 '18 at 13:45
  • 12
    @CaptainMan: Yes, but it's still less obvious. I would argue that it makes logical sense that `max(a,b)` will return a if-and-only-if `min(a,b)` returns b, and _vice versa_ so that they are the reverse of each other and the (unordered) set `{min(a,b), max(a,b)}` is always equal to `{a,b}`. – Jack Aidley Jun 13 '18 at 13:57
  • @JackAidley you mentioned unordered, but I meant ordered because in the answer T.C. mentions "breaks the useful property that [...] you can always sort them with `{min(a, b), max(a, b)}`" – Captain Man Jun 13 '18 at 14:01
  • @CaptainMan Yes, I understood that. Do you not think the property I mentioned makes more sense than an implementation without? To me max(a, b) and min(a, b) should always return different answers. – Jack Aidley Jun 13 '18 at 15:10
  • 1
    @JackAidley Yeah, I think it's nice, but my original comment was coming from a place of uncertainty, not sarcasm :) Then I was trying to understand why you were mentioning unordered sets when the example was an ordered list. (I understand now you meant that the "the (unordered) set ***of*** {`min(a,b), max(a,b)}`") – Captain Man Jun 13 '18 at 16:27
  • 1
    @CaptainMan I'm sorry you understood my comment as thinking you were being sarcastic. That was not my intent, but rather to explain why the property is logical from another point of view. If you follow the link to the paper from Stephanov, you will see that he actually gives a different example than the one T.C. gave and the way I put it :) – Jack Aidley Jun 13 '18 at 17:00
  • Might add the word "stable", maybe? You can still sort (without the word "stable") them just fine if `std::max` is what it is -- if the two are equivalent, they're correctly sorted no matter which one comes first and which one comes last. – Damon Jun 13 '18 at 19:36
  • 1
    @Damon Either order is fine, making `a, b` into `a, a` isn't. – T.C. Jun 13 '18 at 20:29
  • 1
    @T.C. How is it not okay if `a` is equivalent to `b`? If they're not fully interchangeable, they shouldn't be equal. It sounds to me like the problem is with the design of the contents of `a` and `b`, not with `max` or `min`. – jpmc26 Jun 13 '18 at 20:41
  • 5
    @jpmc26: If one is e.g. sorting a list of events by time, one need not to care about whether the sorting operation is stable to care about having each event that appears exactly once in the input, likewise appear exactly once in the output. Certain operations (like finding and eliminating duplicated events) may require using a complete ordering, but in many other cases, it may be acceptable to list simultaneous events in arbitrary order, but not to duplicate or omit them. – supercat Jun 13 '18 at 21:14
  • 2
    @supercat Applying `min` and `max` to anything but the *timestamp* (the sort key) in that scenario makes no sense. The events (the objects) themselves shouldn't even be comparable if equality doesn't imply interchangeability. The only way `{min(a, b), max(a, b)}` makes *any* sense as a sort mechanism is if the objects are interchangeable. – jpmc26 Jun 13 '18 at 21:16
62

This answer explains why the given code is wrong from a C++ standard point-of-view, but it is out of context.

See @T.C.'s answer for a contextual explanation.

The standard defines std::max(a, b) as follows [alg.min.max] (emphasis is mine):

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

Requires: Type T is LessThanComparable (Table 18).

Returns: The larger value.

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

Equivalent here means that !(a < b) && !(b < a) is true [alg.sorting#7].

In particular, if a and b are equivalent, both a < b and b < a are false, so the value on the right of : will be returned in the conditional operator, so a has to be on the right, so:

a < b ? b : a

...seems to be the correct answer. This is the version used by libstdc++ and libc++.

So the information in your quote seems wrong according to the current standard, but the context in which it is defined might be different.

Community
  • 1
  • 1
Holt
  • 36,600
  • 7
  • 92
  • 139
  • 4
    [Godbolt link](https://godbolt.org/g/NRxiE5) that explains the issue (thanks @songyuanyao for the definition of `X`). – Holt Jun 13 '18 at 10:35
  • 1
    @JackAidley I've edited the answer to specify that the reasoning targets the current standard. – Holt Jun 13 '18 at 11:45
  • @codekaizer I was actually referring to *"If we define equiv(a, b) as !comp(a, b) && !comp(b, a)"*. I've changed the link to a better quote (3 lines below in the standard... ). – Holt Jun 13 '18 at 12:29
  • 1
    Surprised nobody has mentioned floating point, where `a – Peter Cordes Jun 13 '18 at 12:42
  • 1
    Also see [Stepanov's Notes on Programming](https://twitter.com/shafikyaghmour/status/987917106724286464) – Shafik Yaghmour Jun 13 '18 at 15:10
22

The point is which one should be returned when they are equivalent; std::max has to return a (i.e. the first argument) for this case.

If they are equivalent, returns a.

So a < b ? b : a should be used; on the other hand, b < a ? a : b; will return b incorrectly.

(As @Holt said, the quote seems opposite.)

"the two values are equivalent but not equal" means they have the same value when being compared, but they migth be different objects at some other aspects.

e.g.

struct X { int a; int b; };
bool operator< (X lhs, X rhs) { return lhs.a < rhs.a; }
X x1 {0, 1};
X x2 {0, 2};
auto x3 = std::max(x1, x2); // it's guaranteed that an X which cantains {0, 1} is returned
songyuanyao
  • 169,198
  • 16
  • 310
  • 405
  • 1
    Could you please elaborate on why `std::max(a, b)` has to return `a`, if `a` and `b` are equivalent? – JFMR Jun 13 '18 at 09:53
  • 4
    @ネロク - [It's just an arbitrary choice on the standard's part](https://timsong-cpp.github.io/cppwp/n4659/alg.min.max#11). Though it's a bit debatable if it's a good one. – StoryTeller - Unslander Monica Jun 13 '18 at 09:57
  • Is it just me or is this in contradiction with the question? If `a` and `b` are equivalent, then `!(a < b) && !(b < a)` is true, so `a < b` and `b < a` are false, so... ? – Holt Jun 13 '18 at 10:00
  • 2
    @ネロク I suppose the standard just wants to make it determine; when they're equivalent which one should be returned. – songyuanyao Jun 13 '18 at 10:02
  • 1
    thanks for refreshing my memory on why an object would be "equivalent" but not "equal". – Jeff Walker Jun 13 '18 at 16:13