std::deque and std::list

Part I · Module 19 · Chapter 19.4 · std::deque and std::list

1. Two Different Things to Give Up

Chapter 19.2's two containers are contiguous and that is where their speed comes from. These two are not, and the useful way to hold them in mind is by what each one traded contiguity for.

std::deque — "double-ended queue" — stores its elements in a number of fixed-size blocks and keeps a separate array of pointers to the blocks. Because the blocks are all the same size, finding element n is two steps of arithmetic rather than one: which block, then where in the block. So random access survives, slightly slower. And because the block index can be extended at either end, inserting at the front is as cheap as inserting at the back — the operation std::vector cannot offer at all.

std::list gives each element its own allocation and links the allocations with two pointers each. There is no arithmetic that finds element n; you walk. In exchange, inserting or erasing anywhere is three pointer writes, and no other element is touched or moved — which is why Chapter 19.1 §7 measured it invalidating nothing.

std::forward_list is std::list with one pointer per node instead of two, which halves the per-node overhead and costs you the ability to iterate backwards. It also has no size(), because maintaining one would cost a word in an object designed to have none.

2. What the Container Objects Cost

sizeof(vector<int>)       = 24
sizeof(deque<int>)        = 48
sizeof(list<int>)         = 24
sizeof(forward_list<int>) =  8

std::deque is the largest of the four because it has the most to track: the block index, its extent, and the positions of the first and last elements within their blocks. std::list at 24 bytes holds head and tail pointers and a size. std::forward_list at 8 bytes holds one pointer and nothing else — not even a count, which is the visible consequence of having no size().

These are the object sizes and none of them says anything about the elements. §3 and §4 are where the real costs are.

3. A List Node Costs Six Times Its Payload

g.reset();
{ std::list<int, Counting<int>> c; c.push_back(1); }
std::printf("one int in a list allocated %zu bytes for a %zu-byte payload\n",
            g.bytes, sizeof(int));

one int in a list allocated 24 bytes for a 4-byte payload (6x)

Twenty-four bytes: a prev pointer, a next pointer, the int, and four bytes of padding to keep the node 8-byte aligned. The payload is 4 of those 24 bytes, so 83% of a std::list<int> is bookkeeping.

Scale it up and add the allocator:

1000 push_backs
vector: allocs=11    bytes=  8188
deque:  allocs= 2    bytes=  4104
list:   allocs=1000  bytes= 24000   (one node per element)

A thousand separate calls to the allocator. Not eleven, not two — one per element, because that is what "every element gets its own allocation" means. Each one is a general-purpose heap request with its own cost and its own opportunity to place the node somewhere unhelpful, which is the subject of Chapter 19.8 §4 and is where std::list's real performance problem lives.

The ratio worth carrying: for a small element type, std::list uses about six times the memory and makes one allocation per element. For a large element type the ratio improves — 24 bytes of overhead on a 200-byte element is 12%, not 500% — which is a genuine qualification and the reason §9's advice is about element size.

4. A Deque's Blocks Are Sized in Bytes

Finding a deque's block size looks like it should be an address-gap test: walk the elements, and where &d[i] - &d[i-1] is not sizeof(T), there is a block boundary. That test does not work, and the reason is worth recording because the wrong method gives a confident wrong answer.

Over 2,000 ints it reported zero discontinuities — implying one block of at least 2,000 elements — because the allocator happened to return two 4096-byte blocks at adjacent addresses, so the arithmetic across the boundary came out to exactly 4 bytes anyway. The address test cannot distinguish "same block" from "two blocks that happen to abut."

The method that does work is to count allocations, since a new block is a new allocation:

std::deque<int, Counting<int>> d; g.reset();
std::size_t last = g.allocs;
for (int i = 1; i <= 4100; ++i) {
    d.push_back(i);
    if (g.allocs != last) { std::printf("%d ", i); last = g.allocs; }
}

deque<int>    new block at n = 1 1024 2048 3072 4096     => 1024 ints = 4096 bytes
sizeof(T)=512 new block at n = 1 16 32                   => 16 elements

A new block every 1,024 ints is 4,096 bytes. But for a 512-byte element the block holds 16 elements, which is 8,192 bytes — so the rule is not "always 4,096 bytes." libc++ uses 4096/sizeof(T) elements per block while that is at least 16, and a flat 16 elements otherwise. Either way the block is sized in bytes first and elements second, which produces the figure that decides when not to use a deque:

a deque<int> holding ONE int costs 4104 bytes in 2 allocations

Four kilobytes for one int — one 4,096-byte block plus the 8-byte block index. A std::vector<int> with one element costs 4 bytes of payload in one allocation. If you are creating many small deques, that is the measurement that matters.

5. What Each One Is Actually For

With the costs established, the capabilities are short.

std::deque is for a queue. Amortised O(1) at both ends, so push_back/pop_front is the natural FIFO, and it is std::queue's default underlying container for exactly that reason. The measurement:

deque 1000 push_front: allocs=4   (amortised O(1) at BOTH ends)

Four allocations for a thousand front-insertions. std::vector has no push_front, and v.insert(v.begin(), x) shifts every element on every call — O(n) per insertion, O(n²) for the loop.

std::deque also offers reference stability at the ends. Inserting at either end does not move existing elements, which Chapter 19.1 §5's probe confirmed with 0 of 4 moved. Iterators are still invalidated by any insertion, so this is another instance of Chapter 19.1 §7's two-promises distinction.

std::list is for splicing. This is its genuinely unique capability and nothing else in the library has it:

std::list<int> a{1,2,3}, b{4,5,6};
a.splice(a.end(), b);

splice moves 6 elements by relinking; b.size() now 0, no allocation

Six elements transferred between containers with no allocation and no element copied or moved — just pointer writes. Moving a range between two std::vectors means copying or moving every element.

std::list is for stable references with insertion in the middle. If you need pointers to elements to stay valid while the container is modified anywhere, and the elements must be in a sequence rather than keyed, std::list is the answer. This is a real requirement and it is the most defensible reason to pick one.

std::list::sort relinks rather than moves, which is unusual enough to be worth proving three ways:

5 of 5 addresses still hold their original value
allocs=0 frees=0
list::sort of 5 elements     ctor=0 copy=0 move=0 dtor=0

Every address kept its value, no allocation occurred, and no element was copied or moved. The sort rearranged the links. This is why std::list has a member sort at all: std::sort requires random-access iterators and cannot be used on a list, and the member version does something std::sort cannot — reorder without touching the elements.

6. The Textbook Argument, and What It Omits

The case for std::list as usually presented is a complexity table: insertion and erasure are O(1) for list and O(n) for vector. Both halves are true. The conclusion drawn from them is usually wrong, and Chapter 19.8 §2 explains why. The short version belongs here because it is this chapter's main point.

The O(1) insertion is O(1) given an iterator to the position. Getting that iterator means finding the position, and in a list, finding anything means walking from one end — O(n), with a pointer dereference per step. So the realistic operation is "find, then insert," and its cost is dominated by the find:

n=100000  vector 7.04 ms [6.94-9.11]   list 31.36 ms [27.37-37.03]   list ~4.4x

The std::vector is more than four times faster at an operation the complexity table says it loses, because its O(n) search walks contiguous memory while the list's O(n) search chases pointers, and because its O(n) insertion is a memmove of trivially copyable data rather than per-element work.

When the position really is already known, the table tells the truth:

20000 inserts at a HELD middle position in 200000 elements:
vector 495.24 ms [316-1521]   list 14.02 ms [11.49-27.48]   list ~36x FASTER

Roughly thirty-six times faster. So the complexity table is not wrong; it is answering a question most code does not ask. The discriminating question is whether you hold the position or have to find it, and §9 turns that into advice.

7. Why There Is No operator[]

std::list has no operator[] and this is a deliberate design decision rather than an omission, which is worth stating because it is a small lesson in interface design.

There is no way to reach the nth element of a linked list except by taking n steps. An operator[] could be provided — the implementation is a loop — and it would be a trap, because the syntax l[40000] looks like constant-time indexing everywhere else in the language and would quietly be a 40,000-step walk. The classic consequence is a loop over l[i] for i from 0 to n, which is O(n²) and looks exactly like the O(n) loop over a vector.

By omitting the operator, the library forces the cost to be visible: you must write std::advance(it, n) or walk explicitly, and both of those read like work. This is the same principle that makes std::list provide a member sort instead of letting std::sort fail mysteriously.

std::forward_list extends the idea by also omitting size(), on the grounds that it would cost a word in every object to support an operation the container is not for.

8. The Comparison Table

9. When to Use Which

• Use std::vector unless something below applies. Chapter 19.2 §12's default stands.
• Use std::deque when you need a queue — cheap insertion and removal at both ends. This is its one strong case and std::queue adopts it by default.
• Use std::deque when you need stable references and random access, which no other container offers together. Note iterators are still invalidated.
• Avoid std::deque for many small containers. 4,104 bytes for one element, measured.
• Use std::list when you splice. Transferring ranges between containers without allocating or moving elements is unique to it.
• Use std::list when references must survive insertion anywhere and the data is a sequence rather than keyed. If it is keyed, std::map offers the same stability with lookup.
• Use std::list when you hold the position and insert or erase constantly. Measured about 36× faster — but check the position really is held and not found.
• Do not use std::list because the complexity table says O(1). Measured about 4.4× slower on find-then-insert.
• Consider std::forward_list only when the per-node word matters and backward iteration genuinely is not needed. In practice this is rare.
• Reconsider the data structure entirely if std::list looks necessary. A std::vector of indices, or a std::vector with tombstones, or a std::map, frequently serves better.

10. The std::queue and std::stack Adapters

These are not containers; they are interfaces over one. std::stack<T> and std::queue<T> wrap another container and expose only the operations the abstraction allows — push, pop, top/front, empty, size — with no iterators at all.

std::queue's default underlying container is std::deque, which §5 explains: a queue needs cheap insertion at one end and cheap removal at the other, and std::deque is the only standard container that does both. std::stack's default is also std::deque, though std::vector is the better choice for a stack and can be requested:

std::stack<int, std::vector<int>> s;      // vector-backed: contiguous, one end only

The adapters are worth using when the restriction is the point. A std::queue cannot be indexed or iterated by accident, so the type documents and enforces the access pattern — the same argument Chapter 16.7 §3 makes for composition over inheritance when you want to expose less than you contain.

11. What to Actually Do

• Default to std::vector. These two are exceptions with named conditions.
• Reach for std::deque when the access pattern is a queue, or when you need stable references and random access.
• Do not create many small std::deques. 4,104 bytes each, measured.
• Reach for std::list for splicing, for reference stability in a sequence, or when you hold the insertion position.
• Never index a list in a loop — there is no operator[] precisely so you cannot write the O(n²) loop by accident.
• Use list::sort, not std::sort, on a list, and know that it relinks rather than moves.
• Count the per-element overhead before choosing std::list for a small element type: 24 bytes for a 4-byte payload.
• Use the std::queue / std::stack adapters when restricting the interface is the goal.
• Measure block boundaries by counting allocations, not by comparing addresses — the address test reported zero boundaries over 2,000 elements because two blocks abutted.

12. Mistakes Worth Making Once

Choosing std::list from the complexity table. Measured about 4.4× slower on find-then-insert. The table is right and answers the wrong question.

Expecting std::deque to be contiguous because it has operator[]. There is no data(), and passing a deque to a C interface does not compile — which is the good outcome.

Creating a std::vector<std::deque<int>> of ten thousand small deques. Forty-one megabytes of blocks for a handful of elements each.

Writing std::advance(it, n) inside a loop over a list. O(n²), and it looks deliberate so reviewers skim it.

Calling std::sort on a std::list. It does not compile, because std::sort needs random-access iterators. The error is long and the fix is the member function.

Assuming splice copies. It does not — measured 0 allocations, 0 copies, 0 moves — which also means the spliced-from container really is empty afterwards.

Testing for deque block boundaries by address arithmetic. My own first attempt reported 0 discontinuities over 2,000 elements and I nearly published it; two 4,096-byte blocks had been allocated adjacently, so the gap across the boundary was exactly sizeof(int).

Using std::forward_list and then wanting size(). It does not have one, by design.

13. Interview Relevance

The frozen curriculum marks this chapter Medium, and the questions are mostly traps that test whether you reason from measurement or from the table.

"When would you use std::list over std::vector?" The honest answer names splicing, reference stability under insertion, and holding the position — and then volunteers that the usual reason given, O(1) insertion, is misleading because the search dominates. Candidates who say "when there are many insertions" without the qualification are giving the answer the question is probing for.

