In what circumstances should I choose to use deque over list?

[Banfa]

So the basic sequenced C++ containers are

vector - holds data in a contiguous memory block that has the same memory footprint as a classical array. Expensive to insert or delete at the front or in the middle as it involves copying to maintain the memory layout, can be expensive to append to the end if it involves reallocating memory, never releases memory once allocated without user intervention. Has random access and therefore random access iterators. Should be the default container of choice unless a specific design decision can be found to use another container type.

deque - holds data in blocks of allocated memory, quick to insert or delete and beginning or end, deletion/insertion in the middle is slow. Has random access and therefore random access iterators.

list - holds data in individually allocated blocks of memory, quick to insert or delete and beginning, end or in the middle also quick to sort/reorder as these just involve swapping pointer values not objects. Does not have random access and therefore does not have random access iterators only sequential iterators.

The derived sequential contains, queue, priority_queue and stack are all implemented as adaptors of one of the basic sequential containers as follows

queue adapts deque
priority_queue adapts vector
stack adapts deque

Note that these adaptions are not fixed but are actually passed as template parameters.

So my question boils down to the queue adaption of deque.

queue interface member functions are

empty Test whether container is empty
size Return size
front Access next element
back Access last element
push Insert element implemented as push_back
pop Delete next element implemented as pop_front

In fact both deque and list have the correct members to be able to implement the queue adaptor. They also both seem to have good efficiency for the operations required. So the question is (finally after that long post :D )...

Why is the default queue implemented as an adaption of deque rather than an adaption of list? What is the design decision that makes deque the better choice in this case?

[weaknessforcats]

deque is a better choice because it allocates memory in chunks rather than allocating each time for one node. The standard templates are optimized for speed not size or efficiency.

Speed is paramount to the extent that PJ Plaugher once said that if you think you can write code that is faster than his templates, then think three times.

I would use list<> when I have a lot of nodes that are processing in a largely sequential manner and vector<> when the processing is more random in nature. Otherwise, I stick with deque.

The container-adapters (priority_queue, queue and stack) are just variants of the sequence containers so they are built on top of one of those containers (HAS-A).