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

Question

我对测试代码的性能std::vector和std::list. 说到find_ifand ，这两者有区别max_element吗？

Answer 1

就大 O 表示法而言，两者都具有相同的 O(n) 性能。（find_if如果更快找到元素，则可以减少，但这对于两个容器都是如此。）

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

Answer 2

两种算法的计算复杂度都是 O(n)，但是向量将它们的元素分配在一个连续的存储区域中，这很可能会导致更高的缓存命中率。另一方面，遍历列表涉及分散的内存访问模式，这很可能导致更高的缓存未命中率。

与往常一样，在性能方面，无论如何，在做出决定之前进行测量。

Answer 3

对于 max_element，将遍历列表和数组的所有元素。因此，就性能而言，两者都是 O(n)。

同样对于 find_if，两个数据结构的遍历都是线性的 (O(n))。

我认为除了相对于每个的常数之外应该没有太大的区别。