9.3.4. Specialized forward_list Operations

To understand why forward_list has special versions of the operations to add and remove elements, consider what must happen when we remove an element from a singly linked list. As illustrated in Figure 9.1, removing an element changes the links in the sequence. In this case, removing elem₃ changes elem₂; elem₂ had pointed to elem₃, but after we remove elem₃, elem₂ points to elem₄.

Figure 9.1. forward_list Specialized Operations

When we add or remove an element, the element before the one we added or removed has a different successor. To add or remove an element, we need access to its predecessor in order to update that element’s links. However, forward_list is a singly linked list. In a singly linked list there is no easy way to get to an element’s predecessor. For this reason, the operations to add or remove elements in a forward_list operate by changing the element after the given element. That way, we always have access to the elements that are affected by the change.

Because these operations behave differently from the operations on the other containers, forward_list does not define insert, emplace, or erase. Instead it defines members (listed in Table 9.8) named insert_after, emplace_after, and erase_after. For example, in our illustration, to remove elem₃, we’d call erase_after on an iterator that denoted elem₂. To support these operations, forward_list also defines before_begin, which returns an off-the-beginning iterator. This iterator lets us add or remove elements “after” the nonexistent element before the first one in the list.

Table 9.8. Operations to Insert or Remove Elements in a forward_list

When we add or remove elements in a forward_list, we have to keep track of two iterators—one to the element we’re checking and one to that element’s predecessor. As an example, we’ll rewrite the loop from page 349 that removed the odd-valued elements from a list to use a forward_list:

forward_list<int> flst = {0,1,2,3,4,5,6,7,8,9};
auto prev = flst.before_begin(); // denotes element "off the start" of flst
auto curr = flst.begin();        // denotes the first element in flst
while (curr != flst.end()) {     // while there are still elements to process
    if (*curr % 2)                     // if the element is odd
        curr = flst.erase_after(prev); // erase it and move curr
    else {
        prev = curr;            // move the iterators to denote the next
        ++curr;                 // element and one before the next element
    }
}

Here, curr denotes the element we’re checking, and prev denotes the element before curr. We call begin to initialize curr, so that the first iteration checks whether the first element is even or odd. We initialize prev from before_begin, which returns an iterator to the nonexistent element just before curr.

When we find an odd element, we pass prev to erase_after. This call erases the element after the one denoted by prev; that is, it erases the element denoted by curr. We reset curr to the return from erase_after, which makes curr denote the next element in the sequence and we leave prev unchanged; prev still denotes the element before the (new) value of curr. If the element denoted by curr is not odd, then we have to move both iterators, which we do in the else.