C++ deque, list and forward_list: Choose the Right Non-Vector Container

vector is the sensible default for sequence storage, but front insertion, stable element handles or a forward-only mutation pattern can make another container attractive. The names alone do not reveal the cost of finding a position, shifting elements, chasing nodes or invalidating an iterator. The edit script runs over {10,20,30,40,50,60,70,80}, followed by a traversal-sum check.

C++ deque, list and forward_list: start with their structural contracts

These are typical models, not guaranteed byte counts. For iterator and STL foundations, use the C++ Tutorial learning sequence.

Container complexity has two bills: locate the edit, then perform it

Separate finding a position from mutating there. Scanning by value is O(n) for all three containers. A list::insert is O(1) only after the destination iterator exists. A forward_list::insert_after is O(1) only after its predecessor exists. This lookup-versus-mutation distinction is central to Time Complexity and Asymptotic Notation.

From the beginning, finding 30 examines 10, 20, then 30. Finding 70 examines seven values. One scan can retain handles to 30, predecessor 60, 70 and tail 80; repeated scans consume much of a linked container's advantage.

A deque reaches a numeric index in constant time. A middle insert or erase still reorganises elements, with linear work on the nearer side. The standard does not promise the precise byte moves shown. End insertion avoids that middle-shift cost.

One editing workload on all three containers: get the exact final sequence

Begin with S0 = [10,20,30,40,50,60,70,80] and apply the same four edits:

1. E1, prepend 5: [5,10,20,30,40,50,60,70,80].

2. E2, insert 35 immediately after 30: [5,10,20,30,35,40,50,60,70,80].

3. E3, erase 70: [5,10,20,30,35,40,50,60,80].

4. E4, append 90: S4 = [5,10,20,30,35,40,50,60,80,90].

The final traversal is 5 + 10 + 20 + 30 + 35 + 40 + 50 + 60 + 80 + 90 = 420, across 10 elements. Every implementation must print that sequence and checksum. We are comparing work and guarantees, not different answers.

For deque, call push_front(5), find 30, and run insert(std::next(pos30), 35). Reacquire 70 after the middle insertion, call erase(pos70), then push_back(90) and std::accumulate(begin, end, 0). Both middle operations are linear. Reacquisition is necessary because the insertion invalidates the saved iterator.

For list, call push_front(5), obtain pos30 and pos70 in one pass, then use insert(std::next(pos30), 35), erase(pos70) and push_back(90). Inserting 35 does not invalidate pos70, so the mutations are constant time after the handles have been found.

forward_list changes the cursor: keep the predecessor and the tail

After push_front(5), make one forward scan that retains iterators to 30, 60 and 80. Call insert_after(it30, 35), erase_after(it60) to remove 70, and insert_after(it80, 90) to append through the retained tail. The result is the same ten-element sequence with checksum 420.

The cursor has a different meaning here. A list iterator to 70 is sufficient for erase(pos70). A forward_list must hold predecessor 60, because a singly linked node cannot move backwards to repair its incoming link. before_begin() provides the special predecessor needed for edits at the front.

Without retained it80, appending 90 requires walking from 5 through 10, 20, 30, 35, 40, 50, 60 and 80 before calling insert_after. There is no member push_back. Code that appends frequently must correctly maintain a tail or choose another container. If an operation erases the saved tail, it must also update that external handle.

Iterator guarantees decide whether saved cursors remain trustworthy

The guarantees for the operations in this trace are narrow and useful:

Apply this to h30, h60, h70 and h80. After the middle insertion, all four are unusable for deque; the relevant linked-container handles remain valid. After erasing 70, only h70 is lost for list and forward_list, while h80 can still append to the forward list. A pointer or reference surviving a deque end insertion is not a promise that its iterator survives.

Cache behaviour can overturn the Big-O story, so measure it

A deque uses separately allocated blocks but retains some within-block locality. list and forward_list usually chase separate nodes through pointers, adding indirection and weakening spatial locality. One link may reduce forward_list metadata, but alignment, allocator bookkeeping and value size can outweigh it.

For a repeatable experiment, build each container with exactly 1,000,000 std::uint64_t values, where element i is i % 1000. Traverse each container 25 times and consume the result. One pass is 1000 x (0 + 1 + ... + 999) = 499,500,000; the 25-pass checksum is 12,487,500,000. Run 3 warm-ups and 20 timed repetitions, rotate the container order, and report median and p95 nanoseconds per element.

Fix the compiler, flags, standard library, allocator, CPU and power mode. Any ranking applies only to that setup. For a FIFO pushing at one end and popping at the other, Stacks and Queues shows why deque fits; std::queue offers a narrower interface.

When each non-vector container wins, and when vector still wins

Choose from constraints:

• Choose deque for both-end pushes and pops plus items[37], without contiguous storage or stable iterators.

• Choose list when valid iterators already exist, traversal is bidirectional, and node edits must preserve other handles.

• Choose forward_list for strictly forward traversal and predecessor-based edits, if measurement shows the missing second link matters.

• Keep vector for traversal-heavy storage, end appends and index access when middle-handle stability is unnecessary.

Avoid six traps:

1. Treating deque as contiguous.

2. Forgetting that deque end insertion invalidates iterators.

3. Calling list insertion O(1) while hiding an O(n) search.

4. Passing the target, rather than its predecessor, to forward_list::erase_after.

5. Expecting forward_list::size() or push_back().

6. Using std::sort with list iterators instead of the containers' member sort().

Trace checksum 420, then select by constraint. Coding For Placements offers broader coding-assessment practice.

C++ container choice: the short version and next step

Start with vector. Move to deque for frequent end edits plus random access, to list when stable iterators and known-position relinking are central, and to forward_list only when one-way traversal and predecessor-based edits genuinely fit. Search cost and cache behaviour still count.

Implement all three versions for {10,20,30,40,50,60,70,80}. Assert [5,10,20,30,35,40,50,60,80,90] and checksum 420, then run the traversal experiment on your toolchain. For broader language and STL study, continue with C++ Programming.