カスタムタイプのstd :: listから重複を削除する最速の方法

Question

これが私に許してもらえない場合は、私はそれを見つけることができませんでした。 私は（曖昧な）等価を実装できるカスタム型を持っていますが、推移型の演算子は<ではありません。 比較にはコストがかかりますが、私は多くの要素がありません。 私はまったく同じ（大部分に重なる）ポリゴンをソートする必要があります。 <を使用して発注することにより、推移的な実装の不足のために不可能であるので、私はSTDを使用しています::リストを次のように：

typedef std::list<Polygon> PolyList; 
PolyList purged(rawList); 
for (PolyList::iterator iter= purged.begin(); iter!= purged.end(); ++iter) { 
    for(PolyList::iterator toRemove = find(boost::next(iter),purged.end(),*iter); toRemove != purged.end();){ 
     PolyList::iterator next = purged.erase(toRemove); 
     toRemove = find(next,purged.end(),*iter); 
    } 
    } 

複雑さは、私の意見と 中で避けられないのn * n/2個ですアルゴリズムはうまく動作しますが、読んだり書いたりするのはまだ非常に面倒です。私はほとんど知っていない標準アルゴリズムがあると思います。私が言ったように、並べ替えはデータの曖昧性のためにオプションではないので、ユニークなセットやソートはありません。 多くのご協力をいただきありがとうございます。

Answer 1

を記録していると考えていますいずれかの推移。つまり、a==b && b==cはa==cを意味しません。

だけではそのため、任意のアルゴリズムはあなたに(N*N-1)/2比較を与える、すべてのペアを比較することがある（あなたの平等が対称であると仮定すると、すなわちa==bがb==aを意味するものではありません）。

Answer 2

2つのポリゴンの違いを説明する距離メトリックを定義すると、（任意の）1つを選択することができますポリゴン（それをベースポリゴンと呼ぶ）と、そのポリゴンから離れたものすべてをソートします。ベースからの距離が近いポリゴンだけが互いに類似している可能性があります。

これで、削除するものを決定する際に、距離が近いポリゴンのグループだけを検討する必要があります。それを証明しなければ - と、私は証拠が関与している可能性がある疑いがある - 私は、これはN、彼らがいないいるようなあなたの「重複」が聞こえるので、あなたはおそらく、標準でasnwerを見つけるつもりはないN.