どのようにSTDからランダム削除を来る::ベクトルがのstd ::リストよりも速いのですか？

StackOverflow https://stackoverflow.com/questions/865666

質問

どのようにのstd ::ベクトルから、ランダム削除がのstd ::リストよりも高速です来ますか？私はそれをスピードアップするためにやっていることは、最後にランダムな要素を交換して、最後に削除されます。 私はランダムな削除は、それがために建てられたものであるため、リストは速いだろうと思っているだろう。

for(int i = 500; i < 600; i++){
    swap(vector1[i], vector1[vector1.size()-1]);
    vector1.pop_back();
}

for(int i = 0; i < 100; i++){
        list1.pop_front();
}
（秒）

結果：
削除VECスワップ：0.00000909461232367903
通常の削除リスト：0.00011785102105932310

役に立ちましたか？

解決

あなたがやっていることはいえランダム削除ではありません。あなたはベクトルが（とりわけ）のために構築されているものであるエンドから削除しています。

とスワッピングするとき、あなたは、単一のランダムなインデックス操作をやっているのものものをベクトルで良いですされます。

他のヒント

std::listとstd::vectorとの違いは、単にダウンし、パフォーマンスにではありません。彼らはまた、別のイテレータの無効化のセマンティクスを持っています。あなたはstd::listからアイテムを消去する場合は、リスト内の他の項目を指しているすべてのイテレータは有効なまま。ない項目を消去すると、その項目の後に指しているすべてのイテレータを無効にstd::vector、とそう。 （いくつかの実装では、彼らはまだ有効なイテレータを果たすことができるが、標準によると、彼らは今使用できない、とチェック実装はあなたがそれらを使用しようと主張するべきである。）

だから、コンテナのあなたの選択は、セマンティクスはあなたが必要とするものをどうすることもある。

これはランダムではありません。試してみてくださいvector1.erase（vector.begin（）+ランド（）％vector.size（））;その代わります。

リストeraseが消去リスト要素を削除するようになります、これはdeleteのオペレータへの呼び出しを呼び出します。ベクトルの消去だけでスワップして、整数の減少の原因となる - 。これは、はるかに高速です。

あなたはさらにスピードアップしたい場合は、

は、実際には、のイテレータのを経由して、ベクトルのインデックスの要素をする必要があります。彼らはいくつかのアーキテクチャのためのより良い性能を有することが知られている。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top