8 Key Standard Library Algorithms

Merging Three or More Sorted Ranges

How do I merge three or more sorted ranges using std::ranges::merge()?

Abstract art representing computer programming

To merge three or more sorted ranges using std::ranges::merge(), you can perform successive merges, combining two ranges at a time until all ranges are merged into a single output range.

Here's a detailed example demonstrating this process. First, define and sort three input vectors:

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

int main() {
  std::vector<int> vec1{1, 3, 5};
  std::vector<int> vec2{2, 4, 6};
  std::vector<int> vec3{0, 7, 8};

  // Ensure all vectors are sorted
  std::ranges::sort(vec1);
  std::ranges::sort(vec2);
  std::ranges::sort(vec3);

  std::vector<int> temp;
  temp.resize(vec1.size() + vec2.size());

  // Merge vec1 and vec2 into temp
  std::ranges::merge(vec1, vec2, temp.begin());

  std::vector<int> result;
  result.resize(temp.size() + vec3.size());

  // Merge temp and vec3 into result
  std::ranges::merge(temp, vec3, result.begin());

  for (int n : result) {
    std::cout << n << ", ";
  }
}
0, 1, 2, 3, 4, 5, 6, 7, 8,

In this example, vec1, vec2, and vec3 are three sorted vectors. We first merge vec1 and vec2 into a temporary vector temp. Then, we merge temp with vec3 into the final result vector result.

This approach can be extended to merge more than three sorted ranges by repeating the merge process. Here’s how you can merge four sorted ranges:

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

int main() {
  std::vector<int> vec1{1, 3, 5};
  std::vector<int> vec2{2, 4, 6};
  std::vector<int> vec3{0, 7, 8};
  std::vector<int> vec4{9, 10, 11};

  // Ensure all vectors are sorted
  std::ranges::sort(vec1);
  std::ranges::sort(vec2);
  std::ranges::sort(vec3);
  std::ranges::sort(vec4);

  std::vector<int> temp1;
  temp1.resize(vec1.size() + vec2.size());
  std::vector<int> temp2;
  temp2.resize(vec3.size() + vec4.size());
  std::vector<int> result;

  // First merge pairs of vectors
  std::ranges::merge(vec1, vec2, temp1.begin());
  std::ranges::merge(vec3, vec4, temp2.begin());

  // Resize result to hold all elements
  result.resize(temp1.size() + temp2.size());

  // Merge the two temporary vectors into result
  std::ranges::merge(temp1, temp2, result.begin());

  for (int n : result) {
    std::cout << n << ", ";
  }
}
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,

By using temporary vectors to hold intermediate merge results, you can manage the merging of multiple sorted ranges effectively.

This method ensures the final output is a single sorted range containing all elements from the input ranges.

Answers to questions are automatically generated and may not have been reviewed.

Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved