C++ 中的 std::merge 演算法

Jinku Hu 2023年1月30日 2021年10月2日
  1. 在 C++ 中使用 std::merge 演算法合併兩個排序範圍的內容
  2. 在 C++ 中使用 std::set_union 演算法合併兩個排序範圍的內容
C++ 中的 std::merge 演算法

本文將解釋如何在 C++ 中使用 std::merge STL 演算法。

在 C++ 中使用 std::merge 演算法合併兩個排序範圍的內容

std::merge 函式在 STL 演算法標題 - <algorithm> 下提供。它可用於合併先前已排序的兩個範圍。範圍迭代器應滿足 LegacyInputIterator 要求。

在下面的示例程式碼中,我們建立了兩個帶有隨機整數值的 vector 容器,並使用 std::merge 演算法將它們合併到第三個向量中。我們在合併之前在 v1v2 容器上呼叫 std::sort 演算法。隨機整數是使用 STL 工具生成的,這是高質量隨機性的推薦方式,並且還使用帶有 lambda 表示式的 std::generate 演算法而不是常規迴圈將值儲存到向量中。

#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> 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 <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> 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,

在 C++ 中使用 std::set_union 演算法合併兩個排序範圍的內容

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,
Author: 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

相關文章 - C++ Algorithm