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.

Answer 1

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.