Difference between a vector and a stack?

My questions

A discussion between the difference of a vector and a stack in C++ can be found .

My question is if stack “needs to be provided the underlying container. By default it’s std::deque, but it can be std::vector or 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 [1], 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:

empty

size

back

push_back

pop_back

The standard container classes , and fulfill these requirements. By default, if no container class is specified for a particular stack class instantiation, the standard container is used. From [1]

Why deque is the default container not the vector?

An explanation from can answer this question.

Conclusion

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.

Reference

[1]

[2]

[3]

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store