словарь — c ++: является ли порядок unordered_map детерминированным?
Мне интересно, есть ли какая-либо гарантия того, что порядок unordered_map всегда будет одинаковым для всех процессоров, потоков и т. Д.
Я понимаю, что, возможно, не существует очевидного паттерна для самого конкретного порядка (следовательно, «неупорядоченная» карта), но если я запускаю свой процесс на другом компьютере, или несколько раз подряд, или в других потоках, порядок вставленных элементов всегда будет быть одинаковым, если хеш-функции и порядок вставки остаются прежними? Другими словами, если мой код не изменится, приведет ли каждое выполнение моего процесса к элементам карты в том же порядке?
Я провел несколько тестов, и порядок элементов после вставки кажется одинаковым каждый раз, но это может быть просто случайностью, и у меня есть только одна машина для тестирования. Мне нужно знать, могут ли на порядок влиять какие-либо другие факторы, такие как архитектура процессора / памяти, ОС (Windows 8 или Windows 10) и т. Д.
Решение
TL; DR: Это может быть сделано, но я бы не рекомендовал это. Используйте другую структуру данных, если можете; ваша собственная хеш-таблица, «трепа», плоский массив или что-то.
Порядок предметов в std::unordered_map (или установлен) больше зависит от реализации стандартной библиотеки, чем аппаратное обеспечение / процессор / и т. д.
По этой причине, если вы используете одну и ту же реализацию библиотеки на разных аппаратных средствах и предоставляете свою собственную хеш-функцию (чтобы она не была рандомизирована между прогонами — для борьбы с атаками DoS против ваших структур данных) или иным образом зависящую от оборудования или ОС, тогда ты должен быть в порядке.
Однако, если вы ищете гарантию в стандарте, вы не найдете ее. Единственная уместная гарантия состоит в том, что в одном и том же экземпляре объекта один и тот же ключ будет хешировать один и тот же сегмент. Я не думаю, что есть гарантия даже для разных экземпляров карты, и я знаю из (болезненного) личного опыта, что нет никакой согласованности при разных запусках приложения.
Но не вся надежда потеряна! Если вы придерживаетесь той же реализации unordered_mapи используйте свои собственные хеш-функции, и посмотрите на реализацию, чтобы убедиться, что нет никаких скрытых сюрпризов (любая зависимость от аппаратного обеспечения / ОС / времени / ГСЧ / и т. д. должна быть относительно легко обнаружима), которой вы можете управлять.
Обратите внимание, что поскольку вы работаете в Windows и, возможно, используете MSVC, по умолчанию unordered_map с алгоритмом хеширования по умолчанию не при всех последовательных порядках между запусками одного и того же скомпилированного двоичного файла (по крайней мере, это не было в 2013/2015 IIRC.)
Следует также помнить, что если вы серьезно относитесь к последовательности, вы должны убедиться, что вы ссылаетесь на CRT статически. Если вы ссылаетесь на версию DLL, некоторые будущие исправления / обновления могут изменить поведение вашего приложения после его выпуска.
Другие решения
Других решений пока нет …