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 分钟)。- vector 的内存使用较少，因为没有存储 key - 随机访问 vector 似乎有点慢，还没有分析代码。

再次感谢大家的帮助。

Answer 1

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

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

你可以

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