2

ループ中に 1 つの要素をすばやく消去できるコンテナが必要です。常にループ内でアクセスするため、直接アクセスする必要はありません。

この場合Listよりも速いですか？Vector

擬似コード:

vector<Item*> myContainer;

for(..loop over it...) {

  if (someCondition)
    myContainer.erase(currentElement)
}

要素を削除した後、残りの要素をループし続ける必要があります

4

3 に答える 3

8

はい、理論的にはリストの方がベクトルよりも高速に削除できますが、実際にはリストを使用する人は誰もいません。なぜだめですか？ベクトルが生成するヒープ アクティビティがはるかに少なく、キャッシュの局所性がはるかに優れているためです。

ベクトルをループして、要素を 1 つずつ消去する必要があるのは確かですか? これはベクトルの二次的な複雑さをもたらしますが、erase-remove-イディオムは線形時間でそれを行います:

#include <algorithm>

myContainer.erase(
    std::remove_if(
        myContainer.begin(),
        myContainer.end(),
        [](Item* p) {
            return p->someCondition;
        }
    ),
    myContainer.end()
);

(ベクターがアイテムを所有している場合は、おそらく に置き換える必要がありvector<unique_ptr<Item>>ます。)

別の方法として、要素を 1 つずつ削除する必要があり、Items の相対的な順序を気にしない場合は、ベクトルの 1 つの要素を一定の時間で削除するための巧妙な小さなトリックがあります。

于 2012-07-22T12:09:35.450 に答える
5

リストを使用すると、任意の位置で要素を消去する方が高速です。

std::vector::erase の複雑さ: 消去された要素 (デストラクタ) の数と、最後の要素が削除された (移動した) 後の要素の数に比例します。

std::list::erase の複雑さ: 消去された要素 (デストラクタ) の数に比例します。

また、イテレータを消去すると無効になるため、イテレータを更新する必要があります。

it = list.erase(it);
于 2012-07-22T09:44:35.467 に答える
0

C++ リストは連結リストです。したがって、要素は次のように配置されます。

 head <--> 1 <--> 2 <--> 3 <--> 4 <--> 5

したがって、3 を削除したい場合は、ポインターをシャッフルするだけです。3 を消去したいので、2 のポインターを 4 に移動する必要があります。この場合、3 まで移動する必要があります (要素を見つけます)。二重にリンクされたリストであり、削除する要素をすでに特定しているため、時間の複雑さは最悪の場合 O(1) になります。

ただし、一方で c++ ベクトルは単なる配列です。したがって、ベクトル要素の削除は、配列からの要素の削除に続きます。この場合、O(1) の複雑さで消去する要素を見つけることができます。ただし、それを消去するには、すべての要素を左シフトして、作成されたボイドを削除する必要があります。したがって、複雑さは O(n) 最悪の場合です。口頭では、複雑さは「n - 削除する要素のインデックス」のようなものになります。

リストは、O(1) の削除の複雑さとベクトル O(n) 漸近を生成します。ただし、リストには、各要素のポインターを維持するための追加のオーバーヘッドがあります (全体的に O(2n) スペースが追加されます)。

于 2012-07-22T10:25:00.720 に答える