不同容器上的 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堆栈上的每个都可能需要在向量中进行大量重新分配。除非明确要求，否则向量也永远不会缩小，因此如果堆栈变大然后缩小，则永远不会释放额外的内存（直到堆栈被销毁）。然而，向量在它们和存储的数据之间只有一层间接。

  因此：如果您知道堆栈将达到的最大大小并且该大小相对较小，那么您reserve()在²上调用的向量在所有情况下都可能比列表或双端队列更快；它具有非常好的数据局部性和更少的访问元素的间接级别。

• std::list是一个链表，因此在弹出¹时堆栈将具有两个间接级别，并且它将始终准确使用所需的内存量。推送时没有昂贵的重新分配，但它的数据局部性很差，因为每个节点都可以分配到堆中的任何位置；处理来自堆栈的大量数据将无法有效地使用各种 CPU 内存缓存，因为每次弹出可能需要跳转到堆中完全不同的某个地方。

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

^{1 数据}有一层间接，但为了移除最后一个元素，链表需要对前一个节点进行另一次间接，以清除下一个指针。

²请注意，在构建容器时您需要移动向量。复制向量不一定保留其容量。例如，您可以使用此助手：

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