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

Question

Карты хороши для простого выполнения задач, но они - проблемы с памятью и страдают от проблем с кэшированием. И когда у вас есть карта в критическом цикле, это может быть плохо.

Поэтому мне было интересно, может ли кто-нибудь порекомендовать другой контейнер, который имеет тот же API, но использует, скажем, реализацию вектора или хеша вместо реализации дерева. Моя цель здесь - поменять контейнеры и не нужно переписывать весь код пользователя, который полагается на карту.

Обновление: с точки зрения производительности лучшим решением будет протестированный фасад карты на std :: vector

Answer 1

Вы можете использовать std :: 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;

Answer 2

Может быть Google SparseHash может вам помочь?

Answer 3

См. Loki :: AssocVector и / или hash_map (у большинства реализаций STL есть такая).

Answer 4

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