1,105,288 Community Members

Multimap and counting number of keys

Member Avatar
SCass2010
Junior Poster in Training
93 posts since Mar 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
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 :)

Member Avatar
Eagletalon
Junior Poster
135 posts since Mar 2011
Reputation Points: 34 [?]
Q&As Helped to Solve: 16 [?]
Skill Endorsements: 0 [?]
 
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?

Member Avatar
SCass2010
Junior Poster in Training
93 posts since Mar 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
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

Member Avatar
Eagletalon
Junior Poster
135 posts since Mar 2011
Reputation Points: 34 [?]
Q&As Helped to Solve: 16 [?]
Skill Endorsements: 0 [?]
 
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?

Member Avatar
SCass2010
Junior Poster in Training
93 posts since Mar 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
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 :(

Member Avatar
vijayan121
Posting Virtuoso
1,769 posts since Dec 2006
Reputation Points: 1,097 [?]
Q&As Helped to Solve: 329 [?]
Skill Endorsements: 16 [?]
 
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<>.

Member Avatar
alwaysLearning0
Junior Poster
119 posts since Apr 2009
Reputation Points: 39 [?]
Q&As Helped to Solve: 19 [?]
Skill Endorsements: 0 [?]
 
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 ;
}
Member Avatar
vijayan121
Posting Virtuoso
1,769 posts since Dec 2006
Reputation Points: 1,097 [?]
Q&As Helped to Solve: 329 [?]
Skill Endorsements: 16 [?]
 
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 three months: Start a new discussion instead
Post:
Start New Discussion
View similar articles that have also been tagged: