std::forward_list
- Create Linked Lists in C++std::forward_list
container to create linked lists.C++ programmers are always searching for ways to optimize data structures and boost performance. One powerful container that deserves attention is the linked list.
The C++ standard library provides a ready-made way for us to create linked lists, which it refers to as forward lists.
In this article, we'll explore the basics of the C++ std::forward_list
container and discuss its key features, advantages, and use cases.
Whether you're a beginner or an experienced programmer, this guide will help you master the std::forward_list and take your C++ coding skills to the next level.
The theory of linked lists, how they work, and how they compare to arrays, is covered here:
There are several different implementations of linked lists, with different capabilities. The most basic form of a linked list is what we described in the previous lesson. In that example, each item in the linked list had a link to only the next item in the list.
This is sometimes referred to as a singly linked list, or a forward list, as the list can only be traversed in one direction -Â forward.
We could expand this concept such that each item in the list also includes a link to the previous item. This would create a doubly linked list, where we can traverse the list in either direction - forward or back.
The C++ standard library also includes an implementation of doubly linked lists, which it calls std::list
. This lesson focuses on the singly linked list, std::forward_list
, but everything we cover also applies to std::list
.
Forward lists are available by including <forward_list>
#include <forward_list>
We can create a forward list by specifying the type of items it will contain:
#include <forward_list>
int main() {
std::forward_list<int> MyList;
}
If we are providing items at the same time we are creating the list, we can omit the type and let the compiler deduce it. This is using class template argument deduction (CTAD):
#include <forward_list>
int main() {
std::forward_list MyList { 1, 2, 3, 4, 5 };
}
The first element in a linked list can be accessed by calling front
:
#include <iostream>
#include <forward_list>
int main() {
std::forward_list MyList { 1, 2, 3, 4, 5 };
std::cout << MyList.front();
}
1
Forward lists support iterators, so we can traverse them using range-based for loops:
#include <iostream>
#include <forward_list>
int main() {
std::forward_list MyList { 1, 2, 3, 4, 5 };
for (int x : MyList) {
std::cout << x << " ";
}
}
1 2 3 4 5
Iterators and range-based for loops are covered in more detail here:
Given the performance characteristics of forward lists, the most efficient way to add items to the list is at the front. std::forward_list
provides two methods for doing this: push_front
and emplace_front
The push_front
method takes an existing object that has already been constructed, and moves or copies it to the front of our linked list:
#include <iostream>
#include <string>
#include <forward_list>
struct Character {
Character(std::string Name):
Name {Name}
{};
std::string Name;
};
int main() {
std::forward_list<Character> MyList;
Character Wizard { "Gandalf" };
MyList.push_front(Wizard);
std::cout << MyList.front().Name;
}
Gandalf
The emplace_front
method constructs a new object in place. The arguments that are provided to emplace_front
are forwarded to the constructor of that type:
#include <iostream>
#include <string>
#include <forward_list>
struct Character {
Character(std::string Name):
Name {Name}
{};
std::string Name;
};
int main() {
std::forward_list<Character> MyList;
MyList.emplace_front("Gandalf");
std::cout << MyList.front().Name;
}
Gandalf
Because emplace_front
eliminates the need to copy or move an object, it is more performant, so should be preferred over push_front
where possible.
It is possible to add items to any position in a forward list, using insert_after
or emplace_after
.
Similar to our previous section, insert_after
will move or copy an existing object into our list, whilst emplace_after
will construct it in place.
However, the first argument that these two methods require is a description of where in the list to insert our new object. Given we lack the ability to directly access random positions in the list, we need to traverse to the correct position first.
As such, the first argument to insert_after
and emplace_after
is an iterator, after which our new addition will be inserted or constructed.
We can replicate the behavior of insert_front
and emplace_front
by passing the iterator returned from before_begin()
:
#include <iostream>
#include <forward_list>
int main() {
std::forward_list MyList { 0, 0, 0, 0, 0 };
MyList.emplace_after(MyList.before_begin(), 1);
for (int x : MyList) {
std::cout << x << " ";
}
}
1 0 0 0 0 0
We can insert an object into the second position by passing the iterator returned from begin()
:
#include <iostream>
#include <forward_list>
int main() {
std::forward_list MyList { 0, 0, 0, 0, 0 };
MyList.emplace_after(MyList.begin(), 1);
for (int x : MyList) {
std::cout << x << " ";
}
}
0 1 0 0 0 0
We can traverse our list to get an iterator for any position using std::next
, available by including <iterator>
std::next
accepts two arguments - an iterator from which to begin traversal, and a number representing how many steps to traverse.
Here, we see how we can use std::next
to get an iterator to the 3rd element, and then use emplace_after
to construct a new object after that position:
#include <iostream>
#include <iterator>
#include <forward_list>
int main() {
std::forward_list MyList { 0, 0, 0, 0, 0 };
auto Iterator { std::next(MyList.before_begin(), 3) };
MyList.emplace_after(Iterator, 1);
for (int x : MyList) {
std::cout << x << " ";
}
}
0 0 0 1 0 0
There are several ways we can remove items from our linked lists:
pop_front
We can remove the first element in a linked list using pop_front
:
#include <iostream>
#include <forward_list>
int main() {
std::forward_list MyList { 1, 2, 3, 4, 5 };
MyList.pop_front();
for (int x : MyList) {
std::cout << x << " ";
}
}
2 3 4 5
remove
We can remove all elements that are equal to a provided object, using the remove
 method:
