C++ algorithm std::stable_sort Function Template

C++ std::stable_sort

The std::stable_sort function template in C++ is part of the <algorithm> header and is used to sort elements in a range while preserving the relative order of equivalent elements. This stability is particularly useful when the order of equal elements carries semantic meaning.

---

Syntax

// Default stable sort using operator<
template <class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

// Stable sort using custom comparison function
template <class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

first, last

Random-access iterators defining the range [first, last) to be sorted.

comp

Binary function that accepts two elements in the range as arguments and returns a boolean. The function should return true if the first element is considered to go before the second.

---

Examples

Example 1: Stable Sorting with Default Comparison

This example demonstrates stable sorting of a vector of integers in ascending order using the default comparison.

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

int main() {
    std::vector<int> myvector = {32, 71, 12, 45, 26, 80, 53, 33};

    // Stable sort entire vector in ascending order
    std::stable_sort(myvector.begin(), myvector.end());

    std::cout << "myvector contains:";
    for (const auto& elem : myvector)
        std::cout << ' ' << elem;
    std::cout << std::endl;

    return 0;
}

Output:

myvector contains: 12 26 32 33 45 53 71 80

Explanation:

1. Initialize the vector: A std::vector named myvector is created and initialized with a list of integers: {32, 71, 12, 45, 26, 80, 53, 33}. This vector contains the unsorted elements that need to be sorted.
2. Sort the vector: The std::stable_sort function is called with the following arguments:
   • myvector.begin(): The starting point of the range to be sorted.
   • myvector.end(): The ending point of the range to be sorted.
   This sorts the elements in ascending order using the default comparison operator (<). The stability of std::stable_sort ensures that elements with equal values retain their original relative order.
3. Print the sorted vector: A range-based for loop iterates over the sorted vector, and each element is printed to the console using std::cout. The elements are displayed separated by a space.

Example 2: Stable Sorting with Custom Comparison Function

This example demonstrates stable sorting of a vector of integers in descending order using a custom comparison function.

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

// Custom comparison function
bool descending(int i, int j) {
    return i > j;
}

int main() {
    std::vector<int> myvector = {32, 71, 12, 45, 26, 80, 53, 33};

    // Stable sort entire vector in descending order
    std::stable_sort(myvector.begin(), myvector.end(), descending);

    std::cout << "myvector contains:";
    for (const auto& elem : myvector)
        std::cout << ' ' << elem;
    std::cout << std::endl;

    return 0;
}

Output:

myvector contains: 80 71 53 45 33 32 26 12

Explanation:

1. Define a custom comparison function: A function named descending is defined to compare two integers:
   • The function takes two integers as input parameters: i and j.
   • It returns true if i > j, ensuring the sorting order is descending.
   This function will be used by std::stable_sort as the comparison criterion.
2. Sort the vector in descending order: The std::stable_sort function is called with three arguments:
   • myvector.begin(): Specifies the start of the range to be sorted.
   • myvector.end(): Specifies the end of the range to be sorted.
   • descending: The custom comparison function, which ensures the elements are sorted in descending order.
   The stability of std::stable_sort ensures that elements with equal values retain their original relative order.

Example 3: Exception Handling in std::stable_sort

This example demonstrates how exceptions can be thrown and handled during the execution of std::stable_sort. If the comparison function throws an exception, the sorting process terminates, and the exception can be caught using a try-catch block.

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdexcept>

bool faultyComparison(int a, int b) {
    if (a == 12 || b == 12) {
        throw std::runtime_error("Comparison failed for value 12.");
    }
    return a < b;
}

int main() {
    std::vector<int> myvector = {32, 71, 12, 45, 26, 80, 53, 33};

    try {
        // Attempt to stable sort using a faulty comparison function
        std::stable_sort(myvector.begin(), myvector.end(), faultyComparison);
    } catch (const std::exception& e) {
        std::cerr << "Exception caught during stable sort: " << e.what() << std::endl;
    }

    return 0;
}

Output:

Exception caught during stable sort: Comparison failed for value 12.

Explanation:

1. Define a faulty comparison function: A custom comparison function named faultyComparison is defined, which:
   • Throws a std::runtime_error exception if either operand is equal to 12.
   • Returns true if the first operand is less than the second for valid comparisons.
   This function is intentionally designed to simulate an error during sorting.
2. Initialize the vector: A std::vector named myvector is created and initialized with a list of integers: {32, 71, 12, 45, 26, 80, 53, 33}. This vector contains the unsorted elements to be sorted.
3. Attempt to stable sort the vector: Inside a try block, the std::stable_sort function is called with the following arguments:
   • myvector.begin(): Specifies the start of the range to be sorted.
   • myvector.end(): Specifies the end of the range to be sorted.
   • faultyComparison: Specifies the custom comparison function.
   When the comparison function encounters the value 12, it throws a std::runtime_error exception, terminating the sorting process.
4. Catch the exception: The catch block catches the exception of type std::exception. The error message is displayed on the standard error stream using std::cerr. The output informs the user that the sorting process failed due to a comparison involving the value 12.