C++ 中的 std::merge 算法
Jinku Hu
2023年10月12日
本文将解释如何在 C++ 中使用 std::merge STL 算法。
在 C++ 中使用 std::merge 算法合并两个排序范围的内容
std::merge 函数在 STL 算法标题 - <algorithm> 下提供。它可用于合并先前已排序的两个范围。范围迭代器应满足 LegacyInputIterator 要求。
在下面的示例代码中，我们创建了两个带有随机整数值的 vector 容器，并使用 std::merge 算法将它们合并到第三个向量中。我们在合并之前在 v1 和 v2 容器上调用 std::sort 算法。随机整数是使用 STL 工具生成的，这是高质量随机性的推荐方式，并且还使用带有 lambda 表达式的 std::generate 算法而不是常规循环将值存储到向量中。
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
template <typename T>
void printRange(std::vector<T> v) {
for (const auto &item : v) {
cout << std::setw(2) << item << ", ";
}
cout << endl;
}
int main() {
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<> dis(0, 10);
std::vector<int> v1(5), v2(5);
std::generate(v1.begin(), v1.end(), [&dis, &mt] { return dis(mt); });
std::generate(v2.begin(), v2.end(), [&dis, &mt] { return dis(mt); });
std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());
cout << "v1: ";
printRange(v1);
cout << "v2: ";
printRange(v2);
std::vector<int> v3(v1.size() + v2.size());
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
cout << "v3: ";
printRange(v3);
return EXIT_SUCCESS;
}
输出：
v1: 2, 2, 4, 9, 10,
v2: 0, 2, 4, 4, 9,
v3: 0, 2, 2, 2, 4, 4, 4, 9, 9, 10,
前面的代码使用向量大小的总和初始化目标向量，以便它可以存储 v1 和 v2 的内容。或者，我们可以使用 std::back_inserter 作为算法的第五个参数来动态增长向量。当使用 std::merge 算法时，这两种方法之间没有功能差异，但我们会看到其他类似的算法可能需要特定版本。
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
template <typename T>
void printRange(std::vector<T> v) {
for (const auto &item : v) {
cout << std::setw(2) << item << ", ";
}
cout << endl;
}
int main() {
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<> dis(0, 10);
std::vector<int> v1(5), v2(5);
std::generate(v1.begin(), v1.end(), [&dis, &mt] { return dis(mt); });
std::generate(v2.begin(), v2.end(), [&dis, &mt] { return dis(mt); });
std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());
cout << "v1: ";
printRange(v1);
cout << "v2: ";
printRange(v2);
std::vector<int> v3;
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(),
std::back_inserter(v3));
cout << "v3: ";
printRange(v3);
return EXIT_SUCCESS;
}
v1: 2, 2, 4, 9, 10,
v2: 0, 2, 4, 4, 9,
v3: 0, 2, 2, 2, 4, 4, 4, 9, 9, 10,
在 C++ 中使用 std::set_union 算法合并两个排序范围的内容
std::merge 构造一个输出范围，该范围正好包含 std::distance(first1, last1) + std::distance(first2, last2) 的元素数量。尽管具有类似功能的 std::set_union 算法检查是否在两个范围内都找到了一个元素，如果是，则从第一个范围复制所有元素实例，但只有 std::max(n-m, 0) 来自第二个范围的实例，其中 m 是第一个范围内的实例数，n 是第二个范围内的实例数。
以下示例使用 std::set_union 算法演示了相同的代码片段。
#include <iostream>
#include <algorithm>
#include <vector>
#include <random>
#include <iomanip>
using std::cout; using std::cin;
using std::endl; using std::vector;
template<typename T>
void printRange(std::vector<T> v) {
for (const auto &item : v) {
cout << std::setw(2) << item << ", ";
}
cout << endl;
}
int main() {
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<> dis(0, 10);
std::vector<int> v1(5), v2(5);
std::generate(v1.begin(), v1.end(), [&dis, &mt] { return dis(mt); });
std::generate(v2.begin(), v2.end(), [&dis, &mt] { return dis(mt); });
std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());
cout << "v1: ";
printRange(v1);
cout << "v2: ";
printRange(v2);
std::vector<int> v4;
std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(v4));
cout << "v4: ";
printRange(v4);
return EXIT_SUCCESS;
}
v1: 2, 2, 4, 9, 10,
v2: 0, 2, 4, 4, 9,
v4: 0, 2, 2, 4, 4, 9, 10,
作者： Jinku Hu
