最快的C++地图?

std:map std:unordered_map 将实现为一个哈希表,它可能会给您O(1)性能(良好的哈希函数和散列桶之间的密钥分布),但它可能是O(n)(所有内容都在一个散列桶中,并转移到一个列表中)。人们通常会期望在这两个极端之间有某种东西。

所以您可以一直有合理的性能(O(logn)),或者 需要确保所有的东西都排成一行,以便通过散列获得良好的性能。

与任何这样的问题一样:在使用一种方法之前,您需要进行度量。除非您的数据集很大,否则您可能会发现没有显著差异。

重要警告: 除非您已经测量过(而且您的问题表明您没有)映射性能对您的应用程序性能有实质性的影响(很大一部分时间花在搜索和更新映射上),否则不要费心让它更快。 坚持 std::map (或 std::unordered_map hash_map 实施)。 让它没有bug。

回应理查德的回答: 测量 使用真实类和真实数据的不同映射实现的性能。

一些附加说明:

• 找出真正的瓶颈在哪里。与IO成本相比,在map中搜索的成本可能微不足道。

• 尝试更专业的map实现。例如,如果你对地图的钥匙有更多的了解,你会得到很多东西。通用map实现的作者并不具备这样的知识。

在您的示例中(32位无符号整数键,强群集,例如按顺序分配),您可以使用基于基数的方法。 非常 简单的例子(以它为例,不准备使用配方):

Item *sentinel[65536];  // sentinel page, initialized to NULLs.
Item (*pages[65536])[65536];  // list of pages,
                              // initialized so every element points to sentinel

Item *value = pages[index >> 16][index & 0xFFFF];

if (pages[index >> 16] == sentinel) {
  pages[index >> 16] = allocate_new_null_filled_page();
}
pages[index >> 16][index & 0xFFFF] = value;

• 调整地图实现。

  • 例如,每 喜欢提前知道元素的大致数目。它有助于避免哈希表的不必要的重新分配和(可能)所有键的重新灰化。

  • 在我上面的特殊示例中,您肯定会尝试不同的页面大小,或者三级版本。

无论何时插入或删除项,内存分配/释放都会花费大量成本。相反,您可以使用如下分配器: https://github.com/moya-lang/Allocator