如何将三元组作为unordered_set元素？有无替代检查方案？

一、正确实现unordered_set存储三元组 #

你原来的代码错误在于unordered_set只能存储单一类型的元素，不能直接声明为unordered_set<long, long, long>，且insert方法仅接受单个元素参数。要实现需求，需要将三个long包装成可哈希、可比较的类型，以下是两种常见实现方式：

1. 使用std::tuple作为元素类型 #

std::tuple<long, long, long>可以直接打包三个值，但标准库未为tuple提供默认哈希函数，需自定义哈希组合逻辑：

#include <unordered_set>
#include <tuple>
#include <functional>

// 自定义tuple的哈希函数
struct TupleHash {
    template <typename T1, typename T2, typename T3>
    size_t operator()(const std::tuple<T1, T2, T3>& t) const {
        auto h1 = std::hash<T1>{}(std::get<0>(t));
        auto h2 = std::hash<T2>{}(std::get<1>(t));
        auto h3 = std::hash<T3>{}(std::get<2>(t));
        // 组合哈希值（可根据需求调整方式，降低碰撞概率）
        return h1 ^ (h2 << 1) ^ (h3 << 2);
    }
};

int main() {
    // 定义unordered_set，指定tuple类型和自定义哈希
    std::unordered_set<std::tuple<long, long, long>, TupleHash> myset;
    
    // 插入三元组
    myset.insert(std::make_tuple(0, 1, 0));
    // 或使用C++11及以后的列表初始化
    myset.insert({1, 2, 3});
    
    // 检查组合是否存在
    if (myset.count(std::make_tuple(0, 1, 0))) {
        // 存在时的逻辑
    }
    return 0;
}

2. 自定义结构体存储三元组 #

如果需要更清晰的语义，可以自定义结构体，同时重载==运算符（用于unordered_set判断元素相等）并提供哈希函数：

#include <unordered_set>
#include <functional>

struct Triple {
    long a, b, c;
    
    // 必须重载==，用于元素相等性判断
    bool operator==(const Triple& other) const {
        return a == other.a && b == other.b && c == other.c;
    }
};

// 为Triple自定义哈希函数
struct TripleHash {
    size_t operator()(const Triple& t) const {
        auto h1 = std::hash<long>{}(t.a);
        auto h2 = std::hash<long>{}(t.b);
        auto h3 = std::hash<long>{}(t.c);
        return h1 ^ (h2 << 1) ^ (h3 << 2);
    }
};

int main() {
    std::unordered_set<Triple, TripleHash> myset;
    
    // 插入元素
    myset.insert({0, 1, 0});
    
    // 检查存在性
    if (myset.count({0, 1, 0})) {
        // 存在时的逻辑
    }
    return 0;
}

二、不使用unordered_set的替代方案 #

如果不想自定义哈希函数，以下几种方法更简便：

1. 使用std::set存储tuple #

std::set基于红黑树实现，不需要哈希函数，因为std::tuple默认重载了<运算符，可直接用于排序：

#include <set>
#include <tuple>

int main() {
    std::set<std::tuple<long, long, long>> myset;
    
    myset.insert({0, 1, 0});
    
    // 检查存在性
    if (myset.find({0, 1, 0}) != myset.end()) {
        // 存在时的逻辑
    }
    return 0;
}

注意：std::set的查找、插入时间复杂度为O(log n)，而unordered_set是平均O(1)，数据量较大时性能会有差异。

2. 将三元组编码为单一数值（数值范围允许时） #

如果三个long的取值范围有限，可以将它们编码成一个64位整数（如long long），直接用unordered_set<long long>存储：

#include <unordered_set>

// 编码函数，需确保每个值的范围不会导致溢出
long long encode(long a, long b, long c) {
    // 假设每个值不超过2^20，左移后不会溢出long long
    return (static_cast<long long>(a) << 40) | (static_cast<long long>(b) << 20) | c;
}

int main() {
    std::unordered_set<long long> myset;
    
    myset.insert(encode(0, 1, 0));
    
    if (myset.count(encode(0, 1, 0))) {
        // 存在时的逻辑
    }
    return 0;
}

这种方式无需自定义哈希，性能最优，但要严格控制数值范围，避免编码冲突或溢出。

3. 使用嵌套的无序容器 #

用unordered_map嵌套存储，结构更直观，无需自定义哈希：

#include <unordered_map>
#include <unordered_set>

int main() {
    std::unordered_map<long, std::unordered_map<long, std::unordered_set<long>>> mymap;
    
    // 插入三元组
    mymap[0][1].insert(0);
    
    // 检查存在性
    if (mymap.count(0) && mymap[0].count(1) && mymap[0][1].count(0)) {
        // 存在时的逻辑
    }
    return 0;
}

这种方式适合需要按前两个值查询第三个值集合的场景，但嵌套结构会增加一点内存开销。

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