C++ algorithm: std::nth_element

C++ std::nth_element

The std::nth_element algorithm partially sorts a given range of elements such that the element at the nth position is the same as if the range were sorted. All elements before the nth position are less than or equal to it, and all elements after are greater than or equal to it.

---

Syntax of std::nth_element

template <class RandomIt>
void nth_element(RandomIt first, RandomIt nth, RandomIt last);

template <class RandomIt, class Compare>
void nth_element(RandomIt first, RandomIt nth, RandomIt last, Compare comp);

Parameters of std::nth_element

Parameter	Description
first, last	Random-access iterators defining the range [first, last) to partially sort.
nth	Random-access iterator pointing to the nth position in the range.
comp (optional)	A binary comparison function defining the sorting order. Defaults to < if not provided.

---

Return Value of std::nth_element

The function does not return a value. However, it ensures that the element at the nth position is correctly placed, with all elements before it smaller or equal and all elements after it larger or equal (based on the comparison function).

---

Examples for std::nth_element

Example 1: Basic Usage of std::nth_element

In this example, we will find the median element in an array using std::nth_element algorithm.

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

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

    std::nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end());

    std::cout << "Median element: " << nums[nums.size() / 2] << std::endl;

    return 0;
}

Output:

Median element: 5

Explanation:

1. Initialize a vector: A vector named nums is created with predefined integer elements {8, 4, 7, 1, 3, 6, 2, 5}. This is the unsorted input data.
2. Use std::nth_element: The std::nth_element function is called with three arguments:
   
   • nums.begin(): The beginning of the range.nums.begin() + nums.size() / 2: The middle of the range, where the median element will be placed.nums.end(): The end of the range.

   The function rearranges the elements such that the middle element is the same as if the vector were fully sorted. All elements before it are less than or equal, and all elements after it are greater than or equal.

3. Find the median: After calling std::nth_element, the element at the middle position (nums[nums.size() / 2]) is guaranteed to be the median of the vector.

Example 2: Using a Custom Comparison Function

Using a custom comparison function with std::nth_element to find the nth largest element:

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

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

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

    std::nth_element(nums.begin(), nums.begin() + 3, nums.end(), descending);

    std::cout << "Fourth largest element: " << nums[3] << std::endl;

    return 0;
}

Output:

Fourth largest element: 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, enabling sorting in descending order.
2. Use std::nth_element: The std::nth_element function is called with four arguments:
   • nums.begin(): The beginning of the range.nums.begin() + 3: The position of the fourth largest element in the range.nums.end(): The end of the range.descending: The custom comparison function to sort elements in descending order.

   The function rearranges the elements in the range such that the element at the fourth position is the fourth largest, with all larger elements before it and all smaller elements after it (based on descending order).

3. Find the fourth largest element: After the call to std::nth_element, the fourth largest element is located at nums[3].

---

Exception Handling in std::nth_element

The std::nth_element function itself does not throw exceptions, but the custom comparison function provided may throw exceptions during execution.

Example: Exception in Custom Comparison Function

This example demonstrates how to handle exceptions when a custom comparison function throws an error:

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

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 = {8, 4, 7, 1, 3, 6, 2, 5};

    try {
        std::nth_element(nums.begin(), nums.begin() + 3, nums.end(), faulty_comparison);
    } 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. We defined a custom comparison function named faulty_comparison. It throws a std::runtime_error exception if either integer being compared is 5. Otherwise, it compares the integers in ascending order.
2. We took a vector named nums and initialized it with the elements {8, 4, 7, 1, 3, 6, 2, 5}.
3. A try block is used to safely execute std::nth_element, anticipating exceptions from the custom comparison function.
4. The std::nth_element function is called to partially sort the vector. It rearranges elements so that the fourth smallest element (at position 3) is correctly placed, with smaller elements before it and larger elements after it.
5. The custom comparison function throws an exception when it encounters the value 5, as per its design.
6. The exception is captured in the catch block, and an error message is displayed using std::cerr.
7. The program terminates gracefully after handling the exception, ensuring no unhandled errors disrupt execution.