std::unordered_map reserve方法为何未减少内存分配次数？

问题原因 #

std::unordered_map::reserve的核心作用是预分配桶数组的内存，目的是提前设置足够的桶数量，避免插入过程中因哈希冲突触发频繁rehash。但它不会预分配存储键值对的节点内存——std::unordered_map的每个元素都是独立的链表节点，默认情况下每次插入都会单独分配一个节点的内存。你看到的1001次分配中，1次是桶数组的分配，剩下1000次是每个元素节点的单独分配，所以调用reserve不会改变这个次数。

解决方案 #

1. 实现内存池分配器 #

自定义分配器时加入内存池逻辑，预先分配一块足够容纳所有元素节点的连续内存，后续插入直接从内存池中取空间，避免多次小内存分配。

修改后的分配器示例：

#include <string>
#include <unordered_map>
#include <iostream>
#include <vector>
#include <cstddef>

using namespace std;

inline size_t AllocationCounter = 0;

template <typename T>
struct pool_alloc {
    using value_type = T;
    static constexpr size_t POOL_CAPACITY = 1000; // 匹配插入总量
    static alignas(T) char memory_pool[POOL_CAPACITY * sizeof(T)];
    static size_t used_slots;

    pool_alloc() = default;

    template <typename U>
    constexpr pool_alloc(const pool_alloc<U>&) noexcept {}

    T* allocate(std::size_t n) {
        // unordered_map每次只分配单个节点，所以只处理n=1的情况
        if (n != 1) {
            AllocationCounter++;
            return static_cast<T*>(::operator new(n * sizeof(T)));
        }
        if (used_slots >= POOL_CAPACITY) {
            AllocationCounter++;
            return static_cast<T*>(::operator new(sizeof(T)));
        }
        // 从内存池取空间，不计入分配计数器
        T* ptr = reinterpret_cast<T*>(memory_pool + used_slots * sizeof(T));
        used_slots++;
        return ptr;
    }

    void deallocate(T* p, std::size_t n) noexcept {
        // 仅释放内存池外的节点
        if (p < reinterpret_cast<T*>(memory_pool) || p >= reinterpret_cast<T*>(memory_pool + POOL_CAPACITY * sizeof(T))) {
            AllocationCounter--;
            ::operator delete(p);
        }
        // 内存池内的节点可选择回收复用，这里简化处理
    }

    template <typename... Args>
    void construct(T* p, Args&&... args) {
        new (p) T(std::forward<Args>(args)...);
    }

    void destroy(T* p) noexcept {
        p->~T();
    }
};

// 静态成员初始化
template <typename T>
alignas(T) char pool_alloc<T>::memory_pool[pool_alloc<T>::POOL_CAPACITY * sizeof(T)];

template <typename T>
size_t pool_alloc<T>::used_slots = 0;

void with_reserve_and_pool()
{
    using MapType = unordered_map<size_t, size_t, std::hash<size_t>, std::equal_to<size_t>, pool_alloc<std::pair<const size_t, size_t>>>;
    MapType m1;
    m1.reserve(1000); // 预分配桶数组，避免rehash

    for (size_t i = 0; i < 1000; i++) {
        m1.insert({i, i});
    }

    printf("With reserve + pool allocator - %llu Allocations\n", AllocationCounter);
    // 重置状态供下一次测试
    pool_alloc<std::pair<const size_t, size_t>>::used_slots = 0;
    AllocationCounter = 0;
}

void without_reserve()
{
    using MapType = unordered_map<size_t, size_t, std::hash<size_t>, std::equal_to<size_t>, pool_alloc<std::pair<const size_t, size_t>>>;
    MapType m1;

    for (size_t i = 0; i < 1000; i++) {
        m1.insert({i, i});
    }

    printf("Without reserve - %llu Allocations\n", AllocationCounter);
}

int main()
{
    with_reserve_and_pool();
    without_reserve();
}

使用这个分配器后，with_reserve_and_pool的分配次数会降到1次（仅桶数组的分配），大幅减少内存分配开销。

2. 使用扁平哈希表替代std::unordered_map #

第三方库如Abseil的absl::flat_hash_map、Boost的boost::flat_hash_map采用扁平存储结构，将元素放在连续内存块中。这类结构支持预分配足够的内存容纳所有元素，天然减少分配次数，同时性能通常优于标准库的unordered_map。

3. 保留reserve优化 #

即使使用内存池或扁平哈希表，调用reserve依然有价值——它能提前设置合适的桶数量，减少哈希冲突和rehash操作，进一步提升插入性能。

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