This article is inspired by Walter E Brown's talk at the Italian C++ Conference 2021: Extrema: Correctly calculating min and max.
Walter brought up several issues with these algorithms starting from the problem of comparing different types to the question of how to pass efficiently parameters, but I only want to focus on one possible issue.
Let's have a look at a simplistic implementation of min and max in C++20 style that he shared:
auto min(auto left, auto right) {
return left < right ? left : right;
}
auto max(auto left, auto right) {
return right < left ? left : right;
}
So what's the problem?
What happens if left == right?
When left and right are equal both min and max would return the same. That is right.
But is that right?
According to Walter, that is not right. He raised his points, but they didn't find them interesting enough in the Committee in 2014.
They are definitely interesting enough to discuss here. I think he unveils some points we might not think about otherwise.
Some opposed his idea because it should not matter which one is returned, because after all if left == right, the values should be indistinguishable.
That is not necessarily the case.
He comes with an example of a student class:
struct Student {
std::string name;
int id;
inline static int registrar = 0;
Student(const std::string& iName):
name(iName), id(registrar++) {}
friend bool operator<(const Student& lhs,
const Student& rhs) {
return lhs.name < rhs.name;
}
};
In this case, we can observe that if two students have the same name - which is not impossible - the objects representing them are not indistinguishable. They do have distinct ids.
Yet, both min and max will return, right - according to the implementation that Walter shared.
We might argue that if we don't want that, we should implement the comparison operators in a different way. We should, in fact, make the Student::id part of the comparison operators and we wouldn't have this problem.
I have a feeling that if we need these logical operators and we are afraid that two objects might be evaluated to be equal while they are not indistinguishable, we should modify the logical operators.
Since C++20, we can use the spaceship operator to automatically define all the comparison operators.
In the case of the Student class, it would look like this:
auto operator<=>(const Student&) const = default;
If it's possible for the compiler to generate the operators, they will take into account "all base classes left to right and all non-static members of the class in their declaration order".
This means that Student::id will be taken into account, hence to have two indistinguishable objects requires having two objects with the same values in each field. Then it should really not matter which one is returned.
You might argue, that logically we cannot do that in all cases. You might be right, you might come up with such a case, but I think this was the main reason while Walter's complaints were not taken into account.
Or were they?
Let's have a look at the MSVCC implementation.
Here is a simplified excerpt.
template <class _Ty>
_NODISCARD _Post_equal_to_(_Left < _Right ? _Right : _Left) constexpr const _Ty& //
(max) (const _Ty& _Left, const _Ty& _Right) noexcept(noexcept(_Left < _Right)) /* strengthened */ {
// return larger of _Left and _Right
return _Left < _Right ? _Right : _Left;
}
template <class _Ty>
_NODISCARD _Post_equal_to_(_Right < _Left ? _Right : _Left) constexpr const _Ty& //
(min) (const _Ty& _Left, const _Ty& _Right) noexcept(noexcept(_Right < _Left)) /* strengthened */ {
// return smaller of _Left and _Right
return _Right < _Left ? _Right : _Left;
}
In case _Left == _Right, max returns _Left, and min returns also _Left.
Let's look at clang too:
template <class _Tp, class _Compare>
_LIBCPP_NODISCARD_EXT inline
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
const _Tp&
min(const _Tp& __a, const _Tp& __b, _Compare __comp)
{
return __comp(__b, __a) ? __b : __a;
}
template <class _Tp, class _Compare>
_LIBCPP_NODISCARD_EXT inline
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
const _Tp&
max(const _Tp& __a, const _Tp& __b, _Compare __comp)
{
return __comp(__a, __b) ? __b : __a;
}
It's essentially the same, but in this case, __a is returned for the case when the elements equal which was called _Left in MS.
So yes, both for clang and MSVCC the returned value is the same for min and max if the inputs are equal. The only difference is that one returns the first input, the other the second. Gcc acts like clang, it returns the first, the lefthand-side input.
It would interesting to know what is the reason of Microsoft having chosen the other value.
But it doesn't change the fact that both are strange. Since Walter raised the point at the Committee, others also called this a bug, for example Sean Paretn at C++Now.
If you are really bothered by this, and you'd expect that min return the first item and max the second, you can use std::minmax since C++11.
It either takes two elements or a list of items, but in our case only the case of two items is interesting.
std::minmax returns a pair where the first item is a const reference to the minimal element and the second is the max. In case the two inputs are equal, the first item is the first input, the second is the max.
Yes, this means that with min and max you cannot model minmax.
At least we have a workaround.
Conclusion
In his recent talk, Walter E Brown shared his view that it's incorrect that both std::min and std::max returns the same value in case its two inputs are equal.
If that matters to you, you have different workarounds. You can manually implement min and max in a way that you like. You can use minmax as well, or you can implement the comparison operator in a way that two values are indistinguishable in case they are equal.
Let me know if you faced this issue in your code.
Connect deeper
If you liked this article, please
- hit on the like button,
- subscribe to my newsletter
- and let's connect on Twitter!
Top comments (4)
This was interesting, thanks! I found the following series of blog posts enlightening on the mathematical basis of current C++ implementations:
foonathan.net/2018/06/equivalence-...
In particular Jonathan clearly describes the basis on which types in C++ can legitimately define an equality operator, and by extension a comparison operator (importantly for me, not like the weaker equivalence used in the
Studentexample above). I particularly like his reference to the 'rule of least surprise', and his closing comment:Thanks, I'm going to check it out!
Great article! Thanks!
Thanks for your comment!