blocks|key|3265871|text|至少自C%2B%2B11以来，std::queue::size+is+：O(1)的复杂性。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|3265872|保证这一点的事实是，std::queue的底层容器(按照第23.6.3.1/1节)必须符合SequenceContainer的要求，后者继承了Container的要求，而后者又根据第23.2.1节要求成员函数size具有恒定的时间复杂度。|3265873|entityMap|0|LINK|mutability|MUTABLE|url|http://en.cppreference.com/w/cpp/container/queue/size|1|http://en.cppreference.com/w/cpp/concept/SequenceContainer|2|http://en.cppreference.com/w/cpp/concept/Container^0|B|G|S|3|0|0|A|A|19|H|1Z|9|2W|4|19|H|1|1Z|9|2|0^^$0|@$1|2|3|4|5|6|7|T|8|@$9|U|A|V|B|C]]|D|@$9|W|A|X|1|Y]]|E|$]]|$1|F|3|G|5|6|7|Z|8|@$9|10|A|11|B|C]|$9|12|A|13|B|C]|$9|14|A|15|B|C]|$9|16|A|17|B|C]]|D|@$9|18|A|19|1|1A]|$9|1B|A|1C|1|1D]]|E|$]]|$1|H|3|-4|5|6|7|1E|8|@]|D|@]|E|$]]]|I|$J|$5|K|L|M|E|$N|O]]|P|$5|K|L|M|E|$N|Q]]|R|$5|K|L|M|E|$N|S]]]]

At least since C++11, the complexity of <code>std::queue::size</code> <a href="http://en.cppreference.com/w/cpp/container/queue/size" rel="nofollow">is constant</a>: O(1). 

This is guaranteed by the fact that the underlying container of <code>std::queue</code>, as per §23.6.3.1/1, have to fit the requirements of <a href="http://en.cppreference.com/w/cpp/concept/SequenceContainer" rel="nofollow"><code>SequenceContainer</code></a>, that inherits the requirement of <a href="http://en.cppreference.com/w/cpp/concept/Container" rel="nofollow"><code>Container</code></a>, which, in turn, as per §23.2.1, requires the member function <code>size</code> to have a constant time complexity.

blocks|key|802242|text|复杂度为常数O(1)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|802243|常量(调用基础容器的大小)。http://www.cplusplus.com/reference/queue/queue/size/|offset|length|802244|entityMap|0|LINK|mutability|MUTABLE|url|http://www.cplusplus.com/reference/queue/queue/size/^0|0|E|1G|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@$D|P|E|Q|1|R]]|A|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|M]]]]

The complexity is constant O(1).

Constant (calling size on the underlying container).
<a href="http://www.cplusplus.com/reference/queue/queue/size/" rel="nofollow">http://www.cplusplus.com/reference/queue/queue/size/</a>

blocks|key|802283|text|它可能取决于您使用的实现，最好自己检查一下。希望检查头文件没有那么困难。尽管较新的标准要求它应该是不变的，但这是唯一确定的方法。一个值得注意的例子是，gcc的libstdc%2B%2B对于std::list仍然有O(n)。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|802284|entityMap^0|2I|9|0^^$0|@$1|2|3|4|5|6|7|H|8|@$9|I|A|J|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|K|8|@]|D|@]|E|$]]]|G|$]]

It may depend on the implementation you use, and it's best to check this yourself. Hopefully inspecting header files are not that hard. Even though newer standards mandate that it should be constant, that's the only way to be sure. For one example worth noting, gcc's libstdc++ still has O(n) for <code>std::list</code>.

