hash_map is saving each key/val pair even when keys are equal

Hey guys, I am using a hash_map to relate strings to one another, with this code:

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

using namespace std;
using namespace stdext;

struct StrCompare : public stdext::has开发者_运维知识库h_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");
}

The problem is that the output is:

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

Why is this happening? I have tried printing the hashes each time, but the hash is the same.

---

One of the reasons hash_map didn't make it into C++0x is that there were a number of conflicting implementations, and little in the way of solid specification.

I'd switch to what was accepted into C++0x instead. std::unordered_map may have a long, clumsy name, but the semantics are well-defined; it will not store duplicate keys (for that you'd use std::unordered_multimap instead).

---

From some of the details of your example, it looks like you're using MSVC. Microsoft's hash_map uses a comparison function that works in conjunction with the hash function to provide an ordering for keys that hash to the same value. This is different than SGI's specification of hash_map. Specifically (from http://msdn.microsoft.com/en-us/library/1s1byw77.aspx):

For any value _Key1 of type Key that precedes _Key2 in the sequence and has the same hash value (value returned by the hash function), hash_comp(_Key2, _Key1) is false. The function must impose a total ordering on values of type Key. The function supplied by hash_compare returns comp(_Key2, _Key1), where comp is a stored object of type Traits that you can specify when you construct the object hash_comp. For the default Traits parameter type less<Key>, sort keys never decrease in value.

So while changing the comparison function to return str1 != str2 seems to work for your test, it's not really correct. It'll confuse the hash_map in the situation where two different strings happen to have the same hashcode.

---

Oh, apparently I'm using the

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

function wrong. Instead of

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

it should be

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