 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
zehzinho
Guest
|
 Posted: Mon Aug 29, 2005 11:21 am Post subject: How to sort a std::map using its values? |
 |
|
Hi people, actually I couldn't sort my map even using its keys.
Can anyone tell me how to do it in both cases? :)
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
ravinderthakur@gmail.com
Guest
|
| Posted: Mon Aug 29, 2005 1:59 pm Post subject: Re: How to sort a std::map using its values? |
|
|
hi,
the mape is already sorted by using its keys. if that is not the case
with your code,
plz check if you have implemented the comparator function properly.
in addition can u plz post the sample code that is creating the
problem.
thanks
rt
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Giulio Guarnone
Guest
|
| Posted: Mon Aug 29, 2005 2:00 pm Post subject: Re: How to sort a std::map using its values? |
|
|
zehzinho ha scritto:
| Quote: | Hi people, actually I couldn't sort my map even using its keys.
Can anyone tell me how to do it in both cases? 
|
Isn't a std::map yet sorted by key ?
If your keys are of type std::string, beware that 'B' comes before 'a'.
Bye,
Giulio
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
zehzinho
Guest
|
| Posted: Mon Aug 29, 2005 4:35 pm Post subject: Re: How to sort a std::map using its values? |
|
|
sorry, i made a mistake. it's already sorted by keys. 
I want to sort it by value, that's it!
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Carlos Moreno
Guest
|
| Posted: Mon Aug 29, 2005 6:14 pm Post subject: Re: How to sort a std::map using its values? |
|
|
zehzinho wrote:
| Quote: | sorry, i made a mistake. it's already sorted by keys.
I want to sort it by value, that's it!
|
I think you're out of luck. Copying the data to another
container such as a vector (vector< pair if you
need to keep track of the associations) may be the only way.
If you need a vector<pair>, then you will need to provide a
comparison function that receives two pairs and compares (for
less-than) the .second members, to end up sorting by values)
Of course, if your values are guaranteed to be distinct (i.e.,
no two different keys map to equivalent/equal values), you
might get away with a second map:
map<string,int> word_count;
// ...
map<int,string> sorted_by_count;
for ( map<...>::const_iterator i = word_count.begin() .... )
{
sorted_by_count [i->second] = i->first;
}
HTH,
Carlos
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Pete Becker
Guest
|
| Posted: Mon Aug 29, 2005 6:14 pm Post subject: Re: How to sort a std::map using its values? |
|
|
zehzinho wrote:
| Quote: | sorry, i made a mistake. it's already sorted by keys.
I want to sort it by value, that's it!
|
Can't be done. A map is sorted by its keys. It sounds like you're using
the wrong data structure for whatever it is that you're trying to do.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Marc Mutz
Guest
|
| Posted: Mon Aug 29, 2005 7:00 pm Post subject: Re: How to sort a std::map using its values? |
|
|
zehzinho wrote:
| Quote: | sorry, i made a mistake. it's already sorted by keys.
I want to sort it by value, that's it!
snip |
You need a second map, like this:
std::map<string,int> originalMap;
// ^ sorted by key, as every map is
std::multimap<int,string> reverseMap;
struct reverse_pair {
template <typename U, typename V>
std::pair<V,U>
operator()( const std::pair<U,V> & in ) const {
return std::pair<V,U>( in.second, in.first );
}
};
std::transform( originalMap.begin(), originalMap.end(),
std::inserter( reverseMap, reverseMap.begin() ),
reverse_pair() );
Marc
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
jrm
Guest
|
|
| Back to top |
|
|
Francis Glassborow
Guest
|
| Posted: Tue Aug 30, 2005 12:28 pm Post subject: Re: How to sort a std::map using its values? |
|
|
In article <1125327580.583958.44050 (AT) f14g2000cwb (DOT) googlegroups.com>,
zehzinho <zehzinho (AT) gmail (DOT) com> writes
| Quote: | sorry, i made a mistake. it's already sorted by keys.
I want to sort it by value, that's it!
|
And you can't because it is a property of associative collections (maps,
multi-maps, sets and multi-sets) that they are held sorted by their
keys.
--
Francis Glassborow ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Joel Eidsath
Guest
|
| Posted: Tue Aug 30, 2005 12:29 pm Post subject: Re: How to sort a std::map using its values? |
|
|
An easier way to get a second map:
//To reverse: map<string,int> m
map<string,int>::iterator pM;
map<int,string> reverseM;
for (pM=m.begin(); pM!=m.end(); pM++){
reverseM[(*pM).second] = (*pM).first;
}
Of course, if the output didn't have to be a map afterwards, but just a
sorted container, I'd do this instead, and save all the map insertions:
bool pair_2less (const pair<string,int> &rhs, const pair<string,int>
&lhs){
return rhs.second < lhs.second;
}
(...)
vector< pair v;
v.assign(m.begin(),m.end());
sort(v.begin(),v.end(), pair_2less);
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
zehzinho
Guest
|
| Posted: Tue Aug 30, 2005 9:55 pm Post subject: Re: How to sort a std::map using its values? |
|
|
joel's second tip worked... that's what i wanted, thank you guy. the
only problem is that another data structure must be allocated.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Marc Mutz
Guest
|
| Posted: Tue Aug 30, 2005 10:05 pm Post subject: Re: How to sort a std::map using its values? |
|
|
Joel Eidsath wrote:
<snip>
| Quote: | An easier way to get a second map:
|
How would rolling your own for-loop be easier than using
std::transform??
| Quote: | //To reverse: map<string,int> m
map<string,int>::iterator pM;
map<int,string> reverseM;
|
Wrong. You need a multimap, b/c there might be more than
one key with the same data attached.
| Quote: | for (pM=m.begin(); pM!=m.end(); pM++){
reverseM[(*pM).second] = (*pM).first;
}
|
This is hardly more readable, nor more efficient than
std::transform.
| Quote: | Of course, if the output didn't have to be a map
afterwards, but just a sorted container, I'd do this
instead, and save all the map insertions:
bool pair_2less (const pair<string,int> &rhs, const
pair<string,int> &lhs){
return rhs.second < lhs.second;
}
(...)
vector< pair v;
v.assign(m.begin(),m.end());
sort(v.begin(),v.end(), pair_2less);
|
Good idea in general. But that wasn't what OP asked for.
And personally, I'd use one of the existing associative
vectors that are floating around directly, for easier
lookup later on. Loki has one IIRC.
Marc
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Joel Eidsath
Guest
|
| Posted: Wed Aug 31, 2005 8:43 am Post subject: Re: How to sort a std::map using its values? |
|
|
Absolutely right about the multimap thing. I have made that mistake
before, and I always kick myself. I need to tattoo that on the backs
of my hands or something.
Let me fix my code before continuing:
//To reverse: map<string,int> m
map<string,int>::iterator pM;
multimap<int,string> reverseM;
for (pM=m.begin(); pM!=m.end(); ++pM){
reverseM.insert( make_pair((*pM).second, (*pM).first));
}
Now, your transform call:
| Quote: | std::map<string,int> originalMap;
// ^ sorted by key, as every map is
std::multimap<int,string> reverseMap;
struct reverse_pair {
template <typename U, typename V
std::pair
operator()( const std::pair
return std::pair<V,U>( in.second, in.first );
}
};
std::transform( originalMap.begin(), originalMap.end(),
std::inserter( reverseMap, reverseMap.begin() ),
reverse_pair() );
|
I do think that my code is more readable here. Especially when you
consider the type of question being asked.
But, in general, for_each and transform are the two standard algorithms
least likely to improve code readability. The best time to use them is
when 1) you have code already written to do the job, or 2) you are
going to be reusing the function object often.
In line with that, I was terribly impressed recently by BOOST_FOREACH,
which will be out in 1.34.
My code for the above would have been just:
multimap<int,string> reverseM;
foreach(pair<string,int> p, m){
reverseM.insert( make_pair(p.second, p.first));
}
Now that is readable. (Assumes "#define foreach BOOST_FOREACH")
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Marc Mutz
Guest
|
| Posted: Wed Aug 31, 2005 9:37 am Post subject: Re: How to sort a std::map using its values? |
|
|
Joel Eidsath wrote:
<snip>
| Quote: | But, in general, for_each and transform are the two
standard algorithms least likely to improve code
readability. The best time to use them is when 1) you
have code already written to do the job, or 2) you are
going to be reusing the function object often.
snip |
Exactly. And we're in case (2) here Of course,
reverse_pair() goes into my/your/his STL toolbox for
reuse. After all, when you need this technique once, it's
bound to crop up again later. if only because it's a
technique you now know.
| Quote: | multimap<int,string> reverseM;
foreach(pair<string,int> p, m){
reverseM.insert( make_pair(p.second, p.first));
}
|
What I hate about foreach (the above, as well as the one
in Qt4) is that it forces you to specify the value_type
of the container. The algorithms usually don't, esp. if
you use modern functors where 'templatation' is on op(),
and not on the class. They're also bound to be more
efficient than a hand-rolled loop. E.g. in your for()
loop you made the usual 'mistake' of re-evaluating
container::end() on each iteration. I've grown the habit
of using
for ( cont::const_iterator it = c.begin(), end =
c.end() ;
Marc
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Marc Mutz
Guest
|
| Posted: Wed Aug 31, 2005 9:38 am Post subject: Re: How to sort a std::map using its values? |
|
|
Joel Eidsath wrote:
<snip>
| Quote: | But, in general, for_each and transform are the two
standard algorithms least likely to improve code
readability. The best time to use them is when 1) you
have code already written to do the job, or 2) you are
going to be reusing the function object often.
snip |
Exactly. And we're in case (2) here Of course,
reverse_pair() goes into my/your/his STL toolbox for
reuse. After all, when you need this technique once, it's
bound to crop up again later. if only because it's a
technique you now know.
| Quote: | multimap<int,string> reverseM;
foreach(pair<string,int> p, m){
reverseM.insert( make_pair(p.second, p.first));
}
|
What I hate about foreach (the above, as well as the one
in Qt4) is that it forces you to specify the value_type
of the container. The algorithms usually don't, esp. if
you use modern functors where 'templatation' is on op(),
and not on the class. They're also bound to be more
efficient than a hand-rolled loop. E.g. in your for()
loop you made the usual 'mistake' of re-evaluating
container::end() on each iteration. STL algorithms don't
make that mistake.
Marc
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
