C++11中STL list的size()复杂度为何为O(1)？其计算方式是什么？为何双向链表统计大小无需遍历（而非O(n)）？

嘿，这个问题问得特别精准——毕竟咱们学数据结构的时候，双向链表统计元素个数确实得从头遍历到尾，时间复杂度是O(n)，那C++11里的std::list为啥能打破这个常规呢？咱们拆解开来聊：

std::list::size()的具体计算方式 #

在符合C++11标准的STL实现里，std::list内部会维护一个专门的成员变量（不同编译器的命名可能不一样，比如GCC里叫_M_size，MSVC里可能是_MySize），这个变量的唯一作用就是实时记录链表当前的元素总数。

当你调用size()函数时，它做的事情非常简单：直接返回这个成员变量的值。没有遍历操作，没有循环计算，就是一次普通的内存读取，所以时间复杂度是实打实的O(1)。

为什么能实现O(1)的时间复杂度？ #

这得从C++标准的演变说起：

• 在C++11之前，标准并没有强制要求std::list::size()必须是常数时间实现，所以早期的一些STL版本（比如旧版GCC）确实是每次调用size()都遍历整个链表来计数，时间复杂度O(n)。
• 到了C++11，标准委员会修改了规则，明确要求std::list的size()必须是O(1)实现。为了满足这个要求，STL的开发者们给链表结构体加了这个计数变量，并且在所有会改变元素数量的操作中同步更新它：
  • 调用push_back()/push_front()：计数变量+1
  • 调用pop_back()/pop_front()：计数变量-1
  • 调用insert()：根据插入的元素数量，给计数变量加上对应数值
  • 调用erase()：根据删除的元素数量，给计数变量减去对应数值
  • 调用clear()：直接把计数变量设为0
  • 像resize()、swap()这类操作，也会同步调整计数变量的值

这种实现的代价是每次修改元素数量时多了一步变量更新，但这个开销微乎其微，相比每次调用size()都要遍历大链表的成本来说，完全是划算的——尤其是当链表元素很多的时候，这个优化能节省大量时间。

内容的提问来源于stack exchange，提问作者sky_walker18