C++20中unordered_set的差集、交集、并集库方法查询

我之前见过类似问题，但大多比较老旧可能已过时。现在是2023年，最新C标准是2020年发布的C20，不同标准差异不小。想请教：通过#include <unordered_set>引入的std::unordered_set在C++20里有没有内置的差集、交集、并集计算方法？

我知道Python里集合可以用a&b求交集、a-b求差集、a^b求对称差集、a|b求并集，C++里有没有比手动循环更高效的类似实现？我听说过set_union、set_difference和set_intersection这些方法，但不清楚它们能不能用在unordered_set上。我自己也会用暴力循环实现这些操作，代码和输出示例如下：

#include <iostream>
#include <unordered_set>

using intSet = std::unordered_set<int>;

void print_set(const intSet& set) {
    std::cout << "{";
    for (int i : set) {
        std::cout << i << ", ";
    }
    std::cout << "}\n";
}

int main()
{
    intSet a = { 16, 1, 14, 7, 18, 5, 12, 19 };
    intSet b = { 0, 9, 1, 8, 19, 2, 18, 13 };
    intSet intersection_set;
    intSet diff_set;
    intSet union_set;
    for (int i : a) {
        if (b.count(i)) {
            intersection_set.insert(i);
        } else {
            diff_set.insert(i);
        }
        union_set.insert(i);
    }
    for (int i : b) {
        union_set.insert(i);
    }
    std::cout << "a = ";
    print_set(a);
    std::cout << "b = ";
    print_set(b);
    std::cout << "a & b = ";
    print_set(intersection_set);
    std::cout << "a - b = ";
    print_set(diff_set);
    std::cout << "a | b = ";
    print_set(union_set);
}

输出：

a = {16, 1, 14, 7, 18, 5, 12, 19, }
b = {8, 0, 1, 9, 19, 18, 2, 13, }
a & b = {1, 18, 19, }
a - b = {16, 14, 7, 5, 12, }
a | b = {16, 1, 14, 7, 18, 5, 12, 19, 8, 0, 9, 2, 13, }

核心结论 #

C++20及之前的标准中，std::unordered_set没有内置的直接计算交集、差集、并集的成员方法，也不能直接用set_union、set_difference、set_intersection这些算法——因为这些算法要求输入序列是有序的，而unordered_set是哈希表实现，内部元素无序。

更高效的实现方案 #

虽然没有内置方法，但可以基于unordered_set的O(1)查找特性，写出比暴力遍历更高效的实现：

• 交集：遍历较小的集合，检查每个元素是否存在于另一个集合中，存在则加入结果。这样能减少遍历次数，比固定遍历其中一个集合更高效。
• 差集（a - b）：遍历集合a，检查元素是否不在b中，不在则加入结果。
• 并集：直接将两个集合的元素全部插入新集合即可（unordered_set会自动去重），可以简化为直接构造。
• 对称差集：遍历两个集合，只保留在其中一个集合中存在但不同时存在的元素。

优化后的示例代码 #

#include <iostream>
#include <unordered_set>

using intSet = std::unordered_set<int>;

void print_set(const intSet& set) {
    std::cout << "{";
    bool first = true;
    for (int i : set) {
        if (!first) std::cout << ", ";
        std::cout << i;
        first = false;
    }
    std::cout << "}\n";
}

// 计算交集
intSet get_intersection(const intSet& a, const intSet& b) {
    intSet result;
    // 遍历更小的集合减少迭代次数
    const auto& smaller = a.size() <= b.size() ? a : b;
    const auto& larger = a.size() > b.size() ? a : b;
    for (int num : smaller) {
        if (larger.contains(num)) { // C++20新增的contains，比count更直观
            result.insert(num);
        }
    }
    return result;
}

// 计算差集 a - b
intSet get_difference(const intSet& a, const intSet& b) {
    intSet result;
    for (int num : a) {
        if (!b.contains(num)) {
            result.insert(num);
        }
    }
    return result;
}

// 计算对称差集
intSet get_symmetric_difference(const intSet& a, const intSet& b) {
    intSet result;
    for (int num : a) {
        if (!b.contains(num)) result.insert(num);
    }
    for (int num : b) {
        if (!a.contains(num)) result.insert(num);
    }
    return result;
}

// 计算并集
intSet get_union(const intSet& a, const intSet& b) {
    intSet result(a.begin(), a.end());
    result.insert(b.begin(), b.end());
    return result;
}

int main()
{
    intSet a = { 16, 1, 14, 7, 18, 5, 12, 19 };
    intSet b = { 0, 9, 1, 8, 19, 2, 18, 13 };
    
    std::cout << "a = ";
    print_set(a);
    std::cout << "b = ";
    print_set(b);
    
    std::cout << "a & b = ";
    print_set(get_intersection(a, b));
    std::cout << "a - b = ";
    print_set(get_difference(a, b));
    std::cout << "a | b = ";
    print_set(get_union(a, b));
    std::cout << "a ^ b = ";
    print_set(get_symmetric_difference(a, b));
}

输出结果 #

a = {16, 1, 14, 7, 18, 5, 12, 19}
b = {8, 0, 1, 9, 19, 18, 2, 13}
a & b = {1, 18, 19}
a - b = {16, 14, 7, 5, 12}
a | b = {16, 1, 14, 7, 18, 5, 12, 19, 8, 0, 9, 2, 13}
a ^ b = {16, 14, 7, 5, 12, 8, 0, 9, 2, 13}

关于set_union等算法的说明 #

std::set_union、std::set_difference、std::set_intersection这些属于有序序列专属算法，要求输入的两个范围必须是已排序的（比如std::set的元素是严格有序的），它们通过双指针遍历实现O(n+m)的时间复杂度。但unordered_set的元素是哈希散列后的无序状态，直接使用这些算法会得到错误结果，因为算法的逻辑完全依赖元素的有序性来正确合并或筛选。

内容的提问来源于stack exchange，提问作者Ξένη Γήινος