Correct implementation of min

问题:

At time 0:43:15 in this Tech-Talk about D, The implementation of the min function is discussed. Concerns about "stability" and "extra shuffling (if values are equal)" when being used in some algorithm(s) is proposed as one of the reasons for the implementation shown.

Can anyone provide a real/practical use-case (or provide a more detailed explanation) where this specific implementation of min is "stable" (aka better) as opposed to its other possible implementation? Or is this just another example of alpha-geeks going a bit too far?

Recommended implementation:

template <class LHS, class RHS, class Return>
inline Return min(LHS& lhs, RHS& rhs)
{
   return (rhs < lhs) ? rhs : lhs;
}

Other possible implementation:

template <class LHS, class RHS, class Return>
inline Return min(LHS& lhs, RHS& rhs)
{
   return (lhs < rhs) ? lhs: rhs;
}

Proposal N2199 provides implementations that are based on the latter, please note that the proposal was not successful at this time.

Other relevant proposals relating to min/max are N1840, N2485 and N2551

回答1:

In this case, I'm pretty sure "stable" is referring to stable as it's applied in sorting -- i.e., that when/if two elements are equal, they stay sorted in the same order as they were to start with. To accomplish that, you want to return lhs when it's less than or equal to rhs -- but in C++ you (normally) want to do that using only operator<, without depending on having operator<=.

回答2:

In general case there is no advantage to one implementation over the other. If you're implementing min for a specific usage, it might make sense to choose one of the forms based on the data to which it will be applied to make the most of branch predictions.

If for most usage cases the expected minimum is rhs, choose the first implementation. If it's lhs, choose the second implementation.