std::unordered_set相等性问题：重叠区间为何能重复插入？

你的猜测完全正确：重叠区间能被同时插入，正是因为它们的哈希值不同，导致被放入哈希表的不同桶中，而std::unordered_set只会对同一桶内的元素执行相等性检查。

核心问题：哈希与相等性的一致性要求 #

std::unordered_set的底层设计有严格规则：如果两个元素被equal_to谓词判定为相等，它们的哈希值必须完全相同。你的实现直接违反了这个规则：

• [1,5]和[2,3]被判定为"相等"（因为重叠），但它们的哈希计算结果完全不同（1 + (5<<16) vs 2 + (3<<16)）。
• 哈希表会先根据哈希值将元素分配到不同桶，只有同一桶内的元素才会触发相等性检查。这两个区间不在同一桶，所以不会被比较，自然都能插入。

另外，你的"相等性"定义（重叠即相等）本身不满足等价关系的传递性：比如A=[1,2]、B=[1.5,2.5]、C=[2,3]，A和B重叠、B和C重叠，但A和C不重叠。这种非传递的关系也不符合std::unordered_set对equal_to的要求。

正确实现不相交区间集合的方案 #

方案1：使用std::set配合自定义排序规则

通过自定义比较器按区间端点排序，可高效定位可能重叠的区间：

#include <set>

struct IntervalCompare {
    // 按区间左端点升序排序，方便快速查找重叠区间
    bool operator()(const Interval& a, const Interval& b) const {
        return a.left < b.left;
    }
};

bool insertIfDisjoint(std::set<Interval, IntervalCompare>& s, const Interval& newInterval) {
    auto it = s.lower_bound(newInterval);
    // 检查前一个区间是否重叠
    if (it != s.begin()) {
        auto prevIt = std::prev(it);
        if (!prevIt->isDisjoint(newInterval)) {
            return false;
        }
    }
    // 检查当前区间是否重叠
    if (it != s.end() && !it->isDisjoint(newInterval)) {
        return false;
    }
    s.insert(newInterval);
    return true;
}

// 使用示例
std::set<Interval, IntervalCompare> disjointIntervals;
for (const auto& i : intervals) {
    insertIfDisjoint(disjointIntervals, i);
}

方案2：手动遍历检查（效率较低）

若坚持用哈希表，插入前需遍历整个集合检查所有元素是否重叠，无重叠再插入。但此方法每次插入的时间复杂度为O(n)，仅适合小规模数据。

额外代码优化建议 #

你的Interval结构体同时作为哈希函数和相等性谓词的模板参数，语法合法但可读性极差，建议拆分独立的仿函数：

struct IntervalHash {
    std::size_t operator()(const Interval& i) const {
        return static_cast<std::size_t>(i.left) + (static_cast<std::size_t>(i.right) << 16);
    }
};

struct IntervalEqual {
    bool operator()(const Interval& lhs, const Interval& rhs) const {
        return !lhs.isDisjoint(rhs);
    }
};

// 使用时
std::unordered_set<Interval, IntervalHash, IntervalEqual> disjointIntervals;

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