插入unordered_map时为bad_alloc

Question

在最近的项目中，使用了stl unordermap。当存储在地图中的密钥数量上升到6倍-7倍甚至8倍时，unordermap的插入接口的性能具有严重的瓶颈。随着插入元素的数量增加，在插入过程中发生碰撞。碰撞打开到某个阈值，触发桶的增加，从而触发重新散列。打印bucket_size可以看到bucketsize一直在增加，这非常昂贵。

这是测试代码：

int main() {
    std::unordered_map<int, int> t;
    for (int i = 0; i <= 10000000; ++i) {
    t.insert(make_pair(i, 1));
    }
}

我应该使用保留元素的数量来提高性能吗？

t.reserve(10000000)

Answer 1

与绩效相关的问题的最佳答案是 - “我们应该衡量”。

以下是您的代码段的基准 - http://quick-bench.com/O5rEF-B_HY9dOzAa7kLbtptUQcQ