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

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 inst开发者_如何转开发ance but their pool should not.

In many cases a hash map may be an option.

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.

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

You could just use a vector and binary search it for contiguous storage and reserve() as well as maintaining O(logn). Inserting would be more expensive, though.

A recent post on the Boost mailing list discussed something similar to this.

Howard Hinnant has created an allocator which can use the stack instead of the heap.

http://howardhinnant.github.io/stack_alloc.html

You might want to take a look at Google's TCMalloc. It is a drop-in replacement for malloc, which might speed up your program. TCMalloc is specifically designed for multiple threads.