std::stack 在不同容器上的实现有什么实际区别？

Question

实施 std::stack

时

有几个选项，例如：

   // stack with default underlying deque
   std::stack< int > intDequeStack;   

   // stack with underlying vector
   std::stack< int, std::vector< int > > intVectorStack;

   // stack with underlying list
   std::stack< int, std::list< int > > intListStack;

定义 std::stack 我有什么优点和缺点在不同的容器上，当我从中得到的只是相同的操作“push、pop 和 top”？

换句话说：双端队列堆栈和向量堆栈以及列表堆栈之间有什么区别，为什么我要选择双端队列以外的任何东西？

Answer 1

堆栈继承了底层容器的性能特征。

std::vector 对于最大大小可能不同的堆栈来说是一个糟糕的选择。堆栈上的每个 push 都可能需要在向量中进行大量重新分配。向量也永远不会收缩，除非明确要求，所以如果堆栈变大然后收缩，额外的内存将永远不会被释放（直到堆栈被销毁）。然而，矢量在它们和存储的数据之间只有一层间接。

因此： 如果您知道您的堆栈将达到的最大大小并且该大小相对较小，您在 [=33] 上调用 reserve() 的向量=]2 在所有情况下都可能比列表或双端队列更快；它具有非常好的数据局部性，并且访问元素的间接级别更少。
std::list是一个链表所以出栈的时候栈会有两层间接¹，总是会用到多少它需要的内存。推送时没有昂贵的重新分配，但它的数据局部性很差，因为每个节点都可以分配到堆中的任何位置；从堆栈处理大量数据将无法有效地使用各种 CPU 内存缓存，因为每个 pop 可能需要跳转到堆中完全不同的某个地方。
std::deque 通过在结构（通常是链表）中维护短数组的集合，结合了两者的某些方面。因此，项目集群将具有良好的数据局部性，并且结构可以按需增长和收缩而不会大惊小怪，因为数组永远不会重新分配——如果它需要更多 space，它会分配一个新数组并添加它到结构的beginning/end。它是 vector 和 list 之间的一个很好的中间地带，这就是为什么它是默认值。

¹ 数据存在一级间接寻址，但为了删除最后一个元素，链表需要对前一个节点的另一个间接寻址以清除下一个-指针。

²注意在构建容器的时候需要移动vector。复制向量并不一定会保留其容量。例如，您可以使用这个助手：

template <typename T>
std::stack<T, std::vector<T>> vector_stack(
    typename std::vector<T>::size_type capacity
) {
    std::vector<T> vec;
    vec.reserve(capacity);

    return std::stack<T, std::vector<T>>{std::move(vec)};
}

std::stack 在不同容器上的实现有什么实际区别？

std::stack implementation on different containers what is the actual difference?

c++

stl

containers

stdstack