Linked Lists using std::forward_list

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>

1#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:

1#include <forward_list>
2
3int main() {
4  std::forward_list<int> MyList;
5}

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):

1#include <forward_list>
2
3int main() {
4  std::forward_list MyList { 1, 2, 3, 4, 5 };
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:

1#include <forward_list>
2#include <iostream>
3
4int main() {
5  std::forward_list MyList { 1, 2, 3, 4, 5 };
6  std::cout << "Size: " << std::distance(
7    MyList.begin(), MyList.end());
8}

1Size: 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:

1#include <forward_list>
2#include <iostream>
3
4int main() {
5  std::forward_list MyList{1, 2, 3, 4, 5};
6  std::cout << "Front: " << MyList.front();
7}

1Front: 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:

1#include <forward_list>
2#include <iostream>
3
4int main() {
5  std::forward_list MyList{1, 2, 3, 4, 5};
6  auto Third{std::next(MyList.begin(), 2)};
7  std::cout << "Third: " << *Third;
8}

1Third: 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.

1#include <forward_list>
2
3int main() {
4  std::forward_list MyList{1, 2, 3, 4, 5};
5  std::next(MyList.end(), -1);
6}

1error: negative advance of non-bidirectional iterator
2example.exe (process 39308) exited with code 3.

Range-Based For Loops

The std::forward_list, container supports the range-based for-loop syntax, letting us easily iterate over the entire collection:

1#include <iostream>
2#include <forward_list>
3
4int main() {
5  std::forward_list MyList { 1, 2, 3, 4, 5 };
6
7  for (int x : MyList) {
8    std::cout << x << ", ";
9  }
10}

11, 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:

1#include <iostream>
2#include <string>
3#include <forward_list>
4
Character Struct|Show
5struct Character {/*...*/}
9
10int main() {
11  std::forward_list<Character> MyList;
12  Character Wizard { "Roderick" };
13  MyList.push_front(Wizard);
14
15  std::cout << "Front: " << MyList.front().Name;
16}

1Front: 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:

1#include <iostream>
2#include <string>
3#include <forward_list>
4
Character Struct|Show
5 struct Character {/*...*/}
9
10int main() {
11  std::forward_list<Character> MyList;
12  MyList.emplace_front("Roderick");
13
14  std::cout << "Front: " << MyList.front().Name;
15}

1Front: 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.

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):

1#include <iostream>
2#include <forward_list>
3
4int main() {
5  std::forward_list MyList { 0, 0, 0, 0, 0 };
6  MyList.insert_after(
7    std::next(MyList.begin(), 2), 1);
8
9  for (int x : MyList) {
10    std::cout << x << " ";
11  }
12}

10 0 0 1 0 0

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:

1#include <iostream>
2#include <string>
3#include <forward_list>
4
Character Struct|Show
5 struct Character {/*...*/}
10
11int main() {
12  std::forward_list<Character> MyList;
13  MyList.emplace_front("Roderick", 50);
14  MyList.emplace_after(
15    MyList.begin(), "Anna", 45);
16
17  for (Character& C : MyList) {
18    std::cout << std::format(
19      "{}, Level {}\n", C.Name, C.Level);
20  }
21}

1Roderick, Level 50
2Anna, 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 pop_front()

We can remove the first element in a linked list using pop_front:

1#include <iostream>
2#include <forward_list>
3
4int main() {
5  std::forward_list MyList { 1, 2, 3, 4, 5 };
6  MyList.pop_front();
7
8  for (int x : MyList) {
9    std::cout << x << ", ";
10  }
11}

12, 3, 4, 5,

Removing Objects by Value using remove()

We can remove all elements that are equal to a provided value, using the remove() method:

1#include <iostream>
2#include <forward_list>
3
4int main() {
5  std::forward_list MyList { 1, 2, 3, 4, 5 };
6  MyList.remove(3);
7
8  for (int x : MyList) {
9    std::cout << x << ", ";
10  }
11}

11, 2, 4, 5,

Algorithm Requirements

When using algorithms on containers of a certain type, some of those algorithms may have additional requirements of that type.

For example, the remove() algorithm removes any objects that pass an equality check. Therefore, the type we’re storing in our container must support that action.

Specifically, the type must support the equality operator, ==, where the right operand is an object of that same type.

The built-in int type supports the == operator, so our earlier example works as expected.

For more details on the requirements of any algorithm, we should check the documentation. Standard library references are available from many online sources, such as cppreference.com

We introduced how to implement capabilities like == to our custom types in our introductory lesson on operator overloading:

Operator Overloading

