2

我需要一个容器，它允许我在循环遍历一个元素时快速擦除它。我不需要直接访问，因为我总是在循环中访问它。

List比Vector这种情况快吗？

伪代码：

vector<Item*> myContainer;

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

  if (someCondition)
    myContainer.erase(currentElement)
}

删除一个元素后，我需要继续遍历其余元素

4

3 回答 3

8

是的，理论上列表比向量提供更快的删除，但实际上，没有人使用列表。为什么不？因为向量产生的堆活动少得多，而且它们提供了更好的缓存局部性。

你确定你绝对需要遍历向量并一个一个地擦除元素吗？这将导致向量的二次复杂度，但擦除删除成语在线性时间内完成：

#include <algorithm>

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

（如果向量拥有项目，您可能应该将其替换为vector<unique_ptr<Item>>.）

作为替代方案，如果您确实必须逐个删除元素，并且您不关心项目的相对顺序，那么有一个巧妙的小技巧可以在恒定时间内删除向量的一个元素。

于 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 回答