2013-09-06 2 views
0

Для моей программы мне нужен неупорядоченный ключ. Чтобы выполнить эту работу, я использую контейнер std :: unordered_map. Вот тестовый код:Различное поведение с контейнером std :: unordered_map в Windows и Linux

#include <iostream> 
#include <unordered_map> 
#include <string> 

int main() 
{ 
    std::unordered_map<std::string, int> toto; 

    toto["Outlook"] = 454; 
    toto["Temperature"] = 4; 
    toto["Humidity"] = 554; 
    toto["Wind"] = 545454; 

    std::unordered_map<std::string, int>::iterator It = toto.begin(); 

    std::cout << toto.size() << std::endl; 

    for (; It != toto.end(); ++It) 
     std::cout << (*It).first << std::endl; 
    getchar(); 
    return (0); 
} 

На окнах (Visual Studio 2012) выводе является:

Outlook 
Temperature 
Humidity 
Wind 

Это правильно. Ни один вид не применялся.

Но на Linux вывод заключается в следующем:

Humidity 
Outlook 
Wind 
Temperature 

PS: В Linux я скомпилировать свою программу с -std :: C++ 0x и -std = Gnu ++ 0x и нет компиляции ошибка.

Итак, как можно вести себя по-разному с одной и той же программой? Заранее благодарим за помощь!

+20

Это неупорядоченный. Почему вас беспокоит заказ? – chris

+1

@chris Насколько я знаю, unordered_map использует хеш-результат как индекс элемента во внутреннем контейнере. Итераторы 'std :: unordered_map' являются итераторами этого контейнера, поэтому, когда вы выполняете trasversal через unordered_map, вы действительно транслируете этот внутренний контейнер. Итак, ** разные заказы означают разные результаты хеширования или разные политики распределения ** ** – Manu343726

+0

@chris Моя точка зрения (и цель задачи ОП, я думаю): ** Почему две версии (исполнения) имеют разные порядки? ** Thats interesting – Manu343726

ответ

6

unordered_map обычно (читать практически всегда) реализуется с помощью хэш-таблицу, которая по умолчанию использует std::hash для выбора ведро поместить предмет в.

Есть много различных хэш-функции, так что то, что вы видите, что реализация двух разных стандартных библиотек std::hash в Windows и Linux использует две разные функции хэша - которые производят разные хеш-коды, которые, в свою очередь, производят разное размещение ковша и, следовательно, разные порядки при повторе.

Я бы потратил некоторое время на изучение hash table data structure вообще, если вы не понимаете, что это значит. Хеширование - действительно классный и полезный математический инструмент во многих аспектах программирования.

+1

Кроме того, даже с той же функцией хэша и хеш-значением, текущее количество ковшей также влияет на размещение элемента. – PlasmaHH

+0

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

4

Как следует из названия (unordered_map) - контейнер неупорядочен. Никто не дает никаких гарантий относительно того, какой порядок пунктов будет и по-настоящему - каждая реализация имеет другой порядок.