如何优化C++中排序规则不同的std::set交集算法？

我完全懂你的困扰——当两个std::set用了不同的排序比较器时，std::set_intersection直接就用不了（它要求输入序列必须按相同规则排序），而作业又卡着时间复杂度要求。下面是实现O(n log m)复杂度的具体方案，分两种常见场景说明：

核心思路 #

我们的核心逻辑是「遍历其中一个集合（大小为n），对每个元素在另一个集合（大小为m）里做O(log m)的查找」，这样总时间复杂度刚好是O(n log m)。关键在于怎么让第二个集合的查找高效匹配到目标元素。

场景1：查找同一对象指针（两个set存的是指向同一个实例的指针） #

如果你的需求是找出同时存在于两个set中的相同指针（指向同一个复杂对象），可以直接这么写：

1. 遍历第一个set的每一个指针元素
2. 用std::set的成员函数find在第二个set里查找该指针。哪怕第二个set的比较器是基于对象字段排序的，find也会通过比较器的等价规则（!comp(a,b) && !comp(b,a)）匹配元素——只要你的比较器是严格弱序，且等价条件包含对象的唯一性（比如对象的唯一ID），就能正确定位到目标。

#include <set>
#include <vector>

// 示例复杂对象
struct ComplexObj {
    int unique_id;
    double sort_key_a;
    double sort_key_b;
};

// 第一个set的比较器：按sort_key_a排序
struct CompareByKeyA {
    bool operator()(const ComplexObj* a, const ComplexObj* b) const {
        return a->sort_key_a < b->sort_key_a;
    }
};

// 第二个set的比较器：按sort_key_b排序
struct CompareByKeyB {
    bool operator()(const ComplexObj* a, const ComplexObj* b) const {
        return a->sort_key_b < b->sort_key_b;
    }
};

std::vector<const ComplexObj*> findCommonElements(
    const std::set<ComplexObj*, CompareByKeyA>& setA,
    const std::set<ComplexObj*, CompareByKeyB>& setB
) {
    std::vector<const ComplexObj*> result;
    result.reserve(setA.size()); // 预分配空间优化性能

    for (const ComplexObj* obj : setA) {
        // 在setB中查找当前指针对应的元素
        auto it = setB.find(obj);
        if (it != setB.end()) {
            result.push_back(obj);
        }
    }

    return result;
}

这个实现的时间复杂度就是O(n log m)：遍历setA的n个元素，每个find操作是红黑树的O(log m)复杂度，完全符合要求。

场景2：查找逻辑等价的对象（比如对象的unique_id相同） #

如果你的需求是找出两个set中逻辑等价的对象（比如unique_id相同，不管指针是不是指向同一个实例），需要调整查找逻辑，让第二个set的比较器能配合定位目标：

1. 遍历第一个set的每个对象，取出唯一标识（比如unique_id）
2. 创建一个临时对象，只填充唯一标识和满足第二个set比较器的必要字段
3. 用setB.find()查找这个临时对象的指针，匹配逻辑等价的元素

#include <set>
#include <vector>

struct ComplexObj {
    int unique_id;
    double sort_key_a;
    double sort_key_b;
};

struct CompareByKeyA {
    bool operator()(const ComplexObj* a, const ComplexObj* b) const {
        return a->sort_key_a < b->sort_key_a;
    }
};

struct CompareByKeyB {
    bool operator()(const ComplexObj* a, const ComplexObj* b) const {
        return a->sort_key_b < b->sort_key_b;
    }
};

// 辅助函数：创建用于查找的临时对象
ComplexObj* createTempObj(int target_id, double key_b) {
    return new ComplexObj{target_id, 0.0, key_b};
}

std::vector<const ComplexObj*> findCommonElementsByID(
    const std::set<ComplexObj*, CompareByKeyA>& setA,
    const std::set<ComplexObj*, CompareByKeyB>& setB
) {
    std::vector<const ComplexObj*> result;
    result.reserve(setA.size());

    for (const ComplexObj* obj : setA) {
        // 创建临时对象，仅设置unique_id和setB比较器需要的字段
        ComplexObj* temp = createTempObj(obj->unique_id, obj->sort_key_b);
        auto it = setB.find(temp);
        delete temp; // 记得释放临时对象内存

        if (it != setB.end()) {
            result.push_back(*it);
        }
    }

    return result;
}

这个实现的时间复杂度同样是O(n log m)，每个find操作保持O(log m)的效率。

额外优化建议 #

如果n远大于m，建议反过来遍历setB（大小m），在setA中做O(log n)的查找，总复杂度O(m log n)会更优——毕竟选更小的集合当遍历源，能减少总操作次数。

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