Whether you’re checking parenthesis balance, performing a DFS or evaluating reverse polish notation, chances are that you’re using a stack. And sure enough STL includes std::stack adapter with convenient API. This convenience hides an important design decision of std::deque as a default container. This is somewhat puzzling, since stack operations modify only its end, while deque is usually used for queues that operate on both ends of the queue. Since nothing comes for free, this deque’s flexibility comes at a price, since instead of using a single contiguous array to store all elements, it’s using chained chunks, which come with additional overhead.
But what does it mean in practice? Let’s generate a 1000 random stack operations
and test a default deque backed stack
and its vector backed versions
The results may surprise you.
I can’t think of a good reason why std::deque makes a better default than an std::vector, but since this decision is unlikely to ever change, you should consider using explicit container type when using std::stack adapter.
Yes. Good point and this what I do. Never understood why the design choice of deque.
Interesting fact to be recalled !
Was your intent only to populate the stack ?
Because as Yooseong said, by doing op_pop = 1 + checking if stack is empty before top() an pop() I observed reversed results.
In fact deque versatility may be overlooked. I often see in code non-reserved vector which feel like some kind of laziness or unconsciousness.
My favorite link on SO: https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl