什么是std :: queue :: size的Big O()顺序？

Question

关于成员函数std::queue的复杂性,该类尚不清楚size.它似乎基于当时使用的数据结构实现.

人们会认为这size将是O(C),但它是完全可能的它是O(N).显然,我可以保持自己的体型,但我宁愿打电话size.

(问题修改):既然deque是默认容器,什么是std :: deque :: size()的O()？

Answer 1

至少从C++ 11开始,复杂性std::queue::size 是恒定的:O(1).

std::queue根据§23.6.3.1/ 1 的基础容器必须符合SequenceContainer继承要求的基础容器Container,这反过来又按照§23.2.1要求成员函数来保证这一点.size有一个恒定的时间复杂性.

@juanchopanza是的,`forward_list`是一个奇怪的鸭子.但它无法满足`queue`的底层容器的要求,因为它没有`push_back`' (3认同)
我不认为这是有保障的. (2认同)

Answer 2

总结一下这里的非常好的答案：

C++11：O(1)（@Jeffrey）
C++98：未强制执行，需要基于容器类做实验
带默认容器的 C++98：std::queue 的默认容器是 std::deque，它通过减去两个迭代器来计算大小，这不是， O(1)但至少是O(C)。（@juanchopanza）

因此，如果需要确保 C++98 中 size() 的 O(1) 性，则必须保留自己的计数。

如果可以的话，我想站起来感谢 C++11 小组弥补了这个可怕的规范漏洞。许多语言/库（例如 Scala）都煞费苦心地定义运算符的 BIG-O。鉴于 C++ 的主要用例是性能，我发现这种规范的缺乏令人惊讶。必须检查标头代码以确定std类的性能特征是完全不可接受的。