C++、ようにポインタのソートされたベクトルのためのstdの独自の実装::独特の書き方をポインタ

Question

のソートされたベクトルのためのユニークなの独自の実装：a）の安定した（メモリリークを避ける

）、

b）大規模なデータセットの場合、できるだけ早く高速化する。

インデックス[i]、[i-1]を持つ2つの隣接アイテムを比較した後、アイテム[i]のデストラクタを呼び出してベクトルから消去するのが最も遅いです。

問題の解決方法を教えてください。サンプルコードは役に立ちます:-)。ありがとう。

次の機能を備えた独自のimplementaionを作成しようとしました。 Tehereは2つの指標です。最初のものはベクトルの最後の固有の要素を表し、2番目のインデックスは共通のインデックスです。

私は要素ごとに配列要素を処理しており、要素のスワップは、一意でない要素がベクトルの最後に残るようにしています。このアプローチは、それがない...そして、最初のインデックスの右側に配置されたすべての要素を削除... K-要素は、私のopininonに、一つの要素の繰り返し削除よりも高速で一度に

を

を消去します宿題、それは深刻な問題です。点群（1e9点）から重複要素を削除する必要があります...

Answer 1

ユニークなアルゴリズムの独自の実装をローリングするのではなく、代わりにBoost pointer containersのいずれかを使用することを検討してみませんか？これらのコンテナは、オブジェクト自体の代わりにオブジェクトへのポインタを格納するように設計されており、すべてのリソース再生を処理するために必要なロジックを自動的にカプセル化します。これらのコンテナのいずれかを使用すると、標準のユニークなアルゴリズムを簡単に使用できます。

ユニークなアルゴリズムの独自のバージョンを使用する場合は、読者用と書き込み用の2つのポインタを持っていると思います。アルゴリズムの高水準スケッチは、次のように動作します。インデックス0の読み込みポインタと書き込みポインタの両方を開始します。次に、この手順を繰り返し適用します。

1. 読み取りポインタの指す値を見て、それを指す新しい一時ポインタを作成します。
2. リードポインタを前方に進めます。
3. 読み取りポインタの下の要素が記憶された値と同じである間に、読み取りポインタを前方に進めます。
4. （この時点で、読み取りポインターの下の要素は、現在の値と等しくない最初の値です）
5. 書き込みポインターの下の要素を、一意の要素への一時ポインターの指す値でスワップします。
6. ライトポインタを前方に進めます。

このアルゴリズムは、書き込みポインターがすべての一意の値を超える最初の値を指して終了します。要素は再順序付けされるだけで破棄されるわけではないので、ポインタを失うことはありません。したがって、完了したら、書き込みポインタから配列の最後まで繰り返し、見つけた各ポインタを解放することができます。これは漸近的に最適なO（n）時間で実行されます。

希望すると便利です。