编辑“︁C++ 合并操作”︁

= C++合并操作 =

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

合并操作的核心思想是：
* 输入两个已排序的序列。
* 输出一个包含两个输入序列所有元素的新序列，且新序列仍然保持有序。

== 合并算法 ==

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

==== 语法 ====
<syntaxhighlight lang="cpp">
template< class InputIt1, class InputIt2, class OutputIt >
OutputIt merge( InputIt1 first1, InputIt1 last1,
               InputIt2 first2, InputIt2 last2,
               OutputIt d_first );
</syntaxhighlight>

==== 示例 ====
<syntaxhighlight lang="cpp">
#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
}
</syntaxhighlight>

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

==== 语法 ====
<syntaxhighlight lang="cpp">
template< class BidirIt >
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last );
</syntaxhighlight>

==== 示例 ====
<syntaxhighlight lang="cpp">
#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
}
</syntaxhighlight>

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

==== 语法 ====
<syntaxhighlight lang="cpp">
template< class InputIt1, class InputIt2, class OutputIt >
OutputIt set_union( InputIt1 first1, InputIt1 last1,
                   InputIt2 first2, InputIt2 last2,
                   OutputIt d_first );
</syntaxhighlight>

==== 示例 ====
<syntaxhighlight lang="cpp">
#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
}
</syntaxhighlight>

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

== 实际应用案例 ==
=== 案例1：合并两个有序列表 ===
假设有两个已排序的学生成绩列表，需要合并成一个大的有序列表。

<syntaxhighlight lang="cpp">
#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
}
</syntaxhighlight>

=== 案例2：归并排序 ===
合并操作是归并排序的核心步骤之一。

<syntaxhighlight lang="cpp">
#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
}
</syntaxhighlight>

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

{| class="wikitable"
|-
! 算法 !! 输入要求 !! 输出 !! 是否去重
|-
| <code>std::merge</code> || 两个已排序的范围 || 合并后的有序范围 || 否
|-
| <code>std::inplace_merge</code> || 同一容器中的两个连续有序子范围 || 原地合并后的有序范围 || 否
|-
| <code>std::set_union</code> || 两个已排序的范围 || 合并后的有序范围（去重） || 是
|}

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

[[Category:编程语言]]
[[Category:C++]]
[[Category:C++stl 算法]]