blocks|key|802311|text|以下是一个很好的答案：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|802312|C%2B%2B11：O(1)+(@Jeffrey)|unordered-list-item|offset|length|style|CODE|802313|C%2B%2B98:非强制的，需要基于容器类进行实验|802314|带有默认容器的C%2B%2B98：：queue的默认容器是std::deque，它通过减去两个迭代器来计算大小，这两个迭代器不是+O(1)，而是至少O(C)。(@juanchopanza)|BOLD|802315|802316|802317|因此，如果需要确保大小为O(1)的-ness在C%2B%2B98中，则必须保持自己的计数。|802318|如果可以的话，我想踩一下我的soap盒，感谢C%2B%2B11组关闭了这个可怕的规范孔。许多语言/库(如Scala)都非常努力地定义操作符的大-O。考虑到C%2B%2B的主要用例是性能，我觉得缺乏规范令人吃惊。必须检查头代码以确定std类的性能特性，这是完全不能接受的。|802319|entityMap^0|0|6|4|0|0|1P|4|1Y|4|24|D|0|0|0|0|2Z|3|0^^$0|@$1|2|3|4|5|6|7|V|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|W|8|@$E|X|F|Y|G|H]]|9|@]|A|$]]|$1|I|3|J|5|D|7|Z|8|@]|9|@]|A|$]]|$1|K|3|L|5|D|7|10|8|@$E|11|F|12|G|H]|$E|13|F|14|G|H]|$E|15|F|16|G|M]]|9|@]|A|$]]|$1|N|3|-4|5|6|7|17|8|@]|9|@]|A|$]]|$1|O|3|-4|5|6|7|18|8|@]|9|@]|A|$]]|$1|P|3|Q|5|6|7|19|8|@]|9|@]|A|$]]|$1|R|3|S|5|6|7|1A|8|@$E|1B|F|1C|G|M]]|9|@]|A|$]]|$1|T|3|-4|5|6|7|1D|8|@]|9|@]|A|$]]]|U|$]]

To sum up the very good answers here:

<ul>
<li>C++11: <code>O(1)</code> (@Jeffrey)</li>
<li>C++98: unenforced, need to do experimentation based on the container class</li>
<li>C++98 with default container: the default container for std::queue
is std::deque, which calculates size by subtracting two
iterators, which is not <code>O(1)</code>, but at least <code>O(C)</code>. (@juanchopanza)</li>
</ul>

Thus, if you need to ensure O(1)-ness of size() in C++98, you must keep your own count.

If I might, I would like to step on my soap box and thank the C++11 group for closing this horrendous specification hole. Many languages/libraries (such as Scala) take great pains to define the BIG-O of an operator. Given that the main use case of C++ is performance, I find this lack of specification amazing. It is completely unacceptable that one should have to inspect header code to determine performance characteristics of std classes.

blocks|key|256195|text|std::queue::size精确地在C%2B%2B11+23.6.3.1/1中指定：|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|256196|size_type+size()+const+{+return+c.size();+}|code-block|syntax|javascript|256197|其中c是一个protected数据成员，其类型是第二个模板参数的类型。因此，它的复杂度正是该模板参数的size成员函数的复杂性。默认的是std::deque<T>，其中T是传递给std::queue的第一个模板参数，它具有默认的O(1)复杂性要求，除非另有规定(23.2.1中的表96+)。|256198|entityMap^0|0|G|0|0|2|1|6|9|1F|4|1W|D|2C|1|2H|A|0^^$0|@$1|2|3|4|5|6|7|O|8|@$9|P|A|Q|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|R|8|@]|D|@]|E|$I|J]]|$1|K|3|L|5|6|7|S|8|@$9|T|A|U|B|C]|$9|V|A|W|B|C]|$9|X|A|Y|B|C]|$9|Z|A|10|B|C]|$9|11|A|12|B|C]|$9|13|A|14|B|C]]|D|@]|E|$]]|$1|M|3|-4|5|6|7|15|8|@]|D|@]|E|$]]]|N|$]]

<code>std::queue::size</code> is specified exactly in C++11 23.6.3.1/1:

<pre><code>size_type size() const { return c.size(); }
</code></pre>

where <code>c</code> is a <code>protected</code> data member whose type is that of the second template parameter. Ergo, its complexity is exactly that of the <code>size</code> member function of said template parameter. The default is <code>std::deque&lt;T&gt;</code> - where <code>T</code> is the first template parameter passed to <code>std::queue</code> - which has the default O(1) complexity requirement common to all containers unless otherwise specified (per Table 96 in 23.2.1).

The <code>std::queue</code> class is unclear as to the complexity of the <code>size</code> member function. It appears to be based on the data structure implementation used at the time.

One would assume that <code>size</code> would be <code>O(C)</code>, but it's totally possible for it to be <code>O(N)</code>. Obviously, I can keep my own size, but I would rather just call <code>size</code>.

(Question modified): since <code>deque</code> is the default container, what is O ( ) of std::deque::size()?

what is the Big O( ) order of std::queue::size?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

std::queue类不清楚size成员函数的复杂性。它似乎是基于当时使用的数据结构实现。人们会假设size将是O(C)，但它完全有可能是O(N)。显然，我可以保持自己的尺寸，但我宁愿打电话给size。(问题修改)：由于deque是默认容器，那么std::deque::size()的O()是什么？

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

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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