Anatomy of std::forward_list

std::forward_list is a dynamic data structure that allows the storage of elements in a linear sequence. Unlike std::list, which is doubly linked list, std::forward_list is a singly linked list, meaning that each element points to the next in the sequence. This choice provides advantages in terms of memory usage and performance for certain use cases.

Functions:

1. Element Access Functions:

None – std::forward_list does not provide direct element access by index.

2. Iterators Functions:

begin():

• Return iterator pointing to the beginning of the forward list.

end():

• Return iterators pointing to the past-the-end of the forward list.

#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> myList = {1, 2, 3, 4, 5};

    auto it = myList.begin(); // Iterator pointing to the beginning
    while (it != myList.end()) {
        std::cout << *it << " ";
        ++it;
    }

    return 0;
}

// Output
1 2 3 4 5

In this example, begin() returns an iterator pointer to the beginning of the forward_list, and end() returns an iterator pointing just past the end. The loop then prints each element of the list.

cbegin():

• Return const iterator pointing to the beginning of the forward list.

cend():

• Return const iterator pointing to the end of the forward list.

#include <iostream>
#include <forward_list>

int main() {
    const std::forward_list<int> myList = {1, 2, 3, 4, 5};

    auto it = myList.cbegin(); // Const iterator pointing to the beginning
    while (it != myList.cend()) {
        std::cout << *it << " ";
        ++it;
    }

    return 0;
}

// Output
1, 2, 3, 4, 5

Similar to begin() and end(), cbegin() and cend() return const iterators, preventing modification of the element through these iterators.

3. Capacity Functions:

empty():

• Check if the forward list is empty.

#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> myList;

    if (myList.empty()) {
        std::cout << "The forward list is empty." << std::endl;
    } else {
        std::cout << "The forward list is not empty." << std::endl;
    }

    return 0;
}

// Output
The forward list is empty

max_size():

• Return the maximum number of elements the forward list can hold.

#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> myList;

    std::cout << "Maximum size of the forward list: " << myList.max_size() << std::endl;

    return 0;
}

// Output
Maximum size of the forward list: 576460752303423487

The max_size() function returns the maximum number of elements the forward list can hold. It depends on the system and the available memory.

4. Modifiers Functions:

push_front():

• Add element from the front.
• The size of forward list increases by 1.
• The value from this function is copied to the space before the first element in the container.

pop_front():

• Remove element from the front.

#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> myList = {2, 3, 4, 5};

    myList.push_front(1); // Add element to the front

    for (const auto& element : myList) {
        std::cout << element << " ";
    }

    std::cout << std::endl;

    myList.pop_front(); // Remove element from the front

    for (const auto& element : myList) {
        std::cout << element << " ";
    }

    return 0;
}

// Output
1 2 3 4 5
2 3 4 5

insert_after():

• Insert element at specified position.

erare_after():

• Erase element at specified position.

#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> myList = {1, 2, 4, 5};
    auto it = myList.begin();
    ++it; // Move to the second element

    myList.insert_after(it, 3); // Insert element after the second element

    for (const auto& element : myList) {
        std::cout << element << " ";
    }

    std::cout << std::endl;

    it = myList.begin();
    ++it; // Move to the second element

    myList.erase_after(it); // Erase element after the second element

    for (const auto& element : myList) {
        std::cout << element << " ";
    }

    return 0;
}

// Output
1 2 3 4 5
2 3 4 5

insert_after() inserts an element after a specified position, erase_after() removes the element after a specified position.

emplace_front():

• Construct and insert elements at the front.
• This function is similar to the push_front() but in this no copying operation occurs, the element is created directly at the memory before the first element of the forward list.

#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<std::string> myList = {"world"};

    myList.emplace_front("Hello"); // Construct and insert element at the front


    for (const auto& element : myList) {
        std::cout << element;
    }

    return 0;
}

// Output
Helloworld

emplace_after():

• Construct and insert elements after a specified position.

#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<std::string> myList = {"world"};

    myList.emplace_front("Hello"); // Construct and insert element at the front
    myList.emplace_after(myList.begin(), ", "); // Construct and insert element after the first element

    for (const auto& element : myList) {
        std::cout << element;
    }

    return 0;
}

// Output
Hello, world

