std::unordered_map 分配、插入和释放时间

Question

我在一个文件中有大约 400 万个值，我想将这些值存储在一个容器中以执行计算。

每个value的key由2个无符号整数组成该值是一个包含 4 个双精度数的结构。

加载后数值不会改变。

typedef pair<unsigned int, unsigned int> aa;
struct MyRecord { double a1; double a2; double a3; double a4; };

class MyRecordHash{
public:
    size_t operator()(const aa &k) const{   return k.first * 10000 + k.second;      }
};

struct MyRecordEquals : binary_function<const aa&, aa&, bool> {
  result_type operator()( nm lhs, nm rhs ) const
  {
    return (lhs.first == rhs.first) && (lhs.second == rhs.second);
  }
};     

std::unordered_map<aa,MyRecord,MyRecordHash,MyRecordEquals> MyRecords;

我在插入记录之前使用 MyRecords.reserve(number_of_records)。

问题A：虽然我在开始插入数据之前调用了reserve，但是分配的内存不够，并且在插入数据时不断重新分配越来越多的内存。它不应该保留分配所需的内存吗？例如，对于 4m 的记录，它会分配 38.9Mb 的保留空间，然后在插入后额外分配 256.5Mb。

问题B：插入过程比较慢。我检查了负载系数，它从未增加超过 0.5。有没有其他检查的建议？我使用 MyRecords.insert 进行插入。

问题 C：完成计算后，我调用 MyRecords.clear() 。它不是删除内容 "instantly"，而是开始逐条记录地删除（大约 3Mb/秒）。如果我不调用 clear() 我会得到相同的行为。这是正常的吗？我检查了所有以前的 Whosebug 问题，我发现的唯一建议是它可能与调试有关。我使用了 -O3 选项，但它没有改变任何东西。

我使用的是MinGW-64编译器4.9.1版本

感谢大家阅读本文并提出建议。

在提出意见和解决方案后进行编辑：

-似乎没有办法为 unordered_maps 释放或预分配 STL 的内存，当使用非标准类型的键和包含的数据时。 - Reserve 方法，只为散列保留内存。 - 使用 vector<> 和根据值的键计算的索引效果很好。只需预分配向量，然后使用 myvector.at() = value，设置值。默认析构函数几乎立即释放向量（4m 值需要 2-3 秒而不是 unordered_map 的 5 分钟）。 -向量的内存使用较少，因为没有存储密钥 -随机访问向量似乎有点慢，还没有分析代码。

再次感谢大家的帮助。

Answer 1

reserve 可能只为散列结构（例如指向数据的指针的向量）而不是数据本身分配 space。

以你插入4M条记录为例。每条记录是 4 个双精度数或 4*8 个字节。 4M记录意味着4*8*4=128Mbytes的数据。所以很明显，38.9Mbyte reserve() 分配是不够的。

Answer 2

unordered_map::reserve 所做的只是增加桶的数量，以便在插入指定数量的元素时不会超过最大加载因子。这对你没有帮助。

unordered_map是一个基于节点的容器；结果，每次插入都是一个单独的分配。您的数据结构的析构函数是微不足道的，但释放 400 万块内存非常昂贵。

你可以

使用可有效处理您的分配模式的自定义分配器，
或者切换到不同的数据结构。 boost::flat_map 是一个不错的选择（稍微增加的时间复杂度可能会被更好的数据局部性带来的性能提升所抵消）。

Answer 3

摘自评论...

我想我会问这个问题（换个角度看问题），你确定你需要一个关联容器吗？

如果您的条目几乎涵盖了所有组合键，那么如果您愿意为未使用的条目浪费一点 space，那么向量可能就可以了。因此，将您的键视为向量中的索引。这将为您提供恒定的时间查找，并允许您预先分配所有需要的内存，避免多次分配的成本。

这种方法的价值将取决于键在键中的分布 space 以及它们映射到从零开始的数组索引的难易程度。

如果您确实尝试这种方法，我很想看看它相对于您当前正在做的事情的表现如何。

std::unordered_map 分配、插入和释放时间

std::unordered_map allocation, insert and deallocation time

c++

stl

c++11