std::unordered_map keeps resulting in error, is this a bug?

Question

So I have this function for hashing internal strings, but when I try to run it Visual Studio 2015 gives me a Debug Assertion Failed! Error:

Program: C:\WINDOWS\SYSTEM32\MSVCP140D.dll
File: c:\program files (x86)\microsoft visual studio 14.0\vc\include\vector
Line: 1232

Expression: vector subscript out of range

Now the first time InternalString gets called I get this error and it breaks on the gStringIdTable.find(sid) line.

static std::unordered_map<StringId, const char*> gStringIdTable;

StringId InternalString(const char* string) {
    StringId sid = std::hash<std::string>()(string);

    std::unordered_map<StringId, const char*>::iterator it = gStringIdTable.find(sid);

    if (it == gStringIdTable.end()) {
        gStringIdTable.insert({sid, string});
    }

    return sid;
}

I thought maybe it was a problem with the way I was initializing the iterator so I figured I'd try this:

if (gStringIdTable.find(sid) == gStringIdTable.end()) {
    gStringIdTable.insert({sid, string});
}

But that gives me the same error. Then I thought maybe it had to do with doing the find before the unordered_map was populated with anything so I tried ONLY doing an insert in the function. But that too gave me the same error. I tried converting the const char* to std::string, and then only dealing with strings in the unordered_map at this answer's suggestion, but got the same error. I tried using emplace instead of insert, tried using std::make_pair, but all combinations to no avail.

Now, am I missing something obviously wrong, or is there bug somewhere?

Update

Okay so here is a compiling version where I still get the error. I started an empty c++ project in visual studio 2015 and added these 3 files to match how it is currently implemented in my project:

main.cc

#include "stringid.h"

const static mynamespace::StringId kSidOne = mynamespace::InternalString("One");

int main(int argc, char *argv[]) {
    return 0;
}

stringid.cc

#include "stringid.h"
#include <string>
#include <unordered_map>

namespace mynamespace {

static std::unordered_map<StringId, std::string*> gStringIdTable;

StringId InternalString(const char* string) {
    StringId sid = std::hash<std::string>()(string);

    if (gStringIdTable.find(sid) == gStringIdTable.end()) {
        gStringIdTable.emplace(sid, new std::string(string));
    }

    return sid;
}

} // mynamespace

string.h

#ifndef STRINGID_H_
#define STRINGID_H_

namespace mynamespace {

typedef unsigned int StringId;
StringId InternalString(const char* string);

} // mynamespace

#endif // STRINGID_H_

I also did some debugging into the functions to see if I could figure out where the problem is arising from and it looked like when the find function grabs the relevant bucket it returns null or 0 and then the _Begin function throws and error because the size is equal to zero.

Small Update

I also tried compiling with gcc. It compiles fine, but I still get an error on find().

Answer 1

You're keying the hash table with... a hash.

That's an error. The hash is not unique.

What you want to do is to key the hash table with... a key!

How the table hashes is an implementation detail and you shouldn't see on the outside.

Simplest way to fix this would be to e.g. use std::unordered_set<std::string>.

Live On Coliru

#include <unordered_set>

const char* InternalString(const char* string) {
    static std::unordered_set<std::string> s_table;
    std::unordered_set<std::string>::iterator it = s_table.find(string);

    return (it != s_table.end())? it->c_str() : s_table.insert(string).first->c_str();
}

#include <cassert>

int main() {
    auto a = InternalString("HelloWorld" + 5);
    auto b = InternalString("World");

    assert(a == b);
}

The assert verifies ok, since World and World match, even though the raw pointer was different.

You can make this a lot more efficietn (by e.g. using some set with a custom key comparator)