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]

Re: Tradeoffs between multi and non-multi associative containers

Dave <better_cs_now@ yahoo.com> spoke thus:
[color=blue]
> 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?[/color]

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.

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cybers pace.org | don't, I need to know. Flames welcome.

[Andrey Tarasevich]

Re: Tradeoffs between multi and non-multi associative containers

Dave wrote:[color=blue]
> ...
> 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?
> ...[/color]

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.

--
Best regards,
Andrey Tarasevich

[Kevin Goodsell]

Re: Tradeoffs between multi and non-multi associative containers

Dave wrote:
[color=blue]
> 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?
>[/color]

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
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.