我正在实现一种拓扑排序的变体，需要一个结构来保存没有入边的元素。无论是使用queue还是stack都可以完成这个任务，因为它们取出元素的顺序并不重要。问题是：它们中有一个比另一个快吗？
STL队列和STL栈哪个更快？
4
- kinokijuf
1
2回答：很可能不是。
最好的答案：尝试两种并测试。
最棒的答案：只使用一个，不必担心。 - s3rius
5个回答
3
queue和stack都是容器适配器，而不是完整的容器。
默认情况下，stack和queue都是基于std::deque实现的，如果您没有更改此设置，则它们应该具有相似的性能。
这真的取决于您正在编写的应用程序类型，您可以选择基础容器，以最大程度地受益于您最需要的操作。
- taocp
3
回答你的主要问题：我不知道。我认为它们中没有一个显着更快，因为对于 std::deque（堆栈和队列的默认内部容器），push_back 和 push_front（以及 pop_back 和 pop_front）是对称的。没有一个应该更快。然而，我建议使用普通的 std::vector，并使用 push_back 和 pop_back，或等效地：
std::stack<T, std::vector<T>>
请点击 这里 查看为何栈默认使用双端队列。
- Armen Tsirunyan
1
虽然queue和stack在性能上并没有太大差异，但它们显然会引起不同的节点访问顺序。其中一个可能比另一个更符合缓存友好的顺序，这取决于节点在内存中的布局方式。
- harold
1
他们都有恒定的复杂度...你只需要计时来确定任何一个常数是否更高。
http://www.cplusplus.com/reference/stack/stack/pop/
http://www.cplusplus.com/reference/queue/queue/pop/
- Aditya Sihag
-3
队列和栈是不同的。队列是先进先出，而栈是后进先出。
- aguyngueran
4
1很抱歉，这并没有回答 OP 的问题。 - taocp
我同意宋旺的观点。我只需要一个临时对象存储器。 - kinokijuf
因此，请使用普通向量。在这里使用堆栈或队列会令人困惑。 - aguyngueran
@aguyngueran 向量由于复制操作而产生了巨大的开销。在客户端应用程序中，这通常不会引起注意，但在服务器端和其他特定应用程序中可能会对性能产生巨大影响。向量并非适用于所有情况的容器。如果你想存储临时列表，向量是很好的选择。但如果你想存储临时单个对象，它将对性能产生影响。 - Pijusn
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接