如何无额外拷贝查询键为std::tuple<A,A>的std::unordered_map并保持O(1)平均复杂度？

这个问题问到点子上了！你已经敏锐地发现了std::unordered_map在处理带引用的键时的尴尬——operator[]的签名要求键必须是std::tuple<A,A>的实例，而std::tie返回的引用型tuple会被隐式转换成值型tuple，到头来还是免不了拷贝A。下面给你几个靠谱的解决方案，既能彻底避免不必要的拷贝，又能保住unordered_map平均O(1)的查找效率：

方案一：用C++20异构查找（最优解） #

C++20给std::unordered_map的find方法增加了异构查找支持，只要你的哈希函数和相等比较器是“透明”的（即能处理与键类型不同但可比较的类型），就能直接用std::tie(a1, a2)查找，完全不用构造std::tuple<A,A>临时对象，自然也就不会拷贝A。

步骤1：定义透明的哈希和相等比较器 #

// 透明哈希：支持对各种tuple类型计算哈希
struct TransparentTupleHash {
    // 基础版本：处理值型tuple
    template <typename T>
    size_t operator()(const T& t) const noexcept {
        using HashT1 = std::hash<std::decay_t<decltype(std::get<0>(t))>>;
        using HashT2 = std::hash<std::decay_t<decltype(std::get<1>(t))>>;
        return HashT1{}(std::get<0>(t)) ^ (HashT2{}(std::get<1>(t)) << 1);
    }

    // 重载：支持引用型tuple（比如std::tie返回的类型）
    template <typename T1, typename T2>
    size_t operator()(const std::tuple<T1&, T2&>& t) const noexcept {
        return operator()(std::make_pair(std::get<0>(t), std::get<1>(t)));
    }
};

// 透明相等比较：支持不同类型tuple的内容比较
struct TransparentTupleEqual {
    template <typename TupleLhs, typename TupleRhs>
    bool operator()(const TupleLhs& lhs, const TupleRhs& rhs) const noexcept {
        return std::get<0>(lhs) == std::get<0>(rhs) && std::get<1>(lhs) == std::get<1>(rhs);
    }
};

步骤2：声明支持透明查找的unordered_map #

std::unordered_map<
    std::tuple<A, A>, 
    B, 
    TransparentTupleHash, 
    TransparentTupleEqual
> my_map;

步骤3：用find替代operator[]进行查找 #

void modify(const A& a1, const A& a2) {
    auto it = my_map.find(std::tie(a1, a2));
    if (it != my_map.end()) {
        it->second.modify(); // 找到元素，直接修改
    } else {
        // 如果需要插入新元素，用emplace避免临时tuple拷贝
        my_map.emplace(
            std::piecewise_construct,
            std::forward_as_tuple(a1, a2), // 若A支持移动可替换为std::move(a1)/std::move(a2)
            std::forward_as_tuple()        // 构造默认初始化的B
        );
        // 不需要自动插入的话，这里可以添加错误处理逻辑
    }
}

这个方案的核心是：find不再强制要求参数必须是键类型的实例，只要哈希和比较器能处理传入的引用型tuple，就可以直接操作原始的a1、a2，完全没有拷贝。

方案二：C++17及以下的兼容方案 #

如果你的项目还不能升级到C++20，也可以手动实现类似逻辑——跳过operator[]，直接用find配合能处理引用的哈希/比较器。

思路和上面一致，重点是让哈希函数支持std::tuple<const A&, const A&>类型。调用find时，传入std::tie(a1,a2)即可，这个临时对象只是引用的包装，不会拷贝A的内容。

需要注意：C++17及以下的unordered_map::find默认只接受键类型的参数，所以你需要确保哈希和比较器的重载能正确识别引用型tuple，或者显式构造一个const std::tuple<const A&, const A&>传入（同样无拷贝）。

为什么之前的两种写法都会产生拷贝？ #

再帮你复盘一下：

1. map[{a1,a2}]：直接构造了一个std::tuple<A,A>临时对象，必然会拷贝a1和a2；
2. map[std::tie(a1,a2)]：std::tie返回的是std::tuple<const A&, const A&>，而operator[]只接受const std::tuple<A,A>&或std::tuple<A,A>&&，编译器会隐式调用转换构造函数把引用型tuple转成值型tuple，这一步还是会拷贝a1和a2。

所以核心问题就是operator[]的类型限制，而find的异构查找（或手动支持）正好绕过了这个限制。

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