Sign in to follow this  
cyphr

Sorting std::map by value

Recommended Posts

cyphr    127
Wow, I haven't posted on these boards in...probably 4 years. I used to be andromeda, if anyone remembers me. Anyways, I have an std::map<string, int> that maps words to the number of times they occur in a block of text. This is fine, but when I output them, I'd kind of like them to be ordered by the number of times they occur, highest to lowest (a.k.a., by the values of the map, not the keys). Is there any easy way to do this? Or do I have to do something like make a std::vector, output all the map elements to that, and then sort it?

Share this post


Link to post
Share on other sites
Mushu    1396
Instead of using a std::vector, you could insert every element of the map into a sorted container (like std::set), then iterate through that.

I can't think of any better way to do it right now - sorting by multiple attributes can get tricky.

Share this post


Link to post
Share on other sites
Thetan    100
std::sort(map.begin(), map.end(), std::greater<int>());

http://www.sgi.com/tech/stl/sort.html
http://www.sgi.com/tech/stl/greater.html

<3 Thetan

Share this post


Link to post
Share on other sites
Sneftel    1788
Quote:
Original post by Thetan
std::sort(map.begin(), map.end(), std::greater<int>());

http://www.sgi.com/tech/stl/sort.html
http://www.sgi.com/tech/stl/greater.html

<3 Thetan

No. a std::map is a sorted container. std::sort and other mutating algorithms won't work on it.

Share this post


Link to post
Share on other sites
Fruny    1658
Quote:
Original post by cyphr
Is there any easy way to do this?


A bidirectional map? (may need tweaking to handle duplicate counts).

Quote:
Or do I have to do something like make a std::vector, output all the map elements to that, and then sort it?


That would be the other easy way, yes.

Share this post


Link to post
Share on other sites
Mushu    1396
Quote:
Original post by Fruny
Quote:
Original post by cyphr
Is there any easy way to do this?


A bidirectional map? (may need tweaking to handle duplicate counts).

O_o

...

Is there anything that Boost doesn't do?

Share this post


Link to post
Share on other sites
_the_phantom_    11250
Quote:
Original post by Mushu
Is there anything that Boost doesn't do?


I tried to get it to make me dinner once... that didn't work [sad]

But, this is just another example of why everyone who programs in C++ should have a copy of boost installed and in use.

Share this post


Link to post
Share on other sites
cyphr    127
Thanks for the replies - bidirectional map is so close, but I can't guarantee uniqueness of the second values. In fact, there will almost definitely be duplicates.

So, I'll probably just copy all the elements to a vector.

Boost is still God, though.

Share this post


Link to post
Share on other sites
jflanglois    1020
Quote:
Original post by cyphr
Thanks for the replies - bidirectional map is so close, but I can't guarantee uniqueness of the second values. In fact, there will almost definitely be duplicates.

So, I'll probably just copy all the elements to a vector.

Boost is still God, though.

They have a couple of examples that do exactly what you are trying to do:


Quote:
Example 5: sequenced indices

See source code.

The combination of a sequenced index with an index of type ordered_non_unique yields a list-like structure with fast lookup capabilities. The example performs some operations on a given text, like word counting and selective deletion of some words.

Quote:
Example 8: hashed indices

See source code.

Hashed indices can be used as an alternative to ordered indices when fast lookup is needed and sorting information is of no interest. The example features a word counter where duplicate entries are checked by means of a hashed index. Confront the word counting algorithm with that of example 5.



As for using a vector, I suppose it is rather easy:

#include <string>
#include <map>
#include <vector>
#include <functional>
#include <algorithm>

typedef std::map< std::string, int > WordMap;
typedef std::pair< std::string, int > Word;


struct OrderByCount : std::binary_function< Word, Word, bool > {
bool operator()( Word const &lhs, Word const &rhs ) {
return lhs.second < rhs.second;
}
};

int main() {
WordMap words;
words["One"] = 3;
words["High"] = 66;
words["Dude"] = 24;
words["Car"] = 31;
words["Foo"] = 143;
words["in"] = 2;
words["Glue"] = 64;

std::vector< Word > ordered_words;

std::copy( words.begin(), words.end(), std::back_inserter( ordered_words ) );
std::sort( ordered_words.begin(), ordered_words.end(), OrderByCount() );
}



jfl.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this