面试题：C++ map复杂键值比较规则及性能优化

Question

有一个`std::map`，键类型是一个包含多个复杂数据成员的自定义类`ComplexKey`，类中有`std::vector<int>`、`std::unordered_map<std::string, double>`等成员。要求设计一个高效的比较函数，比较规则是：先比较`std::vector<int>`的元素和，如果和相同再比较`std::unordered_map<std::string, double>`中特定键对应的值（假设这个特定键是已知的）。同时分析这样的比较函数可能带来的性能问题，并提出优化方案。请写出比较函数及相关分析。

Answer 1

比较函数实现

#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>

class ComplexKey {
public:
    std::vector<int> vec;
    std::unordered_map<std::string, double> umap;
};

bool compareComplexKey(const ComplexKey& a, const ComplexKey& b) {
    int sumA = 0, sumB = 0;
    for (int num : a.vec) {
        sumA += num;
    }
    for (int num : b.vec) {
        sumB += num;
    }
    if (sumA != sumB) {
        return sumA < sumB;
    }
    static const std::string specificKey = "specific_key";
    auto itA = a.umap.find(specificKey);
    auto itB = b.umap.find(specificKey);
    if (itA == a.umap.end() && itB == b.umap.end()) {
        return false;
    } else if (itA == a.umap.end()) {
        return true;
    } else if (itB == b.umap.end()) {
        return false;
    } else {
        return itA->second < itB->second;
    }
}

性能问题分析

1. 向量求和性能：在计算std::vector<int>的元素和时，时间复杂度为O(n)，其中n是向量的大小。如果向量非常大，这一步的计算开销会比较大。
2. 哈希表查找性能：在std::unordered_map<std::string, double>中查找特定键，平均时间复杂度为O(1)，但在最坏情况下（哈希冲突严重），时间复杂度会退化为O(n)，其中n是哈希表的大小。

优化方案

1. 缓存向量和：可以在ComplexKey类中添加一个成员变量来缓存向量的和，这样在比较时就不需要每次都重新计算。每次向量元素改变时，更新这个缓存值。
2. 优化哈希表：确保哈希表的负载因子在合理范围内，减少哈希冲突的可能性。可以在插入元素时，根据预计的元素数量合理设置哈希表的初始大小。同时，选择一个好的哈希函数对于std::string类型的键也很重要。

class OptimizedComplexKey {
public:
    std::vector<int> vec;
    std::unordered_map<std::string, double> umap;
    int sumCache;

    OptimizedComplexKey() : sumCache(0) {}

    void updateSumCache() {
        sumCache = 0;
        for (int num : vec) {
            sumCache += num;
        }
    }
};

bool optimizedCompareComplexKey(const OptimizedComplexKey& a, const OptimizedComplexKey& b) {
    if (a.sumCache != b.sumCache) {
        return a.sumCache < b.sumCache;
    }
    static const std::string specificKey = "specific_key";
    auto itA = a.umap.find(specificKey);
    auto itB = b.umap.find(specificKey);
    if (itA == a.umap.end() && itB == b.umap.end()) {
        return false;
    } else if (itA == a.umap.end()) {
        return true;
    } else if (itB == b.umap.end()) {
        return false;
    } else {
        return itA->second < itB->second;
    }
}