面试题：C++ 泛型算法与容器在复杂场景下的性能优化问题

性能瓶颈分析

std::vector 特定元素过滤与计算：
- 手动遍历 std::vector 进行复杂过滤和计算效率低，因为会有较多重复代码，且无法充分利用现代CPU的特性（如SIMD指令）。
- 如果 std::vector 较大，遍历会花费大量时间，尤其是每次过滤和计算都要完整遍历一遍。
std::unordered_map 频繁插入和删除：
- std::unordered_map 的插入和删除操作平均时间复杂度为 $O(1)$，但在极端情况下（如哈希冲突严重），时间复杂度可能退化为 $O(n)$。
- 每次插入或删除可能会导致哈希表重新调整大小（rehash），这会带来额外的性能开销，特别是在频繁操作时。

性能优化关键思路

利用C++泛型算法：
- 使用 std::algorithm 头文件中的算法，如 std::transform、std::filter（C++20引入）等，来处理 std::vector 中的过滤和计算。这些算法通常经过优化，能利用CPU的特性提高性能。
- 对于C++20之前版本没有 std::filter，可以使用 std::remove_if 结合 erase - remove 惯用法来实现过滤功能。
优化 std::unordered_map：
- 预先估计 std::unordered_map 的大小，通过构造函数设置合适的初始容量，减少rehash的次数。
- 选择合适的哈希函数，对于自定义类型，确保哈希函数能均匀分布哈希值，减少哈希冲突。

代码框架示例

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <numeric>

// 自定义类型
struct MyType {
    int id;
    double value;
};

// 自定义哈希函数
struct MyTypeHash {
    std::size_t operator()(const MyType& mt) const {
        using std::size_t;
        using std::hash;
        using std::string;

        return ((hash<int>()(mt.id)
                ^ (hash<double>()(mt.value) << 1)) >> 1);
    }
};

int main() {
    // 初始化 std::vector
    std::vector<MyType> myVector = { {1, 1.1}, {2, 2.2}, {3, 3.3} };
    // 初始化 std::unordered_map
    std::unordered_map<MyType, int, MyTypeHash> myMap;

    // 1. 利用泛型算法对 std::vector 进行过滤和计算
    // 过滤出 id 大于 1 的元素
    myVector.erase(std::remove_if(myVector.begin(), myVector.end(),
                                  [](const MyType& mt) { return mt.id <= 1; }),
                   myVector.end());

    // 对过滤后的元素的 value 进行累加
    double sum = std::accumulate(myVector.begin(), myVector.end(), 0.0,
                                 [](double acc, const MyType& mt) { return acc + mt.value; });

    // 2. 优化 std::unordered_map 插入操作
    // 预先估计大小
    myMap.reserve(myVector.size());
    for (const auto& mt : myVector) {
        myMap[mt] = static_cast<int>(mt.value * 10);
    }

    // 3. 优化 std::unordered_map 删除操作
    // 找到要删除的元素并删除
    auto it = myMap.find(myVector[0]);
    if (it != myMap.end()) {
        myMap.erase(it);
    }

    return 0;
}

在上述代码框架中：

首先利用 std::remove_if 和 erase - remove 惯用法对 std::vector 进行过滤。
然后使用 std::accumulate 对过滤后的 std::vector 元素进行计算。
对于 std::unordered_map，通过 reserve 预先分配空间优化插入操作，并展示了删除操作。同时为自定义类型 MyType 定义了合适的哈希函数。

星途面试题库

面试题：C++ 泛型算法与容器在复杂场景下的性能优化问题

知识考点

面试题答案

性能瓶颈分析

性能优化关键思路

代码框架示例