"Is std::deque contiguous?" No. It offers random access without contiguity, has no data(), and stores elements in blocks. This separates people who have read the guarantees from people who inferred them from operator[].

"Why does std::list have no operator[]?" Because the only implementation would be a walk, and the syntax would hide a linear cost. §7's design argument.

"Why is std::deque the default for std::queue?" Cheap insertion and removal at both ends; it is the only standard container that does both.

"What does std::list::splice do?" Transfers elements between lists by relinking nodes — no allocation, no element copied or moved, constant time for a whole list.

"How much memory does a std::list<int> use per element?" Twenty-four bytes for four bytes of payload, plus one allocation per element. Being able to quote that is a strong signal.

14. What You Should Be Able to Say Now

• What each container traded contiguity for, and that the trades are different.
• That a std::list<int> node is 24 bytes for a 4-byte payload and costs one allocation per element.
• That a thousand appends made 1,000 allocations in a list, 2 in a deque, 11 in a vector.
• That a deque's blocks are sized in bytes — 1,024 ints or 16 elements of 512 bytes — so one int in a deque costs 4,104 bytes.
• That find-then-insert was about 4.4× faster in a vector, and insert-at-a-held-position was about 36× faster in a list.
• That splice relinks with no allocation, and list::sort relinks without moving elements.
• Why std::list has no operator[] and std::forward_list has no size().
• Why an address-gap test cannot find a deque's block boundaries.

15. Exercises

Exercise 1 — the node size. Measure the per-element allocation for std::list<char>, std::list<int>, std::list<double> and a 200-byte struct. Plot overhead as a percentage and find where it stops mattering.

Exercise 2 — the block rule. Reproduce §4's allocation-counting probe for element sizes 1, 4, 64, 255, 256 and 512, and derive the block-size rule from your output.

Exercise 3 — the bad method. Reproduce the address-gap test that failed and confirm it on your machine. Then make it succeed by allocating something between the blocks, and explain why the method is still invalid.

Exercise 4 — find versus hold. Reproduce §6's two benchmarks. Then write a third where half the insertions use a held iterator and half search, and find the fraction at which the winner changes.

Exercise 5 — the quadratic loop. Write the O(n²) loop that operator[] would have enabled, using std::advance, and time it against the equivalent walk. Then explain the library's design choice in one sentence.

Exercise 6 — splice. Move the middle third of a 30,000-element list into another list and confirm with the counting allocator that nothing was allocated and no element was moved.

Exercise 7 — the small-deque problem. Build a std::vector of 10,000 std::deque<int>, each holding three elements, and measure total memory. Compare with 10,000 std::vector<int>.

Exercise 8 — the adapter. Implement a fixed-capacity ring buffer over std::array with the std::queue interface, and state which of this chapter's containers it replaces and what it gives up.

16. Summary

• std::deque trades contiguity for cheap insertion at both ends and keeps random access at the cost of one indirection.
• std::list trades random access for O(1) insertion at a held position and for invalidating nothing.
• Measured object sizes: vector 24, deque 48, list 24, forward_list 8.
• Measured: one int in a list costs 24 bytes — 83% bookkeeping — and 1000 appends made 1000 allocations against a deque's 2.
• Measured: a deque's blocks are sized in bytes — 1,024 ints per block, or 16 elements when sizeof(T) is 512 — so one int in a deque costs 4,104 bytes in 2 allocations.
• Measured: 1000 push_front on a deque = 4 allocations, the operation std::vector does not have.
• Measured: splice relinked 6 elements with 0 allocations and 0 moves, and list::sort left all 5 addresses holding their original values.
• Measured: find-then-insert was about 4.4× faster in a vector; insert-at-a-held-position was about 36× faster in a list. The deciding question is whether you hold the position.
• std::list has no operator[] by design, so the O(n²) loop cannot be written by accident.
• An address-gap test cannot find block boundaries — adjacent blocks defeat it; count allocations.

Both of this chapter's containers are keyed by position. Chapter 19.5 moves to the containers keyed by value: std::map and std::set, which keep their elements in sorted order in a balanced tree. They bring back a capability neither of these has — finding an element by key in logarithmic time rather than by walking — and they bring the ordering with it, which turns out to be the thing that justifies them once Chapter 19.6's hash containers arrive and beat them at plain lookup. The chapter also measures the single most surprising behaviour in the whole container library: a lookup that inserts.