Хэш-карта, сравнение строк и std :: map?

Question

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

• Хеш-карта хранит строки превращая их в целое число как-то.
• std :: map не является хеш-картой, и если я использую строки, я должен рассмотреть использование хеш-карты для проблем с памятью?
• Сравнение строк не годится, чтобы на него можно было положиться.

Если std :: map не является хеш-картой, и я не должен полагаться на сравнение строк (в основном, у меня есть карта со строками в качестве ключей ... Мне сказали вместо этого искать с использованием хеш-карт?), есть хэш-карта в C ++ STL? Если нет, то как насчет Boost?

Во-вторых, стоит ли хэш-карта [изначально] для std::map< std::string, non-POD GameState >?

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

Спасибо за ваше время.

Answer 1

Я не верю, что большинство ваших пунктов верны.

• в текущем стандарте нет карты хешей. C ++ 0x представляет unordered_map, реализация которого будет хеш-таблицей, и ваш компилятор, вероятно, уже поддерживает ее.

• std :: map реализован в виде сбалансированного дерева, а не хеш-таблицы. При использовании типа карты со строками в качестве ключей или данных не возникает «проблем с памятью».

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

• мой опыт показывает, что unordered_map примерно в два раза быстрее карты - они имеют в основном один и тот же интерфейс, поэтому вы можете попробовать оба с вашими собственными данными - всякий раз, когда вы заинтересованы в производительности, вы всегда должны выполнять свои собственные тесты с ваши собственные реальные данные, а не в зависимости от опыта других. Оба типа карт будут несколько зависеть от длины строкового ключа.

Если у вас есть некоторый класс А, к которому вы хотите получить доступ через строковый ключ, карты будут объявлены как:

map <string, A> amap;
unordered_map <string, A> umap;

Answer 2

Я сделал тест, который сравнивает std :: map с boost :: unordered_map. Мой вывод был в основном таким: если вам не нужны специфичные для карты вещи, такие как equal_range, то всегда используйте boost :: unordered_map. Полный тест можно найти здесь

Answer 3

Хеш-карта обычно будет иметь некоторое интегральное представление строки, да.

std :: map требует сортировки, поэтому реализация ее в виде хеш-таблицы маловероятна, и я никогда не видел ее на практике.

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

Вы хотите unordered_map (это версия Boost - в стандартной библиотеке TR1 также есть версияваш компилятор имеет это).

Стоит ли это для состояний игры?Да, но только потому, что использовать unordered_map просто.Вы преждевременно беспокоитесь об оптимизации на этом этапе.Не беспокойтесь о шаблонах доступа для вещей, которые вы будете искать тысячи раз в секунду (например, когда ваш профилировщик скажет вам, что это проблема).