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

Question

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

每个值的键由2个无符号整数组成 该值是一个包含 4 个 double 字的结构体。

加载后值不会改变。

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() 。它不是“立即”删除内容，而是开始逐条删除记录(大约 3Mb/秒)。如果我不调用clear()，我会得到相同的行为。这是正常的吗？我检查了之前所有的 stackoverflow 问题，我发现的唯一建议是它可能与调试有关。我使用了 -O3 选项，但它没有改变任何东西。

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

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

提出意见和解决方案后编辑:

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

再次感谢大家的帮助。

Answer 1

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

unordered_map是一个基于节点的容器；因此，每次插入都是一次单独的分配。您的数据结构的析构函数很简单，但释放 400 万 block 内存是相当昂贵的。

你可以

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