hash_map сохраняет каждую пару ключ / вал, даже если ключи равны - PullRequest
Новая
       11

hash_map сохраняет каждую пару ключ / вал, даже если ключи равны

1 голос
/ 17 ноября 2010

Эй, ребята, я использую hash_map для связи строк друг с другом, с помощью этого кода: 

#include <string>
#include <iostream>
#include <hash_map>

using namespace std;
using namespace stdext;

struct StrCompare : public stdext::hash_compare<string> {
 unsigned int operator()(const string str) const {
  unsigned int hash = 0;
  unsigned int len = str.length();

  for (unsigned int i = 0; i < len; i++)
   hash = 31 * hash + str[i];

  return hash;
 }

 bool operator()(const string str1, const string str2) const {
  return str1 == str2;
 }
};

int main() {
 hash_map<string, string, StrCompare> m;

 m["asdf"] = "fe";
 m["asdf"] = "asdf";

 for (hash_map<string, string, StrCompare>::iterator i = m.begin(); i != m.end(); ++i)
  cout << i->first << " " << i->second << endl;

 system("PAUSE");
}

Проблема в том, что вывод: 

asdf asdf
asdf fe
Press any key to continue . . .

Почему это происходит? Я пробовал печатать хэши каждый раз, но хэш такой же.

Ответы [ 3 ]

2 голосов
/ 17 ноября 2010

Одна из причин, по которой hash_map не вошел в C ++ 0x, заключается в том, что было несколько противоречивых реализаций, и мало что было в смысле твердой спецификации.

Я бы переключился начто было принято в C ++ 0x вместо.std::unordered_map может иметь длинное, неуклюжее имя, но семантика четко определена;он будет не хранить дубликаты ключей (для этого вместо этого вы будете использовать std::unordered_multimap).

0 голосов
/ 17 ноября 2010

Из некоторых деталей вашего примера видно, что вы используете MSVC.Microsoft hash_map использует функцию сравнения, которая работает в сочетании с хэш-функцией, чтобы упорядочить ключи, которые хэшируют с тем же значением.Это отличается от спецификации SGI hash_map.В частности (от http://msdn.microsoft.com/en-us/library/1s1byw77.aspx):

Для любого значения _Key1 типа Key, которое предшествует _Key2 в последовательности и имеет такое же хеш-значение (значение, возвращаемое хеш-функцией), hash_comp(_Key2, _Key1) имеет значение false. Функция должна наложить полный порядок значений типа Key. Функция, предоставляемая hash_compare, возвращает comp(_Key2, _Key1), где comp - это сохраненный объект типа Traits, который можно указать при созданииобъект hash_comp. Для стандартного Traits типа параметра less<Key> ключи сортировки никогда не уменьшаются в значении.

Так что при изменении функции сравнения на возвращение str1 != str2, кажется, работает для вашегоtest, это не совсем правильно. Это может запутать hash_map в ситуации, когда две разные строки имеют одинаковый хеш-код.

0 голосов
/ 17 ноября 2010

О, очевидно, я неправильно использую функцию 

bool operator()(const string str1, const string str2) const

.Вместо 

bool operator()(const string str1, const string str2) const {
    return str1 == str2;
}

должно быть 

bool operator()(const string str1, const string str2) const {
    return str1 != str2;
}
...