Distinct keys in the multimap

[Przemek]

All,

what is the efficient way to find all distinct keys in a multimap.
I use the code

template<class T1, class T2>
set<T1> GetDistinctKeys(multimap<T1, T2> nMap)
{
T1 temp;
multimap<T1, T2>::iterator i_ptr;
set<T1> lSet;

for(i_ptr=nMap.begin(); i_ptr!=nMap.end(); ++i_ptr)
{
lSet.insert(i_ptr->first);
}

return lSet;
}

but perhaps you have some fresh ideas

Pshem

 

[Ron Natalie]

but perhaps you have some fresh ideas

You could copy all the keys into a set, though I'm not sure
that would be any better than your approach. I guess it depends
what you want to do with the container full of keys when you get done.

 

[Dietmar Kuehl]

what is the efficient way to find all distinct keys in a multimap.

Use a version of the standard library 'unique()' algorithm:

/**/ template <typename T1, typename T2>
/**/ struct pred {
/**/ typedef typename std::multimap<T1, T2>::value_type value_type;
/**/ bool
/**/ operator()(value_type const& v1, value_type const& v2) const {
/**/ return v1.first == v2.first;
/**/ }
/**/ };
/**/
/**/ template <typename T1, typename T2>
/**/ std::vector<T1>
/**/ get_distinct_keys(std::multimap<T1, T2> const& nMap)
/**/ {
/**/ std::vector<T1> distinct;
/**/ std::unique_copy(nMap.begin(), nMap.end(),
/**/ std::back_inserter(distinct),
/**/ pred<T1, T2>());
/**/ return distinct;
/**/ }

After writing this code, I realized that this does not really
do the trick: this tries to assign a pair to a value. It would
be necessary to use an iterator projecting the 'first' component
of the 'std::multimap's 'pair'. I think Boost
(<http://www.boost.org/>) has such iterators. Alternatively,
you could use 'std::transform()' to do the projection first and
then eliminate duplicate keys using 'std::reserve()' on the
container prior to returning it. However, this assumes that the
number of keys removed is relatively small compared to the
total number of keys. Otherwise, the projection approach is
probably preferable.

BTW, THE approach to returning sequences is not by returning
some sequence but rather to accept an output iterator as
argument.

 

[Mike Wahler]

All,

what is the efficient way to find all distinct keys in a multimap.
I use the code

template<class T1, class T2>
set<T1> GetDistinctKeys(multimap<T1, T2> nMap)
{
T1 temp;
multimap<T1, T2>::iterator i_ptr;
set<T1> lSet;

for(i_ptr=nMap.begin(); i_ptr!=nMap.end(); ++i_ptr)
{
lSet.insert(i_ptr->first);
}

return lSet;
}

but perhaps you have some fresh ideas

Look at 'std::unique_copy' (or if you want to remove the
duplicates from your multimap, 'std::unique').

Depending upon what your ultimate goal is, 'unique_copy'
might be want you want (if you want to store the unique
values in some container type other than a set, you won't need
to use an intermediate 'set' container to filter out
the duplicates).


-Mike