std::queue::size的Big O( )顺序是什么？
std::queue类不清楚size成员函数的复杂性。它似乎是基于当时使用的数据结构实现。
人们会假设size将是O(C)，但它完全有可能是O(N)。显然，我可以保持自己的尺寸，但我宁愿打电话给size。
(问题修改)：由于deque是默认容器，那么std::deque::size()的O()是什么？
回答 5
Stack Overflow用户
发布于 2014-02-11 22:59:31
以下是一个很好的答案：
- C++11：
O(1)(@Jeffrey) - C++98:非强制的，需要基于容器类进行实验
- 带有默认容器的C++98：：queue的默认容器是std::deque，它通过减去两个迭代器来计算大小，这两个迭代器不是
O(1)，而是至少O(C)。(@juanchopanza)
因此，如果需要确保大小为O(1)的-ness在C++98中，则必须保持自己的计数。
如果可以的话，我想踩一下我的soap盒，感谢C++11组关闭了这个可怕的规范孔。许多语言/库(如Scala)都非常努力地定义操作符的大-O。考虑到C++的主要用例是性能，我觉得缺乏规范令人吃惊。必须检查头代码以确定std类的性能特性，这是完全不能接受的。
Stack Overflow用户
发布于 2014-02-11 21:59:58
至少自C++11以来，std::queue::size is ：O(1)的复杂性。
保证这一点的事实是，std::queue的底层容器(按照第23.6.3.1/1节)必须符合SequenceContainer的要求，后者继承了Container的要求，而后者又根据第23.2.1节要求成员函数size具有恒定的时间复杂度。
Stack Overflow用户
发布于 2014-02-12 07:26:48
std::queue::size精确地在C++11 23.6.3.1/1中指定：
size_type size() const { return c.size(); }其中c是一个protected数据成员，其类型是第二个模板参数的类型。因此，它的复杂度正是该模板参数的size成员函数的复杂性。默认的是std::deque<T>，其中T是传递给std::queue的第一个模板参数，它具有默认的O(1)复杂性要求，除非另有规定(23.2.1中的表96 )。
https://stackoverflow.com/questions/21713940
复制相似问题
腾讯云开发者
