如何计算vector<set<string>>容器中所有集合的交集？

要实现所有集合的交集，核心逻辑是从第一个集合出发，逐步与后续每个集合求交集，不断缩小结果范围。利用STL的set_intersection算法就能高效完成——因为set本身是有序容器，刚好符合该算法对输入区间的有序要求。

完整实现代码 #

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

using namespace std;

set<string> computeAllIntersections(const vector<set<string>>& sets) {
    // 处理空容器的情况
    if (sets.empty()) {
        return {};
    }

    // 初始化交集为第一个集合
    set<string> result = sets[0];

    // 遍历后续所有集合
    for (size_t i = 1; i < sets.size(); ++i) {
        set<string> temp;
        // 计算当前结果与下一个集合的交集
        set_intersection(
            result.begin(), result.end(),
            sets[i].begin(), sets[i].end(),
            inserter(temp, temp.begin())
        );
        // 更新结果为新的交集
        result.swap(temp);

        // 提前终止：如果交集已经为空，无需继续计算
        if (result.empty()) {
            break;
        }
    }

    return result;
}

int main() {
    // 输入部分（你已实现的逻辑）
    int studentCount;
    cout << "请输入学生数量：";
    cin >> studentCount;

    vector<set<string>> studentCourses;
    for (int i = 0; i < studentCount; ++i) {
        int courseNum;
        cout << "请输入第" << i+1 << "个学生的选课数：";
        cin >> courseNum;

        set<string> courses;
        for (int j = 0; j < courseNum; ++j) {
            string courseName;
            cout << "请输入课程名称：";
            cin >> courseName;
            courses.insert(courseName);
        }
        studentCourses.push_back(courses);
    }

    // 计算所有学生都选了的课程（交集）
    set<string> commonCourses = computeAllIntersections(studentCourses);

    // 输出结果
    cout << "所有学生共同选择的课程：" << endl;
    for (const string& course : commonCourses) {
        cout << course << endl;
    }

    return 0;
}

关键说明 #

• set_intersection的用法：该算法会遍历两个有序区间，把同时存在的元素复制到目标区间。这里用inserter将结果插入临时set，保证元素自动排序且去重。
• 提前终止优化：一旦交集变为空，后续计算不会改变结果，可以直接跳出循环，提升效率。
• 边界情况处理：如果输入的vector为空，直接返回空集合；如果只有一个学生，那他的所有课程就是交集。

内容的提问来源于stack exchange，提问作者momen ehab