#include <iostream>
#include <forward_list>
int main() {
std::forward_list MyList { 1, 2, 3, 4, 5 };
MyList.remove(3);
for (int x : MyList) {
std::cout << x << " ";
}
}
1 2 4 5
Note, for this to work, the object type stored in our list must define what it means for two objects of its type to be equal. That means the type must implement the equality operator, ==
The built-in int
type support the ==
operator, so our earlier example works as expected. But not every type implements ==
. This is particularly likely of any custom types we create.
Refer to the following lesson for an introduction on how we can define operators for our own custom types:
remove_if
The remove_if
method on linked list allows us to pass a predicate. Objects will be removed if that predicate returns true
when passed the object:
#include <iostream>
#include <forward_list>
int main() {
std::forward_list MyList { 1, 2, 3, 4, 5 };
auto isEven {
[](int Number) { return Number % 2 == 0; }
};
MyList.remove_if(isEven);
for (int x : MyList) {
std::cout << x << " ";
}
}
1 3 5
Prior to C++20, remove
and remove_if
do not return anything (ie, their return type is void
)
Since C++20, they now return a number representing the quantity of elements that were removed from the list:
#include <iostream>
#include <forward_list>
int main() {
std::forward_list MyList { 1, 2, 3, 4, 5 };
auto isEven {
[](int Number) { return Number % 2 == 0; }
};
std::cout << MyList.remove_if(isEven)
<< " numbers were removed.";
}
2 numbers were removed.
clear
#include <iostream>
#include <forward_list>
int main() {
std::forward_list MyList { 1, 2, 3, 4, 5 };
MyList.clear();
MyList.emplace_front(7);
MyList.emplace_front(6);
for (int x : MyList) {
std::cout << x << " ";
}
}
6 7
erase_after
Similar to emplace_after
and insert_after
, erase_after
interacts with iterators, allowing us to remove elements from anywhere in the list.
Here, we remove the second element, by erasing the element after the begin()
 iterator:
#include <iostream>
#include <forward_list>
int main() {
std::forward_list MyList { 1, 2, 3, 4, 5 };
MyList.erase_after(MyList.begin());
for (int x : MyList) {
std::cout << x << " ";
}
}
1 3 4 5
Here, we use std::next
to create an iterator for the 2nd element. We pass it to erase_after
to remove the third element:
#include <iostream>
#include <iterator>
#include <forward_list>
int main() {
std::forward_list MyList { 1, 2, 3, 4, 5 };
auto Second = std::next(MyList.before_begin(), 2);
MyList.erase_after(Second);
for (int x : MyList) {
std::cout << x << " ";
}
}
1 2 4 5
Finally, erase_after
accepts a second argument. By passing an iterator here, we can specify a range of objects to remove. Here, we remove everything from the third element until the end:
#include <iostream>
#include <iterator>
#include <forward_list>
int main() {
std::forward_list MyList { 1, 2, 3, 4, 5 };
auto Second = std::next(MyList.before_begin(), 2);
MyList.erase_after(Second, MyList.end());
for (int x : MyList) {
std::cout << x << " ";
}
}
1 2
Linked lists can be sorted in-place using the sort
 method:
#include <iostream>
#include <forward_list>
int main() {
std::forward_list MyList { 3, 2, 5, 1, 4 };
MyList.sort();
for (int x : MyList) {
std::cout << x << " ";
}
}
1 2 3 4 5
The data type in our list needs to define what it means to be sorted. This is done by implementing the <
 operator.
Alternatively, the sort
method allows us to pass a function to it, to define the sorting behavior. This function will accept two objects from our list and will return true
if the first object should come before the second object.
Here, we sort our Characters by level:
#include <iostream>
#include <forward_list>
struct Character {
std::string Name;
int Level;
};
int main() {
std::forward_list MyList {
Character { "Gandalf", 20 },
Character { "Frodo", 10 },
Character { "Legolas", 15 },
};
auto ByLevel {
[](const Character& A, const Character& B){
return A.Level > B.Level;
}
};
MyList.sort(ByLevel);
for (auto x : MyList) {
std::cout << x.Level << " - " << x.Name << "\n";
}
}
20 - Gandalf
15 - Legolas
10 - Frodo
Comprehensive course covering advanced concepts, and how to use them on large-scale projects.