# 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 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 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 on other sites
Sneftel    1788
Quote:
 Original post by Thetanstd::sort(map.begin(), map.end(), std::greater());http://www.sgi.com/tech/stl/sort.htmlhttp://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 on other sites
Fruny    1658
Quote:
 Original post by cyphrIs 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 on other sites
Mushu    1396
Quote:
Original post by Fruny
Quote:
 Original post by cyphrIs 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 on other sites
_the_phantom_    11250
Quote:
 Original post by MushuIs 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 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 on other sites
jflanglois    1020
Quote:
 Original post by cyphrThanks 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 indicesSee 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 indicesSee 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.