なぜerase（）関数が高価なのですか？

Question

2Dベクトルvector < vector <int> > Nを検討し、以下のように、その内容があると言うことができます：

1 1 1 1 
2 2 2 2 
3 3 3 3 
4 4 4 4 

ので、ここでNの大きさは、今4すなわちN.size() = 4

で、次のコードを考えてみます。

int i = 0; 
while(N != empty()){ 
N.erase(i); 
++i; 
} 

を

Nのためにさまざまなサイズのこのコードだけの時間を計算しました。結果は次のとおりです。

.760000s

：Nのサイズが20000 実行時間が22.900000s

ある：Nのサイズが10000 実行時間が0.230000s

ある：10

Nのサイズ1000 実行時間でありますNの大きさは30000 実行時間である：526.540000s

：Nのサイズは47895 実行時間である

を206.620000s

私の質問は、なぜこの機能が高価なのですか？そうであれば、多くのプログラムの条件付き消去文は、この関数のために永久に取ることができます。 std::mapでも消去機能を使うのと同じです。この機能の代替手段はありますか？ Boostのような他のライブラリは何を提供していますか？

私はこの機能を分析しようとしているため、N.erase()全体を行うことはできません。

Answer 1

ベクトルの最初の要素を削除するとどうなるか考えてみましょう。残りのベクトルは、1つのインデックスだけ「移動」されなければなりません。もう一方の端から消してみて、違いがあるかどうかを確認してください（私はそう思う...）

Answer 2

ベクトルは、要素を追加すると自動的に拡大する配列です。したがって、ベクトルの要素はメモリ内で連続しています。これにより、要素への一定時間のアクセスが可能になります。彼らは最後から成長するので、彼らはまた、端に追加/削除するために償却された一定の時間を取る。

今、途中で削除するとどうなりますか？それは、消去された要素が1つの位置に戻されなければならないことを意味します。これは非常に高価です。

途中で多くの挿入/削除を行う場合は、std :: listのようなリンクリストを使用してください。

Answer 3

あなたのアルゴリズムはO（n^2）なので、 eraseを呼び出すたびに、vectorは、消去された要素の後ろのすべての要素を元に戻します。したがって、4要素ベクトルのループでは、最初のループは3つの要素をシフトさせ、2番目の反復は1つの要素をシフトさせ、その後は未定義の動作をします。

8つの要素がある場合、最初の繰り返しは7つの要素を移動し、次の要素は5つの要素を移動し、次の要素は3つの要素を移動し、最後の列挙は1つの要素を移動します。 （また、未定義の動作があります）

このような状況に遭遇した場合は、通常、標準のアルゴリズムを使用する必要があります。std::remove,std::remove_if）の代わりに、それらはコンテナを一度通過し、典型的なO（n^2）アルゴリズムをO（n）アルゴリズムに変えます。詳細については、スコットマイヤーズの「効果的なSTL」を参照してください。項目43：アルゴリズム呼び出しを明示的ループに優先させます。

Answer 4

std :: vectorは、内部的には要素の配列です。途中の要素を削除すると、その後のすべての要素を下にシフトする必要があります。これは非常に高価になる可能性があります。要素に多くの作業を行うカスタムがある場合はさらにそうです！

erase()が高速である必要がある場合は、std::listを使用する必要があります。これは、中間からの高速消去を可能にする二重リンクリスト構造を使用します（ただし、他の操作はやや遅くなります）。リストのの開始をすぐに削除する必要がある場合は、std::dequeを使用してください。これは配列のリンクリストを作成し、std::vectorのスピードの利点のほとんどを提供しながらも、先頭または末尾から高速消去が可能です。

さらに、そこにループを置くと、問題が悪化することに注意してください。まず、ゼロに等しいすべての要素をスキャンして消去します。スキャンにはO（n）回、消去にはO（n）回もかかります。次に、1のように繰り返す - 全体的に、O（n^2）時間。複数の値を消去する必要がある場合は、イテレータを使用し、のイテレータバリアントを使用してstd::listを直接実行する必要があります。または、vectorを使用すると、新しいベクトルにコピーするほうが速くなることがわかります。

std::map（およびstd::set）については、これはまったく問題ありません。 std::mapは、ランダムに要素を取り除くことも、をランダムに要素の検索を、O(lg n)の時間で行うことができます。これはほとんどの用途では非常に妥当です。あなたの素朴なループでさえ、あまりにも悪くあってはいけません。 1回のパスで削除したいものを手動で繰り返して削除するのはやや効率的ですが、std::listと友だちではそれほどではありません。

Answer 5

Oliによると、ベクトルの最初の要素から消去すると、配列が必要に応じて動作するように、それに続く要素をコピーする必要があります。

これは、リスト内の任意の場所から要素が削除される状況でリンクされたリストが使用される理由です。コピーされず、一部のノードポインタのみがリセットされるため、リストが高速になります。

Answer 6

vector.eraseは、iを1だけ進めた後、すべての要素を進めます。これはO（n）操作です。

さらに、参照ではなく値でベクターを渡しています。

このコードでも、ベクター全体が消去されるわけではありません。例えば

： I = 0 消去N [0] N = {{2、2、2、2}、{3、3、3、3}、{4、4、4、4} }

I = 1 消去N [1] N = {{2、2、2、2}、{4、4、4、4}}

I = 2 消去N [2 ]最大インデックスがN [1]なので何も起こらない

最後に、これはvector.erase（）の正しい構文だとは思わない。開始位置にイテレータを渡して、必要な要素を消去する必要があります。これを試してみてください ：あなたはまた、端から消去にこれを比較することができ

vector&ltvector&ltint>> vectors; // still passing by value so it'll be slow, but at least erases everything 
for(int i = 0; i < 1000; ++i) 
{ 
    vector&ltint> temp; 
    for(int j = 0; j < 1000; ++j) 
    { 
     temp.push_back(i); 
    } 
    vectors.push_back(temp); 
} 

// erase starting from the beginning 
while(!vectors.empty()) 
{ 
    vectors.erase(vectors.begin()); 
} 

（むしろ参照よりも値を使用する場合は特にそれは、大幅に高速化する必要があります）：

// just replace the while-loop at the end 
while(!vectors.empty()) 
{ 
    vectors.erase(vectors.end()-1); 
}