引言

C++ STL 提供了强大的集合相关算法，能够高效地处理有序序列的合并、交集、并集、差集等操作。本文将由浅入深，全面介绍以下七个集合算法：merge, inplace_merge, includes, set_union, set_intersection, set_difference, set_symmetric_difference。

1 merge

原理与适用场景

std::merge 用于将两个有序序列合并为一个新的有序序列。它不会去除重复元素。适用于需要将两个已排序的数组或容器合并为一个新序列的场景。

用法

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

// 合并两个有序数组
void MergeExample() {
  std::vector<int> v1 = {1, 3, 5, 7};
  std::vector<int> v2 = {2, 4, 6, 8};
  std::vector<int> result(v1.size() + v2.size());

  // 合并 v1 和 v2 到 result
  std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());

  std::cout << "Merged result: ";
  for (int n : result) std::cout << n << " ";
  std::cout << std::endl;
}

与其他方法对比

• 手动合并：需要遍历两个序列，写复杂的条件判断，效率和代码可读性都不如 std::merge。

• std::merge 仅适用于已排序序列，未排序时需先排序。

2 inplace_merge

原理与适用场景

std::inplace_merge 用于将一个容器中相邻的两段有序区间合并为一个有序区间，直接在原容器上操作，节省空间。适用于归并排序等需要原地合并的场景。

用法

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

// 原地合并
void InplaceMergeExample() {
  std::vector<int> v = {1, 3, 5, 2, 4, 6};
  // 前半部分 [1,3,5]，后半部分 [2,4,6] 都已排序
  std::inplace_merge(v.begin(), v.begin() + 3, v.end());

  std::cout << "Inplace merged: ";
  for (int n : v) std::cout << n << " ";
  std::cout << std::endl;
}

与其他方法对比

• 使用 std::merge 需要额外空间存储结果。

• inplace_merge 原地操作，但效率不一定高于 std::merge，尤其对于大数据量时。

3 includes

原理与适用场景

std::includes 判断一个有序序列是否完全包含另一个有序序列。适合权限、集合包含关系的判断。

用法

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

// 判断包含关系
void IncludesExample() {
  std::vector<int> v1 = {1, 2, 3, 4, 5};
  std::vector<int> v2 = {2, 3, 4};

  bool is_included = std::includes(v1.begin(), v1.end(), v2.begin(), v2.end());
  std::cout << "v1 includes v2? " << (is_included ? "Yes" : "No") << std::endl;
}

与其他方法对比

• 手动遍历判断易出错且效率低。

• 只适用于有序序列，未排序需先排序。

4 set_union

原理与适用场景

std::set_union 计算两个有序序列的并集，结果有序且不重复。适用于集合合并、标签整合等场景。

用法

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

// 并集运算
void SetUnionExample() {
  std::vector<int> v1 = {1, 2, 3, 4};
  std::vector<int> v2 = {3, 4, 5, 6};
  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());

  std::cout << "Set union: ";
  for (int n : result) std::cout << n << " ";
  std::cout << std::endl;
}

与其他方法对比

• 使用 std::set 或 std::unordered_set 也可求并集，但需额外空间，且顺序未必有序。

• set_union 只适用于已排序序列。

5 set_intersection

原理与适用场景

std::set_intersection 求两个有序序列的交集，结果有序且不重复。适用于共同元素筛选、标签交集等。

用法

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

// 交集运算
void SetIntersectionExample() {
  std::vector<int> v1 = {1, 2, 3, 4};
  std::vector<int> v2 = {3, 4, 5, 6};
  std::vector<int> result(std::min(v1.size(), v2.size()));

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

  std::cout << "Set intersection: ";
  for (int n : result) std::cout << n << " ";
  std::cout << std::endl;
}

与其他方法对比

• std::set 可用 std::set_intersection，但需转换容器。

• 手动遍历效率低且易错。

6 set_difference

原理与适用场景

std::set_difference 求两个有序序列的差集，即第一个序列中有但第二个序列中没有的元素。适用于权限剔除、集合去除等场景。

用法

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

// 差集运算
void SetDifferenceExample() {
  std::vector<int> v1 = {1, 2, 3, 4};
  std::vector<int> v2 = {3, 4, 5, 6};
  std::vector<int> result(v1.size());

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

  std::cout << "Set difference: ";
  for (int n : result) std::cout << n << " ";
  std::cout << std::endl;
}

与其他方法对比

• 手动遍历效率低。

• 使用 std::set 的 erase 方法也可实现，但不保证顺序。

7 set_symmetric_difference

原理与适用场景

std::set_symmetric_difference 求两个有序序列的对称差集，即只在其中一个序列中出现的元素。适用于差异分析、集合异同等场景。

用法

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

// 对称差集运算
void SetSymmetricDifferenceExample() {
  std::vector<int> v1 = {1, 2, 3, 4};
  std::vector<int> v2 = {3, 4, 5, 6};
  std::vector<int> result(v1.size() + v2.size());

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

  std::cout << "Set symmetric difference: ";
  for (int n : result) std::cout << n << " ";
  std::cout << std::endl;
}

与其他方法对比

• 手动遍历需多次判断，易出错。

• std::set 可用集合操作，但需转换容器。

8 总结与扩展

• 以上算法都要求输入序列有序，未排序时需先排序。

• 使用 STL 算法通常效率高，代码简洁，且避免了手动实现的繁琐和错误。

• 对于无序集合，可使用 std::unordered_set，但需注意顺序和效率问题。

• 这些算法支持自定义比较器，适用于自定义类型。

扩展：自定义比较器的使用

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

// 自定义比较器
struct MyCompare {
  bool operator()(const int& a, const int& b) const {
    return a > b;  // 降序
  }
};

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

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

  std::cout << "Merged with custom compare: ";
  for (int n : result) std::cout << n << " ";
  std::cout << std::endl;
}