Другими словами, если я заполню два объекта unordered_map или unordered_set абсолютно одинаковым содержимым и одной и той же хеш-функцией, будет ли их перебор давать одинаковую последовательность пар ключ/значение?
Если да, то каковы условия для этого (например, одна и та же функция хэширования, одни и те же ключи, не обязательно одинаковые значения).
Нет. Например, не требуется, чтобы объекты с одинаковым хешем располагались в каком-то определенном порядке. Фактически, неупорядоченная карта вообще не может сделать это, потому что единственная информация, к которой у нее есть доступ, — это хеш-значение.
reserve или чем-то еще), что может заставить их упорядочиваться по-разному?
- person Seth Carnegie; 25.03.2012
Поведение в этом случае не определено. Так вот, в одних ситуациях последовательность будет одинаковая, в других - другая. Ни в чем нельзя быть уверенным. Упомянутые вами типы названы unordered не случайно. Использовать их по заказу — очень-очень плохой и крайне опасный стиль.
Вы можете обнаружить, что ваш компилятор ведет себя особым образом, который вам хотелось бы использовать. Но вы не можете быть уверены. Вы не должны быть уверены! Вы не знаете, какие условия вызывают такое поведение компилятора. Вы никогда не можете быть уверены, что любое изменение версии компилятора не изменит нужное вам поведение.
То, что просто запрещено в других языках, в C/C++ не указано. Но вы также должны воспринимать это как запретное.
Посмотрите c-faq о проблеме неопределенного поведения Эта концепция общая для всех C/C++
std::unordered_* действительно может иметь некоторый последовательный порядок. Но спецификация не применяет это. Принимая во внимание, что он обеспечивает определенный порядок на std::map. Поэтому, если вы хотите, чтобы ваш код был переносимым, вы не можете полагаться на порядок.
- person Nicol Bolas; 25.03.2012
Ну, сначала я процитирую MSDN:
Фактический порядок элементов в контролируемой последовательности зависит от хеш-функции, функции сравнения, порядка вставки, максимального коэффициента загрузки и текущего количества сегментов. В общем случае вы не можете предсказать порядок элементов в контролируемой последовательности. Однако вы всегда можете быть уверены, что любое подмножество элементов с эквивалентным порядком является смежным в контролируемой последовательности.
Приведенная выше цитата одинакова для unordered_map и unordered_set, и, как следует из названия, последовательность не указана, однако они упоминают, что эквивалентные ключи являются смежными.
Если вам нужен гарантированный порядок, эта структура данных не для вас. На самом деле, если вы в основном собираетесь выполнять итерацию, unordered_map/set также не является для вас структурой данных.
Для итерации std::map окажется лучшей структурой данных, поскольку переход от одного узла к другому менее алгоритмически сложен. И порядок итерации для объектов в std::map задается спецификацией (и на самом деле является определяющим свойством самой структуры). (Это все при условии, что вы используете один и тот же оператор сравнения, очевидно). В std::map не используется хеширование.
Достаточно сказать, похоже, что вы лаете не на то дерево. unordered_map обычно следует использовать для таких преимуществ, как поиск O (1), а не для хранения списка объектов, а затем для их повторения. Его определенно не следует использовать, если вы пытаетесь получить детерминированный порядок итераций.
