Why does std::queue use std::dequeue as underlying default container?

Question

As read on cplusplus.com, std::queue is implemented as follows:

queues are implemented as containers adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are pushed into the "back" of the specific container and popped from its "front".

The underlying container may be one of the standard container class template or some other specifically designed container class. This underlying container shall support at least the following operations:

......

The standard container classes deque and list fulfill these requirements. By default, if no container class is specified for a particular queue class instantiation, the standard container deque is used.

I am confused as to why deque (a double-ended-queue on steroids) is used as a default here, instead of list (which is a doubly-linked list).

It seems to me that std::deque is very much overkill: It is a double-ended queue, but also has constant-time element access and many other features; being basically a full-featured std::vector bar the 'elements are stored contiguously in memory' guarantee.

As a normal std::queue only has very few possible operations, it seems to me that a doubly-linked list should be much more efficient, as there is a lot less plumbing that needs to happen internally.

---

Why then is std::queue implemented using std::deque as default, instead of std::list?

Answer 1

Stop thinking of list as "This is awkward to use, and lacks a bunch of useful features, so it must be the best choice when I don't need those features".

list is implemented as a doubly-linked list with a cached count. There are a narrow set of situations where it is optimal; when you need really, really strong reference/pointer/iterator stability. When you erase and insert in the middle of a container orders of magnitude more often than you iterate to the middle of a container.

And that is about it.

The std datatypes were generally implemented, then their performance and other characteristics analyzed, then the standard was written saying "you gotta guarantee these requirements". A little bit of wiggle room was left.

So when they wrote queue, someone probably profiled how list and deque performed and discovered how much faster deque was, so used deque by default.

In practice, someone could ship a deque with horrible performance (for example, MSVC has a tiny block size), but making it worse than what is required for a std::list would be tricky. list basically mandates one-node-per-element, and that makes memory caches cry.

Answer 2

The reason is that deque is orders of magnitude faster than list. List allocates each element separately, while deque allocates large chunks of elements.

The advantage of list is that it is possible to delete elements in the middle, but a queue does not require this feature.