Default stack container

Question

Why is std::deque<T> chosen as the default underlying container for std::stack<T>, although std::vector<T> satisfies the required functionality aswell while being less complex on the inside? Is it because std::deque<T> can grow more efficiently, or is there another design choice behind?

Answer 1

A deque is more optimized for pushing data to the back.

I did a quick speed test,
pushing back 50.000 integers to a vector took 728.991 clock cycles ( on average ) while the same amount took 'only' 428.438 clock cycles for a deque.

A deque is more efficient when working with large data, as reallocation in a big vector is quite costly.
If reallocation didn't happen they would operate at the same speed.

A vector is guaranteed to have its elements contiguous in memory, which is not true for a deque.

That's kinda where my knowledge about deque's ends. :(

Answer 2

Yes, I used the speed test I have on sololearn ( just not run on sololearn, it's like 10x slower here ).

I never learned it specifically, just slowly collected all kinds of bits and pieces and glued them together to form that. :)

Just keep researching the technical aspects of things like you are doing now.
Template metaprogramming ( TMP ), compile time prime numbers for example, and variadic templates are a good source to learn a bunch of new and exciting stuff.

Answer 3

Hmm, okay. I was just reading through this article comparing the three possible containers stack could wrap up which supports your argument regarding huge data types:
https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html

I guess I did not expect std::vector<T> to perform worse in a comparison because they seemed quite alike to me. Did you use your function speed test for that? Were did you learn to implement that?

I guess I'll go with the default for now then.

Answer 4

Impressive!
I will do so, thank you very much!