C++ std::inplace_merge

The std::inplace_merge function in C++ merges two consecutive sorted ranges within the same container into a single sorted range. This operation is performed in place, meaning it does not require additional memory for the merged range. This function is particularly useful when combining two sorted halves of a container.

Syntax of std::inplace_merge

</>
Copy
template <class BidirectionalIterator>
void inplace_merge(BidirectionalIterator first, 
                   BidirectionalIterator middle, 
                   BidirectionalIterator last);

template <class BidirectionalIterator, class Compare>
void inplace_merge(BidirectionalIterator first, 
                   BidirectionalIterator middle, 
                   BidirectionalIterator last, 
                   Compare comp);

Parameters of std::inplace_merge

ParameterDescription
firstBidirectional iterator pointing to the beginning of the range.
middleBidirectional iterator pointing to the beginning of the second sorted range.
lastBidirectional iterator pointing to the end of the range.
comp (optional)A binary comparison function that defines the order of elements. Defaults to <.

Return Value of std::inplace_merge

This function does not return any value. It rearranges the elements in the range [first, last) so that they form a single sorted range.

Examples for std::inplace_merge

Example 1: Basic Usage of std::inplace_merge

This example demonstrates merging two sorted halves of a vector:

</>
Copy
#include <iostream>
#include <algorithm>
#include <vector>

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

    // Indicating the middle of the range
    auto middle = nums.begin() + 3;

    // Merging two sorted ranges
    std::inplace_merge(nums.begin(), middle, nums.end());

    // Output the merged range
    std::cout << "Merged vector: ";
    for (int n : nums) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

Explanation:

  1. Include necessary headers:
    • <iostream>: Used for input/output operations.
    • <algorithm>: Includes the std::inplace_merge function.
    • <vector>: Used for the std::vector container.
  2. Initialize a vector:
    • A vector named nums is initialized with the elements {1, 3, 5, 2, 4, 6}.
    • The first part of the vector {1, 3, 5} and the second part {2, 4, 6} are already sorted.
  3. Indicate the middle of the range:
    • The variable middle is defined as nums.begin() + 3, which points to the fourth element in the vector (2).
  4. Merge the two sorted ranges:
    • The function std::inplace_merge is called with three arguments:
      • nums.begin(): Iterator pointing to the beginning of the range.
      • middle: Iterator pointing to the boundary between the two sorted ranges.
      • nums.end(): Iterator pointing to the end of the range.
    • This function merges the two sorted ranges [nums.begin(), middle) and [middle, nums.end()) into a single sorted range in-place.
  5. Output the merged range:

Output:

Merged vector: 1 2 3 4 5 6

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

This example demonstrates merging two sorted halves of a vector in descending order using a custom comparison function:

</>
Copy
#include <iostream>
#include <algorithm>
#include <vector>

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

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

    // Indicating the middle of the range
    auto middle = nums.begin() + 3;

    // Merging two sorted ranges in descending order
    std::inplace_merge(nums.begin(), middle, nums.end(), descending);

    // Output the merged range
    std::cout << "Merged vector in descending order: ";
    for (int n : nums) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

Explanation:

  1. Define a custom comparison function:
    • The function descending compares two integers and returns true if the first integer is greater than the second, ensuring descending order.
  2. Merge the two sorted ranges:
    • The function std::inplace_merge is called with four arguments:
      • nums.begin(): Iterator pointing to the beginning of the range.
      • middle: Iterator pointing to the boundary between the two sorted ranges.
      • nums.end(): Iterator pointing to the end of the range.
      • descending: Custom comparison function to maintain descending order.
    • This function merges the two sorted ranges [nums.begin(), middle) and [middle, nums.end()) into a single sorted range in descending order, in-place.

Output:

Merged vector in descending order: 6 5 4 3 2 1

Exception Handling in std::inplace_merge

The std::inplace_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:

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

bool faulty_compare(int a, int b) {
    if (a == 4 || b == 4) {
        throw std::runtime_error("Comparison involving 4 is not allowed.");
    }
    return a < b;
}

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

    // Indicating the middle of the range
    auto middle = nums.begin() + 3;

    try {
        // Attempting to merge with a faulty comparison function
        std::inplace_merge(nums.begin(), middle, nums.end(), faulty_compare);
    } catch (const std::exception& e) {
        std::cerr << "Exception caught: " << e.what() << std::endl;
    }

    return 0;
}

Output:

Exception caught: Comparison involving 4 is not allowed.

We have defined a custom comparison function that throws exception:

  • faulty_compare is a custom function that compares two integers, a and b.
  • The function throws a std::runtime_error exception if either a or b equals 4, with the message "Comparison involving 4 is not allowed.".
  • If no exception is thrown, the function compares a and b and returns true if a is less than b, and false otherwise.