c++ - std::vector 和 std::list find_if 和 max_element 性能

Question

我对针对 std::vector 和 std::list 测试的代码的性能感到困惑。这两者在 find_if 和 max_element 方面有区别吗？

Answer 1

就大 O 表示法而言，两者具有相同的 O(n) 性能。 (如果更快找到元素，find_if 可以更少，但这对两个容器同样适用。)

就实际挂钟时间而言，由于缓存一致性， vector 会表现得更好；所有 vector 元素在内存中都是连续的，因此访问它们将更好地利用 CPU 缓存。链表的元素可能分散在整个内存中，您还需要遵循列表链接，这需要时间。