为什么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:

• back（）


• push_back（）


• pop_back（）

对于它是一个deque而不是一个向量？

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

不要deque重新分配在front（）之前给元素一个缓冲区，这样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?

如果没有使用deque的开销，而不是向量，为什么是priority_queue的默认向量不是deque也？ （priority_queue需要front（），push_back（）和pop_back（） - 基本上与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)

strong>根据以下答案更新：

Updated based on the Answers below:

似乎deque通常实现的方式是一个固定大小数组的可变大小数组。这使得增长速度比一个向量（这需要重新分配和复制），所以对于像堆栈这样的所有关于添加和删除元素，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（）。

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.

推荐答案

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

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.

当然，您可以指定使用不同的后端容器喜欢。所以如果你有一个堆栈，你知道不会增长太多，告诉它使用一个向量而不是一个deque如果这是你的偏好。

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屋！