C++ algorithm std::is_sorted Function Template

C++ std::is_sorted

The std::is_sorted function in C++ is part of the <algorithm> header and is used to determine if a range of elements is sorted. We can check if sorting is in ascending or descending order. It returns a boolean value: true if the range is sorted, and false otherwise.

Syntax

// Default version using operator<
template <class ForwardIterator>
bool is_sorted(ForwardIterator first, ForwardIterator last);

// Custom comparison function version
template <class ForwardIterator, class Compare>
bool is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);

first, last

Forward iterators defining the range [first, last) to be checked. The range includes all elements between first and last, excluding the element pointed to by last.

comp

Binary function that accepts two elements in the range as arguments and returns a value convertible to bool. The returned value indicates whether the element passed as the first argument is considered to go before the second in the specific strict weak ordering it defines. The function shall not modify any of its arguments.

Examples

Example 1: Checking if a Vector is Sorted in Ascending Order

This example demonstrates how to use std::is_sorted to check if a vector of integers is sorted in ascending order.

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

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

    if (std::is_sorted(myvector.begin(), myvector.end())) {
        std::cout << "The vector is sorted in ascending order." << std::endl;
    } else {
        std::cout << "The vector is not sorted in ascending order." << std::endl;
    }

    return 0;
}

Output:

The vector is sorted in ascending order.

Explanation:

1. Initialize the vector: A std::vector named myvector is created and initialized with integers {1, 2, 3, 4, 5}. This vector is used to demonstrate whether it is sorted in ascending order.
2. Check if the vector is sorted: The std::is_sorted function is called with two arguments:
   • myvector.begin(): Specifies the starting point of the range to check.
   • myvector.end(): Specifies the ending point of the range to check.
   std::is_sorted evaluates whether the elements in the range [myvector.begin(), myvector.end()) are sorted in ascending order using the default comparison operator <.
3. Output the result:
   • If the vector is sorted in ascending order, std::is_sorted returns true, and the message "The vector is sorted in ascending order." is printed to the console using std::cout.
   • If the vector is not sorted in ascending order, std::is_sorted returns false, and the message "The vector is not sorted in ascending order." is printed.

Example 2: Checking if a Vector is Sorted in Descending Order Using a Custom Comparison Function

This example demonstrates how to use std::is_sorted with a custom comparison function to check if a vector of integers is sorted in descending order.

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

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

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

    if (std::is_sorted(myvector.begin(), myvector.end(), descending)) {
        std::cout << "The vector is sorted in descending order." << std::endl;
    } else {
        std::cout << "The vector is not sorted in descending order." << std::endl;
    }

    return 0;
}

Output:

The vector is sorted in descending order.

Explanation:

1. Define a custom comparison function: The function descending is defined to compare two integers:
   • It takes two integers i and j as input arguments.
   • Returns true if i is greater than j, ensuring a descending order comparison.
   This custom function is used by std::is_sorted to check if the range is sorted in descending order.
2. Initialize the vector: A std::vector named myvector is created and initialized with integers {5, 4, 3, 2, 1}. The vector contains elements arranged in descending order.
3. Check if the vector is sorted: The std::is_sorted function is called with three arguments:
   • myvector.begin(): Specifies the starting point of the range to check.
   • myvector.end(): Specifies the ending point of the range to check.
   • descending: The custom comparison function used to check if the elements are sorted in descending order.
   std::is_sorted evaluates whether the elements in the range [myvector.begin(), myvector.end()) are sorted according to the descending function.
4. Output the result:
   • If the vector is sorted in descending order, std::is_sorted returns true, and the message "The vector is sorted in descending order." is printed to the console using std::cout.
   • If the vector is not sorted in descending order, std::is_sorted returns false, and the message "The vector is not sorted in descending order." is printed.

Example 3: Exception Handling with std::is_sorted

In this example, we will show how to handle an exception during the execution of std::is_sorted. Although std::is_sorted itself does not throw exceptions, a custom comparison function can simulate a failure.

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

// Custom comparison function that throws an exception
bool faultyComparison(int i, int j) {
    if (i == 3 || j == 3) {
        throw std::runtime_error("Comparison failed for value 3.");
    }
    return i < j;
}

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

    try {
        // Check if the vector is sorted using a faulty comparison function
        if (std::is_sorted(myvector.begin(), myvector.end(), faultyComparison)) {
            std::cout << "The vector is sorted." << std::endl;
        } else {
            std::cout << "The vector is not sorted." << std::endl;
        }
    } catch (const std::exception& e) {
        std::cerr << "Exception caught: " << e.what() << std::endl;
    }

    return 0;
}

Output:

Exception caught: Comparison failed for value 3.

Explanation:

1. Define a custom comparison function: The function faultyComparison is defined to simulate an intentional failure during comparison:
   • It takes two integers i and j as input arguments.
   • If either i or j is equal to 3, the function throws a std::runtime_error exception with the message "Comparison failed for value 3.".
   • If no exception is triggered, it returns true if i is less than j, ensuring ascending order comparison.
2. Handle the exception:
   • The try block surrounds the call to std::is_sorted. If an exception is thrown, the catch block catches it.
   • The exception message, "Comparison failed for value 3.", is displayed using std::cerr to inform the user of the failure.
3. Output results:
   • If no exception occurs, the program prints whether the vector is sorted based on the custom comparison function.
   • If an exception is thrown, the catch block ensures that the program handles it gracefully without crashing.

---

Key Points to Remember about std::is_sorted

• std::is_sorted checks if the elements in the specified range are sorted in ascending order by default.
• A custom comparison function can be provided to check for different sorting orders, such as descending.
• If the range contains less than two elements, the function always returns true.
• The function operates in linear time, performing a single pass through the range.