multiset unique values count

[dushkin]

Hi
I wish someone can give a tip on this one..
http://groups.google.co.il/group/comp.lang.c++/browse_thread/thread/1da69b779019d7c4/d060bace91a1830?hl=iw&ie=UTF-8&oe=utf-8&q=multiset+unique+elements+counting#0d060bace91a1830
Thanks!

[tonydee]

On Feb 4, 5:09 pm, dushkin <talt...@gmail.com> wrote:
> Is it possible to know (without iterating ofcourse) how many
> unique keys are in a multiset?
> I know that a set has unique values, but I would prefer
> using multiset in my solution if I have the unique keys
> counting solution.
>
> Example:
>
> Given a multiset with values: {1,1,2,4,5,4,3,1} - The unique
> counting will give me 5 for {1,2,3,4,5} keys.

> A indirect solution may be adding the multiset items to a
> set and then get the set size..
> But I wonder if there is a direct way of getting the unique
> items number

STL's multisets do not have any special support for this, i.e. they
don't spend time / use extra memory to track the unique keys while the
values are being inserted. Therefore, you must either proactively
maintain your own count while inserting and erasing from the multiset
(e.g. insert: check if the multiset includes the key, add 1 to
unique_keys counter if not). Otherwise, you will need to step through
the container to count unique keys... using upper_bound() will skip to
the next key, which just might be faster than a simple iteration, but
could also be slower (may depend on average number of times a key
repeats).

Cheers,
Tony