O algoritmo std::merge em C++
-
Use o algoritmo
std::mergepara mesclar o conteúdo de dois intervalos classificados em C++ -
Use o algoritmo
std::set_unionpara mesclar o conteúdo de dois intervalos classificados em C++
Este artigo irá explicar como usar o algoritmo STL std::merge em C++.
Use o algoritmo std::merge para mesclar o conteúdo de dois intervalos classificados em C++
A função std::merge é fornecida sob o cabeçalho de algoritmos STL - <algorithm>. Ele pode ser utilizado para mesclar dois intervalos que foram classificados anteriormente. Os iteradores de intervalo devem satisfazer os requisitos LegacyInputIterator.
No código de exemplo a seguir, criamos dois contêineres vetor com valores inteiros aleatórios e os fundimos no terceiro vetor usando o algoritmo std::merge. Invocamos o algoritmo std::sort nos contêineres v1 e v2 antes da fusão. Inteiros aleatórios são gerados com recursos STL, que é a forma recomendada para aleatoriedade de alta qualidade, e também usam o algoritmo std::generate com expressão lambda em vez de um loop regular para armazenar os valores em vetores.
#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;
}
Produção:
v1: 2, 2, 4, 9, 10,
v2: 0, 2, 4, 4, 9,
v3: 0, 2, 2, 2, 4, 4, 4, 9, 9, 10,
O código anterior inicializa um vetor de destino com a soma dos tamanhos do vetor para que ele possa armazenar o conteúdo de v1 e v2. Alternativamente, poderíamos usar std::back_inserter como o quinto parâmetro do algoritmo para aumentar o vetor dinamicamente. Não há diferença funcional entre esses dois métodos quando o algoritmo std::merge é usado, mas veremos que outros algoritmos semelhantes podem precisar de uma versão 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,
Use o algoritmo std::set_union para mesclar o conteúdo de dois intervalos classificados em C++
std::merge constrói um intervalo de saída que inclui exatamente std::distance(first1, last1) + std::distance(first2, last2) número de elementos. Embora, o algoritmo std::set_union, que tem uma função semelhante, verifica se um elemento é encontrado em ambos os intervalos e, se for o caso, todas as instâncias do elemento são copiadas do primeiro intervalo, mas apenas std::max(n-m, 0) instâncias do segundo intervalo, onde m é o número de instâncias no primeiro intervalo e n é o número de instâncias no segundo.
O exemplo a seguir demonstra o mesmo fragmento de código com o 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