面试题：C++ 自定义类型作为 map 键时的键值修改挑战与解决方案

挑战分析

哈希冲突：当自定义类型作为 map 的键时，如果哈希函数设计不当，可能会导致大量哈希冲突。这会降低 map 的查找效率，因为在冲突时需要通过链表或其他方式处理，增加了查找时间复杂度。
排序规则变化：对于 std::map，它是基于红黑树实现的有序映射，键值需要满足严格弱序关系。如果修改键值后破坏了原有的排序规则，会导致 map 的内部结构混乱，影响插入、查找和删除操作的正确性。

通用解决方案设计思路

避免直接修改键值：为了防止破坏 map 的内部结构，不直接修改 map 中已有的键值。而是先删除旧键值对，再插入新键值对。
稳定的哈希函数和排序规则：确保自定义类型的哈希函数和排序规则在整个生命周期内保持稳定。如果键值发生变化，重新计算哈希值和排序比较结果。

实现步骤

定义自定义类型：为自定义类型定义哈希函数和比较函数，确保它们的稳定性。
修改键值操作：在修改键值时，先从 map 中删除旧键值对，然后插入新键值对。

关键代码片段

#include <iostream>
#include <unordered_map>
#include <map>
#include <string>

// 自定义类型
struct MyKey {
    int id;
    std::string name;

    // 自定义哈希函数
    struct HashFunc {
        std::size_t operator()(const MyKey& key) const {
            using std::hash;
            return hash<int>()(key.id) ^ hash<std::string>()(key.name);
        }
    };

    // 自定义比较函数，用于 std::map
    struct CompareFunc {
        bool operator()(const MyKey& a, const MyKey& b) const {
            if (a.id != b.id) return a.id < b.id;
            return a.name < b.name;
        }
    };
};

// 修改键值的通用函数，用于 std::unordered_map
template <typename Key, typename Value, typename Hash, typename KeyEqual>
void modifyKeyInUnorderedMap(std::unordered_map<Key, Value, Hash, KeyEqual>& umap, const Key& oldKey, const Key& newKey) {
    auto it = umap.find(oldKey);
    if (it != umap.end()) {
        Value value = std::move(it->second);
        umap.erase(it);
        umap.insert({newKey, std::move(value)});
    }
}

// 修改键值的通用函数，用于 std::map
template <typename Key, typename Value, typename Compare>
void modifyKeyInMap(std::map<Key, Value, Compare>& mmap, const Key& oldKey, const Key& newKey) {
    auto it = mmap.find(oldKey);
    if (it != mmap.end()) {
        Value value = std::move(it->second);
        mmap.erase(it);
        mmap.insert({newKey, std::move(value)});
    }
}

int main() {
    // 使用 std::unordered_map 的示例
    std::unordered_map<MyKey, int, MyKey::HashFunc> umap;
    MyKey key1{1, "Alice"};
    umap.insert({key1, 100});
    MyKey newKey1{1, "Bob"};
    modifyKeyInUnorderedMap(umap, key1, newKey1);

    // 使用 std::map 的示例
    std::map<MyKey, int, MyKey::CompareFunc> mmap;
    MyKey key2{2, "Charlie"};
    mmap.insert({key2, 200});
    MyKey newKey2{2, "David"};
    modifyKeyInMap(mmap, key2, newKey2);

    return 0;
}

上述代码中，定义了自定义类型 MyKey，并为其提供了哈希函数 HashFunc 和比较函数 CompareFunc。同时，实现了两个通用函数 modifyKeyInUnorderedMap 和 modifyKeyInMap，分别用于在 std::unordered_map 和 std::map 中安全地修改键值。通过先删除旧键值对再插入新键值对的方式，避免了直接修改键值带来的问题。

星途面试题库

面试题：C++ 自定义类型作为 map 键时的键值修改挑战与解决方案

知识考点

面试题答案

挑战分析

通用解决方案设计思路

实现步骤

关键代码片段