c++11 - Contiguous associative container : what would be the fastest implementation? -

after 2 months of applied maths research, have found way have substantial gains manage data in application domain (to published...). in short, application domain requires associative container, contiguous in memory avoid cache misses in large scale supercomputing applications. fast insertions , deletions not priority : priority have fastest possible binary search on keys via std::upper_bound. have working implementation, thinking implementing stl-like container design.

so, associative container has following properties:

• it contains between 10 , 100 millions of keys , values
• keys unsigned integers of 8, 16, 32, 64 or 128 bits
• values tuples of ~10 different types
• each key associated single value
• the critical operation binary search on keys (probably via call std::upper_bound)
• insertions/deletions/sorting not critical

so question is: best internal implementation (of course run benchmarks, discarding possibilities great):

1. std::vector<std::pair<key, type>> iterators std::pair<key, type>
2. std::pair<std::vector<key>, std::vector<type>> iterators std::pair<key&, type&>
3. other solutions ?

what best solution ? remarks or ideas appreciated...

for similar application you, i've had success open hash scheme.

a "closed hash" maintains list of objects map each hash value. collisions result in list growth, lists distinct heap objects poor cache locality.

an open hash goes same array. cpu caches.

for performance, use "perfect hash"-like function avoids scrambling data , minimizes randomness. instead try find , preserve temporal locality of items accessed close together, mapping spatial locality.

such optimized hash still need uniform on range, though. used pre-analysis step, randomly sampling domain compute hash function. addition of such complexity needs driven knowing how time being spent on cache misses in first place.