Why Does Std::Stack Use Std::Deque by Default

Why does std::stack use std::deque by default?

As the container grows, a reallocation for a vector requires copying all the elements into the new block of memory. Growing a deque allocates a new block and links it to the list of blocks - no copies are required.

Of course you can specify that a different backing container be used if you like. So if you have a stack that you know is not going to grow much, tell it to use a vector instead of a deque if that's your preference.

Why are deques used as the underlying container for stacks by default, when vectors would do the trick?

I don't see any reason to prefer deques.

A reason to prefer deque that applies to the stack use case is that individual push back has worst case constant complexity compared to vector whose individual push back is linear in worst case (it has amortised constant complexity over multiple push backs). This was particularly significant prior to C++11 when reallocating vector had to copy the elements which could be very expensive. Consider case where the elements themselves are long strings.

Another reason to prefer deques is that they release memory as they shrink. Vectors don't. Hence, if you have a stack that temporarily grows large, then shrinks and remains small for the rest of the execution, then an underlying vector would be wasting a lot of memory.

Historically, when STL was designed and thus when the default was chosen, there used to also be issues with very large vectors because the size of the address space didn't exceed (significantly, or at all) the amount of memory (this was before 64 bit processing was common). The consequence of the limited address space was that memory fragmentation would make it expensive or impossible to allocate large contiguous blocks of memory that a large vector would require. Furthermore, the way that vector grows by deallocating old buffers is a behaviour that causes such fragmentation.

Why does std::queue use std::dequeue as underlying default container?

Stop thinking of list as "This is awkward to use, and lacks a bunch of useful features, so it must be the best choice when I don't need those features".

list is implemented as a doubly-linked list with a cached count. There are a narrow set of situations where it is optimal; when you need really, really strong reference/pointer/iterator stability. When you erase and insert in the middle of a container orders of magnitude more often than you iterate to the middle of a container.

And that is about it.

The std datatypes were generally implemented, then their performance and other characteristics analyzed, then the standard was written saying "you gotta guarantee these requirements". A little bit of wiggle room was left.

So when they wrote queue, someone probably profiled how list and deque performed and discovered how much faster deque was, so used deque by default.

In practice, someone could ship a deque with horrible performance (for example, MSVC has a tiny block size), but making it worse than what is required for a std::list would be tricky. list basically mandates one-node-per-element, and that makes memory caches cry.

Why use std::stack or std::queue?

To limit the user interface
You don't want your stack to be able to remove elements somewhere else instead of top. Why to use vector in place of stack if you have exactly same performance also stack improves readability and reliability.

std::stack is more expressive than std::vector when the container you want to implement is truly a LIFO.

Why are std::deque subarray sizes fixed?

What I don't understand is why the subarrays have their sizes fixed

Because that allows constant complexity random access which is required by the standard, as pointed out in the comments.

But this is not a huge deal

I disagree, and presumably so would the standard committee.

since std::deque is advertised to be a doubly linked list ...

It's not advertised as such.

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

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

Does the stack implementation that's part of the C++ STL have a capacity?

The stack implementation you looked at in your course may have had a limit, but that's not essential to being a stack. (And your course really should have taught you this.)

The C++ standard library stack is just an adapter for any underlying collection that supports the necessary operations, so whether it has a limited capacity or not depends on that underlying type.

(The default is std::deque.)

Why Does Std::Stack Use Std::Deque by Default