3

オブジェクトのベクトルを並べ替えようとすると、無限ループが発生するという問題が発生しました。sort関数に渡したカスタム比較関数を使用しています。

2つのオブジェクトがtrueではなく等しい場合にfalseを返すことで問題を修正できましたが、解決策を完全には理解していません。これは、cplusplus.comで概説されているように、私の比較関数がこのルールに違反していたためだと思います。

範囲に含まれる値と同じタイプの2つの値を取り、最初の引数が定義された特定の厳密な弱順序で2番目の引数の前にある場合はtrueを返し、それ以外の場合はfalseを返す比較関数オブジェクト。

誰かがより詳細な説明を提供できますか？

4

6 に答える 6

6

「厳密な弱順序」とは何かの詳細な説明を探している場合は、ここにいくつかの良い読み物があります：Order I Say！

比較ファンクターを修正するためのヘルプを探している場合は、実際に投稿する必要があります。

于 2011-06-02T18:22:11.160 に答える
6

アイテムが同じである場合、一方が他方より先に進むことはありません。その場合は戻る必要があることを示すドキュメントは非常に明確でしたfalse。

于 2011-06-02T18:22:32.623 に答える
6

他の人が指摘しているように、正解は「厳密な弱順序」とは何かを学ぶことです。特に、comp(x,y)trueの場合、comp(y,x)falseである必要があります。（これはそれcomp(x,x)が誤りであることを意味することに注意してください。）

問題を修正するために知っておく必要があるのはこれだけです。比較関数がルールに違反した場合、sortアルゴリズムはまったく約束をしません。

実際に何がうまくいかなかったのか知りたい場合は、ライブラリのsortルーチンが内部でクイックソートを使用している可能性があります。クイックソートは、シーケンス内の「順序が正しくない」要素のペアを繰り返し見つけて交換することで機能します。比較によって、a、bが「故障」であることがアルゴリズムに示され、b、aが「故障」であることがアルゴリズムに示されている場合、アルゴリズムはそれらを永久に何度も交換することになります。

于 2011-06-02T18:29:07.073 に答える
3

実際のルールは、C++標準で指定されています。25.3[lib.alg.sorting]/2

Comparetrueは、最初の引数が2番目の引数よりも小さい場合に返される関数オブジェクトとして使用され、それ以外の場合は返されますfalse。

引数が等しい場合は「それ以外」に該当します。

于 2011-06-02T18:25:13.230 に答える
2

並べ替えアルゴリズムは、等しい場合にA <B AND B <Aと言っているため、簡単にループする可能性があります。したがって、アルゴリズムは要素AとBを無限に交換し、正しい順序で取得しようとする可能性があります。

于 2011-06-02T18:23:58.973 に答える
0

厳密な弱順序はa<b== trueを意味し、等しい場合にtrueを返すと、そのa <= b==trueになります。この要件は、さまざまなソートアルゴリズムを最適化するために必要です。

于 2011-06-02T18:22:17.693 に答える