C++의 std::merge 알고리즘

Jinku Hu 2023년10월12일
  1. std::merge 알고리즘을 사용하여 C++에서 정렬된 두 범위의 내용 병합
  2. std::set_union 알고리즘을 사용하여 C++에서 정렬된 두 범위의 내용 병합
C++의 std::merge 알고리즘

이 기사에서는 C++에서 std::merge STL 알고리즘을 사용하는 방법을 설명합니다.

std::merge 알고리즘을 사용하여 C++에서 정렬된 두 범위의 내용 병합

std::merge 기능은 STL 알고리즘 헤더 <algorithm> 아래에 제공됩니다. 이전에 정렬된 두 범위를 병합하는 데 사용할 수 있습니다. 범위 반복기는 LegacyInputIterator 요구 사항을 충족해야 합니다.

다음 예제 코드에서는 임의의 정수 값으로 두 개의 vector 컨테이너를 만들고 std::merge 알고리즘을 사용하여 세 번째 벡터로 병합합니다. 병합하기 전에 v1v2 컨테이너에서 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,

이전 코드는 v1v2의 내용을 저장할 수 있도록 벡터 크기의 합으로 대상 벡터를 초기화합니다. 또는 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,
작가: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

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

관련 문장 - C++ Algorithm