By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,234 Members | 1,938 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,234 IT Pros & Developers. It's quick & easy.

Distinct keys in the multimap

P: n/a
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
Jul 23 '05 #1
Share this Question
Share on Google+
3 Replies


P: n/a
Przemek wrote:

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.
Jul 23 '05 #2

P: n/a
Przemek wrote:
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.
--
<mailto:di***********@yahoo.com> <http://www.dietmar-kuehl.de/>
<http://www.contendix.com> - Software Development & Consulting

Jul 23 '05 #3

P: n/a

"Przemek" <pr**************@gazeta.pl> wrote in message
news:12**************************@posting.google.c om...
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
Jul 23 '05 #4

This discussion thread is closed

Replies have been disabled for this discussion.