Кто-нибудь может порекомендовать контейнер для замены C ++ std :: map?

Можно использовать станд.:: tr1:: unordered_map, который уже присутствует в большинстве реализаций STL и является частью C++ 0x стандарт.

Вот, это - текущая подпись:

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;

Maybe Google SparseHash мог помочь Вам?

Если Ваш ключ является простым типом, который может быть очень быстро сравнен, и у Вас есть не больше, чем несколько тысяч записей, у Вас могла быть лучшая производительность, просто вставляя Ваших пар std::vector и итерация для нахождения значения.