c++ - 为什么 std::list.size() 不是恒定时间？

Question

这个问题在这里已经有了答案:

Is list::size() really O(n)? (8 个回答)

关闭 4年前。

这段代码运行了 0.012 秒:

 std::list<int> list;
 list.resize(100);
 int size;
 for(int i = 0 ; i < 10000; i++)
     size = list.size();

这个9.378秒:

 std::list<int> list;
 list.resize(100000);
 int size;
 for(int i = 0 ; i < 10000; i++)
     size = list.size();

在我看来，有可能以这种方式实现 std::list，该大小将存储在私有(private)变量中，但根据此，每次调用 size 时都会再次计算它。谁能解释一下为什么？

Answer 1

常数时间size()和常数时间list.splice有冲突。委员会选择支持 splice。

当您在两个列表之间拼接节点时，您必须计算移动的节点以更新两个列表的大小。仅仅通过改变一些内部指针，这就剥夺了拼接节点的很多优势。

---

正如评论中所指出的，C++11 改变了这一点，放弃了 O(1) 用于 splice 的一些罕见(？)用途:

void splice(const_iterator position, list& x, const_iterator first, const_iterator last);
void splice(const_iterator position, list&& x, const_iterator first, const_iterator last);

Complexity: Constant time if &x == this; otherwise, linear time.