102

由于要在堆栈中使用容器所需的唯一操作是:

  • 背部()
  • 推回()
  • pop_back()

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

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

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


根据以下答案更新:

看起来 deque 通常实现的方式是固定大小数组的可变大小数组。这使得增长比向量(需要重新分配和复制)更快,所以对于像堆栈这样的东西,它都是关于添加和删除元素的,deque 可能是一个更好的选择。

priority_queue 需要大量索引,因为每次删除和插入都需要运行 pop_heap() 或 push_heap()。这可能使向量成为更好的选择,因为无论如何添加元素仍然是摊销常数。

4

2 回答 2

80

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

当然,如果您愿意,您可以指定使用不同的支持容器。因此,如果您有一个知道不会增长太多的堆栈,请告诉它使用向量而不是双端队列(如果这是您的偏好)。

于 2008-09-19T14:58:03.760 回答
12

有关vector 和 deque 的相对优点,请参阅 Herb Sutter第 54 周的 Guru 。

我想priority_queue和queue之间的不一致只是不同的人实现了它们。

于 2008-09-19T15:28:25.403 回答