STL Map versus Static Array

Question

I have to store information about contents in a lookup table such that it can be accessed very quickly.I might need to refer some of the elements in look up table recursively to get complete information about contents. What will be better data structure to use:

1. Map with one of parameter, which will be unique to all the entries in look up table, as key and rest of the information as value
2. Use static array for each unique entries and access them when needed according to key(which will be same as the one used in MAP).

I want my software to be robust as if we have any crash it will be catastrophic for my product.

Answer 1

It depends on the range of keys that you have.

Usually, when you say lookup table, you mean a smallish table which you can index directly ( O(1) ). As a dumb example, for a substitution cipher, you could have a char cipher[256] and simply index with the ASCII code of a character to get the substitution character. If the keys are complex objects or simply too many, you're probably stuck with a map.

You might also consider a hashtable (see unordered_map).

Reply:

If the key itself can be any 32-bit number, it wouldn't make sense to store a very sparse 4-billion element array.

If however your keys are themselves between say 0..10000, then you can have a 10000-element array containing pointers to your objects (or the objects themselves), with only 2000-5000 of your elements containing non-null pointers (or meaningful data, respectively). Access will be O(1).

If you can have large keys, then I'd probably go with the unordered_map. With a map of 5000 elements, you'd get O(log n) to mean around ~12 accesses, a hash table should be pretty much one or two accesses tops.

I'm not familiar with perfect hashes, so I can't advise about their implementation. If you do choose that, I'd be grateful for a link or two with ideas to keep in mind.