I'm looking for a lib that would implement something similar to std::map and multimap, but without tree but vectors instead, like a
pair<vector<key>,vector<value>>. The lib would have to keep the vectors synchronized and sorted.
I'd like to compare the performance of maps,
vector<pair<key,value>> and such a lib. I'm not going to try to make a general benchmark, I only want what's faster for my application.
I could just use map like everyone else, but -and I don't know I'm talking about- I fear for too many cache misses. My wild, uneducated guess is that my app, doing few, grouped inserts and many scattered searches, would benefit from more compact and contiguous keys.
As a matter of fact, if I was to code the thing, I'd do it with two classes. An unsorted version with only fast, push_back inserts permitted, then a transformation into a sorted version that would take the unsorted version, sort it, maybe check for duplicity, and then allow fast searches and slower, sorted inserts. This is actually Scott Meyers' Effective STL's Item 23: "Consider replacing associative containers with sorted vectors".