C++：std::vector与std::list的性能比较

Question

我有以下代码，用于对不同N的std::vector性能和std::list进行分析。

void vectorPerf(size_t n)
{
   std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now();
   std::vector<size_t> cache;
   for (size_t i = 0; i < n; i++) {
      cache.push_back(i);
   }
   std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now();

   auto duration = std::chrono::duration_cast<std::chrono::microseconds>(t2-t1).count();

   std::cout << duration << " us." << "\n";

   return;
}

void listPerf(size_t n)
{
   std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now();
   std::list<size_t> cache;
   for (size_t i = 0; i < n; i++) {
      cache.push_back(i);
   }
   std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now();

   auto duration = std::chrono::duration_cast<std::chrono::microseconds>(t2-t1).count();

   std::cout << duration << " us." << "\n";

   return;
}

int main(int argc, char** argv)
{

   if (argc != 2) {
      return -1;
   }
   std::stringstream ss(argv[1]);
   size_t n;
   ss >> n;
   vectorPerf(n);
   std::cout << "\n";
   listPerf(n);
   std::cout << "\n";
}

对于同一组N的多次运行，我得到的结果通常与下面的数字相同:

N       std::vector  std::list
1000    46           116
2000    85           217
5000    196          575
10000   420          1215
100000  3188         10497
1000000 34489        114330

我想知道为什么std::list的性能始终比std::vector差。对于std::vector，我希望性能是摊销O（N），因为支撑std::vector的内部对象需要不时地调整大小。由于我所做的一切都只是将元素插入到列表的末尾，所以我原本预计std::list的时间复杂度应该是O（1）。这表明std::list的表现应该比std::vector更好，但事实却相反。

我会感激如果有人能够解释这是为什么。我正在使用2015 MBP上的g++编译器，在MacOS 10.12.6上进行编译。

谢谢。

编辑：我现在明白了std::vector ::push_back()的摊销时间复杂度是O（1）。然而，我不清楚的是，为什么std::list ::push_back()的性能始终比std::vector ::push_back()差？

- Jai Prabhu

---

因为每次向列表插入元素都需要进行内存分配，而向向量添加元素通常不需要这样做。 - 1201ProgramAlarm

拥有不同的容器的原因之一是它们对于不同的操作没有相同的性能。因此，根据使用情况（和数据大小），必须选择适当的容器。简单的规则是在大多数情况下使用 std::vector。 - Phil1970

看一下时间消耗之间的比率，向量和列表之间的近似时间比大致保持在1:3左右。因此，这不是复杂性的问题，而是Big-O符号忽略的常数问题。 - lamandy

重复使用 push_back() 会导致代码将数据写入连续的内存地址，这也正是 vector 的特性。现代 CPU 在按顺序访问连续内存地址方面非常出色。而对于 std::list，每个元素都分配在随机的内存块中，因此其性能不如前者。 - Sam Varshavchik

这里有更多的基准测试：https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html - drescherjm

Answer 1

向向量末尾插入元素的摊销常数是恒定的（即摊销O（1）），而不是摊销O（n），其中列表始终为O（n）。在这种情况下，向量容量增长速度比其实际大小更快，它会分配额外的空间，然后随着元素的添加逐步填充，因此不需要为每个push_back操作都进行一次分配。

- SoronelHaetir

---

不矛盾。cppref.com上的描述指出std::list可以在常数时间内插入和删除元素，但是访问其中的任何元素仍然需要遍历整个列表，因此访问元素的时间复杂度仍为O(n)。 - 2785528