Одинаков ли порядок двух одинаковых unordered_maps?

Question

Другими словами, если я заполню два unordered_map, или unordered_set, объекты с одинаковым содержимым и одинаковой функцией хеширования, будет ли повторение по ним давать одинаковую последовательность пар ключ / значение?

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

Answer 1

Нет. Например, не требуется, чтобы объекты с одинаковым хешем располагались в каком-то определенном порядке. Фактически, в общем случае для неупорядоченной карты это невозможно, поскольку единственная информация, к которой она имеет доступ, - это значение хеш-функции.

Answer 2

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

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

Что просто запрещено в других языках, в C / C ++ не указано.Но вы также должны принять это как запрет.

Посмотрите c-faq о проблеме неопределенного поведения Эта концепция является общей для всех C / C ++

Answer 3

Ну сначала я процитирую MSDN :

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

Answer 4

Если вам нужен гарантированный заказ, это , а не структура данных для вас. На самом деле, если вы собираетесь выполнять итерацию, unordered_map/set для вас тоже не структура данных.

Для итерации, std::map окажется лучшей структурой данных, так как гониг от одного узла к другому менее алгоритмически сложен. И порядок итерации для объектов в std::map гарантирован спецификацией (и фактически является определяющим свойством самой структуры). (Это все предполагает, что вы используете один и тот же оператор сравнения, очевидно). В std::map.

нет хеширования

Достаточно сказать, звучит так, будто вы тут не туда лаете. unordered_map обычно следует использовать для таких преимуществ, как поиск O (1), а не для хранения списка объектов и последующей их итерации по ним. определенно не следует использовать, если вы пытаетесь получить детерминированный порядок итерации.