multiset unique elements counting

[dushkin]

Hi all.

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.

Thanks!

[dushkin]

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.

[darshan...@gmail.com]

בתאריך יום שלישי, 2 בפברואר 2010 בשעה 15:11:41 UTC+5:30, מאת dushkin:

TRY USING A SET ALONG WITH A MULTISET, JUST FOR GETTING COUNT OF UNIQUE ELEMENTS IN THAT MULTISET

[Bonita Montero]

template<typename T>
std::size_t unique_in_multiset( std::multiset<T> const &s )
{
using namespace std;
using ms = multiset<T>;
using ms_it = typename ms::const_iterator;
ms_it itFirst, itIncr, itNext;
size_t c = 0;

for( itFirst = s.begin(); itFirst != s.end(); ++c, itFirst = itNext )
for( itIncr = itFirst, ++itIncr, itNext = itIncr;
itNext != s.end() && *itNext == *itFirst; ++itNext );
return c;
}

[Bonita Montero]

A bit simpler:

template<typename T>
std::size_t unique_in_multiset( std::multiset<T> const &s )
{

typename std::multiset<T>::const_iterator itFirst, itIncr, itNext;

size_t c = 0;

for( itFirst = s.begin(); itFirst != s.end(); ++c, itFirst = itNext )

for( itNext = itFirst; ++itNext != s.end() && *itNext == *itFirst; );
return c;
}

[Paavo Helde]

> בתאריך יום שלישי, 2 בפברואר 2010 בשעה 15:11:41 UTC+5:30, מאת dushkin:
>> Hi all.
>>
>> 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.

You need to iterate as this information is not maintained by
std::multiset. However, the iteration can be hidden in a std algorithm,
e.g.:

int CalcUniq(const std::multiset<int>& x) {
if (x.empty()) {
return 0;
} else {
int prev = *x.begin();
return std::accumulate(std::next(x.begin()), x.end(), 1,
[&prev](int sum, int k) {
int diff = (k != prev); prev = k; return sum + diff; });
}
}

Another option is to make a wrapper class around multiset which keeps
account of the number of unique elements.

[Alf P. Steinbach]

For the most common use case better use a `std::unordered_map<key,
int>`, where the `int` value is a count of occurrences. Define
appropriate operations. There.

`multiset` generally supports too much, like keys that are distinct in
some sense other than the set's ordering relation, so that keeping a
simple count per distinct key value doesn't suffice.

`multiset` also supports too little, like, no count of
ordering-relation-distinct keys.


Cheers & hth.,

- Alf