Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Distinct keys in the multimap

Reply
Thread Tools

Distinct keys in the multimap

 
 
Przemek
Guest
Posts: n/a
 
      01-31-2005
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
 
Reply With Quote
 
 
 
 
Ron Natalie
Guest
Posts: n/a
 
      01-31-2005
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.
 
Reply With Quote
 
 
 
 
Dietmar Kuehl
Guest
Posts: n/a
 
      01-31-2005
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.
--
<(E-Mail Removed)> <http://www.dietmar-kuehl.de/>
<http://www.contendix.com> - Software Development & Consulting

 
Reply With Quote
 
Mike Wahler
Guest
Posts: n/a
 
      01-31-2005

"Przemek" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) 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


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: Ordering of same value keys in multimap Howard Hinnant C++ 1 08-28-2012 02:59 PM
number of distinct elements in a const container and iterating over the distinct elements Hicham Mouline C++ 1 04-11-2010 10:56 AM
copy from keys from multimap into the vector puzzlecracker C++ 19 10-30-2008 05:27 PM
stl multimap, insert with duplicate keys, is ordering stable? reppisch C++ 6 06-19-2007 09:38 AM
keyboard keys replacing mouse keys? larry Computer Support 8 09-14-2003 07:32 PM



Advertisments