As I understand, any container that supports push_back(), pop_back() and back() can be used as the underlying container for stacks, but by default, deques are used. I understand the pros of deques over vectors generally (possibility to add elements at the beginning as well as at the end), but in the case of stacks, I don't see any reason to prefer deques.

CodePudding user response：

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.