C++ algorithm: std::is_sorted_until

C++ std::is_sorted_until

The std::is_sorted_until algorithm checks whether a given range is sorted and identifies the point where the sorting order breaks. This is useful for partial checks in large datasets without the overhead of fully sorting them.

---

Syntax of std::is_sorted_until

template <class ForwardIterator>
ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last);

template <class ForwardIterator, class Compare>
ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);

Parameters of std::is_sorted_until

Parameter	Description
first, last	Forward iterators defining the range to check. The range is [first, last).
comp (optional)	A binary comparison function that takes two elements and returns true if the first precedes the second. Defaults to < if not provided.

---

Return Value of std::is_sorted_until

Returns an iterator to the first element in the range where the sorting order is violated. If the entire range is sorted, it returns last.

---

Examples for std::is_sorted_until

Example 1: Basic Usage of std::is_sorted_until

This example demonstrates checking whether a vector of integers is sorted and finding the first unsorted element:

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

int main() {
    std::vector<int> nums = {1, 2, 3, 5, 4, 6};

    auto it = std::is_sorted_until(nums.begin(), nums.end());

    if (it != nums.end()) {
        std::cout << "Range is sorted until: " << *it << std::endl;
    } else {
        std::cout << "The entire range is sorted." << std::endl;
    }

    return 0;
}

Output:

Range is sorted until: 4

Explanation:

1. Initialize a vector: A vector named nums is created with predefined integer elements {1, 2, 3, 5, 4, 6}. This vector contains a partially sorted sequence.
2. Find the point where sorting breaks: The std::is_sorted_until function is used to check how far the vector is sorted. It returns an iterator pointing to the first element that is out of order.
3. Check if the entire range is sorted: A conditional check is performed to determine if the iterator returned by std::is_sorted_until equals nums.end(). If true, the entire range is sorted.
4. Output the result: If the range is not fully sorted, the program prints the value of the first unsorted element (pointed to by the iterator). Otherwise, it prints a message stating that the entire range is sorted.

Example 2: Using a Custom Comparison Function for std::is_sorted_until

You can use a custom comparison function to check for sorting based on a specific condition, such as descending order:

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

bool descending(int a, int b) {
    return a > b;
}

int main() {
    std::vector<int> nums = {10, 8, 6, 4, 5, 2};

    auto it = std::is_sorted_until(nums.begin(), nums.end(), descending);

    if (it != nums.end()) {
        std::cout << "Range is sorted in descending order until: " << *it << std::endl;
    } else {
        std::cout << "The entire range is sorted in descending order." << std::endl;
    }

    return 0;
}

Output:

Range is sorted in descending order until: 5

Explanation:

1. Define a custom comparison function: A function named descending is defined to compare two integers. It returns true if the first integer is greater than the second, enforcing descending order.
2. Initialize a vector: A vector named nums is created with predefined integer elements {10, 8, 6, 4, 5, 2}. This vector is partially sorted in descending order.
3. Find the point where descending order breaks: The std::is_sorted_until function is used with the custom descending comparison function to check how far the vector is sorted in descending order. It returns an iterator pointing to the first element that is out of descending order.
4. Check if the entire range is sorted: A conditional check is performed to determine if the iterator returned by std::is_sorted_until equals nums.end(). If true, the entire range is sorted in descending order.

---

Exception Handling in std::is_sorted_until

While std::is_sorted_until does not throw exceptions itself, the comparison function passed as an argument may throw exceptions.

Example 1: Exception in Custom Comparison Function

In this example, the custom comparison function throws an exception when comparing specific values. This demonstrates how exceptions can be caught during the use of std::is_sorted_until.

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

// Custom comparison function that throws an exception
bool faulty_comparison(int a, int b) {
    if (a == 5 || b == 5) {
        throw std::runtime_error("Comparison involving 5 is not allowed.");
    }
    return a < b;
}

int main() {
    std::vector<int> nums = {1, 2, 3, 5, 4, 6};

    try {
        auto it = std::is_sorted_until(nums.begin(), nums.end(), faulty_comparison);

        if (it != nums.end()) {
            std::cout << "Range is sorted until: " << *it << std::endl;
        } else {
            std::cout << "The entire range is sorted." << std::endl;
        }
    } catch (const std::exception& e) {
        std::cerr << "Exception caught: " << e.what() << std::endl;
    }

    return 0;
}

Output:

Exception caught: Comparison involving 5 is not allowed.

Explanation:

1. Define a custom comparison function: A function named faulty_comparison is defined to compare two integers. It throws a std::runtime_error exception if either of the integers is 5; otherwise, it compares the integers in ascending order.
2. Initialize a vector: A vector named nums is created with predefined integer elements {1, 2, 3, 5, 4, 6}. This vector is partially sorted in ascending order.
3. Use a try-catch block: A try block is used to handle potential exceptions raised by the faulty_comparison function during execution.
4. Check sorting with a custom comparison function: The std::is_sorted_until function is used to determine how far the vector is sorted, passing the faulty_comparison function. If no exception occurs, it returns an iterator pointing to the first unsorted element.
5. Handle exceptions: If the comparison function throws an exception (e.g., when encountering the value 5), the catch block captures it and prints an error message to the console.