std::forward_list

So far, we've only seen array-like structures, but, as we saw, insertion and deletion in the middle of the data structures are very inefficient operations for contiguous data structures. And that's where linked-list-like structures come into the picture. A lot of applications require frequent insertion and deletion in the middle of a data structure. For example, any browser with multiple tabs can have an extra tab added at any point in time and at any location. Similarly, any music player will have a list of songs that you can play in a loop, and you can also insert any songs in the middle. In such cases, we can use a linked-list structure for good performance. We'll see the use case of a music player in Activity 1, Implementing a Song Playlist. Now, let's explore what kind of containers C++ provides us with.

The basic structure of a linked list requires us to have a pointer and to manage memory allocation and deallocation manually using the new and delete operators. Although it is not difficult, it can lead to bugs that are difficult to trace. Hence, just like std::array provides a thin wrapper over C-style arrays, std::forward_list provides a thin wrapper over a basic linked list.

The purpose of std::forward_list is to provide some additional functionality without compromising performance compared to a basic linked list. To maintain performance, it doesn't provide functions to get the size of the list or to get any element but the first one directly. Hence, it has a function called front() to get the reference to the first element, but nothing like back() to access the last element. It does provide functions for common operations, such as insertion, deletion, reverse, and splice. These functions don't affect the memory requirements or performance over basic linked lists.

Additionally, just like std::vector, std::forward_list can also take a custom allocator as the second template parameter if required. Hence, we can easily use it for advanced applications that benefit from custom memory management.

Inserting and Deleting Elements in forward_list

std:: forward_list provides the push_front and insert_after functions, which can be used to insert an element in a linked list. Both of these are slightly different compared to insertion functions for vectors. push_front is useful for inserting an element at the front. Since forward_list doesn't have direct access to the last element, it doesn't provide a push_back function. For insertion at a specific location, we use insert_after instead of insert. This is because inserting an element in a linked list requires updating the next pointer of the element, after which we want to insert a new element. If we provide just the iterator, where we want to insert a new element, we can't get access to the previous element quickly, since traversing backward is not allowed in forward_list.

Since this is a pointer-based mechanism, we don't really need to shift the elements during insertion. Hence, both of the insertion functions are quite a bit faster compared to any array-based structures. Both the functions just modify the pointers to insert a new element at the intended position. This operation is not dependent on the size of the list and therefore has a time complexity of O(1). We shall take a look at the implementation of these functions in the following exercise.

Now, let's see how we can insert elements in a linked list:

std::forward_list<int> fwd_list = {1, 2, 3};
fwd_list.push_front(0);
// list becomes {0, 1, 2, 3}
auto it = fwd_list.begin();
fwd_list.insert_after(it, 5);
// list becomes {0, 5, 1, 2, 3}
fwd_list.insert_after(it, 6);
// list becomes {0, 6, 5, 1, 2, 3}

forward_list also provides emplace_front and emplace_after, which is similar to emplace for a vector. Both of these functions do the same thing as insertion functions, but more efficiently by avoiding extra copying and moving.

forward_list also has pop_front and erase_after functions for the deletion of elements. pop_front, as the name suggests, removes the first element. Since it doesn't require any shifting, the operation is quite fast in practice and has a time complexity of O(1). erase_after has two overloads – to remove a single element (by taking an iterator to its previous element), and to remove multiple elements in a range (by taking an iterator to the element before the first element of the range and another iterator to the last element).

The time complexity of the erase_after function is linear to the number of elements that are erased because the deletion of elements can't be done via deallocating just a single chunk of memory. Since all the nodes are scattered across random locations in memory, the function needs to deallocate each of them separately.

Now, let's see how we can remove the elements from the list:

std::forward_list<int> fwd_list = {1, 2, 3, 4, 5};
fwd_list.pop_front();
// list becomes {2, 3, 4, 5}
auto it = fwd_list.begin();
fwd_list.erase_after(it);
// list becomes {2, 4, 5}
fwd_list.erase_after(it, fwd_list.end());
// list becomes {2}

Let's explore what other operations we can do with forward_list in the following section.

Other Operations on forward_list

Apart from the erase functions to delete elements based on its position determined by iterators, forward_list also provides the remove and remove_if functions to remove elements based on their values. The remove function takes a single parameter – the value of the elements to be removed. It removes all the elements that match the given element based on the equality operator defined for the type of the value. Without the equality operator, the compiler doesn't allow us to call that function and throws a compilation error. Since remove only deletes the elements based on the equality operator, it is not possible to use it for deletion based on other conditions, since we can't change the equality operator after defining it once. For a conditional removal, forward_list provides the remove_if function. It takes a predicate as a parameter, which is a function taking an element of the value type as a parameter, and a Boolean as the return value. So, all the elements for which the predicate returns true are removed from the list. With the latest C++ versions, we can easily specify the predicate with lambdas as well. The following exercise should help you to understand how to implement these functions.

Exercise 3: Conditional Removal of Elements from a Linked List Using remove_if

In this exercise, we'll use the sample information of a few Indian citizens during the elections and remove ineligible citizens, based on their age, from the electoral roll. For simplicity, we'll just store the names and ages of the citizens.

We shall store the data in a linked list and remove the required elements using remove_if, which provides a way to remove elements that meet a certain condition, instead of defining the positions of the elements to be removed:

1. Let's first include the required headers and add the struct citizen:

   #include <iostream>
   #include <forward_list>
   struct citizen
   {
       std::string name;
       int age;
   };
   std::ostream& operator<<(std::ostream& os, const citizen& c)
   {
       return (os << "[Name: " << c.name << ", Age: " << c.age << "]");
   }

