C++ / STANDARD CONTAINERS
std::deque, std::list, and node-based trade-offs
Pick between std::deque and std::list from their memory layout, and say exactly which iterators and references survive each operation.
What you will learn
- Pick deque for O(1) push/pop at both ends plus indexing, but no contiguous data()
- Deque end-insertion keeps references valid while invalidating every iterator
- Reach for list::sort and list::splice instead of std::sort or copying between lists
- Judge list by the walk to a position, not the O(1) insert once you hold the iterator
Understanding std::deque, std::list, and node-based trade-offs
A std::deque is not one buffer. It is an array of pointers (the block map) where each pointer owns a fixed-size block of contiguous elements, so d[i] costs two indirections: work out which block holds i, then index inside that block. Growing at either end chains on a new block instead of copying the old elements somewhere else, which is why push_back and push_front are amortised O(1) and why references and pointers to existing elements stay valid across them, even though all iterators are invalidated because the block map itself may have moved. The price is that the elements are not one array: there is no data(), no reserve(), no capacity(), and inserting or erasing in the middle invalidates iterators and references alike.
A std::list is a chain of independently allocated nodes, each holding a prev pointer, a next pointer, and the value. Because there is no index arithmetic to be done, its iterators are only bidirectional, so std::sort will not compile on it and the container supplies its own sort, merge, reverse, unique, and remove_if as members that rewire prev and next rather than assigning values around. splice is the operation that only a node-based container can offer: it detaches nodes from one list and links them into another in constant time, without touching the elements. In exchange for all that relinking, every iterator, pointer, and reference stays valid until the element it names is itself erased, which is the strongest stability guarantee in the standard library.
The trade-off people get wrong is that O(1) insertion is only free once you already hold the iterator, and getting there means following pointers one node at a time. Each hop lands wherever the allocator happened to put that node, so the CPU stalls on cache misses, while a vector of the same data streams through memory and prefetches ahead; a list<int> node also costs roughly 24 bytes plus allocator bookkeeping to store 4 bytes of payload. So the mental model is: default to vector, move to deque when you genuinely push and pop at both ends and still want subscripting, and move to list only when you need iterators and references that never move, or when you splice nodes you already point at.
<deque>
<iostream>
<iterator>
<list>
int main() {
std::deque<int> d{10, 20, 30};
d.push_front(5);
d.push_back(40);
int* p = &d[2]; // the element 20
for (int i = 0; i < 1000; ++i) d.push_back(i);
std::cout << "d.size() = " << d.size() << ", d[0] = " << d[0] << '\n';
std::cout << "*p = " << *p << " (end insertion never moves elements)\n";
std::list<int> a{1, 2, 3};
std::list<int> b{7, 8};
auto it = std::next(a.begin()); // the element 2
a.splice(a.begin(), b); // relink b's nodes into a
std::cout << "a:";
for (int v : a) std::cout << ' ' << v;
std::cout << "\nb.size() = " << b.size() << ", *it = " << *it << '\n';
}
A container's memory layout, not its big-O table, decides both its real cost and what stays valid: chained blocks for deque, scattered nodes for list.
Worked examples
list::sort relinks nodes
Sorting a list reorders the chain without moving any value, so an old iterator still names the same element.
<iostream>
<iterator>
<list>
int main() {
std::list<int> l{5, 1, 4, 2, 3};
auto it = l.begin(); // the node holding 5
l.sort(); // member sort, not std::sort
std::cout << "sorted:";
for (int v : l) std::cout << ' ' << v;
std::cout << "\n*it = " << *it << '\n';
std::cout << "position of it = " << std::distance(l.begin(), it) << '\n';
}
Example explained
Line 1l.sort() has to be a member because std::sort demands random-access iterators and std::list only offers bidirectional ones.
Line 2*it is still 5 because the sort rewired prev/next pointers; no value was assigned over the node it points at.
Line 3std::distance must walk the chain to report 4, and that walk is exactly why a list has no operator[].
Deque as a fixed-size window
A rolling history needs cheap removal at the front and indexing at the same time, which is the case deque is built for.
<cstddef>
<deque>
<iostream>
int main() {
std::deque<int> window;
const std::size_t cap = 3;
for (int x : {1, 2, 3, 4, 5}) {
window.push_back(x);
if (window.size() > cap) window.pop_front();
std::cout << "after " << x << ':';
for (int v : window) std::cout << ' ' << v;
std::cout << " (front=" << window.front()
<< ", window[0]=" << window[0] << ")\n";
}
}
Example explained
Line 1pop_front() only moves deque's internal start position inside the first block, whereas a vector would shift every surviving element on erase(begin()).
Line 2window[0] compiles because deque iterators are random access; the same subscript on a std::list is a compile error.
Line 3front() and window[0] always agree here, which shows nothing was copied when the window slid forward.
Erasing while other iterators stay alive
list::erase returns the next node, and iterators to untouched nodes remain valid throughout.
<iostream>
<iterator>
<list>
int main() {
std::list<int> l{1, 2, 3, 4, 5, 6};
auto keep = std::next(l.begin(), 4); // the element 5
for (auto it = l.begin(); it != l.end(); ) {
if (*it % 2 == 0) it = l.erase(it);
else ++it;
}
std::cout << "kept:";
for (int v : l) std::cout << ' ' << v;
std::cout << "\n*keep = " << *keep << " after 3 erasures\n";
}
Example explained
Line 1it = l.erase(it) is required because erase destroys the node, so the old iterator cannot be incremented afterwards.
Line 2The ++it lives in the else branch only; advancing in the loop header would step from a node that may already be gone.
Line 3*keep is still 5 because a list node's address never changes and erase invalidates only iterators to the erased nodes.
Important notes
Deque block size is implementation-defined: libstdc++ uses 512-byte blocks, while MSVC uses 16 bytes, so a deque<int> there holds only four elements per block and allocates far more often.
std::list::size() is constant time since C++11, but there is still no operator[]; std::next(l.begin(), n) costs n hops, and std::forward_list drops the prev pointer and size() entirely if you only ever walk forward.
Common mistakes
Treating &d[0] as the start of one array and handing it to memcpy or a C API: a deque's elements live in separate blocks, so the copy runs past the end of the first block into unrelated memory.
Caching a deque iterator across push_back or push_front: the standard invalidates all iterators there even though a pointer to the same element would still be fine, so the loop reads a stale block pointer.
Choosing std::list "because insertion is O(1)" and then calling std::find or std::advance to reach the position: every insert becomes a cache-missing linear walk that loses to vector's single memmove.
Calling std::sort(l.begin(), l.end()) on a list and being surprised by a wall of template errors instead of a clear message about the missing random-access iterator.
Try it yourself
Change, predict, then run
Write a std::deque<int> that keeps only the last four values pushed, printing window[0] and window.back() after each push of 1 through 8. Then change the type to std::list<int> and note which line stops compiling and why.
Open the C++ workspaceCheck your understanding
You hold int* p = &d[0] and auto it = d.begin() into a std::deque<int>, then call d.push_back(x), which needs a new block. What does the standard guarantee?
- p stays valid; it may be invalidated
- Both stay valid, because no existing element was moved
- Both are invalidated, because deque reallocates its storage like vector
- it stays valid; p is invalidated because the block holding d[0] was moved
Show answer
Inserting at either end of a deque never moves existing elements, so pointers and references to them keep pointing at live objects. Option 1 is tempting for exactly that reason, but an iterator is more than an address: it also carries a position in the map of block pointers, and appending a block can reallocate that map, so the standard invalidates all deque iterators on any end insertion.