This is basically almost impossible to become significantly faster if you're using std::unordered_map
already simply due to the fact that there's always some overhead based on the number of elements (so you can't get a perfect O(1) (unless you're able to reference all possible keys as indexes in an array)).
However, if you still think that a std::unordered_map
is too slow simply due to the sheer amount of entries, try adding another layer reducing the number of elements in a map.
In your example, using std::string
as keys(?), you could just use the very first character (untested but should work):
std::vector<std::unordered_map<const std::string, myWhateverType> > container(256);
// To access an element, this just adds one more layer:
container[key[0]][key] = value;
Iterating over all elements becomes a bit more complicated though. However, this essentially reduces the number of elements in your std::unordered_map
to 1/255 (depending on the actual distribution of key values of course; if all keys start with something such as key
, then you won't gain anything other than a small overhead).
Will it improve performance? This really depends on the number of entries and your keys.