为什么std::list.size()具有恒定的复杂度？

Question

在学校，我学到链表由元素组成，并且链表的一个缺点是查找大小具有线性复杂性，因为您必须遍历每个元素并进行计数。然而，我注意到在C++11中，std::list.size()具有恒定的复杂性。这怎麽可能？

Answer 1

可能只是保留了一个成员变量，每当你添加或删除元素时，该变量就会更新。或者，如果将两个列表合并在一起，只需将它们的计数相加即可。

这样你就不需要遍历整个列表来计算元素数了。