A map and set which uses contiguous memory and has a reserve function

Question

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?

---

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.

Answer 1

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

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.

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

EDIT (May 13, 2015)

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:

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.

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.

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

Answer 2

Boost.Interprocess and Boost.Container provide flat set and flat map that could help you to improve the performances of your application.

See https://svn.boost.org/svn/boost/sandbox/move/libs/container/doc/html/boost_container_reference.html#header.boost.container.flat_set_hpp