## Featured Replies in this Discussion

- by vijayan121

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