Merging Three or More Sorted Ranges
How do I merge three or more sorted ranges using std::ranges::merge()?
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.
8 Key Standard Library Algorithms
An introduction to 8 more useful algorithms from the standard library, and how we can use them alongside views, projections, and other techniques