Tradeoffs between multi and non-multi associative containers

[Dave]

Hello NG,

Why would one not just always use std::multiset<> instead of std::set<> (and
similarly for maps)? Clearly, there must be tradeoffs to gain the ability
to have repeated keys. What are the tradeoffs?

Thanks,
Dave

 

[Christopher Benson-Manica]

Why would one not just always use std::multiset<> instead of std::set<> (and
similarly for maps)? Clearly, there must be tradeoffs to gain the ability
to have repeated keys. What are the tradeoffs?

I think the specific tradeoffs are related to QOI, whatever they might
be. There may well be times when you specifically do NOT want the
semantics of a std::multiset, I imagine.

 

[Andrey Tarasevich]

...
Why would one not just always use std::multiset<> instead of std::set<> (and
similarly for maps)? Clearly, there must be tradeoffs to gain the ability
to have repeated keys. What are the tradeoffs?
...

In certain applications one might specifically require the functionality
of 'std::set', not 'std::multiset'. For example, one might want to use a
simple combination of 'std::copy', 'std::inserter' and 'std::set' in
order to generate a set of unique elements in a given sequence (say,
'std::vector'). 'std::mutliset' isn't immediately applicable in this case.

 

[Kevin Goodsell]

Hello NG,

Why would one not just always use std::multiset<> instead of std::set<> (and
similarly for maps)? Clearly, there must be tradeoffs to gain the ability
to have repeated keys. What are the tradeoffs?

I don't know for sure, but I definitely use the non-multi versions more
frequently. I think the code would be more complicated using multimaps
when maps do the job. For example, you don't get operator[].

Consider looking up a single element. In a map, it's either found or
not. In a multimap, if it's found, you still might need to check whether
there are others.

Consider storing a unique key-value pair. In a map you just do it. In a
multimap, you have to first look up and remove any existing matching keys.

-Kevin