跳到主要内容

C++ 集合操作

STL（标准模板库）提供了一系列强大的算法，可以对有序和无序容器执行集合操作。在数学中，集合是一组不同元素的集合，而在编程中，我们可以使用容器（如vector、set等）来表示集合，并使用STL算法来执行集合操作。

什么是集合操作？​

集合操作是指对两个或多个集合执行的操作，如并集、交集、差集和对称差集。在C++中，我们可以使用STL算法来实现这些操作：

  1. 并集（Union）：包含出现在任一集合中的所有元素
  2. 交集（Intersection）：只包含同时出现在两个集合中的元素
  3. 差集（Difference）：包含在第一个集合中但不在第二个集合中的元素
  4. 对称差集（Symmetric Difference）：包含只出现在其中一个集合中的元素

前提条件​

要使用STL集合操作，需要满足以下条件：

  1. 输入序列必须是有序的（按升序排列）
  2. 输出序列有足够的空间来容纳结果

主要STL集合操作算法​

1. set_union - 并集操作​

set_union 算法创建一个新的集合，包含在两个输入集合中出现的所有元素。如果一个元素在两个集合中都出现，在结果集合中只出现一次。

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {3, 4, 5, 6, 7};
    std::vector<int> result;
    
    // 确保有足够空间
    result.resize(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 << "并集: ";
    for(int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

输出：

并集: 1 2 3 4 5 6 7

2. set_intersection - 交集操作​

set_intersection 算法创建一个新的集合，只包含同时在两个输入集合中出现的元素。

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {3, 4, 5, 6, 7};
    std::vector<int> result;
    
    // 交集最大的可能大小是两个输入集合中最小的那个
    result.resize(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 << "交集: ";
    for(int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

输出：

交集: 3 4 5

3. set_difference - 差集操作​

set_difference 算法创建一个新的集合，包含在第一个集合中但不在第二个集合中的元素。

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {3, 4, 5, 6, 7};
    std::vector<int> result;
    
    // 差集最大可能大小是第一个集合的大小
    result.resize(v1.size());
    
    // 执行差集操作 (v1 - v2)
    auto it = std::set_difference(v1.begin(), v1.end(),
                                 v2.begin(), v2.end(),
                                 result.begin());
    
    result.resize(it - result.begin());
    
    std::cout << "差集 (v1 - v2): ";
    for(int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

输出：

差集 (v1 - v2): 1 2

4. set_symmetric_difference - 对称差集操作​

set_symmetric_difference 算法创建一个新的集合，包含只出现在其中一个输入集合中的元素，不包括同时出现在两个集合中的元素。

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {3, 4, 5, 6, 7};
    std::vector<int> result;
    
    // 对称差集最大可能大小是两个集合大小之和
    result.resize(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 << "对称差集: ";
    for(int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

输出：

对称差集: 1 2 6 7

使用 std::set 容器进行集合操作​

上面的例子使用了 vector，但 set 容器更适合表示数学意义上的集合，因为它自动排序并去除重复元素。下面是使用 set 容器的例子：

cpp
#include <iostream>
#include <set>
#include <algorithm>
#include <iterator>

int main() {
    std::set<int> s1 = {1, 2, 3, 4, 5};
    std::set<int> s2 = {3, 4, 5, 6, 7};
    std::set<int> result;
    
    // 并集
    std::set_union(s1.begin(), s1.end(),
                   s2.begin(), s2.end(),
                   std::inserter(result, result.begin()));
    
    std::cout << "并集: ";
    for(int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // 清空结果集合
    result.clear();
    
    // 交集
    std::set_intersection(s1.begin(), s1.end(),
                          s2.begin(), s2.end(),
                          std::inserter(result, result.begin()));
    
    std::cout << "交集: ";
    for(int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

输出：

并集: 1 2 3 4 5 6 7
交集: 3 4 5
提示

std::inserter 是一个函数，它创建一个插入迭代器，可以将元素插入到容器中。这对于像 set 这样不支持使用索引直接访问的容器特别有用。

实际应用案例​

案例1：查找共同好友​

假设我们有两个用户的好友列表，我们想找出他们的共同好友。

cpp
#include <iostream>
#include <set>
#include <string>
#include <algorithm>
#include <iterator>

int main() {
    // 用户1的好友列表
    std::set<std::string> friends1 = {"Alice", "Bob", "Charlie", "David", "Eve"};
    
    // 用户2的好友列表
    std::set<std::string> friends2 = {"Bob", "David", "Frank", "Grace", "Helen"};
    
    // 存储共同好友
    std::set<std::string> commonFriends;
    
    // 找出共同好友（交集）
    std::set_intersection(friends1.begin(), friends1.end(),
                         friends2.begin(), friends2.end(),
                         std::inserter(commonFriends, commonFriends.begin()));
    
    std::cout << "共同好友: ";
    for(const auto& friend_name : commonFriends) {
        std::cout << friend_name << " ";
    }
    std::cout << std::endl;
    
    // 找出用户1独有的好友（差集）
    std::set<std::string> uniqueFriends1;
    std::set_difference(friends1.begin(), friends1.end(),
                        friends2.begin(), friends2.end(),
                        std::inserter(uniqueFriends1, uniqueFriends1.begin()));
    
    std::cout << "用户1独有的好友: ";
    for(const auto& friend_name : uniqueFriends1) {
        std::cout << friend_name << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

输出：

共同好友: Bob David 
用户1独有的好友: Alice Charlie Eve

案例2：检查课程先修要求​

假设我们有已修课程列表和某课程的先修要求，需要检查是否满足所有先修要求。

cpp
#include <iostream>
#include <set>
#include <string>
#include <algorithm>

bool canTakeCourse(const std::set<std::string>& completedCourses,
                  const std::set<std::string>& prerequisites) {
    // 检查所有先修课程是否都已完成
    std::set<std::string> missingPrerequisites;
    
    std::set_difference(prerequisites.begin(), prerequisites.end(),
                       completedCourses.begin(), completedCourses.end(),
                       std::inserter(missingPrerequisites, missingPrerequisites.begin()));
    
    // 如果没有缺少的先修课程，则可以学习该课程
    return missingPrerequisites.empty();
}

int main() {
    std::set<std::string> completedCourses = {
        "CS101", "CS102", "MATH101", "PHYS101"
    };
    
    std::set<std::string> advancedAlgorithmPrereqs = {
        "CS101", "CS102", "MATH101"
    };
    
    std::set<std::string> quantumComputingPrereqs = {
        "CS102", "PHYS101", "MATH201"
    };
    
    if(canTakeCourse(completedCourses, advancedAlgorithmPrereqs)) {
        std::cout << "你可以学习高级算法课程！" << std::endl;
    } else {
        std::cout << "你还不能学习高级算法课程。" << std::endl;
    }
    
    if(canTakeCourse(completedCourses, quantumComputingPrereqs)) {
        std::cout << "你可以学习量子计算课程！" << std::endl;
    } else {
        std::cout << "你还不能学习量子计算课程。" << std::endl;
    }
    
    return 0;
}

输出：

你可以学习高级算法课程！
你还不能学习量子计算课程。

多重集合操作​

有时我们需要处理允许重复元素的集合。对于这种情况，可以使用 multiset 容器或者算法的多重集合版本（如果存在的话）。不过，标准的集合算法在处理有序的重复元素时也能正常工作。

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

int main() {
    std::vector<int> v1 = {1, 2, 2, 3, 4, 5};
    std::vector<int> v2 = {2, 2, 3, 3, 4, 6};
    std::vector<int> result;
    
    // 为结果分配足够的空间
    result.resize(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 << "多重并集: ";
    for(int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // 清空结果，为交集做准备
    result.clear();
    result.resize(std::min(v1.size(), v2.size()));
    
    // 执行交集操作
    it = std::set_intersection(v1.begin(), v1.end(),
                              v2.begin(), v2.end(),
                              result.begin());
    
    result.resize(it - result.begin());
    
    std::cout << "多重交集: ";
    for(int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

输出：

多重并集: 1 2 2 3 3 4 5 6 
多重交集: 2 2 3 4
备注

对于多重集合操作，输出结果中元素出现的次数取决于它在输入序列中出现的次数：

  • 对于并集，元素的出现次数是它在两个输入序列中出现次数的最大值
  • 对于交集，元素的出现次数是它在两个输入序列中出现次数的最小值

性能考虑​

STL集合操作算法的时间复杂度为 O(n)，其中 n 是两个输入序列的长度之和。这是因为这些算法只需要线性扫描输入序列一次。

对于大型集合，使用 set 容器可能比 vector 更高效，尤其是在需要频繁插入和移除元素时。然而，对于小型集合或者只需要读取元素的情况，vector 可能更高效，因为它没有红黑树的开销。

总结​

C++的STL提供了强大的集合操作算法，可以轻松地实现各种集合操作：

  1. set_union - 计算两个集合的并集
  2. set_intersection - 计算两个集合的交集
  3. set_difference - 计算两个集合的差集
  4. set_symmetric_difference - 计算两个集合的对称差集

这些算法要求输入序列是有序的，输出目标有足够的空间来存储结果。使用 std::set 容器时，通常需要结合 std::inserter 来插入结果元素。

集合操作在许多实际应用中非常有用，如查找共同好友、检查条件满足情况、数据比较和分析等。掌握这些操作可以让你更高效地解决与集合相关的问题。

练习​

  1. 编写一个程序，找出三个集合的公共元素。
  2. 实现一个函数，接受两个字符串，找出只在第一个字符串中出现的字符。
  3. 编写一个程序，模拟图书馆新书和旧书的比较，找出新增的书籍和被移除的书籍。
  4. 实现一个函数，接受两个集合，返回它们的对称差集除以它们的并集的比例（衡量两个集合的不同程度）。
  5. 用集合操作实现对两个数组去重后的元素合并。
提示

别忘了利用 STL 中的其他算法（如 std::sort）来保证输入序列是有序的，这是使用集合操作算法的前提条件。