使用连续内存并具有保留功能的映射和集合

我使用了几张地图和套件。缺乏连续内存以及大量的分配（解除）是性能瓶颈。我需要一个主要与 STL 兼容的映射和集合类，它可以将连续的内存块用于内部对象（或多个块）。它还需要有一个reserve函数，以便我可以预先分配预期的大小。

在我自己编写之前，我想先检查一下可用的内容。 Boost中有什么东西可以做到这一点吗？有人知道其他地方有可用的实现吗？

侵入式集合类型在这里不可用，因为相同的对象需要存在于多个集合中。据我所知，STL 内存池是按类型计算的，而不是按实例计算的（有点，有点不是，有很多注意事项）。这些全局池在多 CPU/核心处理中的内存局部性方面效率不高。

对象池不起作用，因为类型将在实例之间共享，但它们的池不应该共享。

在许多情况下，哈希映射可能是一种选择。

看看这个：谷歌稀疏哈希图 https://github.com/sparsehash/sparsehash。自从几年前我偶然发现它以来，它一直是我最喜欢的 C++ 库。

它的性能令人难以置信，既有地图又有集合类，并且具有所需的储备功能。我已经将无数项目从各种其他类似地图的数据结构切换到 googlespareshash，并取得了令人难以置信的结果。语法与 C++0x 直接兼容unordered_map（可怕，可怕的名字！），但也有额外的功能和特性。

在内部，它是通过使用稀疏哈希技术的哈希表来实现的。

编辑（2015 年 5 月 13 日）

由于这已成为一个流行的答案，我只想指出我近年来一直在使用的另外两种类似地图的结构。这M各种各样的C容器T模板 (MCT) 库 https://launchpad.net/libmct提供多种兼容的高性能 unorderd_map 实现：

它提供了六个通用哈希表容器 - 已关闭的哈希集、已关闭的哈希图、已链接的哈希集、已链接的哈希图、 forward_hash_set 和forward_hash_map。前两个非常相似 到 TR1 unordered_set 和 unordered_map。链接的提供 附加功能，而前向哈希表效率更高 比链接，但有受限的接口。某些情况下的性能 Closed_hash_* 容器的数量可以进一步改进 可选的侵入性支持。

And folly https://github.com/facebook/follyby facebook 有一些非常棒的结构。他们本身没有直接的 unordered_map 替换，但是有一个 unordered_map 的无锁/线程安全实现并围绕它构建东西fbvector由于更好的内存使用和布局，可以带来巨大的性能提升。

在我的测试中，对于 Google 的单线程代码dense_hash_map仍然是我获得最佳性能的首选。