c++ - List vs Vector，在循环时删除一个元素

Question

我需要一个容器，让我可以在循环播放时快速删除 ONE 元素。我不需要直接访问，因为我总是在循环中访问它。

在这种情况下，List 是否比 Vector 快？

伪代码:

vector<Item*> myContainer;

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

  if (someCondition)
    myContainer.erase(currentElement)
}

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

Answer 1

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

你确定你绝对需要遍历 vector 并一个一个地删除元素吗？这将导致 vector 的二次复杂度，但是 erase-remove-idiom在线性时间内完成:

#include <algorithm>

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

(如果 vector 拥有项目，您可能应该将其替换为 vector<unique_ptr<Item>>。)

作为替代方案，如果您真的必须一个一个地删除元素，并且您不关心项目的相对顺序，那么有一个 neat little trick在常数时间内删除 vector 的一个元素。