Why does std :: stack use std :: deque by default?

Question

Since the only operations required for the container to be used on the stack are:

• back ()
• push_back ()
• pop_back ()

Why is the default container for it is deque instead of vector?

Do not overload requeocations in front of the element buffer in front of the front (), so push_front () is an efficient operation? Are these elements not lost as they will never be used in the context of the stack?

If there is no need to use deque for this path instead of a vector, why is the default for priority_queue not a vector, not a deque? (priority_queue requires front (), push_back () and pop_back () - essentially the same as for the stack)

---

Updated based on the answers below:

It seems that the deque method is usually implemented as an array of variable-size arrays with a fixed size. This increases the speed than the vector (redistribution and copying is required), so for something like a stack that is connected with adding and removing elements, this is most likely the best choice.

priority_queue requires significant indexing, as pop_heap () or push_heap () must be run for each deletion and insertion. This probably makes the vector the best choice there, as adding the item is still depreciated anyway.

Answer 1

As the container grows, redistributing the vector requires copying all the elements to a new memory block. The deque expression selects a new block and associates it with a list of blocks — no copies are required.

Of course, you can specify that another supporting container will be used if necessary. Therefore, if you have a stack that, as you know, will not grow, tell it to use a vector instead of deque if you prefer.

Answer 2

See Herb Sutter Guru of the Week 54 for the relative merits of vector and deque, wherever it is.

I assume that the inconsistency between priority_queue and the queue is simply that different people implemented them.