2. Now, let's write a main function and initialize a few citizens in a std::forward_list. We'll also make a copy of it to avoid having to initialize it again:

   int main()
   {
     std::forward_list<citizen> citizens = {{"Raj", 22}, {"Rohit", 25}, {"Rohan", 17}, {"Sachin", 16}};
     auto citizens_copy = citizens;
     std::cout << "All the citizens: ";
     for (const auto &c : citizens)
         std::cout << c << " ";
     std::cout << std::endl;

3. Now, let's remove all of the ineligible citizens from the list:

   citizens.remove_if(
       [](const citizen& c)
       {
           return (c.age < 18);
       });
   std::cout << "Eligible citizens for voting: ";
   for(const auto& c: citizens)
       std::cout << c << " ";
   std::cout << std::endl;

   The remove_if function removes all the elements for which the given predicate is true. Here, we've provided a lambda since the condition is very simple. If it were a complicated condition, we could also write a normal function that takes one parameter of the underlying type of list and returns a Boolean value.

4. Now, let's find out who'll be eligible for voting next year:

   citizens_copy.remove_if(
       [](const citizen& c)
       {
       // Returns true if age is less than 18
           return (c.age != 17);
       });
   std::cout << "Citizens that will be eligible for voting next year: ";
   for(const auto& c: citizens_copy)
       std::cout << c << " ";
   std::cout << std::endl;
   }

   As you can see, we are only keeping those citizens with an age of 17.

5. Run the exercise. You should get an output like this:

   All the citizens: [Name: Raj, Age: 22] [Name: Rohit, Age: 25] [Name: Rohan, Age: 17] [Name: Sachin, Age: 16] 
   Eligible citizens for voting: [Name: Raj, Age: 22] [Name: Rohit, Age: 25] 
   Citizens that will be eligible for voting next year: [Name: Rohan, Age: 17] 

The remove_if function has a time complexity of O(n) since it simply traverses the list once while removing all the elements as required. If we want to remove the elements with specific values, we can use another version of remove, which simply takes one parameter of the object and removes all the objects from the list matching the given value. It also requires us to implement the == operator for the given type.

forward_list also provides a sort function to sort the data. All the array-related structures can be sorted by a generic function, std::sort(first iterator, last iterator). However, it can't be used by linked list-based structures because we can't access any data randomly. This also makes the iterators provided by forward_list different from the ones for an array or a vector. We'll take a look at this in more detail in the next section. The sort function that is provided as part of forward_list has two overloads – sort based on the less than operator (<), and sort based on a comparator provided as a parameter. The default sort function uses std::less<value_type> for comparison. It simply returns true if the first parameter is less than the second one, and hence, requires us to define the less than operator (<) for custom-defined types.

In addition to this, if we want to compare it based on some other parameters, we can use the parametric overload, which takes a binary predicate. Both the overloads have a linearathmic time complexity – O(n × log n). The following example demonstrates both overloads of sort:

std::forward_list<int> list1 = {23, 0, 1, -3, 34, 32};
list1.sort();
// list becomes {-3, 0, 1, 23, 32, 34}
list1.sort(std::greater<int>());
// list becomes {34, 32, 23, 1, 0, -3}

Here, greater<int> is a predicate provided in the standard itself, which is a wrapper over the greater than operator (>) to sort the elements into descending order, as we can see from the values of the list..

Other functions provided in forward_list are reverse and unique. The reverse function simply reverses the order of the elements, in a time duration that is linear to the number of elements present in the list, that is, with a time complexity of O(n). The unique function keeps only the unique elements in the list and removes all the repetitive valued functions except the first one. Since it is dependent on the equality of the elements, it has two overloads – the first takes no parameters and uses the equality operator for the value type, while the second takes a binary predicate with two parameters of the value type. The unique function was built to be linear in time complexity. Hence, it doesn't compare each element with every other element. Instead, it only compares consecutive elements for equality and removes the latter one if it is the same as the former one based on the default or custom binary predicate. Hence, to remove all of the unique elements from the list using the unique function, we need to sort the elements before calling the function. With the help of a given predicate, unique will compare all the elements with their neighboring elements and remove the latter elements if the predicate returns true.

Let's now see how we can use the reverse, sort, and unique functions for lists:

std::forward_list<int> list1 = {2, 53, 1, 0, 4, 10};
list1.reverse();
// list becomes {2, 53, 1, 0, 4, 10}
list1 = {0, 1, 0, 1, -1, 10, 5, 10, 5, 0};
list1.sort();
// list becomes {-1, 0, 0, 0, 1, 1, 5, 5, 10, 10}
list1.unique();
// list becomes {-1, 0, 1, 5, 10}
list1 = {0, 1, 0, 1, -1, 10, 5, 10, 5, 0};
list1.sort();
// list becomes {-1, 0, 0, 0, 1, 1, 5, 5, 10, 10}

The following example will remove elements if they are not greater than the previously valid element by at least 2:

list1.unique([](int a, int b) { return (b - a) < 2; });
// list becomes {-1, 1, 5, 10}

Note

Before calling the unique function, the programmer must make sure that the data is already sorted. Hence, we are calling the sort function right before it. The unique function compares the element with the previous element that has already met the condition. Additionally, it always keeps the first element of the original list. Hence, there's always an element to compare with.

In the next section, we will take a look at how the forward_list iterator is different from the vector/array iterators.