std::list的size()函数调用复杂度是O(1)还是O(n)？

核心结论 #

std::list::size() 的时间复杂度在不同C++标准版本中有明确差异：

• C++11及之后：标准强制要求该函数的复杂度为O(1)。实现必须维护一个内部元素计数器，在insert()、erase()、clear()、push_back()等所有修改元素数量的操作中同步更新计数器，调用size()时直接返回该值即可。
• C11之前（C98/C++03）：标准未对size()的复杂度做硬性约束，编译器厂商可自由选择实现方式——部分实现会维护计数器（O(1)），另一些则需要遍历整个链表统计元素总数（O(n)）。

两种说法的由来 #

这是C标准迭代导致的历史差异：早期标准仅要求std::list符合双向链表的特性，未统一size()的实现逻辑，因此出现了两种不同的实现思路；C11为了消除这种行为差异，明确将std::list::size()的复杂度定为O(1)，同时强制所有修改链表元素数量的操作必须正确更新内部计数器。

快速验证当前实现的方法 #

你可以通过简单的测试代码判断当前环境下的size()实现复杂度：

#include <list>
#include <chrono>
#include <iostream>

int main() {
    std::list<int> large_list;
    // 构造一个包含百万级元素的链表
    for (int i = 0; i < 1000000; ++i) {
        large_list.push_back(i);
    }

    auto start = std::chrono::high_resolution_clock::now();
    // 重复调用size()多次，观察耗时
    for (int i = 0; i < 1000; ++i) {
        [[maybe_unused]] auto sz = large_list.size();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

    std::cout << "1000次size()调用耗时：" << elapsed.count() << " 微秒\n";
    return 0;
}

如果耗时在几微秒级别，说明是O(1)实现；如果耗时随链表长度线性增长，则是O(n)的遍历实现。

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