由于要在堆栈中使用容器所需的唯一操作是:
- 背部()
- 推回()
- pop_back()
为什么它的默认容器是双端队列而不是向量?
deque 重新分配是否在 front() 之前提供元素缓冲区,以便 push_front() 是一种有效的操作?这些元素是不是被浪费了,因为它们永远不会在堆栈的上下文中使用?
如果以这种方式使用双端队列而不是向量没有开销,为什么priority_queue 的默认值也是向量而不是双端队列?(priority_queue 需要 front()、push_back() 和 pop_back() - 与堆栈基本相同)
根据以下答案更新:
看起来 deque 通常实现的方式是固定大小数组的可变大小数组。这使得增长比向量(需要重新分配和复制)更快,所以对于像堆栈这样的东西,它都是关于添加和删除元素的,deque 可能是一个更好的选择。
priority_queue 需要大量索引,因为每次删除和插入都需要运行 pop_heap() 或 push_heap()。这可能使向量成为更好的选择,因为无论如何添加元素仍然是摊销常数。