L'algorithme std::merge en C++
-
Utilisez l’algorithme
std::mergepour fusionner le contenu de deux plages triées en C++ -
Utilisez l’algorithme
std::set_unionpour fusionner le contenu de deux plages triées en C++
Cet article explique comment utiliser l’algorithme STL std::merge en C++.
Utilisez l’algorithme std::merge pour fusionner le contenu de deux plages triées en C++
La fonction std::merge est fournie sous l’en-tête des algorithmes STL - <algorithm>. Il peut être utilisé pour fusionner deux plages qui ont été triées précédemment. Les itérateurs de plage doivent satisfaire aux exigences LegacyInputIterator.
Dans l’exemple de code suivant, nous créons deux conteneurs vecteur avec des valeurs entières aléatoires et les fusionnons dans le troisième vecteur à l’aide de l’algorithme std::merge. Nous invoquons l’algorithme std::sort sur les conteneurs v1 et v2 avant de fusionner. Les entiers aléatoires sont générés avec les installations STL, ce qui est le moyen recommandé pour un caractère aléatoire de haute qualité, et utilisent également l’algorithme std::generate avec une expression lambda au lieu d’une boucle régulière pour stocker les valeurs dans des vecteurs.
#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;
}
Production:
v1: 2, 2, 4, 9, 10,
v2: 0, 2, 4, 4, 9,
v3: 0, 2, 2, 2, 4, 4, 4, 9, 9, 10,
Le code précédent initialise un vecteur de destination avec la somme des tailles de vecteurs afin qu’il puisse stocker le contenu de v1 et v2. Alternativement, nous pourrions utiliser std::back_inserter comme cinquième paramètre de l’algorithme pour faire croître le vecteur dynamiquement. Il n’y a pas de différence fonctionnelle entre ces deux méthodes lorsque l’algorithme std::merge est utilisé, mais nous verrons que d’autres algorithmes similaires peuvent nécessiter une version spécifique.
#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,
Utilisez l’algorithme std::set_union pour fusionner le contenu de deux plages triées en C++
std::merge construit une plage de sortie qui inclut exactement le nombre d’éléments std::distance(first1, last1) + std::distance(first2, last2). Bien que l’algorithme std::set_union, qui a une fonction similaire, vérifie si un élément est trouvé dans les deux plages et si c’est le cas, toutes les instances d’élément sont copiées à partir de la première plage, mais seulement std::max(n-m, 0) instances de la deuxième plage, où m est le nombre d’instances de la première plage et n est le nombre d’instances de la seconde.
L’exemple suivant illustre le même extrait de code avec l’algorithme 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,
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