std :: unordered map не хранит записи в порядке возрастания значений хеша

Я использую Visual Studio 2010 и использую функцию C ++ 11 std :: unordered_map :: hash_function () для печати значений хеша, которые вычисляются для каждой из ключевых строк.

Однако я считаю, что внутренне записи хранятся в случайном порядке, а не в порядке возрастания значений хеш-значений.

В приведенном ниже примере папа вычисляет самое низкое значение хеш-функции и должна быть начальной записью my_family_height_map, но это не так. И начальный элемент — это sis-пара, которая вычисляет более высокое хеш-значение, чем папа.

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

// unorderedmap_usage.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"#include <unordered_map>
#include <string>
#include <iostream>

int main()
{
typedef std::unordered_map<std::string, double> height_map;
height_map my_family_height_map;

my_family_height_map["Dad"] = 5.10;
my_family_height_map["Mom"] = 5.3;
my_family_height_map["Sis"] = 5.3;
my_family_height_map["Zach"] = 6.2;

height_map::const_iterator c_it;

// Print everything in the map
for(c_it = my_family_height_map.begin(); c_it!= my_family_height_map.end(); ++c_it)
{
std::cout << "Hash:" << hasher_func(c_it->first) << "  Person is : " << c_it->first << " - height is " << c_it->second << "\n";
}
}

O / P:
Hash: 572570820 Персона: Sis — рост 5.3
Hash: 306541572 человек: папа — рост 5.1
Hash: 1076885014 человек: мама — рост 5,3
Хэш: 2613037907 Персона: Зак — высота 6,2
Нажмите любую клавишу для продолжения . , ,

0

Решение

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

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

1 Технически это называется «неупорядоченным», потому что многие реализации стандартной библиотеки C ++ уже поставляются с типами, называемыми hash_map/set/etc, И комитет не хотел пересекаться с ними.

3

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]