std::list::push_back() 的运行时间复杂度

Question

以下代码的运行时复杂度是多少

std::list<int> a;
a.push_back(1); //initialize
a.push_back(2);
a.push_back(3);
std::list<int>::iterator i = a.begin();
std::cout<<*(++i); // displays 2
std::cout<<*(++i); // displays 3

我目前正在编写一个数据挖掘程序，我需要注意它的时间副性能。我只是有一个疑问（我以前没有这样的疑问，因为我不关心早期程序的时间复杂度，因为它们很简单）。因此，从更安全的角度来看，我想询问向列表 a 添加元素的实际时间复杂度。上面的指针“i”的行为就像一个数组，这让我怀疑它是否真的是一个数组或一个重载了 ++ 和 * 运算符的对象。

如果 'i' 是一个数组，那么 std::list::push_back() 的时间复杂度应该是 O(n)，这对于我的情况来说是不需要的。但如果不是，您能否解释一下运算符 * 和 ++ 所采用的算法，以便可以确定它们的时间复杂度？对于我的情况是否建议使用列表？（如果 'i' 不是数组，则可以安全地假设 std::list::push_back() 的时间复杂度为 O(1) ）

抱歉，我以前的问题版本不太可读

Answer 1

所以应该有一个指针数组，每个指针都指向链表中的每个节点。每次我们调用push_back()成员函数时，指针数组都应该被清除并重新分配；你不这么认为吗？

不，我不这么认为。标准中没有提到这样的数组，并且在列表容器中包含这样的数组会很奇怪。

旁注：如果存在这样的数组，则增长它的时间复杂度为 O(n)，而不是 O(n^2)。如果它的大小在满时乘以，则可以使插入分摊 O(1)，例如如何std::vector做。