Array with generic index type

Question

Is there any data structure in C++11/STL/Boost which represents an array with a generic index type or do I have to implement such a type on my own?

I.e. I would like to do something like this:

std::set<std::string>> to_lookup, to_lookup2;
int i = 10, j = 13;

// initialization of to_lookup

// count is of the container type/data structure I am looking for
count[to_lookup] = i;
count[to_lookup2] = j;

I know the std::map and std::unordered_map containers from the STL but those do not match my requirements. It is critical for me that insert and look up can be done in O(1).

Answer 1

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.