c++ - 在修改序列的同时迭代它。使用 vector 还是列表？ C++/标准语言

Question

假设我有一个长序列的无序元素 S s1, s2, s3,.... 是任意但固定的数据类型，我希望通过它根据某些规则迭代和删除某些元素 bool 标准。

现在，如果在遍历序列之后，如果我不对序列的最终排序感兴趣，那么我可以用两种方式存储我的序列

1. 使用普通的 ol' std::list 来表示序列。使用 std::list 方法执行删除。
2. 使用std::vector 来表示序列。如果某个元素不符合标准并且必须删除，则将其与最后一个 vector 元素交换并执行 pop_back。

我的问题是

1.哪种时间方式和/或内存方式更好/更有效地存储我的序列？

2.如果我不得不冒险猜测，那么我会说列表，因为如果 si 的数据类型内存大小很大，交换将很昂贵。这个推理是正确的吗？

Answer 1

在实践中，std::vector 由于其紧凑的内存局部性，与其他容器相比具有很大的性能优势。如果您的元素是可移动的(即交换成本低)，那么您的第二个选择应该是您的第一个尝试。使用标准的 remove/erase 习惯用法实现它:

v.erase(std::remove_if(v.begin(), v.end(), predicate), v.end());

您还应该使用 std::list 设置第二个版本并比较性能:

l.remove_if(predicate);

该列表避免移动任何元素，因此理论上它可能是高效的，但是内存局部性的实际影响无法被语言标准捕获，您无法绕过测量和比较实际性能。

(据推测，如果您的元素类型很大，例如 sizeof(T) > 10000，列表可能会开始比 vector 快。测试和比较，并保持您的代码模块化，这样稍后更改它很容易。)