c++ - std::queue::size 的大 O() 顺序是什么？

Question

std::queue 类在size 成员函数的复杂性方面并不清楚。它似乎是基于当时使用的数据结构实现。

一个人会假设 size 是O(C)，但它完全有可能是O(N )。显然，我可以保持自己的大小，但我宁愿只调用 size。

(修改问题):既然deque是默认容器，那么std::deque::size()的O()是多少？

Answer 1

至少自 C++11 以来，std::queue::size 的复杂度 is constant :O(1)。

根据 §23.6.3.1/1，std::queue 的底层容器必须满足 SequenceContainer 的要求，这一点得到了保证。 , 继承了 Container 的要求，反过来，根据 §23.2.1，要求成员函数 size 具有恒定的时间复杂度。