C++14 outlines 3 container adaptors: stack, queue, priority_queue. They are outlined in section [container.adaptors/23.6]. If you take a look at their constructors, you’ll notice they’re implemented in terms of other containers. Hence the “adaptor” part of their name. Looking specifically at queue, the constructor has a default parameter set to a deque, but allowing the parameter to be set to another type. Here’s the declaration:
template <class T, class Container = deque <T> > class queue;
Your first question may be:
“Why does stack use a deque as its default underlying container?”
Your second question may be:
“What other types of containers should you use?”
If we look a the usage of a queue, we expect to be able to insert elements at the back of the container, remove from the front of the container, and read from both ends of the queue. Explicitly, this means an interface supporting front(), back(), pop_front(), push_back(). Let’s look at the available sequence containers [sequences / 23.2]: array, deque, forward_list, list, vector.
Let’s investigate and rule out the containers we can’t use:
- array: Doesn’t offer push_back() or push_front(). It’s fixed size also makes it unwieldy since we may want our queue to grow dynamically
- forward_list: Doesn’t offer access to the back of the list, back() or push_back(). Also would make each insertion at the back a linear operation in the order of n.
- vector: Doesn’t offer a pop_front(). The reason is removing from anywhere other then the back means shifting each item forward. This would be of linear complexity n.
This leaves us with list and deque, which both offer the necessary interface of back(), front(), push_back(), pop_front().
We have more information, but we still haven’t answered the question. Why should deque be the default container? Ultimately it boils down to deque “generally” being more efficient at allocation, hence the default part. Since it allocates chunks which can store multiple items, it has to allocate memory less often then list does. A queue implemented with a deque is therefore generally more efficient than a queue implemented with a list. If during profiling you ever determine the implementation of deque isn’t what it should be, you’ll know to profile your application next with a list.