0

std::vector私は比較的小さいサイズ(5から20要素)のソートを持っています。データが連続しているので使用std::vectorしたので、キャッシュのおかげでスピードが出ました。特定の点で、これから要素を削除する必要がありますvector

私は今疑問を持っています:以下の2つのオプションの間でこの値を削除する最も速い方法はどれですか?

  1. その要素を0に設定し、sort並べ替えを呼び出します。これには複雑さがありますが、要素は同じキャッシュライン上にあります。
  2. erase1つの場所の後にすべての要素をコピーする(または知っているmemcpy ??)呼び出し(消去の背後にあるシーンを調査する必要があります)。

どちらが速いか知っていますか?

ベクトルの最大容量に達することなく、新しい要素を挿入することについても同じアプローチが考えられると思います。

よろしく

AFG

4

1 に答える 1

1

要素の順序を気にしない場合は、要素を最後の要素と交換できる場合があります。

void Remove( std::vector<Object> &vec, iterator i ) {
    iterator last = vec.end()-1;
    if (i != last)
        std::swap( *i, *last );
    vec.erase( last );
}

要素を0に設定することに言及しました。それがポインターを持っていることを意味する場合は、スワップは必要ないかもしれません。

void Remove( std::vector<Object *> &vec, iterator i ) {
    vec[i] = vec.back();
    vec.erase( vec.end()-1 );
}

順序を気にする場合は、erase()を使用する2番目のオプションで順序が保持され、最小限の作業が実行されます。ほぼ確実に、頼るよりも速くなります。

于 2012-06-06T18:25:03.453 に答える