为什么 std::stack 默认使用 std::deque ? [英] Why does std::stack use std::deque by default?

问题描述

因为在堆栈中使用容器所需的唯一操作是:

Since the only operations required for a container to be used in a stack are:

• 返回()
• push_back()
• pop_back()

为什么它的默认容器是双端队列而不是向量?

Why is the default container for it a deque instead of a vector?

不要在 front() 之前给 deque 重新分配一个元素缓冲区，以便 push_front() 是一个有效的操作?这些元素是不是被浪费了，因为它们永远不会在堆栈的上下文中使用?

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?

如果以这种方式使用双端队列而不是向量没有开销，为什么priority_queue 的默认值是向量而不是双端队列?(priority_queue 需要 front()、push_back() 和 pop_back() - 本质上与堆栈相同)

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)

根据以下答案更新:

看起来deque通常的实现方式是固定大小数组的可变大小数组.这使得增长速度比向量(需要重新分配和复制)更快，因此对于像堆栈这样的所有关于添加和删除元素的东西，双端队列可能是更好的选择.

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 需要大量索引，因为每次删除和插入都需要您运行 pop_heap() 或 push_heap().这可能使 vector 成为更好的选择，因为无论如何添加元素仍然是摊销常数.

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.

推荐答案

随着容器的增长，向量的重新分配需要将所有元素复制到新的内存块中.增长双端队列会分配一个新块并将其链接到块列表 - 不需要副本.

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.

这篇关于为什么 std::stack 默认使用 std::deque ?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！