0

I have a dilemma of whether to have a multimap <int key, int value> or maintain a vector containing a vector of all values corresponding to int key.

I'm interested in which performs faster when looking up the values for a certain int key.

2
  • 3
    Did you try both and profile the results with some typical data from your domain?
    – Mankarse
    Sep 8, 2011 at 9:55
  • I've only just recently tried to use a profiling tool AMD CodeAnalyst, and still I'm not quite proficient with it. Sorry, but I'm new in this world. :/
    – vedran
    Sep 8, 2011 at 10:36

5 Answers 5

4

If you want a multimap and not just a map, the alternative will probably be a vector< list<int> > or something like that (a multimap, being generally implemented as an RB tree that allows multiple equivalent keys, is somewhat akin to a map with a list element type).

In general, a vector lookup is faster: it's O(1) for the array vs O(log n) for the map (in both case I'm not counting the search into the list/vector/set/whatever is used for the "multi" part). But, to use the vector, you have to make it as big as the biggest int key you want to use; if your keys are sequential this is not a problem, but if your index is sparse the multimap can be a better choice.

On the other hand, if you don't need ordered traversal, unordered_multimap (which is actually a hash table) could be the best of both worlds: you get array-like O(1) lookup without having to keep an enormous empty array.

2
  • 1
    Based on what I've read, a multimap is not more or less a map with a list element. Rather, it tends to be implemented as a RedBlack Tree. May 7, 2020 at 22:20
  • Yep, both map and multimap are generally an RB tree, only with multimap being allowed to have multiple keys with the same value. IDK if, when writing this answer, I already knew that, or if that was a "simplifying" lie (as in, as each node of the RB tree is generally stored on its own, the equivalent elements are in a linked list, in a manner of speaking); anyhow, I'll make it explicit in the answer. May 8, 2020 at 8:02
4

Forget which is "faster". You can profile it later, but don't obsess over this. Far more important is that one approach gives you sparse storage, and the other does not -- focus on this and decide which is the most appropriate for your problem.

2

I would say if your keys are sequential go with the vector, but if there are big holes in your keys then the map will be better (as you won't have to store "empty" records as in your vector), plus it will make it easier to count how many records you have etc. Performance wise vectors are based on arrays so lookups are generally faster (as maps have to go through a few pieces of data to do a lookup).

1

I would recommend map<int, vector<int>>

Since once you have done the search in the map you have a vector with all the values.

Otherwise you solution will require a new search of each value

4
  • 2
    multimap has the equal_range function, so you do not need a new search for each value.
    – Mankarse
    Sep 8, 2011 at 10:02
  • This is not quite true. A typical implementation is a tree structure so the equal range function just traverses the tree from a given starting point.
    – Ed Heal
    Sep 8, 2011 at 10:10
  • @EdHeal: What's wrong with traversing the tree from a given starting point? If it's slower than iterating through the vector, it's only marginally so. Sep 8, 2011 at 10:16
  • Eventhough this is a valid proposal, don't forget that updating the vector can be quite costly.
    – stefaanv
    Sep 8, 2011 at 11:29
1

I guess you are doing premature optimization. It's not good because you should optimize only after everything is working with use of profilers. Don't waste time and use a specialized container for your needs.

3
  • 2
    To some extent, sure. Though don't leave profiling too late, because if you picked the wrong container and your code isn't easily modular with containers, then you're going to have a nightmare changing it later. You should pick the correct container for the job and, sometimes, thinking in terms of "speed" (actually complexity growth) can help you to realise what the correct container for the job is. Sep 8, 2011 at 10:17
  • Herb Sutter wrote about this in his 101 advices. Your code must be based on abstractions but not on details like containers. So in future refactor it'll be aesy to change the concrete container
    – Camelot
    Sep 8, 2011 at 10:32
  • Right, and what data model you choose is very much a part of those abstractions... even if the specific type in code is not. Sep 8, 2011 at 10:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.