Почему мой unordered_map упорядочивает себя?

Question

Итак, я играл с новым стандартизированным unordered_map из STL.Код, который у меня есть, выглядит примерно так: я просто создаю unordered_map, заполняю его и распечатываю:

    unordered_map<int,string> m1;

    m1[5]="lamb";
    m1[2]="had";
    m1[3]="a";
    m1[1]="mary";
    m1[4]="little";
    m1[7]="fleece";
    m1[6]="whose";
    m1[10]="fleecey";
    m1[8]="was";
    m1[9]="all";

for(unordered_map<int,string>::const_iterator i = m1.begin(); i != m1.end(); ++i)
cout<<i->first<<" "<<i->second<<endl;

Однако полученный вывод упорядочен следующим образом:

1 mary
2 had
3 a
4 little
5 lamb
6 whose
7 fleece
8 was
9 all
10 fleecey

Но я не хочу платить цену за заказ моей карты!Вот почему я использую unordered_map ... Что здесь происходит?

дополнительное примечание: я использую gcc version 4.3.4 20090804 (release) 1 (GCC) и собираю вот так g++ -std=c++0X maptest.cpp

Answer 1

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

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

Answer 2

Для вашего удовольствия, вот вывод из libc ++, который также имеет функцию идентификации для std::hash<int>.

9 all
8 was
10 fleecey
6 whose
7 fleece
4 little
1 mary
3 a
2 had
5 lamb

Существует несколько способов реализации хеш-контейнера, каждый из которых имеет свои собственные компромиссы.