3

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".

Edit: As pointed out by the Boost documentation about flat_(multi)map/set, Matt Austern, not Scott Meyers first suggested replacing maps and sets with vectors: http://lafstern.org/matt/col1.pdf

Deduplicator
  • 44,692
  • 7
  • 66
  • 118
Gabriel
  • 2,841
  • 4
  • 33
  • 43
  • I had a look at boost::zip_iterator, but one can't sort() two vectors with a zip_iterator : http://stackoverflow.com/questions/9343846/boost-zip-iterator-and-stdsort – Gabriel Nov 25 '12 at 21:11

2 Answers2

2

Maybe you are looking something like flat_(multi)map/set from Boost.Container ?

Eugene Mamin
  • 749
  • 4
  • 8
  • 2
    This is very interesting. However, I see that flat_map uses flat_tree, which is a vector. I'd like to have two separate vectors, so that the keys are even closer in memory. This way, values won't have to be brought to a lower (closer to the CPU) cache level when searching. – Gabriel Nov 06 '12 at 11:32
  • I rolled my own, but oddly flat_map is faster for my particular use. No thorough benching though. It also has the advantage to be boost, that is, tested, algorithm-compatible, etc. – Gabriel Nov 28 '12 at 10:09
0

You should look into std::make_heap and associated functions, which manages a collection as a sorted heap. It fits almost perfectly your requirement of fast, unsorted inserts, and quick retrieval from a sorted collection.

Daniel Gehriger
  • 7,339
  • 2
  • 34
  • 55