为什么 std::stack 默认使用 std::deque ？
由于在堆栈中使用容器所需的唯一操作是：
- back()
- push_back()
- pop_back()
为什么它的默认容器是双端队列而不是向量？
双端队列重新分配不会在 front() 之前提供元素缓冲区，以便 push_front() 是一个有效的操作吗？ 这些元素是否被浪费了，因为它们永远不会在堆栈上下文中使用？
如果以这种方式使用双端队列而不是向量没有开销，为什么priority_queue的默认值也是向量而不是双端队列？ （priority_queue 需要 front()、push_back() 和 pop_back() - 本质上与堆栈相同）
根据以下答案进行更新：
看来双端队列通常实现的方式是可变大小固定大小数组的数组。 这使得增长速度比向量（需要重新分配和复制）更快，因此对于像堆栈这样只需要添加和删除元素的东西，双端队列可能是更好的选择。
priority_queue 需要大量索引，因为每次删除和插入都需要运行 pop_heap() 或 push_heap()。 这可能使向量成为更好的选择，因为无论如何添加元素仍然摊销常数。
Since the only operations required for a container to be used in a stack are:
- back()
- push_back()
- pop_back()
Why is the default container for it a deque instead of a vector?
Don't deque reallocations give a buffer of elements before front() so that push_front() is an efficient operation? Aren't these elements wasted since they will never ever be used in the context of a stack?
If there is no overhead for using a deque this way instead of a vector, why is the default for priority_queue a vector not a deque also? (priority_queue requires front(), push_back(), and pop_back() - essentially the same as for stack)
Updated based on the Answers below:
It appears that the way deque is usually implemented is a variable size array of fixed size arrays. This makes growing faster than a vector (which requires reallocation and copying), so for something like a stack which is all about adding and removing elements, deque is likely a better choice.
priority_queue requires indexing heavily, as every removal and insertion requires you to run pop_heap() or push_heap(). This probably makes vector a better choice there since adding an element is still amortized constant anyways.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
随着容器的增长，向量的重新分配需要将所有元素复制到新的内存块中。 增长双端队列会分配一个新块并将其链接到块列表 - 不需要副本。
当然，如果您愿意，您可以指定使用不同的支持容器。 因此，如果您知道堆栈不会增长太多，请告诉它使用向量而不是双端队列（如果这是您的偏好）。
As the container grows, a reallocation for a vector requires copying all the elements into the new block of memory. Growing a deque allocates a new block and links it to the list of blocks - no copies are required.
Of course you can specify that a different backing container be used if you like. So if you have a stack that you know is not going to grow much, tell it to use a vector instead of a deque if that's your preference.
请参阅 Herb Sutter 的第 54 周大师，了解向量和双端队列的相对优点，其中任何一个都可以做。
我想priority_queue和queue之间的不一致只是因为不同的人实现了它们。
See Herb Sutter's Guru of the Week 54 for the relative merits of vector and deque where either would do.
I imagine the inconsistency between priority_queue and queue is simply that different people implemented them.