El algoritmo std::merge en C++
-
Utilice el algoritmo
std::mergepara fusionar el contenido de dos rangos ordenados en C++ -
Utilice el algoritmo
std::set_unionpara fusionar el contenido de dos rangos ordenados en C++
Este artículo explicará cómo utilizar el algoritmo STL std::merge en C++.
Utilice el algoritmo std::merge para fusionar el contenido de dos rangos ordenados en C++
La función std::merge se proporciona bajo el encabezado de algoritmos STL - <algorithm>. Se puede utilizar para fusionar dos rangos que se han ordenado previamente. Los iteradores de rango deben satisfacer los requisitos de LegacyInputIterator.
En el siguiente código de ejemplo, creamos dos contenedores vectoriales con valores enteros aleatorios y los fusionamos en el tercer vector usando el algoritmo std::merge. Invocamos el algoritmo std::sort en los contenedores v1 y v2 antes de fusionar. Los enteros aleatorios se generan con funciones STL que es la forma recomendada para la aleatoriedad de alta calidad, y también utilizan el algoritmo std::generate con expresión lambda en lugar de un bucle regular para almacenar los valores en vectores.
#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;
}
Producción :
v1: 2, 2, 4, 9, 10,
v2: 0, 2, 4, 4, 9,
v3: 0, 2, 2, 2, 4, 4, 4, 9, 9, 10,
El código anterior inicializa un vector de destino con la suma de tamaños de vector para que pueda almacenar el contenido de v1 y v2. Alternativamente, podríamos usar std::back_inserter como el quinto parámetro del algoritmo para hacer crecer el vector dinámicamente. No hay diferencia funcional entre estos dos métodos cuando se usa el algoritmo std::merge, pero veremos que otros algoritmos similares pueden necesitar una versión específica.
#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,
Utilice el algoritmo std::set_union para fusionar el contenido de dos rangos ordenados en C++
El algoritmo std::merge construye un rango de salida que incluye exactamente std::distance(first1, last1) + std::distance(first2, last2) número de elementos. Aunque, el algoritmo std::set_union, que tiene una función similar, verifica si un elemento se encuentra en ambos rangos y, de ser así, todas las instancias de elementos se copian del primer rango, pero sólo las instancias std::max(n-m, 0) del segundo rango, donde m es el número de instancias del primer rango y n es el número de instancias del segundo.
El siguiente ejemplo demuestra el mismo fragmento de código con el algoritmo 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