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

So there should be an array of pointers each pointing to each node in the linked list. Each time we call the push_back() member function, the array of pointers should be cleared and reallocated; don't you think so?

不，我不这么认为。标准中没有任何地方提到这样的数组，在 list 容器中有这样的数组会很奇怪。

作为旁注：如果存在这样的数组，增长它将是 O(n)，而不是 O(n^2)。如果它的大小在它已满时成倍增加，这可能会使插入分摊 O(1)，例如 std::vector 会怎么做。

Answer 2

std::list 通常是双向链表实现而不是数组 implementation.In 其他方式 std::list 是双向链表的更高级别抽象。

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

run time complexity of std::list::push_back()

c++

arrays

list

c++11

time-complexity