如何用std::reduce/std::accumulate合并16个3D std::unordered_map？

核心问题分析 #

你遇到的合并速度慢，本质是std::unordered_map的插入操作涉及哈希查找、冲突处理，以及频繁扩容导致的内存重分配，嵌套结构会进一步放大这些开销。下面直接给出std::accumulate和std::reduce的正确用法，以及针对性优化手段。

简化类型别名 #

先定义别名减少冗长的类型声明：

using Level3Map = std::unordered_map<int, int>;
using Level2Map = std::unordered_map<int, Level3Map>;
using Level1Map = std::unordered_map<int, Level2Map>;

1. 用std::accumulate顺序合并 #

基础合并函数 #

实现将源map合并到目标map的函数（默认重复key覆盖，需累加可修改三级map插入逻辑）：

void merge_into(Level1Map& dest, const Level1Map& src) {
    for (const auto& [k1, level2_src] : src) {
        auto& level2_dest = dest[k1]; // 不存在则默认构造空Level2Map
        for (const auto& [k2, level3_src] : level2_src) {
            auto& level3_dest = level2_dest[k2];
            // 批量插入比逐个插入更高效
            level3_dest.insert(level3_src.begin(), level3_src.end());
        }
    }
}

结合std::accumulate使用 #

// 假设thread_maps是存储16个线程生成的map的容器
std::vector<Level1Map> thread_maps;
// ... 填充thread_maps ...

Level1Map merged;
std::accumulate(thread_maps.begin(), thread_maps.end(), std::ref(merged),
    [](auto& dest, const auto& src) {
        merge_into(dest, src);
        return dest;
    });

用std::ref避免每次迭代拷贝目标map，大幅降低内存开销。

2. 用std::reduce并行合并（C++17+） #

std::reduce支持并行执行，能充分利用CPU多核，适合多线程场景下的合并，需确保合并操作满足结合律。

可结合的合并函数 #

Level1Map merge_maps(Level1Map a, Level1Map b) {
    // 总是将小map合并到大map中，减少插入次数
    if (a.size() < b.size()) {
        std::swap(a, b);
    }
    merge_into(a, b);
    return a;
}

并行合并调用 #

#include <execution> // 必须包含此头文件

Level1Map merged = std::reduce(
    std::execution::par,
    thread_maps.begin(),
    thread_maps.end(),
    Level1Map{},
    merge_maps
);

并行策略会自动拆分任务到多线程处理，16个map的合并速度会比顺序版本显著提升。

3. 关键优化手段 #

预分配哈希桶 #

unordered_map扩容会触发大量哈希重计算，合并前预分配足够的bucket可避免频繁扩容：

// 统计所有层级的总元素数
size_t total_level1 = 0, total_level2 = 0, total_level3 = 0;
for (const auto& m : thread_maps) {
    total_level1 += m.size();
    for (const auto& l2 : m) {
        total_level2 += l2.second.size();
        for (const auto& l3 : l2.second) {
            total_level3 += l3.second.size();
        }
    }
}

Level1Map merged;
merged.rehash(total_level1 * 1.5); // 预留1.5倍空间，避免后续扩容

// 修改merge_into，给二级、三级map也预分配
void merge_into(Level1Map& dest, const Level1Map& src) {
    for (const auto& [k1, level2_src] : src) {
        auto& level2_dest = dest[k1];
        level2_dest.reserve(level2_dest.size() + level2_src.size());
        for (const auto& [k2, level3_src] : level2_src) {
            auto& level3_dest = level2_dest[k2];
            level3_dest.reserve(level3_dest.size() + level3_src.size());
            level3_dest.insert(level3_src.begin(), level3_src.end());
        }
    }
}

移动语义减少拷贝 #

如果线程生成的map用完后不再需要，用移动语义直接转移数据，避免拷贝开销：

Level1Map merged;
for (auto&& m : thread_maps) { // 右值引用接收map
    for (auto&& [k1, level2] : m) {
        auto [it, inserted] = merged.emplace(std::move(k1), std::move(level2));
        if (!inserted) {
            // 若key已存在，移动合并二级map
            for (auto&& [k2, level3] : level2) {
                auto [it_l2, inserted_l2] = it->second.emplace(std::move(k2), std::move(level3));
                if (!inserted_l2) {
                    it_l2->second.insert(std::make_move_iterator(level3.begin()), std::make_move_iterator(level3.end()));
                }
            }
        }
    }
}

替换为更高效的哈希容器 #

标准库std::unordered_map性能不算顶尖，若允许引入第三方库，可替换为Abseil的flat_hash_map或Folly的F14Map，这类容器在插入、查找、合并操作上都有显著性能提升。

内容的提问来源于stack exchange，提问作者chetan-set