C++ std::list::sort

C++ std::list::sort

The std::list::sort function is used to sort the elements of a std::list in ascending order by default. Additionally, a custom comparison function can be provided to define a specific sorting order. Since std::list is implemented as a doubly-linked list, sorting is performed efficiently using merge sort, which has a time complexity of O(n log n).

---

Syntax of std::list::sort

// 1. Sort in ascending order (default)
void sort();

// 2. Sort with a custom comparison function
template <class Compare>
void sort(Compare comp);

Parameters

Parameter	Description
comp	(Optional) A binary comparison function that returns true if the first argument should precede the second in the sorted order.

Return Value

This function does not return a value. It modifies the list in place, arranging its elements in the specified order.

Exceptions

The std::list::sort function does not throw exceptions unless the comparison function throws an exception. It provides strong exception safety: if an exception is thrown, the list remains unchanged.

---

Examples for std::list::sort

Example 1: Sorting in Ascending Order

This example demonstrates how to use sort to arrange the elements of a list in ascending order:

Program

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {30, 10, 40, 20};

    std::cout << "List contents before sort: ";
    for (const auto& elem : myList) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

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

    std::cout << "List contents after sort: ";
    for (const auto& elem : myList) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

Explanation:

1. A std::list named myList is initialized with unsorted values {30, 10, 40, 20}.
2. The sort function is called without any arguments, arranging the elements in ascending order using the default comparison (operator<).
3. The sorted contents of myList are printed, showing {10, 20, 30, 40}.

Output:

List contents before sort: 30 10 40 20
List contents after sort: 10 20 30 40

Example 2: Sorting in Descending Order

This example demonstrates how to use sort with a custom comparison function to arrange elements in descending order:

Program

#include <iostream>
#include <list>

// Custom comparison function: Sort in descending order
bool compareDescending(int a, int b) {
    return a > b;
}

int main() {
    std::list<int> myList = {30, 10, 40, 20};

    std::cout << "List contents before sort: ";
    for (const auto& elem : myList) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // Sort the list in descending order
    myList.sort(compareDescending);

    std::cout << "List contents after sort: ";
    for (const auto& elem : myList) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

Explanation:

1. A std::list named myList is initialized with unsorted values {30, 10, 40, 20}.
2. A custom comparison function compareDescending is defined to sort elements in descending order.
3. The sort function is called with compareDescending, arranging the elements in descending order.
4. The sorted contents of myList are printed, showing {40, 30, 20, 10}.

Output:

List contents before sort: 30 10 40 20
List contents after sort: 40 30 20 10

Example 3: Sorting Strings by Length

This example demonstrates how to use sort with a custom comparison function to sort strings by their length:

Program

#include <iostream>
#include <list>
#include <string>

// Custom comparison function: Sort strings by length
bool compareByLength(const std::string& a, const std::string& b) {
    return a.size() < b.size();
}

int main() {
    std::list<std::string> myList = {"apple", "dog", "banana", "cat"};

    std::cout << "List contents before sort: ";
    for (const auto& elem : myList) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // Sort the list by string length
    myList.sort(compareByLength);

    std::cout << "List contents after sort: ";
    for (const auto& elem : myList) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

Explanation:

1. A std::list of strings named myList is initialized with {"apple", "dog", "banana", "cat"}.
2. A custom comparison function compareByLength is defined to compare strings by their length.
3. The sort function is called with compareByLength, arranging the strings in ascending order of their length.
4. The sorted contents of myList are printed, showing {"dog", "cat", "apple", "banana"}.

Output:

List contents before sort: apple dog banana cat
List contents after sort: dog cat apple banana