C++ algorithm: std::merge – Function Template

C++ std::merge

The algorithm std::merge function in C++ is used to merge two sorted ranges into a single sorted range. It operates based on the sorting order of the input ranges. The result is written to a destination range starting from the specified output iterator.

---

Syntax of std::merge

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
                     InputIterator2 first2, InputIterator2 last2,
                     OutputIterator result);

template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
                     InputIterator2 first2, InputIterator2 last2,
                     OutputIterator result, Compare comp);

Parameters of std::merge

Parameter	Description
first1, last1	Input iterators defining the first sorted range to merge.
first2, last2	Input iterators defining the second sorted range to merge.
result	Output iterator to the beginning of the destination range where the merged elements are stored.
comp (optional)	A binary comparison function that defines the order of elements. Defaults to <.

---

Return Value of std::merge

Returns an iterator to the element in the destination range corresponding to the end of the merged range.

---

Examples for std::merge

Example 1: Basic Usage of std::merge

This example demonstrates merging two sorted arrays into a single sorted array.

Steps:

1. Create two sorted input vectors, vec1 and vec2, with elements {1, 3, 5, 7} and {2, 4, 6, 8}, respectively.
2. Initialize a third vector, result, with a size equal to the sum of the sizes of vec1 and vec2. This vector will hold the merged elements.
3. Call the std::merge function to merge the two sorted input vectors into the result vector:
   • Provide the range of vec1 using vec1.begin() and vec1.end().
   • Provide the range of vec2 using vec2.begin() and vec2.end().
   • Specify the destination range starting at result.begin().
4. Iterate over the result vector using a range-based for loop and print each element to the console.

Program:

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

int main() {
    std::vector<int> vec1 = {1, 3, 5, 7};
    std::vector<int> vec2 = {2, 4, 6, 8};
    std::vector<int> result(vec1.size() + vec2.size());

    std::merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());

    std::cout << "Merged array: ";
    for (int n : result) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

Output:

Merged array: 1 2 3 4 5 6 7 8

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

This example demonstrates merging two sorted ranges using a custom comparison function:

Steps:

1. Define a custom comparison function named descending that takes two integers as arguments and returns true if the first integer is greater than the second. This will enable sorting in descending order.
2. Create two sorted input vectors, vec1 with elements {7, 5, 3, 1} and vec2 with elements {8, 6, 4, 2}. These vectors are already sorted in descending order.
3. Initialize a third vector, result, with a size equal to the sum of the sizes of vec1 and vec2. This vector will hold the merged elements.
4. Call the std::merge function to merge the two sorted input vectors into the result vector in descending order:
   • Provide the range of vec1 using vec1.begin() and vec1.end().
   • Provide the range of vec2 using vec2.begin() and vec2.end().
   • Specify the destination range starting at result.begin().
   • Pass the custom comparison function descending to ensure the merge is done in descending order.
5. Iterate over the result vector using a range-based for loop and print each element to the console.

Program

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

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

int main() {
    std::vector<int> vec1 = {7, 5, 3, 1};
    std::vector<int> vec2 = {8, 6, 4, 2};
    std::vector<int> result(vec1.size() + vec2.size());

    std::merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin(), descending);

    std::cout << "Merged array in descending order: ";
    for (int n : result) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

Output:

Merged array in descending order: 8 7 6 5 4 3 2 1

---

Exception Handling in std::merge

The std::merge function itself does not throw exceptions. However, the comparison function passed as an argument may throw exceptions, which can be caught and handled appropriately.

Example 1: Exception in Custom Comparison Function

This example demonstrates how exceptions in a custom comparison function are handled:

Algorithm Steps:

1. Define a custom comparison function named faulty_compare that throws a std::runtime_error if either of the integers being compared is 5. Otherwise, it compares the integers in ascending order.
2. Initialize two sorted input vectors:
   • vec1 with elements {1, 3, 5}.
   • vec2 with elements {2, 4, 6}.
3. Create a third vector, result, with a size equal to the combined size of vec1 and vec2. This vector will store the merged output.
4. Wrap the merge operation in a try block to handle potential exceptions from the faulty_compare function.
5. Call the std::merge function with the following arguments:
   • The range of vec1 defined by vec1.begin() and vec1.end().
   • The range of vec2 defined by vec2.begin() and vec2.end().
   • The destination range starting at result.begin().
   • The custom comparison function faulty_compare.
6. If faulty_compare encounters the value 5, it throws a std::runtime_error, interrupting the merge operation.
7. In the catch block, capture the exception and print an error message to the console using std::cerr, indicating the reason for the failure.

Program

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

bool faulty_compare(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> vec1 = {1, 3, 5};
    std::vector<int> vec2 = {2, 4, 6};
    std::vector<int> result(vec1.size() + vec2.size());

    try {
        std::merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin(), faulty_compare);
    } catch (const std::exception& e) {
        std::cerr << "Exception caught: " << e.what() << std::endl;
    }

    return 0;
}

Output:

Exception caught: Comparison involving 5 is not allowed.