assign():

• Assign new value to the forward list.

Different ways of using assign():

forward_list<int> forwardList1;

forward_list<int> forwardList2;

forward_list<int> forwardList3;

// Assigning values using assign()
forwardList1.assign({7, 8, 9});

// Assigning repeating values using assign()
// 5 elements with value 10
forwardList2.assign(5, 10);

// Assigning values of list 1 to list 3
forwardList3.assign(forwardList1.begin(), forwardList1.end());

// Output
-> forwardList1 = 7 8 9
-> forwardList2 = 10 10 10 10 10
-> forwardList3 = 7 8 9

#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> myList;

    // Assign values to the forward list
    myList.assign({1, 2, 3, 4, 5});

    for (const auto& element : myList) {
        std::cout << element << " ";
    }

    return 0;
}

The assign() function replaces the contents of the forward list with the specified values.

resize():

• Change the size of the forward list.
• It can do both increase/decrease of the size.

#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> myList = {1, 2, 3};

    myList.resize(5, 0); // Change the size to 5, fill with 0 if necessary

    for (const auto& element : myList) {
        std::cout << element << " ";
    }

    return 0;
}

// Output
1 2 3 0 0

The resize() function changes the size of the forward list. In this example, it fills with zeroes if the new size is greater than the current size.

5. Operations Functions:

splice_after():

• splice_after() transfers elements from one forward list to another after a specified position.

#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> list1 = {1, 2, 3};
    std::forward_list<int> list2 = {4, 5};

    auto it = list1.begin();
    ++it; // Move to the second element

    list1.splice_after(it, list2); // Transfer elements from list2 after the second element of list1

    for (const auto& element : list1) {
        std::cout << element << " ";
    }

    std::cout << std::endl;

    for (const auto& element : list2) {
        std::cout << element << " ";
    }

    return 0;
}

// Output
1 2 4 5 3

In the example, elements from list2 are transferred after the second element of list1.

remove():

• Removes all occurrences of a specified value.

#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> myList = {1, 2, 3, 2, 4, 5, 2};

    myList.remove(2); // Remove all occurrences of 2

    for (const auto& element : myList) {
        std::cout << element << " ";
    }

    return 0;
}

// output
1 3 4 5

In the example, all occurrences of 2 are removed from the forward list.

remove_if():

• Removes elements for which a specified predicate is true.

#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> myList = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    // Remove all even numbers
    myList.remove_if([](int x) { return x % 2 == 0; });

    // Print the modified list
    for (const auto& element : myList) {
        std::cout << element << " ";
    }

    return 0;
}

// Output
1 3 5 7 9

In this example, the lambda function [](int x) {return x % 2 == 0;} is used to predicate to identify even numbers.

unique():

• Removes consecutive duplicate elements.

#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> myList = {1, 2, 1, 2, 3, 4, 4, 5};

    myList.unique(); // Remove consecutive duplicate elements

    for (const auto& element : myList) {
        std::cout << element << " ";
    }

    return 0;
}

// Output
1 2 1 2 3 4 5

In the example, consecutive duplicates are removed from the forward list.

reverse():

• Reverses the order of elements.

#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> myList = {1, 2, 3, 4, 5};

    myList.reverse(); // Reverse the order of elements

    for (const auto& element : myList) {
        std::cout << element << " ";
    }

    return 0;
}

// Output
5 4 3 2 1

In the above example, elements are reversed.

sort():

• Sorts the elements in ascending order.

#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> myList = {5, 2, 1, 4, 3};

    myList.sort(); // Sort the elements in ascending order

    for (const auto& element : myList) {
        std::cout << element << " ";
    }

    return 0;
}

// Output
1 2 3 4 5

Advantages

1. Memory Efficiency:
   * Requires less memory per element compared to doubly linked lists (std::list).
2. Insertion and Deletion:
   * Efficient for operations at the beginning or after a specific element.
3. Performance:
   * Performs well in scenarios where frequent insertions and deletions are required.

Disadvantages

1. Sequential Access:
   * Slower for sequential access compared to arrays or vectors.
2. No Direct Access:
   * Lacks direct access to elements by index, impacting random access performance.
3. Limited Operations:
   * Fewer operations compared to other containers, limiting functionality.