C++의 std::merge 알고리즘
이 기사에서는 C++에서 std::merge STL 알고리즘을 사용하는 방법을 설명합니다.
std::merge 알고리즘을 사용하여 C++에서 정렬된 두 범위의 내용 병합
std::merge 기능은 STL 알고리즘 헤더 <algorithm> 아래에 제공됩니다. 이전에 정렬된 두 범위를 병합하는 데 사용할 수 있습니다. 범위 반복기는 LegacyInputIterator 요구 사항을 충족해야 합니다.
다음 예제 코드에서는 임의의 정수 값으로 두 개의 vector 컨테이너를 만들고 std::merge 알고리즘을 사용하여 세 번째 벡터로 병합합니다. 병합하기 전에 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의 내용을 저장할 수 있도록 벡터 크기의 합으로 대상 벡터를 초기화합니다. 또는 std::back_inserter를 알고리즘의 다섯 번째 매개변수로 사용하여 벡터를 동적으로 증가시킬 수 있습니다. std::merge 알고리즘을 사용할 때 이 두 방법 사이에는 기능적 차이가 없지만 다른 유사한 알고리즘에는 특정 버전이 필요할 수 있습니다.
#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,
std::set_union 알고리즘을 사용하여 C++에서 정렬된 두 범위의 내용 병합
std::merge는 정확히 std::distance(first1, last1) + std::distance(first2, last2) 요소 수를 포함하는 출력 범위를 구성합니다. 유사한 기능을 가진 std::set_union 알고리즘은 두 범위 모두에서 요소가 발견되는지 확인하고 발견되면 모든 요소 인스턴스가 첫 번째 범위에서 복사되지만 std::max(n-m, 0) 두 번째 범위의 인스턴스. 여기서 m은 첫 번째 범위의 인스턴스 수이고 n은 두 번째 범위의 인스턴스 수입니다.
다음 예제는 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