C ++：std :: vector vs std :: list [duplicate]的性能

Question

这个问题在这里已有答案：

• What are the complexity guarantees of the standard containers? 2回答
• Relative performance of std::vector vs. std::list vs. std::slist? 6个答案

我有以下代码来分析各种N的std :: vector performance vs 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（）差？

Answer 1

向量插入到最后是摊销常数（即摊销的O（1））而不是摊销的O（n），其中列表总是O（n），在这种情况下，矢量容量增长快于其实际大小，它分配额外的空格然后填充，因此每个push_back都不需要分配。