C++ Standard Template Library (STL) forward_list tutorial

The forward_list in the C++ Standard Template Library (STL) is a single-linked list container.

Unlike list, it only allows traversal in one direction (forward), making it more memory-efficient but less flexible for operations that require bidirectional traversal.

Key Features of forward_list

1. Singly Linked List: Supports only forward traversal.
2. Memory Efficient: Lower memory overhead compared to list due to the absence of backward pointers.
3. Efficient Insertions and Deletions: Operations at the front and anywhere within the list are efficient.

Basic Syntax

#include <forward_list>
using namespace std;

forward_list<int> fl;

Let's explore various operations and examples to understand how forward_list works.

1. Initializing a forward_list

You can initialize a forward_list with default values, a specified size, or with an initializer list.

#include <iostream>
#include <forward_list>
using namespace std;

int main() {
    // Empty forward_list
    forward_list<int> fl1;

    // Initializing with values
    forward_list<int> fl2 = {10, 20, 30, 40, 50};

    // Displaying elements
    cout << "Elements in fl2: ";
    for (int val : fl2) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

Output:

Elements in fl2: 10 20 30 40 50 

2. Adding Elements

forward_list provides functions like push_front and emplace_front for adding elements at the front, as well as insert_after for inserting elements at specific positions.

#include <iostream>
#include <forward_list>
using namespace std;

int main() {
    forward_list<int> fl = {10, 20, 30};

    // Add element at the front
    fl.push_front(5);

    // Insert element after the first position
    auto it = fl.insert_after(fl.begin(), 15);

    cout << "Elements after insertions: ";
    for (int val : fl) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

Output:

Elements after insertions: 5 15 10 20 30 

3. Removing Elements

You can remove elements using pop_front to remove the first element or erase_after to remove elements after a specific position. Additionally, remove can remove all occurrences of a specific value.

#include <iostream>
#include <forward_list>
using namespace std;

int main() {
    forward_list<int> fl = {10, 20, 30, 40, 50};

    // Remove the first element
    fl.pop_front();

    // Remove an element after the first position
    fl.erase_after(fl.begin());

    // Remove all occurrences of 50
    fl.remove(50);

    cout << "Elements after removals: ";
    for (int val : fl) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

Output:

Elements after removals: 20 40 

4. Accessing Elements

While forward_list does not support random access (no [] operator or at function), you can access elements using iterators.

#include <iostream>
#include <forward_list>
using namespace std;

int main() {
    forward_list<int> fl = {10, 20, 30, 40, 50};

    // Accessing elements using iterator
    cout << "Elements: ";
    for (auto it = fl.begin(); it != fl.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    return 0;
}

Output:

Elements: 10 20 30 40 50 

5. Inserting Multiple Elements

The insert_after function can insert multiple elements if you pass a range or initializer list.

#include <iostream>
#include <forward_list>
using namespace std;

int main() {
    forward_list<int> fl = {10, 20, 30};

    // Insert multiple elements after the first position
    fl.insert_after(fl.begin(), {15, 25, 35});

    cout << "Elements after inserting multiple values: ";
    for (int val : fl) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

Output:

Elements after inserting multiple values: 10 15 25 35 20 30 

6. Resizing a forward_list

You can resize a forward_list using the resize function, which adds or removes elements to achieve the desired size.

#include <iostream>
#include <forward_list>
using namespace std;

int main() {
    forward_list<int> fl = {10, 20, 30};

    // Resize to larger size with default value 0
    fl.resize(5);

    cout << "Elements after resizing to 5: ";
    for (int val : fl) {
        cout << val << " ";
    }
    cout << endl;

    // Resize to smaller size
    fl.resize(2);
    cout << "Elements after resizing to 2: ";
    for (int val : fl) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

Output:

Elements after resizing to 5: 10 20 30 0 0 
Elements after resizing to 2: 10 20 

7. Clearing the List

The clear function removes all elements from the forward_list, making it empty.

#include <iostream>
#include <forward_list>
using namespace std;

int main() {
    forward_list<int> fl = {10, 20, 30};

    cout << "Size before clear: ";
    for (int val : fl) cout << val << " ";
    cout << endl;

    // Clear the list
    fl.clear();

    cout << "Size after clear: ";
    for (int val : fl) cout << val << " ";
    cout << "(Empty)" << endl;

    return 0;
}

Output:

Size before clear: 10 20 30 
Size after clear: (Empty)

8. Sorting a forward_list

The sort function sorts elements in ascending order.

#include <iostream>
#include <forward_list>
using namespace std;

int main() {
    forward_list<int> fl = {30, 10, 40, 20, 50};

    // Sorting the list
    fl.sort();

    cout << "Elements after sorting: ";
    for (int val : fl) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

Output:

Elements after sorting: 10 20 30 40 50 

9. Reversing a forward_list

The reverse function reverses the order of elements in the forward_list.

#include <iostream>
#include <forward_list>
using namespace std;

int main() {
    forward_list<int> fl = {10, 20, 30, 40, 50};

    // Reversing the list
    fl.reverse();

    cout << "Elements after reversing: ";
    for (int val : fl) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

Output:

Elements after reversing: 50 40 30 20 10 

10. Merging Two forward_lists

The merge function merges two sorted forward_list objects into one sorted list. Both lists must be sorted beforehand.

#include <iostream>
#include <forward_list>
using namespace std;

int main() {
    forward_list<int> fl1 = {10, 30, 50};
    forward_list<int> fl2 = {20, 40, 60};

    // Merging two sorted lists
    fl1.merge(fl2);

    cout << "Merged list: ";
    for (int val : fl1) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

Output:

Merged list: 10 20 30 40 50 60 

Summary Table of forward_list Operations

Complete Example

This example demonstrates initializing a forward_list, adding and removing elements, sorting, reversing, and merging two lists.

#include <iostream>
#include <forward_list>
using namespace std;

int main() {
    forward_list<int> fl1 = {10, 30, 50};
    forward_list<int> fl2 = {20, 40, 60};

    // Add elements
    fl1.push_front(5);
    fl1.insert_after(fl1.begin(), 15);

    cout << "fl1 after adding elements: ";
    for (int val : fl1) {
        cout << val << " ";
    }
    cout << endl;

    // Sort and reverse
    fl1.sort();
    fl1.reverse();

    cout << "fl1 after sorting and reversing: ";
    for (int val : fl1) {
        cout << val << " ";
    }
    cout << endl;

    // Merge with another sorted list
    fl1.sort();
    fl2.sort();
    fl1.merge(fl2);

    cout << "fl1 after merging with fl2: ";
    for (int val : fl1) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

Sample Output:

fl1 after adding elements: 5 15 10 30 50 
fl1 after sorting and reversing: 50 30 15 10 5 
fl1 after merging with fl2: 5 10 15 20 30 40 50 60 

Key Takeaways

• forward_list in C++ is a singly linked list that supports only forward traversal, making it memory-efficient.
• It provides operations like insertion, deletion, sorting, reversing, and merging, which are efficient for certain types of sequential access.
• Ideal for applications where memory efficiency is important, but bidirectional access isn’t necessary.