Linked Lists using std::forward_list
This lesson provides an in-depth exploration of std::forward_list
, covering creation, management, and advanced list operations
Similar to arrays like std::vector
and std::array
, a linked list lets us store a sequential collection of objects.
Unlike arrays, linked lists store their objects in a more free-form memory layout, that causes them to have different performance characteristics. We covered these characteristics, and their implications, in more detail in the previous lesson:
Data Structures and Algorithms
This lesson introduces the concept of data structures beyond arrays, and why we may want to use alternatives.
The std::forward_list
Type
The C++ standard library provides a ready-made way for us to create and manage linked lists, using the std::forward_list
type.
In this article, we'll explore the basics of the std::forward_list
container and discuss its key features, advantages, and use cases.
Creating Forward Lists
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. Below, we create a forward list that stores int
objects:
#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 };
}
Forward List Size
Unlike many other containers, std::forward_list
does not keep track of its size - that is, how many objects it currently contains. To determine its size, we need to traverse the entire list and keep track of how many links we had to follow.
The std::distance()
function can do this for us. We pass it the iterators returned from the begin()
and end()
methods respectively:
#include <forward_list>
#include <iostream>
int main() {
std::forward_list MyList { 1, 2, 3, 4, 5 };
std::cout << "Size: " << std::distance(
MyList.begin(), MyList.end());
}
Size: 5
Iterators
This lesson provides an in-depth look at iterators in C++, covering different types like forward, bidirectional, and random access iterators, and their practical uses.
Accessing Elements in a Linked List
The first element in a linked list can be accessed by calling the front()
method:
#include <forward_list>
#include <iostream>
int main() {
std::forward_list MyList{1, 2, 3, 4, 5};
std::cout << "Front: " << MyList.front();
}
Front: 1
To access elements in arbitrary positions, we need to traverse the links to that position.
We can do this using iterators and std::next()
. Below, we generate an iterator to the third position by traversing two steps from the begin()
iterator:
#include <forward_list>
#include <iostream>
int main() {
std::forward_list MyList{1, 2, 3, 4, 5};
auto Third{std::next(MyList.begin(), 2)};
std::cout << "Third: " << *Third;
}
Third: 3
As we covered in our earlier lessons, linked lists are not designed to support this access pattern. If we require fast access to our objects by index, we should likely be using an array instead of a linked list.
Range-Based For Loops
The std::forward_list
, container supports the range-based for-loop syntax, letting us easily iterate over the entire collection:
#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,
Adding Items to Forward Lists
The std::forward_list
provides two methods for adding objects to the start of our list: 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 {/*...*/}
int main() {
std::forward_list<Character> MyList;
Character Wizard { "Roderick" };
MyList.push_front(Wizard);
std::cout << "Front: " << MyList.front().Name;
}
Front: Roderick
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 {/*...*/}
int main() {
std::forward_list<Character> MyList;
MyList.emplace_front("Roderick");
std::cout << "Front: " << MyList.front().Name;
}
Front: Roderick
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.
Adding Items at any position using Iterators
Given the performance characteristics of forward lists, the most efficient way to add items to the list is at the front. Inserting an object at any other position requires us to traverse the list to find that position.
However, if we've already traversed the list and generated an iterator to the position we want to use, we can insert or emplace an object there 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.
Using insert_after()
The first argument to insert_after()
is an iterator pointing at the node we want our new object to be inserted after.
The second argument is the value to insert. Below, we generate an iterator to the third element using std::next()
, and then insert a new object after it (that is, in the fourth position):
#include <iostream>
#include <forward_list>
int main() {
std::forward_list MyList { 0, 0, 0, 0, 0 };
MyList.insert_after(
std::next(MyList.begin(), 2), 1);
for (int x : MyList) {
std::cout << x << " ";
}
}
0 0 0 1 0 0
Using emplace_after()
As before, if we can construct our object directly into the linked list, that will be more performant than constructing it outside, and then moving it in.
The emplace_after()
method lets us do this. We pass an iterator as the first argument.
Any additional arguments we provide will be forwarded to an appropriate constructor of the underlying type our list is storing:
#include <iostream>
#include <string>
#include <forward_list>
struct Character {/*...*/}
int main() {
std::forward_list<Character> MyList;
MyList.emplace_front("Roderick", 50);
MyList.emplace_after(
MyList.begin(), "Anna", 45);
for (Character& C : MyList) {
std::cout << std::format(
"{}, Level {}\n", C.Name, C.Level);
}
}
Roderick, Level 50
Anna, Level 45
Removing and Filtering Items from Forward Lists
There are several ways we can remove items from our linked lists:
Removing the First Object with 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,
Removing Objects by Value with remove()
We can remove all elements that are equal to a provided value, 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,
Removing Objects Based on a Predicate Using remove_if()
The remove_if()
method on the linked list allows us to pass a predicate - a function that receives an object and returns a boolean. The remove_if()
algorithm will pass every object in our collection to our predicate one at a time, and remove any for which our predicate returns true
:
Below, we use this to remove all the negative numbers from our linked list:
#include <iostream>
#include <forward_list>
bool isNegative(int x) { return x < 0; }
int main() {
std::forward_list MyList { -1, 4, -3, 2, 0 };
MyList.remove_if(isNegative);
for (int x : MyList) {
std::cout << x << " ";
}
}
4, 2, 0
Before 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 number of elements that were removed from the list:
#include <forward_list>
#include <iostream>
bool isNegative(int x) { return x < 0; }
int main() {
std::forward_list MyList{-1, 4, -3, 2, 0};
std::cout << "Removed "
<< MyList.remove_if(isNegative)
<< " Objects";
}
Removed 2 Objects
Removing All Objects Using clear()
The clear()
method simply removes all the objects from the linked list:
#include <forward_list>
#include <iostream>
int main() {
std::forward_list MyList{1, 2, 3, 4, 5};
std::cout << "Size: " << std::distance(
MyList.begin(), MyList.end());
MyList.clear();
std::cout << "\nNew Size: " << std::distance(
MyList.begin(), MyList.end());
}
Size: 5
New Size: 0
Removing Objects Using Iterators with erase_after()
Similar to emplace_after()
and insert_after()
, the erase_after()
method 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,
Erasing Multiple Objects using Iterators
The erase_after()
accepts a second argument. By passing an iterator here, we can specify a range of objects to remove. Objects from the first iterator until the second iterator will be erased, excluding those objects.
Below, we remove everything after the first element until the end of the container, leaving us with only one object. Remember. end()
is a "past-the-end" iterator, meaning the last element of the collection is included in this range:
#include <forward_list>
#include <iostream>
#include <iterator>
int main() {
std::forward_list MyList{1, 2, 3, 4, 5};
auto Start = MyList.begin();
MyList.erase_after(Start, MyList.end());
std::cout << "List Contents: ";
for (int x : MyList) {
std::cout << x << ", ";
}
}
List Contents: 1,
Below, we erase everything from position 2 to position 5, excluding those objects:
#include <forward_list>
#include <iostream>
#include <iterator>
int main() {
std::forward_list MyList{1, 2, 3, 4, 5};
auto Start = std::next(MyList.begin(), 1);
auto End = std::next(Start, 3);
MyList.erase_after(Start, End);
std::cout << "List Contents: ";
for (int x : MyList) {
std::cout << x << ", ";
}
}
List Contents: 1, 2, 5,
Sorting a std::forward_list
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
This is another example of an algorithm that has underlying requirements. Specifically, the data type in our list needs to define what it means for their objects to be sorted. This is done by implementing the <
operator.
Customizing the Sort Behaviour
The sort()
method allows us to pass a function to it, to customize how our objects are sorted. This function will receive two objects from our list and will return true
if the first object should come before the second object.
Using this overload of the sort()
method also means the algorithm no longer needs to use the <
operator, meaning it is compatible with types that don't implement it.
Here, we sort our Characters by level:
#include <iostream>
#include <forward_list>
struct Character {
std::string Name;
int Level;
};
bool isHigherLevel(
const Character& A, const Character& B) {
return A.Level > B.Level;
}
int main() {
std::forward_list MyList {
Character { "Anna", 20 },
Character { "Roderick", 10 },
Character { "Bruce", 15 },
};
MyList.sort(isHigherLevel);
for (auto x : MyList) {
std::cout
<< x.Level << " - " << x.Name << '\n';
}
}
20 - Anna
15 - Bruce
10 - Roderick
Summary
In this lesson, we have explored std::forward_list
, learning how to create, manage, and manipulate singly-linked lists. The key topics we learned included:
- The differences between arrays (like
std::vector
andstd::array
) and linked lists (std::forward_list
), especially in terms of memory layout. - Creating forward lists using the
<forward_list>
header. - Using
std::distance()
to determine the size of astd::forward_list
, as it does not track its size natively. - Accessing the first element with
front()
and arbitrary elements using iterators andstd::next()
. - Limitations of
std::forward_list
in backward traversal and the inability to use negative offsets withstd::next()
. - Implementing range-based for loops to iterate over
std::forward_list
. - Adding elements to a forward list using
push_front()
andemplace_front()
. - Inserting and emplacing elements at specific positions with
insert_after()
andemplace_after()
. - Various methods of removing items from the list, including
pop_front()
,remove()
,remove_if()
,clear()
, anderase_after()
. - Sorting
std::forward_list
using thesort()
method and customizing the sort behavior with a comparison function.
Hashing and std::hash
This lesson provides an in-depth look at hashing in C++, including std::hash
, collision strategies, and usage in hash-based containers.