c++ - 大小的时间复杂度是多少？

Question

我正在研究不同 STL 容器的各种操作的复杂性。通过 different question在这个网站上，我找到了这张图表。

website link



我注意到这张图表中缺少的一项操作是尺寸操作。
我想，如果知道 .begin 和 .end 的复杂性，也可以计算大小的复杂性。但那些也不见了。

我在 this 中找到了类似于我正在寻找的答案问题，但这个是针对 Java 的，所以它没有涵盖所有 STL 容器，它只为一些给定的数据类型定义了大小的大 O。

有谁知道各种容器的 .size 操作的复杂性，或者有人可以告诉我在哪里可以找到这些复杂性。任何帮助将不胜感激。

另外，如果我的问题措辞错误和/或偏离主题。不要犹豫，建议编辑。

Answer 1

从 C++11 开始，size 的复杂性成员函数对于所有标准容器都是常量。
std::forward_list这是单向链表数据结构的实现不提供 size成员函数。可以使用迭代器在线性时间内计算大小。

除了标准的 C++ 容器之外，所有数据结构都可以使用单独存储的大小变量进行扩充，以实现这种恒定的复杂性，但代价是插入和删除操作的恒定开销很小。 Array 的特殊之处在于它不需要任何额外的开销，假设迭代器到 end 被存储。