How do I sort and stable_sort elements with std::forward_list?

In C++, the std::forward_list is a single-linked list that allows for efficient insertion and deletion of elements. However, it does not provide random access iterators, which means that sorting can be a bit more challenging compared to vector or list. To sort elements in a std::forward_list, you can use the std::sort and std::stable_sort algorithms. However, note that these algorithms require random access iterators, so they cannot be applied directly to std::forward_list. Instead, you can transfer elements to a container that supports random access, sort them, and then transfer them back.

Here’s an example that demonstrates how to sort and stable sort a std::forward_list by first moving its elements to a std::vector:


        #include <iostream>
        #include <forward_list>
        #include <vector>
        #include <algorithm>

        int main() {
            std::forward_list flist = {5, 3, 2, 8, 1};

            // Copy elements to a vector
            std::vector vec(flist.begin(), flist.end());

            // Sort the vector
            std::sort(vec.begin(), vec.end());

            // Transfer sorted elements back to forward_list
            flist.clear();
            flist.insert_after(flist.before_begin(), vec.begin(), vec.end());

            std::cout << "Sorted forward_list: ";
            for (int n : flist) {
                std::cout << n << " ";
            }
            std::cout << std::endl;

            // Using stable_sort
            // Clear the forward_list and add same elements again
            flist = {5, 3, 2, 8, 1};
            std::vector vec2(flist.begin(), flist.end());

            // Sort using stable_sort
            std::stable_sort(vec2.begin(), vec2.end());

            // Transfer sorted elements back to forward_list
            flist.clear();
            flist.insert_after(flist.before_begin(), vec2.begin(), vec2.end());

            std::cout << "Stable sorted forward_list: ";
            for (int n : flist) {
                std::cout << n << " ";
            }
            std::cout << std::endl;

            return 0;
        }

C++ std::forward_list sort stable_sort data structures algorithms

How do I sort and stable_sort elements with std::forward_list?

Popular Topics

Recent Languages

How do I sort and stable_sort elements with std::forward_list?

Related Questions

Popular Topics

Recent Languages