I would like to store a mapping of an integer key to a float value in-memory.
I have roughly 130 million keys (and, accordingly, 130 million values).
My focus is on lookup performance -- I have to do many, many millions of lookups.
The C++ STL library has a map class for associative arrays of this sort. I have several questions about map.
What is the storage overhead of map for a dataset of the size mentioned above? How does storage overhead scale, in general, with map?
It looks like the underlying data structure for map is a red-black, balanced binary tree. It sounds like the real-world performance for this is O(log n) for insertion and retrieval.
It mentions O(1) for a hinted insertion. My input is pre-sorted, so I believe I should be able to provide a hint for insertion events. How would I provide this hint, using the methods listed here?
Is there an STL container that provides better lookup performance?
Are there other publicly-available, open-source frameworks with an associate array class that uses an underlying data structure that would perform better than STL map?
If writing my own container class would provide better lookup performance, what data structures might I research?
I am using GCC 4 for this task, running under either Linux or Mac OS X.
I apologize in advance if these are dumb questions. Thank you for your advice.