C++ STL 中常见集合算法 - 交集、并集、差集

1. 集合概述

在STL中，常用的集合类包括 std::set、std::vector、std::unordered_set 等。以 std::set 为例进行这些算法的讲解。

2. 交集（Intersection）

定义： 交集是指两个集合中共同存在的元素的集合。

算法： 使用 std::set_intersection 函数实现。

std::set<int> set1 = {1, 2, 3, 4, 5};
std::set<int> set2 = {3, 4, 5, 6, 7};

std::set<int> intersect;
std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), std::inserter(intersect, intersect.begin()));

// 输出交集
for (const auto& element : intersect) {
    std::cout << element << " ";
}

3. 并集（Union）

定义： 并集包含两个集合中的所有唯一元素。

算法： 使用 std::set_union 函数实现。

std::set<int> set1 = {1, 2, 3, 4, 5};
std::set<int> set2 = {3, 4, 5, 6, 7};

std::set<int> united;
std::set_union(set1.begin(), set1.end(), set2.begin(), set2.end(), std::inserter(united, united.begin()));

// 输出并集
for (const auto& element : united) {
    std::cout << element << " ";
}

4. 差集（Difference）

定义： 差集是指只存在于第一个集合而不在第二个集合中的元素的集合。

算法： 使用 std::set_difference 函数实现。

std::set<int> set1 = {1, 2, 3, 4, 5};
std::set<int> set2 = {3, 4, 5, 6, 7};

std::set<int> difference;
std::set_difference(set1.begin(), set1.end(), set2.begin(), set2.end(), std::inserter(difference, difference.begin()));

// 输出差集
for (const auto& element : difference) {
    std::cout << element << " ";
}