This lesson introduces operator overloading, a fundamental concept to create more intuitive and readable code by customizing operators for user-defined types

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:

1#include <iostream>
2#include <forward_list>
3
4bool isNegative(int x) { return x < 0; }
5
6int main() {
7  std::forward_list MyList { -1, 4, -3, 2, 0 };
8
9  MyList.remove_if(isNegative);
10
11  for (int x : MyList) {
12    std::cout << x << " ";
13  }
14}

14, 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:

1#include <forward_list>
2#include <iostream>
3
4bool isNegative(int x) { return x < 0; }
5
6int main() {
7  std::forward_list MyList{-1, 4, -3, 2, 0};
8
9  std::cout << "Removed "
10    << MyList.remove_if(isNegative)
11    << " Objects";
12}

1Removed 2 Objects

Removing all objects using clear()

The clear() method simply removes all the objects from the linked list:

1#include <forward_list>
2#include <iostream>
3
4int main() {
5  std::forward_list MyList{1, 2, 3, 4, 5};
6  std::cout << "Size: " << std::distance(
7    MyList.begin(), MyList.end());
8
9  MyList.clear();
10
11  std::cout << "\nNew Size: " << std::distance(
12    MyList.begin(), MyList.end());
13}

1Size: 5
2New 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:

1#include <iostream>
2#include <forward_list>
3
4int main() {
5  std::forward_list MyList { 1, 2, 3, 4, 5 };
6  MyList.erase_after(MyList.begin());
7
8  for (int x : MyList) {
9    std::cout << x << ", ";
10  }
11}

11, 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:

1#include <iostream>
2#include <iterator>
3#include <forward_list>
4
5int main() {
6  std::forward_list MyList { 1, 2, 3, 4, 5 };
7  auto Second = std::next(MyList.before_begin(), 2);
8  MyList.erase_after(Second);
9
10  for (int x : MyList) {
11    std::cout << x << ", ";
12  }
13}

11, 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:

1#include <forward_list>
2#include <iostream>
3#include <iterator>
4
5int main() {
6  std::forward_list MyList{1, 2, 3, 4, 5};
7  auto Start = MyList.begin();
8  MyList.erase_after(Start, MyList.end());
9
10  std::cout << "List Contents: ";
11  for (int x : MyList) {
12    std::cout << x << ", ";
13  }
14}

1List Contents: 1,

Below, we erase everything from position 2 to position 5, excluding those objects:

1#include <forward_list>
2#include <iostream>
3#include <iterator>
4
5int main() {
6  std::forward_list MyList{1, 2, 3, 4, 5};
7  auto Start = std::next(MyList.begin(), 1);
8  auto End = std::next(Start, 3);
9  MyList.erase_after(Start, End);
10
11  std::cout << "List Contents: ";
12  for (int x : MyList) {
13    std::cout << x << ", ";
14  }
15}

1List Contents: 1, 2, 5,

Sorting a std::forward_list

Linked lists can be sorted in place using the sort() method:

1#include <iostream>
2#include <forward_list>
3
4int main() {
5  std::forward_list MyList { 3, 2, 5, 1, 4 };
6  MyList.sort();
7
8  for (int x : MyList) {
9    std::cout << x << " ";
10  }
11}

11 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:

1#include <iostream>
2#include <forward_list>
3
4struct Character {
5    std::string Name;
6    int Level;
7};
8
9bool isHigherLevel(
10  const Character& A, const Character& B) {
11    return A.Level > B.Level;
12}
13
14int main() {
15  std::forward_list MyList {
16      Character { "Anna", 20 },
17      Character { "Roderick", 10 },
18      Character { "Bruce", 15 },
19  };
20
21  MyList.sort(isHigherLevel);
22
23  for (auto x : MyList) {
24    std::cout
25      << x.Level << " - " << x.Name << '\n';
26  }
27}

120 - Anna
215 - Bruce
310 - 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 and std::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 a std::forward_list, as it does not track its size natively.
• Accessing the first element with front() and arbitrary elements using iterators and std::next().
• Limitations of std::forward_list in backward traversal and the inability to use negative offsets with std::next().
• Implementing range-based for loops to iterate over std::forward_list.
• Adding elements to a forward list using push_front() and emplace_front().
• Inserting and emplacing elements at specific positions with insert_after() and emplace_after().
• Various methods of removing items from the list, including pop_front(), remove(), remove_if(), clear(), and erase_after().
• Sorting std::forward_list using the sort() method and customizing the sort behavior with a comparison function.

Next Lesson

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.

ContinueView Course