multimap vs map with set

Question

I'm wondering which is more efficient.

std::map< String, std::set<int> >

or

std::multimap< String, int >

EDIT: I do not plan on doing anything out of the ordinary with these maps. Standard insert, delete, modify, search. The size of each set or multi keyed String shouldn't be more than 100.

What are the operations that you want to perform? That will define the different costs, as the first approach will allow you to perform fast lookups by both string and integer and the second will require you to iterate and test the int part against each value for which the string is the same... But if you do not need that operation, it might be the case that the second option is better in some use cases... — David Rodríguez - dribeas, Sep 08 '11 at 16:13
The two aren't equivalent: The multimap can store multiple copies of `("foo", 1)`, the map+set cannot. — Kerrek SB, Sep 08 '11 at 16:18
Is there any particular reason, do we think, that today on SO has been filled with these "which is more efficient" container-related questions, one after another after another after another.... — Lightness Races in Orbit, Sep 08 '11 at 16:21
I will mostly be looking up a String and traversing every integer associated to that String. I was wondering if there were any glaring differences or things to watch out for comparing the two containers. — Kaiser Wilhelm, Sep 08 '11 at 16:35
@Kaiser: The last comment is what should be in your question: the fact that you are looking strings, and then iterating over *all* of the contained elements means that (and again, depending on usage patterns, i.e. if there are no repeated integers) there is no clear advantage in the `map>` over the second alternative, and then again, a `map>` might be better in some scenarios or worse in others... It is impossible to judge without knowing the problem. — David Rodríguez - dribeas, Sep 08 '11 at 16:45
Possible duplicate of [What's the difference between std::multimap and std::map >](http://stackoverflow.com/questions/8602068/whats-the-difference-between-stdmultimapkey-value-and-stdmapkey-stds) — Ciro Santilli OurBigBook.com, Dec 31 '16 at 22:03

score 12 · Accepted Answer · answered Sep 08 '11 at 16:12

This I believe is implementation dependant, but an (un)educated guess:

In practice it depends on the number of integers that you will be keeping in the multimap or the std::set. A multimap will most likely use a linear search of the values after the log(n) search of the key. If you have a large number of integer values, then the log(n) search of the keys followed by a log(n) search of the values may be slightly faster.

However, in terms of efficiency, storing anything in a map or multimap with a string key will almost certainly outweigh the differences in either case.

As said below, a multimap will likely be easier to use and more clear to maintain giving it a distinct advantage.

score 6 · Answer 2 · answered Jan 29 '13 at 16:11

6

The "set" option will eliminate the key+value pairs duplications, whether the multimap won't.

answered Jan 29 '13 at 16:11

Pedro Reis

1,587
1
19
19

score 5 · Answer 3 · answered Nov 22 '17 at 13:44

They are actually not equivalent anyway. A multimap<X,Y> allows storing duplicate key-value pairs, whereas a map<T, set<X>> does not.

multimap<int, int> m;
m.insert(make_pair(2, 3));
m.insert(make_pair(2, 3)); // This changes the size of m!

Whereas

map<int, set<int>> m;
m[2].insert(3);
m[2].insert(3); // This does nothing.

So I would use the set approach unless you need duplicate key-value pairs. The syntax is also nicer. I expect the difference in performance and memory use is not that great.

That should be the accepted answer. It makes no sense to talk about efficiency of things which do different things. — Andreas Pasternak, Feb 22 '20 at 18:36

score 2 · Answer 4 · answered Sep 08 '11 at 16:34

If you're not happy with those answers so far (not saying that you are not) and I am absolutely forced to answer, I'll give my educated "guess" too:

To insert, the multimap appears to be more "efficient". With the map approach, you first have to retrieve, then perform operation on the set. To delete/retrieve, map seems more "efficient".

score 1 · Answer 5 · answered Sep 08 '11 at 16:11

I can't say for sure but given that multimap was designed to do what the other is an expression of, it should be better to be specific and use the multimap, it makes a lot more sense, it also has member functions for working with a multimap as a concept, those functions would be a bit funky using the other approach.

score 1 · Answer 6 · answered Sep 08 '11 at 16:13

1

std::multimap< String, int > is most likely more memory efficient.

answered Sep 08 '11 at 16:13

Man Vs Code

1,058
10
14

The number of numbers stored is the same in both but because you are using two red black trees you are using twice the number of "book keeping" strctures than neccessary. Furthermore, given that most std::string STL implementations use reference counting and copy on write semantics, the data used by the strings may not be doubled. Hope this makes sense as i type this on my phone. – Man Vs Code Sep 08 '11 at 16:46
1

Actually, you haven't proven that a map and sets take up more space than a multimap (what about multimap's _additional_ bookkeeping?), but in fact you'll be storing a lot more than two trees. And that these are implemented as trees is not specified. And there is no `std` namespace in the STL. And, really, my comment was intended to provoke you into adding a rationale to your _answer_ ;) – Lightness Races in Orbit Sep 08 '11 at 16:49
1

No std namespace in the STL? Thats a new one for me. std::multimap is usually implemented with a red-black tree using opetator<=. std::set is also usually a red black tree but with operaror<. Fact is, its implementation dependent but on PCs what I've said is generally true. – Man Vs Code Sep 08 '11 at 16:59
You may be confusing the STL with the C++ Standard Library. – Lightness Races in Orbit Sep 08 '11 at 17:00

multimap vs map with set

6 Answers6

Linked