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

当实施一个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”？

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

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

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

  Therefore: If you know the maximum size your stack will reach and that size is relatively small, a vector that you've called reserve() on² will likely be faster in all cases than either list or deque; it has very good data locality and one fewer levels of indirection to access an element.

• std::list is a linked list so the stack will have two levels of indirection when popping¹, and it will always use exactly how much memory it needs. There are no expensive reallocations on push, but it will have poor data locality since each node can be allocated anywhere in the heap; processing large amounts of data from the stack will not be able to effectively use the various CPU memory caches since each pop is likely to need to jump somewhere totally different in the heap.

• std::deque通过在结构（通常是链表）中维护短数组的集合来结合两者的某些方面。因此，项目集群将具有良好的数据局部性，并且该结构可以按需增长和收缩，而不会大惊小怪，因为数组永远不会重新分配——如果需要更多空间，它会分配一个新数组并将其添加到开头/ 结构结束。它是向量和列表之间的一个很好的中间立场，这就是为什么它是默认值。

¹ There is one level of indirection to the data, but in order to remove the last element, the linked list needs another indirection to the previous node to clear out the next-pointer.

² Note that you will need to move the vector when constructing the container. Copying a vector does not necessarily preserve its capacity. For example, you could use this helper:

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)};
}