CODEWITHSUNDEEP
c++stack
cutcrew
cutcrew

Reputation: 27

Is there any performance penalty for using std::stack rather than the underlying std::deque?

I want to implement a LIFO stack object. The C++ standard lib provides a convenient stack structure (std::stack) with a very simple interface. By default, it uses std::deque as its underlying container.

Is there any performance penalty to using std::stack rather than using std::deque directly?

My use case would involve many pops and pushes per second.

Upvotes: 1

Views: 903

Answers (2)

janekb04
janekb04

Reputation: 4915

As commenters pointed out, you should always benchmark first in such cases. As an example I used a tool called Quick Bench, as it is online and can be embedded in here. You should always pick the tool that fits the particular need the best.

In this case the answer depends on whether you have optimizations turned on. Please note that you should always benchmark optimized builds, but I included the unoptimized version to show how results differ. If we run a benchmark (link) with optimizations off (-O0 on g++), we see that stack is slightly slower:

enter image description here

However when we run the benchmark (link) with optimizations (-O3 on g++), the story is different:

enter image description here

The performance is nearly identical. This is due to inlining. This means that in release builds you won't suffer any performance loss from using stack. In C++ this is called zero cost abstractions.

Its worth pointing out that in reality even "zero cost" abstractions still carry a cost - increased compile times.

Upvotes: 2

SergeyA
SergeyA

Reputation: 62563

No, there will be no performance profile changes by using std::stack (as compared to using std::deque directly).

Upvotes: 2

Related Questions