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

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

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

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


c++ stdmap
person Robert Gould    schedule 24.09.2008    source источник

Ответы (4)


arrow_upward
4
arrow_downward

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

person yrp    schedule 24.09.2008
comment
По сути, это отсортированный std::vector‹std::pair‹Key, T›› с картоподобным интерфейсом. Лицензия достаточно разрешительная, чтобы вырвать ее и вставить куда-нибудь в ваш проект. - person Greg Rogers; 24.09.2008
comment
Извините, я не вернулся, чтобы проверить ответ до сих пор, но это именно то, что мне нужно! Спасибо, отличное дополнение (учитывая варианты использования, которые у меня есть) - person Robert Gould; 17.10.2008

arrow_upward
11
arrow_downward

Вы можете использовать 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;
person Luc Touraille    schedule 24.09.2008
comment
Я не использовал std::tr1::unordered_map, но если это что-то вроде hash_map в STLport, я не удивлюсь, если типичная реализация потребляет еще больше памяти, чем std::map, и имеет такое же плохое пространственное расположение. - person bk1e; 25.09.2008

arrow_upward
6
arrow_downward

Возможно, вам поможет Google SparseHash?

person Igor Semenov    schedule 24.09.2008

arrow_upward
2
arrow_downward

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

person Carl Seleborg    schedule 24.09.2008
comment
В идеале это было бы лучшим решением, но я не хочу писать (и отлаживать) интерфейс/оболочку вектора, чтобы он был совместим с картой. Знаете ли вы о какой-либо реализации этой техники? - person Robert Gould; 24.09.2008
comment
Набор концепций boost::property_map и особенно boost::vector_property_map - это то, что вам нужно... - person Paul Michalik; 12.11.2011