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

Question

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

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

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

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

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

Answer 1

从 C++11 开始，size成员函数的复杂性对于所有标准容器都是恒定的。

std::forward_list它是单向链表数据结构的实现，不提供size成员函数。可以使用迭代器在线性时间内计算大小。

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