c++ - 为什么STL集合大小的复杂度是O(1)，它是如何计算的？

Question

集合在内部被维护为平衡二叉树。计算集合大小的复杂度为 O(1)。大小是如何计算的，它是否维护任何变量来存储大小。

Answer 1

规范仅声明所有 set(实际上，所有容器)都有一个 size() 成员函数，该函数需要常数时间。除此之外，您的标准库的特定版本的实现者可能已经按照他们的意愿完成了它，只要它是 O(1)。

在实践中，大小很可能存储在一个成员变量中，该成员变量随着项目的插入或删除而更新； PiotrNycz 的实现者已经做到了这一点。