C++ 合并操作

C++合并操作

介绍

合并操作是C++标准模板库（STL）算法中的一种常见操作，用于将两个已排序的序列合并成一个新的有序序列。合并操作在数据处理、算法设计和数据库操作中有着广泛的应用。C++提供了多种合并算法，包括std::merge、std::inplace_merge和std::set_union等。

合并操作的核心思想是：

• 输入两个已排序的序列。
• 输出一个包含两个输入序列所有元素的新序列，且新序列仍然保持有序。

合并算法

std::merge

std::merge是STL中最基础的合并算法，它将两个已排序的范围合并到一个新的范围中，并保持排序顺序。

语法

template< class InputIt1, class InputIt2, class OutputIt >
OutputIt merge( InputIt1 first1, InputIt1 last1,
               InputIt2 first2, InputIt2 last2,
               OutputIt d_first );

示例

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v1 = {1, 3, 5};
    std::vector<int> v2 = {2, 4, 6};
    std::vector<int> result(v1.size() + v2.size());

    std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());

    for (int num : result) {
        std::cout << num << " ";
    }
    // 输出：1 2 3 4 5 6
}

std::inplace_merge

std::inplace_merge用于合并同一个容器中两个连续的有序子范围，直接在原容器上操作，无需额外空间。

语法

template< class BidirIt >
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last );

示例

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 3, 5, 2, 4, 6};
    std::inplace_merge(v.begin(), v.begin() + 3, v.end());

    for (int num : v) {
        std::cout << num << " ";
    }
    // 输出：1 2 3 4 5 6
}

std::set_union

std::set_union用于合并两个已排序的范围，并去除重复元素。

语法

template< class InputIt1, class InputIt2, class OutputIt >
OutputIt set_union( InputIt1 first1, InputIt1 last1,
                   InputIt2 first2, InputIt2 last2,
                   OutputIt d_first );

示例

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v1 = {1, 2, 3};
    std::vector<int> v2 = {2, 3, 4};
    std::vector<int> result(v1.size() + v2.size());

    auto it = std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());
    result.resize(it - result.begin());

    for (int num : result) {
        std::cout << num << " ";
    }
    // 输出：1 2 3 4
}

合并操作的时间复杂度

合并操作的时间复杂度通常为$O(n+m)$，其中$n$和$m$分别是两个输入范围的大小。

实际应用案例

案例1：合并两个有序列表

假设有两个已排序的学生成绩列表，需要合并成一个大的有序列表。

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> classA = {65, 75, 85};
    std::vector<int> classB = {70, 80, 90};
    std::vector<int> allScores(classA.size() + classB.size());

    std::merge(classA.begin(), classA.end(), classB.begin(), classB.end(), allScores.begin());

    for (int score : allScores) {
        std::cout << score << " ";
    }
    // 输出：65 70 75 80 85 90
}

案例2：归并排序

合并操作是归并排序的核心步骤之一。

#include <algorithm>
#include <vector>
#include <iostream>

void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        std::inplace_merge(arr.begin() + left, arr.begin() + mid + 1, arr.begin() + right + 1);
    }
}

int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};
    mergeSort(arr, 0, arr.size() - 1);

    for (int num : arr) {
        std::cout << num << " ";
    }
    // 输出：5 6 7 11 12 13
}

合并操作的比较

以下是三种合并操作的比较：

算法	输入要求	输出	是否去重
std::merge	两个已排序的范围	合并后的有序范围	否
std::inplace_merge	同一容器中的两个连续有序子范围	原地合并后的有序范围	否
std::set_union	两个已排序的范围	合并后的有序范围（去重）	是

总结

合并操作是C++ STL中强大且灵活的工具，适用于多种场景。通过选择合适的合并算法，可以高效地处理有序数据。初学者应重点掌握std::merge和std::inplace_merge，而高级用户可以利用std::set_union等算法实现更复杂的功能。