潜在的に多くの要素を持つ C++ ベクトルを取得し、重複を消去して並べ替える必要があります。
現在、以下のコードがありますが、動作しません。
vec.erase(
std::unique(vec.begin(), vec.end()),
vec.end());
std::sort(vec.begin(), vec.end());
これを正しく行うにはどうすればよいですか?
さらに、最初に重複を削除する (上記のコードと同様) 方が速いですか、それとも最初にソートを実行する方が速いですか? 最初にソートを実行した場合、std::unique
実行後もソートされたままであることが保証されますか?
それとも、これらすべてを実行する別の(おそらくより効率的な)方法があるのでしょうか?
ベストアンサー1
同意するR.ペイトそしてトッド・ガードナー; は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() );
重複数が変化した場合のパフォーマンスは次のようになります。
要約: 重複の数が十分に多い場合、実際にはセットに変換してからデータをベクトルに戻す方が高速です。
そして、何らかの理由で、セット変換を手動で行う方が、セット コンストラクターを使用するよりも高速であるようです (少なくとも、私が使用したおもちゃのランダム データでは)。