Can anyone recommend a C++ std::map replacement container?

Question

Maps are great to get things done easily, but they are memory hogs and suffer from caching issues. And when you have a map in a critical loop that can be bad.

So I was wondering if anyone can recommend another container that has the same API but uses lets say a vector or hash implementation instead of a tree implementation. My goal here is to swap the containers and not have to rewrite all the user code that relies on the map.

Update: performance wise the best solution would be a tested map facade on a std::vector

Answer 1

See Loki::AssocVector and/or hash_map (most of STL implementations have this one).

Answer 2

If your key is a simple type that can be very quickly compared and you have no more than a few thousands of entries, you could have better performance by simply putting your pairs in an std::vector and iterating to find your value.

Answer 3

You can use std::tr1::unordered_map, which is already present in most STL implementations, and is part of the C++0x standard.

Here is it's current signature :

template <class Key,
          class T,
          class Hash = std::tr1::hash<Key>,
          class Pred = std::equal_to<Key>,
          class Alloc = std::allocator<std::pair<const Key, T> > >
class unordered_map;

Answer 4

Maybe Google SparseHash could help you?