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
