List比Vector更快吗？vector<Item*> myContainer;
for(..loop over it...) {
if (someCondition)
myContainer.erase(currentElement)
}
理论上，列表提供比向量更快的删除，但在实践中，没有人使用列表。为什么呢？因为向量产生的堆活动要少得多，并且它们提供更好的缓存局部性。
你确定需要循环遍历向量并逐个删除元素吗？这将导致向量具有二次复杂度，但erase-remove-idiom可以在线性时间内完成：
#include <algorithm>
myContainer.erase(
std::remove_if(
myContainer.begin(),
myContainer.end(),
[](Item* p) {
return p->someCondition;
}
),
myContainer.end()
);
(如果向量拥有Items，您应该考虑将其替换为vector<unique_ptr<Item>>。)
作为替代方案，如果您真的必须逐个删除元素，并且不关心Items的相对顺序，则有一个小技巧可以在常数时间内删除向量中的一个元素。
使用列表在任意位置删除元素更快：
std::vector::erase的复杂度：与被删除的元素数量（析构函数）和最后一个被删除元素之后的元素数量（移动）成线性关系。
std::list::erase的复杂度：与被删除的元素数量（析构函数）成线性关系。
此外，在删除后，迭代器会变得无效，因此需要更新迭代器：
it = list.erase(it);
Item*）可能与释放列表节点（这也需要一些重新链接）一样快。O(1)并不总是比O(n)更快。 - Bo PerssonO（1））并不总是比移动n个小盒子（O（n））更好。 - Bo Persson 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)空间）。
2和4中），然后处理包含3的节点。对于向量，您只需复制两个指针（4和5），然后完成操作。哪种操作最快？ - Bo Persson
return p->someCondition;行之前。具有可变谓词有点不寻常，但我不认为在这种特定情况下它不能工作。或者，首先使用for_each更新项目，然后应用擦除/删除习语以删除不需要的项目。这样会更加清洁，但也可能会稍微影响缓存友好性。 - fredoverflow