在c++11之前，std::list::size()为o(n)时间复杂度，因标准未强制缓存大小，多数实现需遍历链表计数；而c++11起要求o(1)，通过维护内部计数器实现。
std::list::size() 在 C++11 之前为什么慢？
在 C++11 之前，std::list::size() 不是常数时间操作——它必须遍历整个链表计数，时间复杂度为 O(n)。这和 std::vector::size() 形成鲜明对比，后者始终是 O(1)。如果你在循环里反复调用 my_list.size()（比如做边界判断），性能会明显退化。
原因在于旧标准未强制要求维护内部计数器，实现可自由选择是否缓存大小。多数老编译器（如 GCC 4.8 以前、MSVC 2013 及更早）默认不缓存，每次调用都走遍历逻辑。
- 检查方式：查阅你所用 STL 版本的
std::list实现源码，或运行简单 benchmark（对含 10 万节点的 list 调用 1000 次size()，对比std::vector同样操作） - 典型错误场景：
for (int i = 0; i —— 即使你只是想“遍历”，也千万别这么写 - 替代做法：改用迭代器范围循环，或提前缓存结果：
const auto n = lst.size(); for (int i = 0; i
C++11 及以后 size() 是 O(1)，但仍有陷阱
C++11 标准明确要求 std::list::size() 必须是常数时间，所有合规实现（GCC 4.9+、Clang 3.4+、MSVC 2015+）都维护了内部计数器。但这不意味着你可以高枕无忧。
问题出在「自定义分配器」或「非标准容器封装」上：某些第三方 wrapper（比如带调试计数的 proxy list）可能重载了 size() 但没同步更新计数器；或者你用了自定义 allocator 且其构造/析构未正确触发计数增减（极少见，但调试时值得怀疑）。
- 验证是否真为 O(1)：在 release 模式下用 perf 或 VTune 观察
size()调用耗时是否随 list 长度增长而变化 - 避免依赖隐式转换：不要写
if (lst.size())来判空——虽然合法，但语义模糊；直接用if (!lst.empty())更清晰、无开销 - 注意迭代器失效场景：
splice()、merge()等操作不会导致size()错误，但若手动绕过接口直接修改节点指针（比如裸指针操作），计数器不会自动更新
什么时候不该用 size()，而该用 empty()？
哪怕 size() 是 O(1)，只要目的只是判断容器是否为空，empty() 就是更优解——它语义明确、无计算开销、且对所有标准容器都是 O(1)。
尤其在模板代码或泛型算法中：if (c.size() == 0) 可能触发不必要的整数比较，而 if (c.empty()) 直接返回布尔值，且部分容器（如 std::forward_list）甚至没有 size() 成员函数（C++11 中它是可选的）。
- 错误写法：
while (my_list.size() > 0) { /* pop_front */ } - 正确写法：
while (!my_list.empty()) { my_list.pop_front(); } - 注意：
empty()和size() == 0在逻辑上等价，但前者是约定俗成的惯用法，编译器也可能对其做额外优化
手写计数器？通常没必要，除非你控制整个生命周期
有人为了“绝对可控”会自己维护一个 int count，每次 push_back()、erase() 后手动增减。这种做法在绝大多数情况下得不偿失。
它引入了额外状态、破坏了封装性，并极易因遗漏某处修改（比如异常路径下的 pop_back() 失败）导致计数错乱。STL 的 size() 经过多年验证，可靠性远高于手写逻辑。
- 唯一合理场景：你在实现一个轻量级、无异常保证的嵌入式 list，且编译器不支持 C++11（比如某些 ARM GCC 4.6 工具链）
- 如果真要这么做，务必把计数器声明为
mutable并只在 const 成员函数内读取，否则违反 const 正确性 - 切勿混合使用：一旦引入手写计数器，就彻底弃用
size()，否则两者必然不一致
实际项目里，最常被忽略的是：别在 hot path 上反复调用 size() 做条件判断，哪怕它是 O(1)。CPU 分支预测失败的成本有时比一次加法还高，而 empty() 或预存变量能消除这类不确定性。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
