地图和一套利用连续的内存，并具有储备功能 [英] A map and set which uses contiguous memory and has a reserve function

问题描述

我用几个地图和集。缺乏连续的内存，以及高数（DE）的分配，是一个性能瓶颈。我需要一个主要STL-compatbile地图，并设置类可以使用的内存为内部对象（或多个块）相邻块。它也需要有一个储备函数，这样我可以preallocate的预期大小。

I use several maps and sets. The lack of contiguous memory, and high number of (de)allocations, is a performance bottleneck. I need a mainly STL-compatbile map and set class which can use a contiguous block of memory for internal objects (or multiple blocks). It also needs to have a reserve function so that I can preallocate for expected sizes.

在我写我自己，我想查什么是可用的第一位。有什么在推动，这样做呢？是否有人知道其他可用的执行？

Before I write my own I'd like to check what is available first. Is there something in Boost which does this? Does somebody know of an available implementation elsewhere?

侵入集合类型是不可用此作为相同的对象需要在多个集合存在。据我所知STL内存池是每个类型，而不是每个实例（那种，有点不是很多注意事项）。这些全球性的池是效率不高，在辑阵-CPU对于内存局部性/核心处理。

Intrusive collection types are not usable here as the same objects need to exist in several collections. As far as I know STL memory pools are per-type, not per instance (kind of, sort of not, many caveats). These global pools are not efficient with respect to memory locality in mutli-cpu/core processing.

对象池不工作的类型将实例之间共享，但他们的水池不应该。

Object pools don't work as the types will be shared between instance but their pool should not.

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

In many cases a hash map may be an option.

推荐答案

有一个看看这个：的谷歌稀疏散列地图。它是我最喜欢的C ++库，因为我在它几年前绊倒了。

Have a look at this: Google Sparse Hash Map. It's been my favorite C++ library since I stumbled upon it some years ago.

其表现是令人难以置信的，既有一张地图和一组类，并有要求，储备功能。我切换从其他多种地图状数据结构无数的项目，谷歌sparsehash以令人难以置信的结果。语法是下拉兼容与C ++ 0x中 unordered_map （可怕，可怕的名字！），但额外的功能及特性。

Its performance is incredible, has both a map and a set class, and has the asked-for reserve functions. I've switched over countless projects from various other map-like datastructures to google sparsehash with incredible results. The syntax is drop-in compatible with the C++0x unordered_map (terrible, terrible name!), but has extra functions and features as well.

内部，它与使用sparsehashing技术哈希表来实现。

Internally, it is implemented with a hash table using the sparsehashing technique.

编辑（2015年5月13日）

EDIT (May 13, 2015)

由于这已经成为一种普遍的回答，我只是想指出，我一直在使用近两年其他地图状结构。该的 M iscellaneous C ontainer的 T emplates（ MCT）库提供插入式兼容高性能unorderd_map实现在几个品种：

As this has become a popular answer, I just wanted to point out two other map-like structures I have been using in recent years. The Miscellaneous Container Templates (MCT) library provides drop-in compatible high-performance unorderd_map implementations in a few varieties:

它提供了6个通用哈希表容器 -
  closed_hash_set，closed_hash_map，linked_hash_set，linked_hash_map，
  forward_hash_set和forward_hash_map。前两个非常相似
  到TR1 unordered_set和unordered_map。所链接的人提供
  附加功能，而前锋哈希表更有效
  比联，但有限制的接口。在某些情况下表现
  所述closed_hash_的*容器可以进一步具有改进
  可选的侵扰支持。

It provides six general-purpose hash table containers — closed_hash_set, closed_hash_map, linked_hash_set, linked_hash_map, forward_hash_set and forward_hash_map. The first two are very similar to TR1 unordered_set and unordered_map. The linked ones provide additional functionality, while forward hash tables are more efficient than linked, but have restricted interface. In some cases performance of the closed_hash_* containers can be improved even further with optional intrusiveness support.

和愚蠢通过Facebook有一些真正伟大的结构。他们没有一个下拉每本身unordered_map更换，但有的unordered_map和建筑物周围的事物 fbvector 无锁/线程安全的实现可能会导致巨大性能提升是由于更好的内存使用和布局。

And folly by facebook has some really great structures. They don't have a drop-in unordered_map replacement per-se, but there's a lock-free/thread-safe implementation of unordered_map and building things around fbvector can result in huge performance gains due to better memory usage and layout.

在我的测试中，单线程code谷歌的 dense_hash_map 仍然是我的preferred选项以获得最大性能。

In my testing, for single-threaded code Google's dense_hash_map is still my preferred option for maximum performance.

这篇关于地图和一套利用连续的内存，并具有储备功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！