C++ algorithm std::partial_sort_copy

C++ std::partial_sort_copy

The std::partial_sort_copy algorithm in C++ allows you to copy and partially sort elements from one range to another. This is useful when you need a sorted subset of elements without modifying the original container.

---

Syntax of std::partial_sort_copy

template <class InputIterator, class RandomAccessIterator>
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
                                       RandomAccessIterator result_first, RandomAccessIterator result_last);

template <class InputIterator, class RandomAccessIterator, class Compare>
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
                                       RandomAccessIterator result_first, RandomAccessIterator result_last,
                                       Compare comp);

Parameters of std::partial_sort_copy

Parameter	Description
first, last	Input iterators defining the range to copy and sort. The range is [first, last).
result_first, result_last	Random-access iterators defining the destination range where the sorted elements are copied. The range is [result_first, result_last).
comp (optional)	A binary comparison function that takes two elements and returns true if the first should go before the second. If omitted, the default comparison (<) is used.

---

Return Value of std::partial_sort_copy

The function returns an iterator to the element past the last element copied into the destination range. If the destination range is smaller than the input range, only the smallest result_last - result_first elements are copied and sorted.

---

Examples for std::partial_sort_copy

Example 1: Basic Usage

Let’s consider an example where we have a vector of unsorted integers, and we want to copy the smallest three elements into another vector in sorted order.

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

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

    std::partial_sort_copy(source.begin(), source.end(), destination.begin(), destination.end());

    std::cout << "The smallest 3 elements are: ";
    for (int n : destination)
        std::cout << n << ' ';
    std::cout << std::endl;

    return 0;
}

Output:

The smallest 3 elements are: 2 3 4

Explanation:

1. Initialize a source vector: A vector named source is created with predefined integer elements {10, 2, 8, 6, 7, 5, 3, 4}. This serves as the input data.
2. Create a destination vector: Another vector named destination is created with a size of 3, intended to hold the smallest 3 elements from the source vector.
3. Sort and copy smallest elements: The std::partial_sort_copy function is used to sort the source vector and copy only the smallest 3 elements into the destination vector. The sorting is partial, focusing on the smallest elements.
4. Display the smallest elements: A for loop iterates over the destination vector, and its elements are printed to the console, displaying the smallest 3 elements in sorted order.

Example 2: Using a Custom Comparison Function

You can also use a custom comparison function to define the sorting criteria. For instance, to sort in descending order:

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

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

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

    std::partial_sort_copy(source.begin(), source.end(), destination.begin(), destination.end(), descending);

    std::cout << "The largest 3 elements are: ";
    for (int n : destination)
        std::cout << n << ' ';
    std::cout << std::endl;

    return 0;
}

Output:

The largest 3 elements are: 10 8 7

Explanation:

1. Define a custom sorting function: A function named descending is defined to compare two integers and return true if the first is greater than the second. This function is used to sort elements in descending order.
2. Initialize a source vector: A vector named source is created with predefined integer elements {10, 2, 8, 6, 7, 5, 3, 4}. This serves as the input data.
3. Create a destination vector: Another vector named destination is created with a size of 3, intended to hold the largest 3 elements from the source vector.
4. Sort and copy the largest elements: The std::partial_sort_copy function is used to sort the source vector in descending order (using the descending function) and copy the largest 3 elements into the destination vector.

---

Exception Handling

While std::partial_sort_copy itself does not throw exceptions, the operations performed during sorting (such as comparisons or element assignments) may throw exceptions. It’s essential to handle such exceptions to ensure program stability.

Example 3: Handling Exceptions

Consider a scenario where the comparison function may throw an exception.

The program defines a custom comparison function faulty_comparison, which throws a std::runtime_error exception if either argument is equal to 5.

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

// Faulty 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> source = {10, 2, 8, 6, 7, 5, 3, 4};
    std::vector<int> destination(3);

    try {
        // Attempt to partially sort with a faulty comparison function
        std::partial_sort_copy(source.begin(), source.end(), destination.begin(), destination.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. Define a faulty comparison function: A function named faulty_comparison is defined to compare two integers. If either of the integers is 5, it throws a std::runtime_error exception. Otherwise, it compares the integers in ascending order.
2. Initialize a source vector: A vector named source is created with predefined integer elements {10, 2, 8, 6, 7, 5, 3, 4}. This serves as the input data.
3. Create a destination vector: Another vector named destination is created with a size of 3, intended to hold partially sorted elements from the source vector.
4. Use a try-catch block: A try block is used to attempt partial sorting with std::partial_sort_copy, passing the faulty comparison function. If the comparison function throws an exception, it will be caught in the catch block.
5. Catch and display the exception: When the faulty comparison function encounters the number 5, it throws a std::runtime_error exception. The catch block captures this exception and prints an error message to the console.
6. End the program: The program terminates gracefully after handling the exception, ensuring no unhandled errors disrupt execution.