面试题：C++ set 交集并集操作在复杂场景下的应用

Question

假设你正在开发一个系统，其中有多个`std::set`，每个`set`代表不同用户的兴趣标签集合。现在需要找出所有用户都有的兴趣标签（交集），以及所有用户兴趣标签的总和（并集）。请设计一个通用的C++ 类来处理这种情况，该类需要提供方法来添加用户兴趣标签集合，获取所有用户兴趣标签的交集和并集。要求代码具有良好的扩展性和可读性，同时说明如何处理可能出现的性能问题。

Answer 1

#include <iostream>
#include <set>
#include <vector>

class InterestTags {
private:
    std::vector<std::set<std::string>> userInterestSets;

public:
    void addUserInterestSet(const std::set<std::string>& set) {
        userInterestSets.push_back(set);
    }

    std::set<std::string> getIntersection() const {
        if (userInterestSets.empty()) {
            return std::set<std::string>();
        }
        std::set<std::string> intersection = userInterestSets[0];
        for (size_t i = 1; i < userInterestSets.size(); ++i) {
            std::set<std::string> temp;
            std::set_intersection(intersection.begin(), intersection.end(),
                                  userInterestSets[i].begin(), userInterestSets[i].end(),
                                  std::inserter(temp, temp.begin()));
            intersection = temp;
        }
        return intersection;
    }

    std::set<std::string> getUnion() const {
        std::set<std::string> unionSet;
        for (const auto& set : userInterestSets) {
            unionSet.insert(set.begin(), set.end());
        }
        return unionSet;
    }
};

性能问题处理

1. 交集计算：当前使用std::set_intersection进行交集计算，时间复杂度为$O(n log n)$，其中$n$是集合中元素的总数。如果用户集合数量非常大，可以考虑使用更高效的数据结构，如std::unordered_set（前提是标签类型支持哈希），其平均时间复杂度为$O(n)$。
2. 并集计算：当前实现通过依次插入每个集合的元素到结果集中，时间复杂度为$O(n log n)$，其中$n$是集合中元素的总数。如果元素数量非常大，同样可以考虑使用std::unordered_set，平均时间复杂度可以优化到$O(n)$。
3. 空间复杂度：当前代码存储了每个用户的兴趣标签集合，如果用户数量和标签数量非常大，空间消耗可能成为问题。可以考虑使用更紧凑的数据结构或进行数据压缩。