std :: hash_set против std :: unordered_set, это одно и то же?

Question

Я знаю, hash_set нестандартно, а unordered_set стандартно. Тем не менее, мне интересно, с точки зрения производительности, в чем разница между этими двумя? Почему они существуют отдельно?

Answer 1

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

Поставщики компиляторов обычно называют эти контейнеры "хэш-карта" или "хэш-набор", что вам и нужновероятно, имеется в виду (в стандарте нет буквального std::hash_set, но я думаю, что он есть в GCC в отдельном пространстве имен и аналогично для других компиляторов).

Когда был написан новый стандарт, авторыЯ хотел избежать возможной путаницы с существующими библиотеками расширений, поэтому они пошли на имя, которое отражает типичное мышление C ++: говорите, что это такое, а не как это реализовано.Неупорядоченные контейнеры, ну, неупорядоченные .Это означает, что вы получаете меньше от них по сравнению с заказанными контейнерами, но эта уменьшенная утилита предоставляет вам более эффективный доступ.

В зависимости от реализации, hash_set, Boost-unordered, TR1-unordered и C ++ 11-unordered willбыть очень похожим, если не идентичным.

Answer 2

Относительно вопроса «это одно и то же» из строки темы: основываясь на моем опыте обновления кода с __gnu_cxx :: hash_set до std :: unordered_set, они почти, но не совсем одно и то же.

Разница, с которой я столкнулся, заключается в том, что итерация через __gnu_cxx :: hash_set возвращала элементы в том порядке, в котором они выглядели в первоначальном порядке вставки, тогда как std :: unordered_set - нет.Таким образом, как следует из названия, нельзя полагаться на итератор, который возвращает элементы в любом конкретном порядке при итерации, хотя весь std :: unordered_set.

Answer 3

Visual Studio 2010, например, имеет как hash_xxx, так и unordered_xxx, и если вы посмотрите заголовки, то по крайней мере их реализация одинакова для всех этих классов (одинаковые базовые - / "policy"). Что касается других компиляторов, я не знаю, но из-за того, как обычно должен быть реализован хэш-контейнер, я думаю, что различий не будет, если вообще будет вообще.

Answer 4

Это почти одно и то же.Стандартное (C ++ 0x) имя - unordered_set.hash_set был более ранним именем от boost и других.