std::forward_list

A forward list in C++ is the linked list: each node stores the address of the next node. The first node may be located in another completely different region of memory, but the first node is aware of the address of the second, an so on. The iterators can only move forward in the linked list, because we only know the next entry in the linked list (and not the previous), and thus the name. Such a linked list is also called a "singly linked list", because there is only one link between the nodes.

1. Member functions and operators

We will describe the various member functions for constructing and querying this container and for inserting, accessing, and removing items from this container.

1.1 Declaring (constructing) a forward list

The the most common declaration (constructor) simply creates an empty forward list:

    std::forward_list<T> identifier{};

You can replace the T with any type you want, so if you wanted to create a forward list of int and one of double, you would use:

    std::forward_list<int> int_list{};
    std::forward_list<double> real_list{};

If you know that the forward list should a fixed and known collection of items when the forward list is being constructed, you can use an "initializer list":

    std::forward_list<T> identifier{ item_1, ..., item_n };

The initializer list entry item_1 is at the front of the linked list.

If you have a range of two iterators from another container also storing T items, you can can pass that range as arguments to the constructor:

    std::forward_list<T> identifier( itr_first, iter_last );

The item referred to by itr_first is at the front of the linked list.

1.2 Querying a forward list

bool empty() const

As with most containers, you can query if a forward list is empty with bool empty() const; however, unlike most containers, you cannot even access the number of items in the forward list.

    // Prints '0' (false) or '1' (true)
    std::cout << identifier.empty()
              << std::endl;

1.3 Inserting an item or items into a forward list

void push_front( T const &item )

The only operation to insert an item into a std::forward_list<T> is void push_front( T const &item ). This inserts a single item into the linked list.

itr_t insert_after( itr_t itr, T const &item )
itr_t insert_after( itr_t itr, T const &item, n )
itr_t insert_after( itr_t itr, {item_1, ..., item_n} )
itr_t insert_after( itr_t itr, itr_t itr_first, itr_t itr_last )

If you have an iterator referring to one of the items in a forward list, you can insert items after the referenced node, including inserting one item with itr_t insert_after( itr_t itr, T const &item ), $n$ copies of that item with itr_t insert_after( itr_t itr, T const &item, n ), all items in an initializer list itr_t insert_after( itr_t itr, {item_1, ..., item_n} ), and all entries in a given range after itr_t insert_after( itr_t itr, itr_t itr_first, itr_t itr_last ). If nothing is inserted, itr is returned; otherwise an iterator referring to the last item inserted is returned.

1.4 Accessing an item in a forward list

T front() const

The member function T front() const member function returns the item at the front of the linked list. This can be assigned to, in which case, the first item in the linked list is changed.

1.5 Removing an item or items from a forward list

void pop_front()

The member function void pop_front() erases the entry at the front of the forward list.

itr_t erase_after( itr_t itr )
itr_t erase_after( itr_t itr_first, itr_t itr_last )

If you have an iterator referring to an item in a forward list, you can erase the item immediately after it using the itr_t erase_after( itr_t itr ) member function, and if both itr_first and itr_last are passed, then all entries after itr_first up to but not including itr_last. The iterator returned refers to the next entry after the last entry erased (so in the second case, it will return itr_last).

void clear()

The member function void clear() member function erases all entries from the forward list.

std::size_t remove( T const &value )

The member function std::size_t remove( T const &value ) removes all entries equal to the argument, and returns the number of items removed.

Please note, this is the first example of an argument being passed by constant reference. This makes no difference for primitive data types, but for more complex classes, this prevents the need to copy the value of the object being removed.

std::size_t remove_if( bool predicate( T value ) )

The member function std::size_t remove_if( bool predicate( T value ) ) removes all entries such that the Boolean-valued function as an argument returns true and returns the number of items removed.

For example, the following uses a lambda expression to define a function that returns true if $n$ is one of $5, 6, 7$:

  std::forward_list<int> list{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

  std::cout << list.remove_if( []( int n ){
    return (5 <= n) && (n <= 7);
  } ) << std::endl;

std::size_t unique()
std::size_t unique( bool prediate( T a, T b ) )

The member function std::size_t unique() removes all entries immediately following a given item that are equal to that item. If the list is sorted, this will guarantee the entries of the list are unique. If you want to pass a Boolean-valued function that returns true if the two arguments are equal, you can pass this as a first argument. For example, the following would remove subsequent enteries if the integer component is equal. This is done using lambda expressions:

  std::forward_list<double> list{0.3, 0.6, 1.7, 0.3, 0.9, 0.2, 1.9, 1.3, 0.4, 0.2};

  // This reduces the list to
  //    0.3, 1.7, 0.3, 1.9, 0.4
  std::cout << list.remove_if( []( double x, double y ){
    return std::floor( x ) == std::floor( y );
  } ) << std::endl;

This function

In this case, if you had a forward list of type double, you could simply call list.unique( integer_equality );. If this list had an entry storing $3.14$, then all subsequent entries in the half-open interval $[3, 4)$ would be removed until either an entry is found less than three or greater than or equal to four, or we reach the end of the forward list.

An alternative choice is to define a function in the source code using a lambda expression:

  std::forward_list<double> list{3.2, 4.5, 4.2, 5.6, 4.7, 4.8, 4.1, 3.8};

  std::cout << list.unique( []( double x, double y ){
    return std::floor( x ) == std::floor( y );
  } ) << std::endl;

1.6 Operations on a forward list

void sort()

The member function void sort() member function sorts the forward list. This uses a merge sort algorithm and is as efficient as one can be with such a data structure. If an alternate Boolean-valued comparison operation (indicating less-than) is required, this can be passed as an argument; for example,

    std::forward_list<int> list{};

    // Reverse sort the list
    list.sort( []( int m, int n )->bool {
      return m > n;
    } );

Alternatively, if you use the #include <functional> library, you can use

    std::forward_list<int> list{};

    // Reverse sort the list
    list.sort( std::greater<typename>() );

void merge( std::forward_list<T> list )

Given a second forward list list, the member function void merge( std::forward_list<T> list ) assumes both lists are sorted and merges the entries in the second list with this list (the second list being empty after this operation).

If an alternate Boolean-valued comparison operation (indicating less-than) is required, this can be passed as an argument; for example,

    std::forward_list<int> list1{};
    std::forward_list<int> list2{};

    // Assume both are reverse sorted...
    //   list1.merge( list2, std::greater<int>() );
    list1.merge( list2, []( int m, int n )->bool {
      return m > n;
    } );

    std::cout << "List 2 should be empty: " << list2.empty() 
              << std::endl;

void reverse()

The function void reverse() reverses the entries in the forward list.

If it is necessary to increase or decrease the size of the list (adding new nodes or removing nodes from the back), the void resize( std::size_t count ) member function will remove nodes there are more than count nodes, or add new nodes with a default value of the type so that there are count nodes in the forward list. If a second augment is passed, that will be the value assigned to any new nodes.

2. Iterators

A number of the member functions mentioned above already allow arguments that are iterators or return iterators. There are, of course, the itr_t begin() const and itr_t end() const member functions, which return iterators that form a range for all entries in the forward list.

3. A possible implementation

A forward list is implemented as a singly linked list: the data structure itself stores the address of the first node, and each node stores the address of the next.

You can see the use of this class at replit.com.