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 :)

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?

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

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?

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 :(

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<>.

Comments

@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 ;
}

Edited 5 Years Ago by alwaysLearning0: EDIT:Cleaner version

> 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 ;
}
This article has been dead for over six months. Start a new discussion instead.