A sequence is not automatically best represented by a linked list because it supports insertion. Finding the insertion position can cost a traversal, and node storage has overhead. A deque can efficiently support both ends while still offering random access, but its elements are not one guaranteed contiguous block. The choice depends on the complete workload and the validity requirements of retained handles.
This guide uses C++17. You will use a deque for a small double-ended work queue and a list for node transfer. The examples explain what each structure promises rather than claiming one container is universally faster. A vector remains a good default for many ordinary sequence workloads.
Deque supports both ends and random access
Std::deque is a double-ended sequence container with efficient insertion and removal at its ends. It also supports random-access iterators and indexing. That combination can fit a workflow where urgent work enters at the front and ordinary work enters at the back.
Its storage is not required to be contiguous like vector's storage. Do not pass a pointer to the first deque element and the size to an API expecting a contiguous array. Access through iterators or supported element operations instead. Middle insertions and erasures have different costs and invalidation consequences from endpoint operations. A deque is therefore not merely “vector with faster push_front”; the storage and handle contracts are distinct.
List supports bidirectional node traversal
Std::list is a doubly linked sequence. Its iterators support moving forward and backward, but not constant-time random indexing. It has no ordinary operator[] access. Reaching the hundredth element requires traversal from an available position rather than arithmetic on a random-access iterator.
Insertion or removal at an already known position can be efficient, and handles to unrelated nodes generally remain valid under those operations. Finding that position can still be linear. Each node can carry allocation and link overhead, and noncontiguous traversal can have different cache behavior from vector. Choose list when node-level operations and stability are actually useful, not from a simplified chart that ignores lookup and memory costs.
Iterator categories affect available algorithms
Std::sort requires random-access iterators, so it works with vector and deque but not list iterators. List provides its own sort operation that can reorder nodes under its contract. Other algorithms can work with bidirectional or forward iterators, depending on their requirements.
Use the algorithm's documented iterator requirement to understand a compile error. Do not copy a list into a vector merely to silence the error unless that transformation matches the intended ownership and cost. Member operations such as splice, merge and remove_if can exploit list's structure. Their preconditions still matter, including sorting requirements for merge and allocator compatibility for node transfer.
Invalidation is operation-specific
List erasure invalidates handles to the erased node; it does not permit continuing to use that node because other nodes are stable. Deque endpoint insertion can invalidate iterators even where references to existing elements remain valid under its specified rules. Middle operations have further consequences.
Do not infer iterator stability from reference stability. An iterator can contain traversal information beyond the element's address. Review the exact modifier and reacquire traversal handles after mutation when the design does not need to preserve them. A copied value such as a job ID can remain useful even when the container's handles change. Thread safety is also separate: stable nodes do not permit unsynchronized concurrent mutation.
Select from a realistic workload
List can be useful when a system already holds positions and frequently relocates nodes. Deque can fit endpoint-heavy sequences that also need random access. Vector's contiguous storage can make traversal and many ordinary operations efficient even when occasional shifts occur. Benchmark the complete operation, including finding positions, allocations and iteration.
A container choice should also support the API's ownership and invalidation contract. If callers need durable logical IDs, a list may not be necessary merely to preserve pointers. If an external library needs contiguous data, deque and list cannot satisfy that contract directly. Keep the structure private when possible so an implementation can change without exposing its incidental storage details to every caller.
Check empty and boundary cases
Front, back and pop operations need the container to be nonempty under their contracts. A missing find result must be compared with end before dereferencing. The examples handle those conditions explicitly. Test an empty queue, one item, missing selected IDs and transferring the only node.
Also test whether the intended order is preserved. A double-ended queue can produce surprising scheduling if urgent insertion is overused. A list transfer can change which collection owns the node even though the iterator remains valid. Correctness includes the feature's ordering and ownership rule, not only the absence of invalid memory access.
Official references
C++ List and Deque Container Choices Examples
Each example shows the code, the output it produces and what each part does.
A deque and a stable list position
The complete program handles urgent work first through a deque, then demonstrates a retained list iterator while another node is inserted.
The list insertion preserves the iterator to review. The deque loop acquires front only while the container is nonempty and does not retain a reference after removing that element.
#include <algorithm>
#include <deque>
#include <iostream>
#include <list>
#include <string>
int main() {
std::deque<std::string> work{"regular"};
work.push_front("urgent");
while (!work.empty()) {
std::cout << "Work: " << work.front() << '\n';
work.pop_front();
}
std::list<std::string> stages{"draft", "review"};
auto review = std::find(stages.begin(), stages.end(), "review");
if (review != stages.end()) {
stages.insert(review, "verify");
std::cout << "Saved stage: " << *review << '\n';
}
for (const auto& stage : stages)
std::cout << stage << '\n';
}Work: urgent
Work: regular
Saved stage: review
draft
verify
reviewC++ List and Deque Container Choices in Real Projects
Worked exercise: move one list node into a ready queue
The task is to move job two from a backlog list to a ready list without copying its value. Both lists use the same default allocator. Find the node, splice it into the destination, then inspect the transferred node and both sequences. The saved iterator now refers to the node in the destination.
#include <algorithm>
#include <iostream>
#include <list>
int main() {
std::list<int> backlog{1, 2, 3};
std::list<int> ready;
auto selected = std::find(backlog.begin(), backlog.end(), 2);
if (selected == backlog.end()) {
std::cout << "Job missing\n";
return 0;
}
ready.splice(ready.end(), backlog, selected);
std::cout << "Transferred: " << *selected << '\n';
std::cout << "Backlog:";
for (int id : backlog)
std::cout << ' ' << id;
std::cout << '\n';
std::cout << "Ready:";
for (int id : ready)
std::cout << ' ' << id;
std::cout << '\n';
}Transferred: 2
Backlog: 1 3
Ready: 2Splice preserves the transferred element's identity under its contract. Do not compare its iterator against the old list's end as though it still belonged there. Custom allocators require checking the node-transfer preconditions; allocator compatibility is not an optional performance hint.
C++ List and Deque Container Choices FAQ
Is list insertion always faster than vector insertion?
Only the insertion at a known list position has the favorable node operation. Finding that position, allocating a node and traversing the result can dominate the real workload. Vector's contiguous storage often helps traversal. Measure the full use case and choose from requirements, rather than comparing one isolated operation while ignoring the work needed to reach it.
Can deque be treated as one contiguous array?
No. It offers random access but does not guarantee one contiguous block of elements. A pointer to its first element plus its size is not a valid substitute for a vector-like contiguous range. Use iterators or an explicit copied buffer when an external API requires contiguity. Random access and contiguous storage are separate properties.
Why does std::sort reject list iterators?
The algorithm requires random-access iterators, while list iterators are bidirectional. List supplies a member sort designed for its structure. Choose that operation or intentionally transform the data when appropriate. The compiler error reflects the algorithm's capability requirement; it is not a reason to force pointer arithmetic onto a linked structure.
Does splice preserve the moved element's iterator?
Under its specified valid preconditions, the iterator continues to refer to the moved node, now in the destination list. That includes respecting allocator requirements for transfers between lists. The node's collection membership has changed, so use destination traversal boundaries appropriately. Erasing the node later still invalidates its handles, and concurrent access needs separate synchronization.
C++ List and Deque Container Choices Exercises
Answer each one and check it instantly. If you get stuck, open the hint before the answer.
A compatible-allocator list node is spliced into another list. What should the caller remember?
C++ List and Deque Container Choices Quiz
2 questions to check what you learned.
Which statement about deque is correct?
- Its elements are guaranteed to form one contiguous array.
- It permits dereferencing front on an empty container.
- It supports efficient endpoint operations and random access.
- Every iterator remains valid after every mutation.
Why can a list still be slow for insertion by a searched value?
- Its iterators are random-access pointers.
- List insertion always copies every other node.
- Locating a value is constant time because insertion at a known node is constant time.
- Finding the position can require linear traversal.