不同容器上的 std::stack 实现有什么实际区别? [英] std::stack implementation on different containers what is the actual difference?

问题描述

在实现 std::stack

时

有几个选项，例如:

//栈与默认底层双端队列std::stack<国际 >intDequeStack;//与底层向量堆栈std::stack>intVectorStack;//与底层列表堆栈std::stack>intListStack;

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

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

解决方案

栈继承了底层容器的性能特性.

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

  因此:如果您知道堆栈将达到的最大大小并且该大小相对较小，那么您在 ^{上调用了 reserve() 的向量2} 在所有情况下都可能比 list 或 deque 更快；它具有非常好的数据局部性和更少的访问元素的间接级别.

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

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

---

¹ 数据有一层间接，但为了删除最后一个元素，链表需要另一个到前一个节点的间接，以清除下一个指针.>

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

template std::stack>矢量堆栈(类型名称 std::vector::size_type 容量){std::vectorvec;vec.reserve(容量)；返回 std::stack>{std::move(vec)};}

when implementing an std::stack

there are a few options, for example:

   // 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;

what advantages and disadvantages do i gain from defining std::stack on different containers when all i get from it is the same operations " push, pop and top " ?

in other words: what is the difference between a stack of deque and a stack of vector and a stack of list and why would i want to choose anything other than deque?

解决方案

The stack inherits the performance characteristics of the underlying container.

• std::vector is a bad choice for a stack that can vary in maximum size. Each push on the stack can potentially require a large reallocation in the vector. Vectors also never shrink unless explicitly requested to, so if the stack grows large then shrinks down, the additional memory will never be freed (until the stack is destroyed). However, vectors only have one level of indirection between them and the stored data.

  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 combines some aspects of both by maintaining a collection of short arrays in a structure (usually a linked list). Therefore, clusters of items will have good data locality, and the structure can grow and shrink on-demand without very much fuss since the arrays are never reallocated -- if it needs more space, it allocates a new array and adds it to the beginning/end of the structure. It's a good middle ground between vector and list, which is why it is the default.

---

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

这篇关于不同容器上的 std::stack 实现有什么实际区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！