Как unordered_set определяет порядок вставки в C++?

Question

Я знаю, что люди используют unordered_set, когда они не заботятся о порядке элементов в наборе. Тем не менее, когда я запускаю пример программы на C++ Shell

#include <iostream> 
#include <unordered_set> 
#include <string> 

int main() 

{ 
std::unordered_set<std::string> inputSet; 
inputSet.insert("Hello world"); 
inputSet.insert("Abcdef"); 
inputSet.insert("This is the test string..."); 

for(const auto &val : inputSet) 
    std::cout << val.c_str() << std::endl; 

return 0;} 

это дает мне

This is the test string... 
Abcdef 
Hello world 

И я попытался запустить его в течение 3 или 4 раза, она по-прежнему дает мне тот же результат, который подразумевает, что это способ, которым unordered_set определяет порядок вставки.

Может кто-нибудь объяснить, как unordered_set определить порядок вставки?

Извините, если он был задан раньше, я искал в Интернете какое-то время, и я не могу найти конкретный ответ на этот вопрос. Заранее спасибо.

Answer 1

Нет конкретного заказа ... Он использует по умолчанию std::hash для хэш-строки. И независимо от значения хэш, он преобразуется в соответствующий индекс ковшом в контейнер ..

Значение хеш-функции, мы говорим о том, может быть получено:

auto hello = std::hash<std::string>()("Hello world"); 
auto abcd = std::hash<std::string>()("Abcdef"); 
auto test = std::hash<std::string>()("This is the test string..."); 

Для конкретной реализации STL, это решает чтобы:

Hello maps to: 14420674105493498572 
abcd maps to: 10830572898531769673 
test maps to: 13068738153895491918 

Посмотреть Живите на C++Shell

значение обычно преобразуется в соответствующий индекс ковша по заявл ying % Оператор. Опять же, итератору std::unordered_set не поручено последовательно перебирать все ведра (как насчет столкновений?). Таким образом, вы не должны полагаться на какие-либо заказы, которые вы наблюдаете из итераторов между прогонами программы.

---

От C++ 14, std::hash<> явно разрешено производить различные результаты между работает другая программа.Для того, чтобы quote:

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

Answer 2

Как указано здесь http://en.cppreference.com/w/cpp/container/unordered_set

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

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

Answer 3

Порядок в std::unordered_set<T> является, ну, неупорядоченным. Однако, если используется детерминированный хеш и выполняется один и тот же порядок операций вставки, разные прогоны программы будут иметь элементы в том же порядке. Вставка элементов в другом порядке и/или использование хэша, который создает разные значения для разных прогонов, приведет к другому порядку элементов.