1. ホーム
  2. c++

[解決済み】 ベクターの重複を消去してソートする最も効率的な方法は何ですか?

2022-02-07 11:50:20

質問内容

私は潜在的に多くの要素を持つC++ベクトルを取り、重複を消去し、それを並べ替える必要があります。

現在、以下のようなコードを持っていますが、うまくいきません。

vec.erase(
      std::unique(vec.begin(), vec.end()),
      vec.end());
std::sort(vec.begin(), vec.end());

どうしたら正しくできるのでしょうか?

さらに、重複を先に消す(上記のコードと同様)のと、ソートを先に実行するのでは、どちらが速いでしょうか? もし最初にソートを実行した場合、その後にソートされたままであることが保証されますか? std::unique が実行されますか?

それとも、これらすべてを行う別の(おそらくより効率的な)方法があるのでしょうか?

どのように解決するのですか?

に同意します。 R. ペイト トッド・ガードナー ; a std::set がいいかもしれませんね。 ベクターにこだわっても、重複が多ければ、セットを作って汚れ仕事をしたほうがいいかもしれません。

3つのアプローチを比較してみましょう。

ベクトルだけで、ソート+ユニーク

sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );

セットに変換する(手動)

set<int> s;
unsigned size = vec.size();
for( unsigned i = 0; i < size; ++i ) s.insert( vec[i] );
vec.assign( s.begin(), s.end() );

セットに変換する(コンストラクタを使用する)

set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );

以下は、重複の数が変化したときのこれらのパフォーマンスです。

概要 : 重複の数が十分多い場合。 集合に変換してベクトルに戻した方が速いんです .

そしてなぜか、セットコンストラクタを使うよりも手動でセット変換をした方が速いようです -- 少なくとも私が使ったおもちゃのランダムデータでは。