c++ - min の正しい実装

Question

D に関するこのTech-Talk の時間 0:43:15 では、 min 関数の実装について説明しています。一部のアルゴリズムで使用される場合の「安定性」と「余分なシャッフル (値が等しい場合)」に関する懸念は、示されている実装の理由の 1 つとして提案されています。

min のこの特定の実装が、他の可能な実装とは対照的に「安定」(別名、より良い) である、実際の/実用的なユースケースを提供する (またはより詳細な説明を提供する) ことはできますか? それとも、これはアルファオタクが行き過ぎた例の 1 つにすぎないのでしょうか?

推奨される実装:

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

他の可能な実装:

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

提案N2199は後者に基づく実装を提供しますが、現時点では提案が成功していないことに注意してください。

最小/最大に関連するその他の関連する提案は、 N1840、N2485、およびN2551 です。

Answer 1

この場合、「安定」とは、並べ替えに適用される安定性を指していると確信しています。つまり、2つの要素が等しい場合、最初と同じ順序で並べ替えられたままになります。lhsこれを実現するには、以下の場合に戻りたいと考えていますが、C ++では、（通常は）を使用せずに、rhsのみを使用してこれを実行したいと考えています。operator<operator<=

Answer 2

一般に、ある実装が他の実装に勝る利点はありません。特定の用途のために実装している場合はmin、分岐予測を最大限に活用するために、適用されるデータに基づいてフォームの 1 つを選択することが理にかなっている場合があります。

ほとんどの使用例で予想される最小値が である場合はrhs、最初の実装を選択してください。の場合lhsは、2 番目の実装を選択します。