問題タブ [strict-weak-ordering]

まず、同様の質問を検索しようとしましたが、私の問題が何であるかを説明する回答が見つかりませんでした.

問題は次のとおりです。座標 (x、y、z) を持つ N 個のノードのセットが与えられた場合、それらを 4 番目の値 F を使用してできるだけ速く並べ替えます。

std::setO(log(N)) の複雑さがあるため、この目的のためにカスタム コンパレータを使用したいと考えています。a とonstd::vectorの呼び出しを試すこともできますが、理論的には操作が遅くなります。std::sortstd::vector

なぜこれ？私は常にセットに要素を挿入し、F値を変更しているため（値を変更し、コンテナ内の要素を並べ替えて消去して再挿入することを意味します）、F値が小さい要素を取得したい(コンテナの前にある要素です)。

std::setしかし、問題に行きましょう。

座標は一意性プロパティを定義し、厳密な弱い順序付けルールに従います。つまり、aとbは同じオブジェクトと見なされます。

この問題は、座標に基づく一意性基準と F 値に基づく並べ替え基準の定義に関連しています。セットに同じ座標を持つ 2 つの要素を格納したくないが、座標は異なるが同じ F 値を持つ 2 つの要素を格納できるようにしたい

コンパレータは、次の 3 つのプロパティも満たす必要があります。

1. 無反射 x < x false
2. 非対称x < y true性が意味することy < x false
3. 推移x < y && y < z 性が意味することx < z true

したがって、これらすべてのプロパティを知っているので、次の実装例を使用して取り組んできました。

いくつかの定義

ここでは便宜上ポインタを使用しています

クラス ノード

ここで、オペレーター<<はデバッグ目的でのみオーバーロードされます

コンパレータ

1つの問題は、座標は異なるがF値が同じ2つのノードの場合である可能性があると思います

具体的なケースを含む完全な例

この例では、上記のクラスを使用していくつかの要素を挿入/検索/消去していますが、出力に表示されているため、期待どおりに動作していません:

C++11 以降でコンパイルするには:g++ -o main main.cpp

出力：

**期待される出力: ** F が小さいもの (n1) から F が大きいもの (n3) に並べられた要素 n1、n5、n2、n3 に対応します。

実装の助けやアイデア、代替案をいただければ幸いです。ありがとう