Der std::merge-Algorithmus in C++
-
Verwenden des
std::merge-Algorithmus zum Zusammenführen der Inhalte zweier sortierter Bereiche in C++ -
Verwendung des
std::set_union-Algorithmus zum Zusammenführen von Inhalten zweier sortierter Bereiche in C++
Dieser Artikel erklärt, wie Sie den STL-Algorithmus std::merge in C++ verwenden.
Verwenden des std::merge-Algorithmus zum Zusammenführen der Inhalte zweier sortierter Bereiche in C++
Die Funktion std::merge wird unter dem Header der STL-Algorithmen bereitgestellt - <algorithm>. Es kann verwendet werden, um zwei zuvor sortierte Bereiche zusammenzuführen. Bereichsiteratoren sollten die Anforderungen von LegacyInputIterator erfüllen.
Im folgenden Beispielcode erstellen wir zwei Vektor-Container mit zufälligen Integer-Werten und fügen sie mit dem std::merge-Algorithmus in den dritten Vektor zusammen. Wir rufen den std::sort-Algorithmus auf v1- und v2-Containern vor dem Zusammenführen auf. Zufällige Ganzzahlen werden mit STL-Funktionen generiert, was der empfohlene Weg für qualitativ hochwertige Zufälligkeit ist, und verwenden auch den std::generate-Algorithmus mit Lambda-Ausdruck anstelle einer regulären Schleife, um die Werte in Vektoren zu speichern.
#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;
}
Ausgabe:
v1: 2, 2, 4, 9, 10,
v2: 0, 2, 4, 4, 9,
v3: 0, 2, 2, 2, 4, 4, 4, 9, 9, 10,
Der vorherige Code initialisiert einen Zielvektor mit der Summe der Vektorgrößen, damit er den Inhalt von v1 und v2 speichern kann. Alternativ könnten wir std::back_inserter als fünften Parameter des Algorithmus verwenden, um den Vektor dynamisch zu vergrößern. Es gibt keinen funktionalen Unterschied zwischen diesen beiden Methoden, wenn der std::merge-Algorithmus verwendet wird, aber wir werden sehen, dass andere ähnliche Algorithmen möglicherweise eine bestimmte Version benötigen.
#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,
Verwendung des std::set_union-Algorithmus zum Zusammenführen von Inhalten zweier sortierter Bereiche in C++
std::merge konstruiert einen Ausgabebereich, der genau std::distance(first1, last1) + std::distance(first2, last2) die Anzahl der Elemente umfasst. Allerdings prüft der Algorithmus std::set_union, der eine ähnliche Funktion hat, ob ein Element in beiden Bereichen gefunden wird und wenn ja, werden alle Elementinstanzen aus dem ersten Bereich kopiert, aber nur std::max(n-m, 0) Instanzen aus dem zweiten Bereich, wobei m die Anzahl der Instanzen im ersten Bereich und n die Anzahl der Instanzen im zweiten Bereich ist.
Das folgende Beispiel demonstriert das gleiche Code-Snippet mit dem std::set_union-Algorithmus.
#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,
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook