列表与矢量,循环时删除元素

Question

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

是List不是快Vector这种情况？

伪代码:

vector<Item*> myContainer;

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

  if (someCondition)
    myContainer.erase(currentElement)
}

删除一个元素后,我需要继续循环其余的元素

Answer 1

是的,理论列表提供了比矢量更快的删除,但在实践中,没有人使用列表.为什么不？因为向量生成的堆活动少得多,并且它们提供了更好的缓存局部性.

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

#include <algorithm>

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

(如果向量拥有Items,您应该用a替换它vector<unique_ptr<Item>>.)

作为替代方案,如果你真的必须逐个删除元素,并且你不关心Items的相对顺序,那么有一个巧妙的小技巧可以在恒定时间内删除向量的一个元素.

Answer 2

使用列表可以更快地删除任意位置的元素:

std :: vector :: erase的复杂性:删除的元素数量(析构函数)加上最后一个元素删除(移动)后的元素数量.

std :: list :: erase的复杂性:删除的元素数量上的线性(析构函数).

此外,擦除后迭代器将无效,因此您需要更新迭代器:

it = list.erase(it);