5

cppreferenceによると：

不等式比較（<、>）では、最初の要素が最初に比較され、不等式比較がそれらに当てはまらない場合にのみ、2番目の要素が比較されます。

これは次のように変換されます。

return ((a.first < b.first) || (!(b.first < a.first) && (a.second < b.second)));

私の質問は、なぜそれがそれほど直感的でないのですか？その背後にある理由は何ですか？そして、この推論が正しい答えにつながる例はありますか？

実装は単純に次のようになると思いました。

return a.first < b.first && a.second < b.second
4

3 に答える 3

12

この種の比較は辞書式順序と呼ばれ、2つの異なる順序を1つに組み合わせるより自然な方法の1つです。

C ++で要求される順序付けは、厳密な弱順序付けと呼ばれます。これは、次のことが当てはまるはずであることを意味します。

  • 非反射性： x<xは常にfalseです。
  • 推移性： x<yおよびy<zの場合、x<z。
  • 反対称： x <yの場合、y<xは常にfalseです。
  • 同等性の推移性：xとyが比較できない場合、yとzが比較できない場合、xとzは比較できません。

これらのプロパティは、オブジェクトのリストを取得して、並べ替えられた昇順で並べ替えることができることを保証するために必要なものです。これは、それらで使用std::sortしたり、に保存したりできることを意味しますstd::set。

少しの数学で、2つの異なる厳密な弱順序がある場合、それらを組み合わせることによって得られる辞書式順序も厳密な弱順序であることを証明できますstd::pair。辞書式順序は、厳密な弱順序を組み合わせて新しい厳密な弱順序を作成できる数少ない方法の1つです。

ただし、提案した順序は厳密な弱順序ではなく、特定の仮定が破られる原因になります。特に、（0、5）、（3、3）、および（1、6）のペアを検討してください。その場合、（0、5）は（3、3）と比較できず、（3、3）は（1、6）と比較できません。ただし、実際には（0、5）<（1、6）であり、これは等価性の推移性の規則に違反します。その結果、同等性が推移的であると想定する多くの並べ替えアルゴリズム（ほとんどの主要な並べ替えアルゴリズムを含む）は、範囲で正しく機能しません。つまり、正しくstd::sort動作しない可能性があります。std::setまた、これらをに保存できなかったことも意味します。std::setすべてをある種のソートされた順序（通常は平衡二分探索木）で内部的に格納すると、完全に間違った結果が得られる可能性があります。

お役に立てれば！

于 2012-01-19T23:04:09.450 に答える
6

a.firstが未満の場合b.first、ペアはすでに少なくなっています。2番目の部分を比較する理由はありません。名前が最初に最初の文字でソートされるのと同じように、ペアは暗黙的に最初に最初の部分でソートされます。「Apple」は「Zebra」の前にあります。「A」は「Z」の前にあるため、「p」と「e」はまったく比較されません。

したがって、の場合a.first < b.firstは完了です。ただし、そうでない場合は、完了していません。a未満にすることができる別の方法がありますb。そうb.first < a.firstでない場合は、そしてa.second < b.second。

例えは「ゼブラ」と「ザイマン」です。「Z」は「Z」以上ですが、「e」は「y」よりも小さいため、最初の値は2番目の値よりも小さくなります。

次のようにコーディングされていることがあります。

bool operator<(const foo& a, const foo& b) {
 if (a.first < b.first) return true;
 if (a.first > b.first) return false;
 return (a.second < b.second);
}

これは直感的に理解しやすいと思いますが、ロジックは同じです。

于 2012-01-19T23:03:55.357 に答える
4

直感性は見る人の目にあります。私は実際にそれを非常に直感的に感じています。

他のシーケンスを比較するときと同じように機能します。たとえば、文字列"az"は前"ba"に来ると言うでしょう？しかし、あなたは持っていません'a' < 'b' && 'z' < 'a'！同じ推論がペアにも適用されます。それはより直感的であるだけでなく、そのような関係のすべての望ましい特性を維持します。

于 2012-01-19T23:04:43.867 に答える