1.11M Members

Multimap and counting number of keys

 
0
 

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

 
0
 

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?

 
0
 

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

 
0
 

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?

 
0
 

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

 
1
 

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

 
0
 

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

> 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 ;
}
You
This article has been dead for over six months: Start a new discussion instead
Post:
Start New Discussion
View similar articles that have also been tagged: