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
- Singly Linked List: Supports only forward traversal.
- Memory Efficient: Lower memory overhead compared to list due to the absence of backward pointers.
- 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
Operation | Code Example | Description |
---|---|---|
Initialize | forward_list<int> fl = {10, 20, 30}; | Creates a forward_list with initial values |
Add at front | fl.push_front(5); | Adds an element to the front |
Insert after position | fl.insert_after(fl.begin(), 15); | Inserts element after specified position |
Remove first element | fl.pop_front(); | Removes the first element |
Remove specific value | fl.remove(20); | Removes all occurrences of a specified value |
Erase after position | fl.erase_after(fl.begin()); | Erases element after specified position |
Clear | fl.clear(); | Removes all elements |
Resize | fl.resize(5, 100); | Resizes forward_list, fills new slots with value |
Sort | fl.sort(); | Sorts elements in ascending order |
Reverse | fl.reverse(); | Reverses the order of elements |
Merge | fl1.merge(fl2); | Merges two sorted forward_lists |
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.