C++ default implementation of stack and queue

Question

In C++ Primer 5th, it says that the default implementation of stack and queue is deque.

I'm wondering why they don't use list? Stack and Queue doesn't support random access, always operate on both ends, therefore list should be the most intuitive way to implement them, and deque, which support random access (with constant time) is somehow not necessary.

Could anyone explain the reason behind this implementation?

Answer 1

Let's compare the sequence containers:

std::array is right out, it doesn't change size.

std::list optimises for iterator non-invalidation, allows insertion at known positions, and lacks random access. It has O(N) space overhead, with a large constant, and it has bad cache locality.

std::forward_list is an even more crippled list with smaller space overhead

std::deque optimises for appending or prepending, at the expense of not being contiguous. It has O(N) space overhead, with a smaller constant, and it has mediocre cache locality.

std::vector optimises for access speed, at the expense of insertion / removal anywhere but the end. It has O(1) space overhead, and the great cache locality.

So what does this mean for stack and queue?

std::stack only requires operations at one end. std::vector, std::deque and std::list all provide the necessary operations

std::queue requires operations at both ends. std::deque and std::list are the only candidates.

The choice of std::deque as the default is then one of consistency, as std::vector is generally better for std::stack, but inapplicable for std::queue.

Note that std::priority_queue, whilst named similar to std::queue, is actually more akin to std::stack in requiring only modification at one end. It also benefits more from the raw access speed of std::vector, maintaining the heap invariant.

Answer 2

the main reason is because deque is faster than the list in average for front and back insertions and deletions

deque is faster because memory is allocated by chunks were as list need allocation on each elements and allocation are costly operations.

benchmark

Answer 3

I think the question should be asked the other way around: Why use a list if you can use an array?

The list is more complicated: More allocations, more resources (for storing pointers) and more work to do (even if it is all in constant time). On the other hand, the main property for preferring lists is also not relevant to stacks and queues: constant-time random insertion and deletion.

Answer 4

With std::list as underlying container each std::stack::push does a memory allocation. Whereas std::deque allocates memory in chunks and can reuse its spare capacity to avoid the memory allocation.

With small elements the storage overhead of list nodes can also become significant. E.g. std::list<int> node size is 24 bytes (on a 64-bit system), with only 4 bytes occupied by the element - at least 83% storage overhead.