3

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?

Alex Butane
  • 127
  • 8
  • your premise is a tiny bit broken. A `stack` has more than `push`, `pop` and `top`. For example it has a member `c` which is the underlying container. It is protected, so if you like you can mess around with it – 463035818_is_not_an_ai Jul 22 '20 at 21:20
  • 4
    Forget the stack. What is the advantage of a vector, list, or deque in normal usage? Then think about it from a stack perspective. – ChrisMM Jul 22 '20 at 21:22
  • 1
    you made me curious, how do i mess with it and should i really? – Alex Butane Jul 22 '20 at 21:22

1 Answers1

13

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() on2 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 popping1, 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.

1 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.

2 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)};
}
cdhowie
  • 158,093
  • 24
  • 286
  • 300