C++ の std::merge アルゴリズム
-
C++ で
std::mergeアルゴリズムを使用して 2つのソートされた範囲のコンテンツをマージする -
C++ で
std::set_unionアルゴリズムを使用して 2つのソートされた範囲のコンテンツをマージする
この記事では、C++ で std::merge STL アルゴリズムを使用する方法について説明します。
C++ で std::merge アルゴリズムを使用して 2つのソートされた範囲のコンテンツをマージする
std::merge 関数は、STL アルゴリズムヘッダー-<algorithm> の下にあります。以前にソートされた 2つの範囲をマージするために利用できます。範囲イテレータは、LegacyInputIterator 要件を満たす必要があります。
次のサンプルコードでは、ランダムな整数値を持つ 2つの vector コンテナを作成し、std::merge アルゴリズムを使用してそれらを 3 番目のベクトルにマージします。マージする前に、v1 および v2 コンテナで std::sort アルゴリズムを呼び出します。ランダム整数は、高品質のランダム性のために推奨される方法である STL 機能を使用して生成されます。また、値をベクトルに格納するために、通常のループの代わりにラムダ式を使用した 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 の内容を格納できるようにします。または、アルゴリズムの 5 番目のパラメーターとして std::back_inserter を使用して、ベクトルを動的に拡張することもできます。std::merge アルゴリズムが使用されている場合、これら 2つの方法の間に機能的な違いはありませんが、他の同様のアルゴリズムには特定のバージョンが必要な場合があります。
#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 アルゴリズムを使用して 2つのソートされた範囲のコンテンツをマージする
std::merge は、正確に std::distance(first1, last1) + std::distance(first2, last2) の要素数を含む出力範囲を構築します。ただし、同様の機能を持つ std::set_union アルゴリズムは、要素が両方の範囲で見つかったかどうかをチェックし、見つかった場合は、すべての要素インスタンスが最初の範囲からコピーされますが、std::max(n-m, 0)2 番目の範囲のインスタンス。ここで、m は最初の範囲のインスタンスの数、n は 2 番目の範囲のインスタンスの数です。
次の例は、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,
