deque, list and forward_list
std::vector is the default sequence because it is contiguous and cheap to iterate. The other three sequences trade that for a different cost: a deque makes push_front cheap, a list makes insertion in the middle cheap once the position is known, and a forward_list stores one link per node instead of two.
The operations are where the difference shows: a vector cannot push_front, a list has splice and no [] operator, and insert and erase always take an iterator because an index would cost a walk. This lesson uses each container for the operation it is good at.
deque
std::deque is a double-ended queue: it supports push_front and push_back in constant time, and it still supports [] and random access. It does that by keeping a map of fixed-size blocks instead of one contiguous array.
The program pushes at both ends and prints the result. The order is the order of the pushes from the front followed by the pushes from the back.
A deque is the default container under std::stack and std::queue, which is why the adaptors of the next lesson do not need a vector. Its iterators are random access, so the algorithms of lesson 050 work on it.
A deque grows in blocks, so its elements are not contiguous and a pointer into it cannot be passed to a C function. The vector remains the container for a buffer that a library reads directly.
#include <deque>
#include <iostream>
int main()
{
std::deque<int> values;
values.push_back(3);
values.push_back(4);
values.push_front(2);
values.push_front(1);
for (int value : values) {
std::cout << value << ' ';
}
std::cout << '\n';
}
g++ -std=c++23 -Wall -Wextra deque.cpp -o deque_demo
./deque_demo
1 2 3 4
list and splice
std::list is a doubly linked list. Insertion and erase are constant time when the position is an iterator, and no element moves; the cost is one allocation per node and a pointer chase per step.
splice moves nodes from one list to another without copying or allocating. The program moves one element from the second list to the front of the first, and both lists print their new contents.
A list has no operator[] and no random access iterators, so the standard sort cannot run on it. It has its own sort member that relinks nodes, which is the next section's point.
#include <iostream>
#include <list>
int main()
{
std::list<int> first{1, 2, 3};
std::list<int> second{7, 8};
auto it = second.begin();
first.splice(first.begin(), second, it);
for (int value : first) {
std::cout << value << ' ';
}
std::cout << "| ";
for (int value : second) {
std::cout << value << ' ';
}
std::cout << '\n';
}
g++ -std=c++23 -Wall -Wextra list.cpp -o list_demo
./list_demo
7 1 2 3 | 8
forward_list
std::forward_list is a singly linked list: each node has one pointer, so the container is smaller than a list and cannot walk backwards. It has no size() and no push_back, because both would need a walk.
Insertion uses insert_after and a before_begin() iterator, which points before the first element so that the head can be modified. The program inserts three values in order and prints the result.
The container is for the case where memory per node matters and iteration only moves forward. For most code a vector is smaller, faster and simpler; forward_list earns its place in embedded and in intrusive structures.
#include <forward_list>
#include <iostream>
int main()
{
std::forward_list<int> values;
values.insert_after(values.before_begin(), 3);
values.insert_after(values.before_begin(), 2);
values.insert_after(values.before_begin(), 1);
for (int value : values) {
std::cout << value << ' ';
}
std::cout << '\n';
}
g++ -std=c++23 -Wall -Wextra forward_list.cpp -o forward_list_demo
./forward_list_demo
1 2 3
Erasing while iterating
erase returns an iterator to the next element, which is the only safe way to remove elements in a loop. The program removes every even number from a list with that pattern.
The loop does not increment in the erasing branch: the returned iterator is already the next element. Incrementing as well would skip one element, which is the classic bug of this loop.
The same pattern works for a vector, a map and a set. It is the reason erase returns an iterator instead of void.
#include <iostream>
#include <list>
int main()
{
std::list<int> values{1, 2, 3, 4, 5, 6};
for (auto it = values.begin(); it != values.end();) {
if (*it % 2 == 0) {
it = values.erase(it);
} else {
++it;
}
}
for (int value : values) {
std::cout << value << ' ';
}
std::cout << '\n';
}
g++ -std=c++23 -Wall -Wextra erase.cpp -o erase_list
./erase_list
1 3 5
std::sort needs random access
The standard sort moves elements by index arithmetic, so it requires random access iterators. A list provides bidirectional iterators and the call has no matching overload.
The program sorts a list with std::sort, and the message says there is no matching function and lists the candidates, all of which require random access. The fix is values.sort(), the member that relinks the nodes.
The same error appears for std::reverse, std::shuffle and any algorithm that needs it + n. Sorting a list with the member is also faster, because no element is copied.
#include <algorithm>
#include <list>
int main()
{
std::list<int> values{3, 1, 2};
std::sort(values.begin(), values.end());
return values.front();
}
g++ -std=c++23 -Wall -Wextra sort_list.cpp -o sort_list
In file included from /usr/include/c++/15.2.0/algorithm:63,
from sort_list.cpp:1:
/usr/include/c++/15.2.0/bits/stl_algo.h: In instantiation of 'constexpr void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = _List_iterator<int>; _Compare = __gnu_cxx::__ops::_Iter_less_iter]':
/usr/include/c++/15.2.0/bits/stl_algo.h:4841:18: required from 'constexpr void std::sort(_RAIter, _RAIter) [with _RAIter = _List_iterator<int>]'
4841 | std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sort_list.cpp:7:14: required from here
7 | std::sort(values.begin(), values.end());
| ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/15.2.0/bits/stl_algo.h:1907:50: error: no match for 'operator-' (operand types are 'std::_List_iterator<int>' and 'std::_List_iterator<int>')
1907 | std::__lg(__last - __first) * 2,
| ~~~~~~~^~~~~~~~~
/usr/include/c++/15.2.0/bits/stl_algo.h:1907:50: note: there are 2 candidates
In file included from /usr/include/c++/15.2.0/bits/stl_algobase.h:67,
from /usr/include/c++/15.2.0/algorithm:62:
/usr/include/c++/15.2.0/bits/stl_iterator.h:620:5: note: candidate 1: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__y.base() - __x.base())) std::operator-(const reverse_iterator<_IteratorL>&, const reverse_iterator<_IteratorR>&)'
620 | operator-(const reverse_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/15.2.0/bits/stl_iterator.h:620:5: note: template argument deduction/substitution failed:
/usr/include/c++/15.2.0/bits/stl_algo.h:1907:50: note: 'std::_List_iterator<int>' is not derived from 'const std::reverse_iterator<_IteratorL>'
1907 | std::__lg(__last - __first) * 2,
| ~~~~~~~^~~~~~~~~
/usr/include/c++/15.2.0/bits/stl_iterator.h:1785:5: note: candidate 2: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__x.base() - __y.base())) std::operator-(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)'
1785 | operator-(const move_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/15.2.0/bits/stl_iterator.h:1785:5: note: template argument deduction/substitution failed:
/usr/include/c++/15.2.0/bits/stl_algo.h:1907:50: note: 'std::_List_iterator<int>' is not derived from 'const std::move_iterator<_IteratorL>'
1907 | std::__lg(__last - __first) * 2,
| ~~~~~~~^~~~~~~~~
Exercises
- Push a thousand values at both ends of a deque and a vector and compare the sizes and the time with a stopwatch.
- Use list::sort to order the list in sort_list.cpp and check that no element was copied.
- Remove every value above 3 from a forward_list with remove_if and print the result.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
Which sequence is cheapest for push_front?
Answer
std::deque
A deque keeps a map of blocks, so it can add at both ends without moving the elements.
-
What does
list.splicedo?Answer
It moves nodes between lists without copying the elements
The nodes are relinked, which is the operation a list exists for.
-
What does a
forward_listsave compared with alist?Answer
One back pointer per node
The singly linked list stores only the next pointer.
-
What must a loop do when it erases from a list?
Answer
Use the iterator that erase returns
The erased iterator is invalid, and the returned one points at the next element.
-
What does this program print?
#include <deque> #include <iostream> int main() { std::deque<int> values{2, 3}; values.push_front(1); values.push_back(4); for (int v : values) std::cout << v << ' '; }Answer
1 2 3 4
The front insert goes before the two elements, and the back insert after them.
-
What does this program print?
#include <iostream> #include <list> int main() { std::list<int> first{1, 2, 3}; std::list<int> second{8}; second.splice(second.begin(), first); std::cout << first.size() << ' ' << second.size() << ' '; std::cout << second.front() << ' ' << second.back(); }Answer
0 4 1 8
The splice empties the first list and puts its nodes at the front of the second.
-
What does this program print?
#include <forward_list> #include <iostream> int main() { std::forward_list<int> values{1, 2, 3}; values.push_front(0); for (int v : values) std::cout << v << ' '; }Answer
0 1 2 3
The forward list only adds at the front, and the loop reads it in order.
-
What does this program print?
#include <iostream> #include <list> int main() { std::list<int> values{1, 2, 3, 4, 5}; for (auto it = values.begin(); it != values.end();) { if (*it % 2 == 0) it = values.erase(it); else ++it; } for (int v : values) std::cout << v << ' '; }Answer
1 3 5
erase returns the next element, and the loop continues from it without skipping.
-
What does the compiler report for this call?
#include <algorithm> #include <list> int main() { std::list<int> values{3, 1, 2}; std::sort(values.begin(), values.end()); }Answer
no match for 'operator-' on two list iterators
std::sort needs random access, and a list iterator only moves one step at a time; the list has its own sort member.
-
When is a deque better than a vector?
Answer
When elements are added and removed at both ends
The deque avoids moving the whole block when it grows at the front.
The code on this page was built with g++ 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container. The programs whose section shows a compiler error were compiled until that error and were not run.
Article author: Arthur Isaev
