Difference between a vector and a stack?
A discussion between the difference of a vector and a stack in C++ can be found here.
My question is if stack “needs to be provided the underlying container. By default it’s
std::deque, but it can be
std::list too.”. My questions are:
- Why don’t we directly use the vector? As vector seems faster than deque.
- When should we use stack instead of vector?
In order to fully answer those questions, I’d like to do some online searching.
What is stack?
From , it is pretty clear described about what is stack.
stacks are implemented as container adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are pushed/popped from the “back” of the specific container, which is known as the top of the stack.
The underlying container may be any of the standard container class templates or some other specifically designed container class. The container shall support the following operations:
The standard container classes vector, deque and list fulfill these requirements. By default, if no container class is specified for a particular stack class instantiation, the standard container deque is used. From 
Why deque is the default container not the vector?
An explanation from here can answer this question.
Based on the previous section, we know that deque is preferred as “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.”
So based on this, we can do the following:
- If we know the upper bound of the stack size, we can use vector as a stack and reserve enough space before using this “stack”
- If we wanna use stack with an unknown upper bound of the stack size, we can either use stack (with deque as the default container) or we can use deque directly: stack is push and pop while deque is push_back and pop_back (slightly different in the API).
Thanks for reading and I hope this is helpful.