Multimap and counting number of keys

[SCass2010]

Hi everyone again :)

Bit of a weird problem, but is there any way of counting how many keys are stored within a multimap?

Say for example I have the keys A, B, C and D. Each of these keys have say 100 values for each, so there should be 100 instances of A, 100 of B and so on. I know how to count how many pairs there are for the keys, but is there a way of counting how many unique keys there are in the multimap (in this case you should get 4)?

Many thanks in advance :)

[Eagletalon]

Just a shot in the dark... but how about saving the keys in a List... and then removing the duplicates... and running the list through a count?

[SCass2010]

I was thinking something like that, but the other problem is the multimap could have anything from a few hundred values to a few hundred thousand or more, and finding the unique keys would need to be run maybe every few seconds :S

[Eagletalon]

Would the values change at all? otherwise you load on the values and check it initially... and upon a new entry you could add that one in (if it is not yet contained) then there is no need to handle ALL of them EVERY time?

[SCass2010]

Yeah it's pretty confusing so it is, but thanks anyways! Might just be a case of re-thinking what I'm doing sadly lol :(

[vijayan121]

Since std::multimap<> stores the keys in an ordered manner,

#include <map>

template< typename K, typename T, typename C, typename A >
typename std::multimap<K,T,C,A>::size_type num_unique_keys( const std::multimap<K,T,C,A>& mmap )
{
    if( mmap.size() < 2U ) return mmap.size() ;

    const C& cmp = mmap.key_comp() ;
    typename std::multimap<K,T,C,A>::size_type n = 1 ;
    auto prev = mmap.begin()->first ;

    for( auto iter = mmap.begin() ; iter != mmap.end() ; ++iter )
        if( cmp( prev, iter->first ) ) { ++n ; prev = iter->first ; }

    return n ;
}

Obviously, this won't work with std::unordered_multimap<>.

[alwaysLearning0]

@vijayan121 Cool..

Little optimization if there are millions of keys and million of values per keys.

template< typename K, typename T, typename C, typename A >
typename std::multimap<K,T,C,A>::size_type num_unique_keys( const std::multimap<K,T,C,A>& mmap )
{
	if( mmap.size() < 2U ) return mmap.size() ;

	const C& cmp = mmap.key_comp() ;
	typename std::multimap<K,T,C,A>::size_type n = 0 ;
	auto prev = mmap.begin()->first ;

	for( auto iter = mmap.begin() ; iter != mmap.end() ; iter = mmap.upper_bound( iter->first )  )
		++n;

	return n ;
}

EDIT:
Just little bit cleaner version:

template< typename T>
typename T::size_type num_unique_keys( const T& mmap )
{
	if( mmap.size() < 2U ) return mmap.size() ;

	typename T::size_type n = 0 ;

	for( auto iter = mmap.begin() ; iter != mmap.end() ; iter = mmap.upper_bound( iter->first )  )
		++n;

	return n ;
}

[vijayan121]

> Little optimization if there are millions of keys and million of values per keys.

Neat! That's not just a 'little optimzation'; it's a lot more efficient and also more elegant than my feeble effort.

Bravo!

In fact, line 4 is not required; the loop takes care of an empty multi_map<> as well.
Reduces to just three lines:

template< typename K, typename T, typename C, typename A >
typename std::multimap<K,T,C,A>::size_type num_unique_keys( const std::multimap<K,T,C,A>& mmap )
{
    typename std::multimap<K,T,C,A>::size_type n = 0 ;
    for( auto iter = mmap.begin() ; iter != mmap.end() ; iter = mmap.upper_bound(iter->first) ) ++n ;
    return n ;
}