0

I was wondering in which cases to use a multimap rather than a map of sets.

Say I have a bunch of tuples that consist of <[0-9],[0-9]+>. So, they have 0-9 on the left and 0 - unlimited on the right.

I could now make a map and have the left side of the tuples as the key. The value would be a set of the right sides of all the tuples that have the same left side. This way I would have log(10) lookup time for the left and in case of an unordered set “hash-time” lookup time for the right side. I don't know how multimaps work internally... so, assuming they put all right sides in a vector and then do binary search on it that would be worse that hash-tiem lookup (provided a good has function)... but I don’t know how they work. So, in cases like this, what is the better choice? What takes less time, what uses less memory?

And I know this has been asked already for example here: multimap vs map with set

But my question is more specific, as the left side of the tuples is very restricted in variance and also the answers in that thread contain a lot of guessing about the implementation of multimaps.

Edit

So to go with the numbers example I could have <2, 928947>. Specifically I need this for strings though, to store a grammar for a parser, which needs to lookup rules by their left hand side.

Community
  • 1
  • 1
lo tolmencre
  • 3,804
  • 3
  • 30
  • 60
  • Can you add example to your question - what you want to have in your container - just a few entries – PiotrNycz Sep 25 '15 at 20:52
  • 1
    Under the circumstances, it seems to me that you'd be better off with `std::vector> s(10);` I don't see any benefit from using anything set-like given that the only keys are 0..9. You might, however, want to just create a trie of some sort. – Jerry Coffin Sep 25 '15 at 20:54
  • well... I need it to be be scalable. I know the left side will always have a lower variance than the right, but the variance could be larger than 10 and not necessarily be integers. – lo tolmencre Sep 25 '15 at 21:01

0 Answers0