問題タブ [partial-ordering]

ポインター関係演算子は全順序を定義しません ( § C++11 標準の 5.9 )。

同じ型の2 つのポインターpとqが、同じオブジェクトのメンバーではない異なるオブジェクト、同じ配列の要素、または異なる関数を指している場合、またはそのうちの 1 つだけが null である場合、 、 、 、および の結果p<qはp>q指定p<=qされていませんp>=q。

std::lessのドキュメントには次のように書かれています。

std::less任意のポインター型に対するの部分的な特殊化は、組み込みoperator<がそうでなくても、全体の順序をもたらします。

部分的な順序からこの全体的な順序をどのように生成しますか?

定義を調べ/usr/include/c++/4.9/bits/stl_function.hても、この質問に答えることができません。struct less

（私の前の質問に関連）

QT では、QMapドキュメントには次のように記載されています。

QMap のキー タイプは、合計順序operator<()を指定する必要があります。

ただし、 では、ポインターを比較するqmap.hために次のようなものを使用しているようです。std::less

quintptrポインターをs (の QT バージョンuintptr_t、つまり、ポインターを格納できる unsigned int )にキャストし、結果を比較するだけです。

次の型は、void への任意の有効なポインターをこの型に変換し、その後 void へのポインターに戻すことができるプロパティを持つ符号なし整数型を指定します。結果は元のポインターと等しくなります。uintptr_t

qMapLessThanKey()このon ポインターの実装は問題ないと思いますか?

もちろん、整数型には完全な順序があります。しかし、これは、この操作がポインターの全体的な順序を定義していると結論付けるのに十分ではないと思います。

AFAIKが指定されていないことをp1 == p2意味する場合にのみ、それは真実だと思います。quintptr(p1) == quintptr(p2)

この状態の反例として、ポインターに 40 ビットを使用するターゲットを想像してください。ポインターを に変換しquintptr、最下位 40 ビットをポインター アドレスに設定し、最上位 24 ビットを変更せずに (ランダムに) 残すことができます。これは と ポインター間の変換可能性を尊重するのに十分ですquintptrが、これはポインターの全体的な順序を定義しません。

どう思いますか？

[temp.class.order] §14.5.5.2 によるとt、この例での部分的な特殊化の選択:

fこの例では、オーバーロードの選択と同等です。

ただし、GCC、Clang、および ICC はすべて、最初の例があいまいであるとして拒否しますが、2 番目の例は受け入れます。

さらに奇妙なことに、最初の例は、::vが に置き換えられた場合、::wまたはその逆に置き換えられた場合に機能します。推論されていないコンテキストc::とs< c >::は明らかに特殊化の順序で考慮されていますが、これは意味がありません。

標準に何か欠けているのでしょうか、それともこれらすべての実装に同じバグがありますか?

まず第一に、これは質問Partial Ordered Comparatorの複製ではなく、それに基づいています。

私の目標は、オブジェクトのリスト ([2, "a", 1] など) をその場で並べ替えて、並べ替え後に 2 つの整数の順序が乱れないようにすることです。

このために、この回答の実装を次の半順序で使用し、次の結果を得ましたIllegalArgumentException。

これは、提案されたコンパレータに欠陥があるためです。デモンストレーション：

iffとが両方とも整数であり、整数の自然な順序付けに従っているRすべてのObjectインスタンスに対して半順序付けを使用します。a.before(b)aba < b

この理由は、次の実装では

これにより、生成された順序でサイクルが発生する可能性があります。

つまり、2 < "a"、"a" < 1、"1 < 2 です。これは明らかに有効な全順序付けではありません。

最後の質問は次のとおりです。このバグを修正するにはどうすればよいですか?

半順序の単一の線形拡張から推移的な削減を作成する効率的なアルゴリズムはありますか?

更新:実際には、半順序が知られています。また、与えられた半順序の推移還元を計算する時間の複雑さも認識しています。私が知りたかったのは、半順序とその線形拡張の 1 つが与えられた場合、その時間の複雑さを減らすことができるかということです。

入力セットが与えられると、そこからすべての事前注文関係 (または、同等にすべての弱い注文) を生成する、中途半端に効率的なアルゴリズムを探しています。n 個のラベル付き要素のすべての優先配置と呼ぶこともできます。

最初にサイズ n のすべての順列を生成し、次にそれらのサブシーケンスを '~' で折りたたむことによって、これを実装しようとしましたが、これは多くの重複のために非常に非効率的であり、いくつかの結果を逃しました。サイズは、Fubini 番号 1、1、3、13、75、541、4683、47293、545835、... (OEIS 番号 A000670) で指定され、n と共に急速に成長しています。n=8 まで、最初の数個だけが必要です。

例: A={a, b, c} で n=3 の場合、結果は 13 の予約注文になります。

b>a>c、b>a~c、b>c>a、b~c>a、c>b>a、c>a~b、c>a>b、a~c>b、a> c>b、a>b~c、a>b>c、a~bc、a~b~c