Skip to main content
GameDev.net gamedev.net
🔒 Locked

Sorting std::map by value

Started by cyphr May 17, 2006 at 8:28 PM 7 replies 1.4k views
Original Post
cyphr
cyphr
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 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?
Mushu
Mushu
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.
Thetan
Thetan
std::sort(map.begin(), map.end(), std::greater());

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

<3 Thetan
___#define ever (;;)for ever delete (void *) rand();
Sneftel
Sneftel
Quote:
Original post by Thetan
std::sort(map.begin(), map.end(), std::greater());

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.
Fruny
Fruny
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.
"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." — Brian W. Kernighan
Mushu
Mushu
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?
_the_phantom_
_the_phantom_
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.

cyphr
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.
jflanglois
jflanglois
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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.