9

C ++ / STLでは、より小さい演算子のみを使用してソートが行われます。並べ替えアルゴリズムが実際にどのように実装されているかはわかりませんが、他の操作は暗黙的に作成されていると思います。

a > b *equals* b < a == true
a == b *equals* !(a < b) && !(b < a)

たとえばJavaのようなtrivalue*比較関数を使用する場合と比較して、これはパフォーマンスに優れているのでしょうか、それともこの設計上の決定がなされたのでしょうか。

私の仮定では、3値比較関数はそれ自体でこれらの比較を実装する必要があり、同じパフォーマンスが得られます。

** 3値比較関数とは、以下、等しい、およびより大きい場合に-1、0、および1を返す比較関数を意味します*

更新： 宇宙船の<=>オペレーターはC ++ 20で登場するようですので、委員会は明らかに、のみを使用することの欠点があると考えましたoperator<。

4

3 に答える 3

11

ある意味で他の2つは暗黙的ですが、より正確には、比較ソートは実際には3値のコンパレータを必要とせず、C ++のソートは、最小化するために1つを使用しない方法で実装されます。コンパレータに必要な動作。

std :: sortが次のようなものを定義して排他的に使用するのは間違っているでしょう：

template <typename T, typename Cmp>
int get_tri_value(const T &a, const T &b, Cmp lessthan) {
    if (lessthan(a,b)) return -1;
    if (lessthan(b,a)) return 1;
    return 0;
}

...への呼び出しの数に関して非効率的なアルゴリズムになってしまうためですlessthan。アルゴリズムが1リターンと0リターンの違いで何の役にも立たない場合は、比較を無駄にしています。

C ++は、「厳密な弱順序」を指します。<が厳密な弱順序である場合、および、は必ずしもそれに続く!(a < b) && !(b < a)とは限りません。それらは順序付けの「同じ場所」にあり、同値関係です。したがって、オブジェクトの順序等価クラスに必要なコンパレータは、全順序を提供しません。a == b!(a < b) && !(b < a)sort

それが作る唯一の違いは、あなたがいつ言うかです!(a < b)。厳密な全順序については、b <= a「以下」と読み替えてください。b <= a厳密な弱順序の場合、これを意味するように定義しb < a || b == aて、これを真にすることはできません。C ++はこれについて衒学者であり、演算子のオーバーロードを可能にするため、演算子をオーバーロードする人々は、演算子の関係に関して期待できることをコードのユーザーに伝えるために専門用語を必要とするため、それはほとんど必要です。Javaは、コンパレータとhashCodeがequalsと一致していることについて話しますが、これが必要なすべてです。C ++は、<、>、==、<=、> =、割り当ての事後条件などを処理する必要があります。

C ++は、APIでこれに対して非常に純粋数学的なアプローチを採用しているため、すべてが単一の二項関係で定義されます。Javaはいくつかの点で親しみやすく、基本単位の定義（比較）が少し複雑であるが、そこから導かれるロジックが単純である3者間比較を好みます。また、ソートアルゴリズムが比較ごとにより多くの情報を取得することも意味します。これは、場合によっては便利です。例については、「オランダの旗」クイックソートの最適化を参照してください。これは、データに「同じ場所に」重複が多数ある場合に役立ちます。

その場合、3つの値のコンパレータは速度ゲインです。ただし、C ++は、並べ替えやおよびなどにコンパレータの一貫した定義を使用します。setこれは、3つの値のコンパレータからほとんどメリットがありません（1つの比較を保存する場合もあれば、そうでない場合もあります）。特定のまたは限られた潜在的な効率向上のために、彼らは彼らの素晴らしい一般的なインターフェースを複雑にしないことに決めたと思います。maplower_bound

于 2010-03-05T12:20:32.640 に答える
1

C ++での私の推測では、コードの重複を減らすためだけに行われました。クラス/タイプで比較操作を定義すると、<bを記述するだけでこれらのオブジェクトを比較できるだけでなく、次のセットを並べ替えることもできます。そのようなオブジェクト。

ソートに関しては、必要なのはより少ない演算子だけですが、なぜ追加のものを導入するのですか？:)

于 2010-03-05T09:39:39.780 に答える
0

std :: sort（）を参照している場合、同等の要素の相対的な順序を保持する必要がないため、less（）演算子のみを使用します。したがって、less（）演算子と、暗黙的にgreater（）演算子が必要になります。

std :: stable_sortはそれを保持しますが、速度は遅くなります。「trivalue」比較関数を作成するには、equal（）演算子と引き換えにless（）演算子と双方向イテレータが必要です。

于 2010-03-05T11:05:38.037 に答える