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

Question

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?

cdhowie · Answer

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 implementation on different containers what is the actual difference?

One Answer

Add your own answers!

Ask a Question