C++: производительность std::vector против std::list

Question

У меня есть следующий код для профиля std:: вектор производительности vs std:: list для различных N.

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, но, похоже, все наоборот.

Буду признателен, если кто-нибудь сможет пролить свет на то, почему это происходит. Я компилирую на MacOS 10.12.6, используя g++ на MBP 2015 года.

Благодарю.

РЕДАКТИРОВАТЬ: Теперь я понимаю, что std::vector::push_back() амортизируется O(1). Однако мне неясно, почему std::list::push_back() работает хуже, чем std::vector::push_back()?

Answer 1

Вставка вектора до конца является амортизированной постоянной (то есть амортизированной O(1)), а не амортизированной O(n), где список всегда равен O(n), емкость вектора растет быстрее, чем его фактический размер, в этом случае он выделяет дополнительные пространство, а затем заполняется, как это идет, так что распределение не требуется для каждого push_back.